Home » Modeling » OCL » OCL Performance
| OCL Performance [message #4450] |
Sun, 11 February 2007 01:38  |
Eclipse User |
|
|
|
Originally posted by: Zaid.Altahat.gmail.com
Hi, was there any work done on measuring OCL performance?
What I'm interested in is not actually performance numbers but how OCL works
under the hood.
For example if I'm writing an OCL query for a state diagram to check if
there is a transition from any state to a state named X.
The OCL engine would need to check all states in the system and check for a
name match and then check its transitions?
In a discussion I had with one of my professors at the school is that this
would be a subgraph isomorphism problem(
http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem )which is an
NP-Complete.
Does anyone know if this is the case or direct me to any literature on or
near this matter.
Regards,
Zaid.
|
|
| |
| Re: OCL Performance [message #4589 is a reply to message #4520] |
Sun, 11 February 2007 12:35  |
| Eclipse User |
|
|
|
Originally posted by: Zaid.Altahat.gmail.com
This is assuming that each element is given an Name/ID, but I think I gave a
bad example. What I had in mind is more of model comparison, i.e., finding
the correspondence between two graphs. For example, querying a state diagram
(Target) if it has a certain pattern (Source).
There seems to be two ways to represent models, XML and graphs. I assume OCL
engine is using XML.
In Graphs representation, without the use of a Universal Unique Identifier
(UUID) we will have an isomorphic problem.
Does OCL also overcomes this problem by assigning UUID to all elements, OR
this problem doesn't exist at all in XML even w/o UUID?
Regards,
Zaid.
"Ed Merks" <merks@ca.ibm.com> wrote in message
news:eqn7as$ci6$1@utils.eclipse.org...
> Zaid,
>
> What you describe doesn't sound NP-complete. You need to search n states
> for one named X; that's takes O(n). Once you have that state, you can
> look at all it's in coming transitions to know all the other states that
> have a transition to X. Perhaps there's more to the problem than you've
> described...
>
> Zaid wrote:
>> Hi, was there any work done on measuring OCL performance?
>> What I'm interested in is not actually performance numbers but how OCL
>> works under the hood.
>> For example if I'm writing an OCL query for a state diagram to check if
>> there is a transition from any state to a state named X.
>> The OCL engine would need to check all states in the system and check for
>> a name match and then check its transitions?
>> In a discussion I had with one of my professors at the school is that
>> this would be a subgraph isomorphism problem(
>> http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem )which is an
>> NP-Complete.
>> Does anyone know if this is the case or direct me to any literature on or
>> near this matter.
>>
>> Regards,
>> Zaid.
>>
>>
|
|
|
| Re: OCL Performance [message #4658 is a reply to message #4589] |
Sun, 11 February 2007 12:48 |
| Eclipse User |
|
|
|
Originally posted by: merks.ca.ibm.com
This is a multi-part message in MIME format.
--------------030202050009080309040307
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Zaid,
Comparison problems do quickly become NP-complete. We are just in the
process of starting an EMF compare component based on these
contributions. https://bugs.eclipse.org/bugs/show_bug.cgi?id=157166 and
https://bugs.eclipse.org/bugs/show_bug.cgi?id=161382 and there is a
panel discussion about it at EclipeCon
http://www.eclipsecon.org/2007/index.php?page=sub/&id=35 93
< http://www.eclipsecon.org/2007/index.php?page=sub/&id=35 93>. OCL uses
EMF models that are graphs and even XML has IDREF and anyURI to
represent non-containment links. Whether model instances use UUIDs or
not is independent of OCL itself, so some will and some won't. Even
when you have UUIDs, you might still want to do structural comparison...
Zaid wrote:
> This is assuming that each element is given an Name/ID, but I think I gave a
> bad example. What I had in mind is more of model comparison, i.e., finding
> the correspondence between two graphs. For example, querying a state diagram
> (Target) if it has a certain pattern (Source).
> There seems to be two ways to represent models, XML and graphs. I assume OCL
> engine is using XML.
> In Graphs representation, without the use of a Universal Unique Identifier
> (UUID) we will have an isomorphic problem.
> Does OCL also overcomes this problem by assigning UUID to all elements, OR
> this problem doesn't exist at all in XML even w/o UUID?
>
> Regards,
> Zaid.
>
> "Ed Merks" <merks@ca.ibm.com> wrote in message
> news:eqn7as$ci6$1@utils.eclipse.org...
>
>> Zaid,
>>
>> What you describe doesn't sound NP-complete. You need to search n states
>> for one named X; that's takes O(n). Once you have that state, you can
>> look at all it's in coming transitions to know all the other states that
>> have a transition to X. Perhaps there's more to the problem than you've
>> described...
>>
>> Zaid wrote:
>>
>>> Hi, was there any work done on measuring OCL performance?
>>> What I'm interested in is not actually performance numbers but how OCL
>>> works under the hood.
>>> For example if I'm writing an OCL query for a state diagram to check if
>>> there is a transition from any state to a state named X.
>>> The OCL engine would need to check all states in the system and check for
>>> a name match and then check its transitions?
>>> In a discussion I had with one of my professors at the school is that
>>> this would be a subgraph isomorphism problem(
>>> http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem )which is an
>>> NP-Complete.
>>> Does anyone know if this is the case or direct me to any literature on or
>>> near this matter.
>>>
>>> Regards,
>>> Zaid.
>>>
>>>
>>>
>
>
>
--------------030202050009080309040307
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
<title></title>
</head>
<body bgcolor="#ffffff" text="#000000">
Zaid,<br>
<br>
Comparison problems do quickly become NP-complete. We are just in the
process of starting an EMF compare component based on these
contributions. <a
href="https://bugs.eclipse.org/bugs/show_bug.cgi?id=157166">https://bugs.eclipse.org/bugs/show_bug.cgi?id=157166</a>
and <a href="https://bugs.eclipse.org/bugs/show_bug.cgi?id=161382">https://bugs.eclipse.org/bugs/show_bug.cgi?id=161382</a>
and there is a panel discussion about it at EclipeCon <a
href="http://www.eclipsecon.org/2007/index.php?page=sub/&id=3593">http://www.eclipsecon.org/2007/index.php?page=sub/&id=3593</a>.
OCL uses EMF models that are graphs and even XML has IDREF and anyURI
to represent non-containment links. Whether model instances use UUIDs
or not is independent of OCL itself, so some will and some won't. Even
when you have UUIDs, you might still want to do structural comparison...<br>
<br>
<br>
Zaid wrote:
<blockquote cite="mideqnk5o$h7a$1@utils.eclipse.org" type="cite">
<pre wrap="">This is assuming that each element is given an Name/ID, but I think I gave a
bad example. What I had in mind is more of model comparison, i.e., finding
the correspondence between two graphs. For example, querying a state diagram
(Target) if it has a certain pattern (Source).
There seems to be two ways to represent models, XML and graphs. I assume OCL
engine is using XML.
In Graphs representation, without the use of a Universal Unique Identifier
(UUID) we will have an isomorphic problem.
Does OCL also overcomes this problem by assigning UUID to all elements, OR
this problem doesn't exist at all in XML even w/o UUID?
Regards,
Zaid.
"Ed Merks" <a class="moz-txt-link-rfc2396E" href="mailto:merks@ca.ibm.com"><merks@ca.ibm.com></a> wrote in message
<a class="moz-txt-link-freetext" href="news:eqn7as$ci6$1@utils.eclipse.org">news:eqn7as$ci6$1@utils.eclipse.org</a>...
</pre>
<blockquote type="cite">
<pre wrap="">Zaid,
What you describe doesn't sound NP-complete. You need to search n states
for one named X; that's takes O(n). Once you have that state, you can
look at all it's in coming transitions to know all the other states that
have a transition to X. Perhaps there's more to the problem than you've
described...
Zaid wrote:
</pre>
<blockquote type="cite">
<pre wrap="">Hi, was there any work done on measuring OCL performance?
What I'm interested in is not actually performance numbers but how OCL
works under the hood.
For example if I'm writing an OCL query for a state diagram to check if
there is a transition from any state to a state named X.
The OCL engine would need to check all states in the system and check for
a name match and then check its transitions?
In a discussion I had with one of my professors at the school is that
this would be a subgraph isomorphism problem(
<a class="moz-txt-link-freetext" href="http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem">http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem</a> )which is an
NP-Complete.
Does anyone know if this is the case or direct me to any literature on or
near this matter.
Regards,
Zaid.
</pre>
</blockquote>
</blockquote>
<pre wrap=""><!---->
</pre>
</blockquote>
<br>
</body>
</html>
--------------030202050009080309040307--
|
|
|
| Re: OCL Performance [message #4727 is a reply to message #4658] |
Sun, 11 February 2007 13:47 |
| Eclipse User |
|
|
|
Originally posted by: Zaid.Altahat.gmail.com
This is a multi-part message in MIME format.
------=_NextPart_000_0167_01C74DDA.C35E87B0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Ed,
Query View Transformation (QVT) extends OCL and Atlas Transformation =
Language (ATL) uses OCL as their query language. With today's =
implementations of QVT/ATL would I run into the comparison problem if I =
want to run a query like: State A, followed by zero or more (*) set of =
states & transitions, followed by state B. ?
Rephrasing the query in regulars expression-like notation, it has 3 =
parts as follows:
(A) (set of states & transitions)* (B)
Or these kind of queries don't necessarily map to a comparison problem?
Also, when you say OCL is independent of UUID usage, how does it =
guarantee not running into the comparison problem?
Thank Ed,
Zaid.
"Ed Merks" <merks@ca.ibm.com> wrote in message =
news:eqnkst$lmt$1@utils.eclipse.org...
Zaid,
Comparison problems do quickly become NP-complete. We are just in the =
process of starting an EMF compare component based on these =
contributions. https://bugs.eclipse.org/bugs/show_bug.cgi?id=3D157166 =
and https://bugs.eclipse.org/bugs/show_bug.cgi?id=3D161382 and there is =
a panel discussion about it at EclipeCon =
http://www.eclipsecon.org/2007/index.php?page=3Dsub/&id= 3D3593. OCL =
uses EMF models that are graphs and even XML has IDREF and anyURI to =
represent non-containment links. Whether model instances use UUIDs or =
not is independent of OCL itself, so some will and some won't. Even =
when you have UUIDs, you might still want to do structural comparison...
Zaid wrote:=20
This is assuming that each element is given an Name/ID, but I think I =
gave a=20
bad example. What I had in mind is more of model comparison, i.e., =
finding=20
the correspondence between two graphs. For example, querying a state =
diagram=20
(Target) if it has a certain pattern (Source).
There seems to be two ways to represent models, XML and graphs. I assume =
OCL=20
engine is using XML.
In Graphs representation, without the use of a Universal Unique =
Identifier=20
(UUID) we will have an isomorphic problem.
Does OCL also overcomes this problem by assigning UUID to all elements, =
OR=20
this problem doesn't exist at all in XML even w/o UUID?
Regards,
Zaid.
"Ed Merks" <merks@ca.ibm.com> wrote in message=20
news:eqn7as$ci6$1@utils.eclipse.org...
Zaid,
What you describe doesn't sound NP-complete. You need to search n =
states=20
for one named X; that's takes O(n). Once you have that state, you can=20
look at all it's in coming transitions to know all the other states that =
have a transition to X. Perhaps there's more to the problem than you've =
described...
Zaid wrote:
Hi, was there any work done on measuring OCL performance?
What I'm interested in is not actually performance numbers but how OCL=20
works under the hood.
For example if I'm writing an OCL query for a state diagram to check if=20
there is a transition from any state to a state named X.
The OCL engine would need to check all states in the system and check =
for=20
a name match and then check its transitions?
In a discussion I had with one of my professors at the school is that=20
this would be a subgraph isomorphism problem(=20
http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem )which is an=20
NP-Complete.
Does anyone know if this is the case or direct me to any literature on =
or=20
near this matter.
Regards,
Zaid.
=20
=20
------=_NextPart_000_0167_01C74DDA.C35E87B0
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE></TITLE>
<META http-equiv=3DContent-Type =
content=3Dtext/html;charset=3DISO-8859-1>
<META content=3D"MSHTML 6.00.2900.2995" name=3DGENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY text=3D#000000 bgColor=3D#ffffff>
<DIV><FONT face=3DArial size=3D2>Ed,</FONT></DIV>
<DIV><FONT face=3DArial size=3D2>Query View Transformation (QVT) extends =
OCL and Atlas Transformation Language (ATL) uses OCL as their =
query=20
language. With today's implementations of QVT/ATL would I run into the=20
comparison problem if I want to run a query like: State A, followed by =
zero or=20
more (*) set of states & transitions, followed by state B. =
?</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>Rephrasing the query in regulars =
expression-like=20
notation, it has 3 parts as follows:</FONT></DIV>
<DIV><FONT face=3DArial size=3D2>(A) (set of states & transitions)*=20
(B)</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>Or these kind of queries don't =
necessarily map to a=20
comparison problem?</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>Also, when you say OCL is independent =
of UUID=20
usage, how does it guarantee not running into the comparison=20
problem?</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>Thank Ed,</FONT></DIV>
<DIV><FONT face=3DArial size=3D2>Zaid.</FONT></DIV>
<BLOCKQUOTE=20
style=3D"PADDING-RIGHT: 0px; PADDING-LEFT: 5px; MARGIN-LEFT: 5px; =
BORDER-LEFT: #000000 2px solid; MARGIN-RIGHT: 0px">
<DIV>"Ed Merks" <<A =
href=3D"mailto:merks@ca.ibm.com">merks@ca.ibm.com</A>>=20
wrote in message <A=20
=
href=3D"news:eqnkst$lmt$1@utils.eclipse.org">news:eqnkst$lmt$1@utils.ecli=
pse.org</A>...</DIV>Zaid,<BR><BR>Comparison=20
problems do quickly become NP-complete. We are just in the =
process of=20
starting an EMF compare component based on these contributions. =
<A=20
=
href=3D"https://bugs.eclipse.org/bugs/show_bug.cgi?id=3D157166">https://b=
ugs.eclipse.org/bugs/show_bug.cgi?id=3D157166</A>=20
and <A=20
=
href=3D"https://bugs.eclipse.org/bugs/show_bug.cgi?id=3D161382">https://b=
ugs.eclipse.org/bugs/show_bug.cgi?id=3D161382</A>=20
and there is a panel discussion about it at EclipeCon <A=20
=
href=3D" http://www.eclipsecon.org/2007/index.php?page=3Dsub/&id=3D359=
3"> http://www.eclipsecon.org/2007/index.php?page=3Dsub/&id=3D3593</A>=
.. =20
OCL uses EMF models that are graphs and even XML has IDREF and anyURI =
to=20
represent non-containment links. Whether model instances use =
UUIDs or=20
not is independent of OCL itself, so some will and some won't. =
Even when=20
you have UUIDs, you might still want to do structural=20
comparison...<BR><BR><BR>Zaid wrote:=20
<BLOCKQUOTE cite=3Dmideqnk5o$h7a$1@utils.eclipse.org =
type=3D"cite"><PRE wrap=3D"">This is assuming that each element is given =
an Name/ID, but I think I gave a=20
bad example. What I had in mind is more of model comparison, i.e., =
finding=20
the correspondence between two graphs. For example, querying a state =
diagram=20
(Target) if it has a certain pattern (Source).
There seems to be two ways to represent models, XML and graphs. I assume =
OCL=20
engine is using XML.
In Graphs representation, without the use of a Universal Unique =
Identifier=20
(UUID) we will have an isomorphic problem.
Does OCL also overcomes this problem by assigning UUID to all elements, =
OR=20
this problem doesn't exist at all in XML even w/o UUID?
Regards,
Zaid.
"Ed Merks" <A class=3Dmoz-txt-link-rfc2396E =
href=3D"mailto:merks@ca.ibm.com"><merks@ca.ibm.com></A> wrote in =
message=20
<A class=3Dmoz-txt-link-freetext =
href=3D"news:eqn7as$ci6$1@utils.eclipse.org">news:eqn7as$ci6$1@utils.ecli=
pse.org</A>...
</PRE>
<BLOCKQUOTE type=3D"cite"><PRE wrap=3D"">Zaid,
What you describe doesn't sound NP-complete. You need to search n =
states=20
for one named X; that's takes O(n). Once you have that state, you can=20
look at all it's in coming transitions to know all the other states that =
have a transition to X. Perhaps there's more to the problem than you've =
described...
Zaid wrote:
</PRE>
<BLOCKQUOTE type=3D"cite"><PRE wrap=3D"">Hi, was there any work =
done on measuring OCL performance?
What I'm interested in is not actually performance numbers but how OCL=20
works under the hood.
For example if I'm writing an OCL query for a state diagram to check if=20
there is a transition from any state to a state named X.
The OCL engine would need to check all states in the system and check =
for=20
a name match and then check its transitions?
In a discussion I had with one of my professors at the school is that=20
this would be a subgraph isomorphism problem(=20
<A class=3Dmoz-txt-link-freetext =
href=3D"http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem">http:/=
/en.wikipedia.org/wiki/Subgraph_isomorphism_problem</A> )which is an=20
NP-Complete.
Does anyone know if this is the case or direct me to any literature on =
or=20
near this matter.
Regards,
Zaid.
</PRE></BLOCKQUOTE></BLOCKQUOTE><PRE wrap=3D""><!---->
</PRE></BLOCKQUOTE><BR></BLOCKQUOTE></BODY></HTML>
------=_NextPart_000_0167_01C74DDA.C35E87B0--
|
|
|
| Re: OCL Performance [message #4798 is a reply to message #4727] |
Sun, 11 February 2007 16:59 |
| Eclipse User |
|
|
|
Originally posted by: merks.ca.ibm.com
This is a multi-part message in MIME format.
--------------090404070804000808070707
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Zaid,
It doesn't sound to me like what you express below would result in
non-polynomial time performance. It doesn't even seem like UUIDs would
even be involved. UUIDs are typically used to express and resolve cross
resource references, so while the underlying model might be using them
for that purpose, OCL likely won't care nor notice that. You should
just try it and see how it goes...
Zaid wrote:
> Ed,
> Query View Transformation (QVT) extends OCL and Atlas Transformation
> Language (ATL) uses OCL as their query language. With today's
> implementations of QVT/ATL would I run into the comparison problem if
> I want to run a query like: State A, followed by zero or more (*) set
> of states & transitions, followed by state B. ?
>
> Rephrasing the query in regulars expression-like notation, it has 3
> parts as follows:
> (A) (set of states & transitions)* (B)
>
> Or these kind of queries don't necessarily map to a comparison problem?
>
> Also, when you say OCL is independent of UUID usage, how does it
> guarantee not running into the comparison problem?
>
> Thank Ed,
> Zaid.
>
> "Ed Merks" <merks@ca.ibm.com <mailto:merks@ca.ibm.com>> wrote in
> message news:eqnkst$lmt$1@utils.eclipse.org...
> Zaid,
>
> Comparison problems do quickly become NP-complete. We are just in
> the process of starting an EMF compare component based on these
> contributions.
> https://bugs.eclipse.org/bugs/show_bug.cgi?id=157166 and
> https://bugs.eclipse.org/bugs/show_bug.cgi?id=161382 and there is
> a panel discussion about it at EclipeCon
> http://www.eclipsecon.org/2007/index.php?page=sub/&id=35 93
> < http://www.eclipsecon.org/2007/index.php?page=sub/&id=35 93>. OCL
> uses EMF models that are graphs and even XML has IDREF and anyURI
> to represent non-containment links. Whether model instances use
> UUIDs or not is independent of OCL itself, so some will and some
> won't. Even when you have UUIDs, you might still want to do
> structural comparison...
>
>
> Zaid wrote:
>> This is assuming that each element is given an Name/ID, but I think I gave a
>> bad example. What I had in mind is more of model comparison, i.e., finding
>> the correspondence between two graphs. For example, querying a state diagram
>> (Target) if it has a certain pattern (Source).
>> There seems to be two ways to represent models, XML and graphs. I assume OCL
>> engine is using XML.
>> In Graphs representation, without the use of a Universal Unique Identifier
>> (UUID) we will have an isomorphic problem.
>> Does OCL also overcomes this problem by assigning UUID to all elements, OR
>> this problem doesn't exist at all in XML even w/o UUID?
>>
>> Regards,
>> Zaid.
>>
>> "Ed Merks" <merks@ca.ibm.com> wrote in message
>> news:eqn7as$ci6$1@utils.eclipse.org...
>>
>>> Zaid,
>>>
>>> What you describe doesn't sound NP-complete. You need to search n states
>>> for one named X; that's takes O(n). Once you have that state, you can
>>> look at all it's in coming transitions to know all the other states that
>>> have a transition to X. Perhaps there's more to the problem than you've
>>> described...
>>>
>>> Zaid wrote:
>>>
>>>> Hi, was there any work done on measuring OCL performance?
>>>> What I'm interested in is not actually performance numbers but how OCL
>>>> works under the hood.
>>>> For example if I'm writing an OCL query for a state diagram to check if
>>>> there is a transition from any state to a state named X.
>>>> The OCL engine would need to check all states in the system and check for
>>>> a name match and then check its transitions?
>>>> In a discussion I had with one of my professors at the school is that
>>>> this would be a subgraph isomorphism problem(
>>>> http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem )which is an
>>>> NP-Complete.
>>>> Does anyone know if this is the case or direct me to any literature on or
>>>> near this matter.
>>>>
>>>> Regards,
>>>> Zaid.
>>>>
>>>>
>>>>
>>
>>
>>
>
--------------090404070804000808070707
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
Zaid,<br>
<br>
It doesn't sound to me like what you express below would result in
non-polynomial time performance. It doesn't even seem like UUIDs would
even be involved. UUIDs are typically used to express and resolve
cross resource references, so while the underlying model might be using
them for that purpose, OCL likely won't care nor notice that. You
should just try it and see how it goes...<br>
<br>
<br>
Zaid wrote:
<blockquote cite="mideqnoc7$r9i$1@utils.eclipse.org" type="cite">
<title></title>
<meta http-equiv="Content-Type" content="text/html;charset=ISO-8859-1">
<meta content="MSHTML 6.00.2900.2995" name="GENERATOR">
<style></style>
<div><font face="Arial" size="2">Ed,</font></div>
<div><font face="Arial" size="2">Query View Transformation (QVT)
extends OCL and Atlas Transformation Language (ATL) uses OCL as their
query language. With today's implementations of QVT/ATL would I run
into the comparison problem if I want to run a query like: State A,
followed by zero or more (*) set of states & transitions, followed
by state B. ?</font></div>
<div> </div>
<div><font face="Arial" size="2">Rephrasing the query in regulars
expression-like notation, it has 3 parts as follows:</font></div>
<div><font face="Arial" size="2">(A) (set of states &
transitions)* (B)</font></div>
<div> </div>
<div><font face="Arial" size="2">Or these kind of queries don't
necessarily map to a comparison problem?</font></div>
<div> </div>
<div><font face="Arial" size="2">Also, when you say OCL is
independent of UUID usage, how does it guarantee not running into the
comparison problem?</font></div>
<div> </div>
<div><font face="Arial" size="2">Thank Ed,</font></div>
<div><font face="Arial" size="2">Zaid.</font></div>
<blockquote
style="border-left: 2px solid rgb(0, 0, 0); padding-right: 0px; padding-left: 5px; margin-left: 5px; margin-right: 0px;">
<div>"Ed Merks" <<a href="mailto:merks@ca.ibm.com">merks@ca.ibm.com</a>>
wrote in message <a href="news:eqnkst$lmt$1@utils.eclipse.org">news:eqnkst$lmt$1@utils.eclipse.org</a>...</div>
Zaid,<br>
<br>
Comparison problems do quickly become NP-complete. We are just in the
process of starting an EMF compare component based on these
contributions. <a
href="https://bugs.eclipse.org/bugs/show_bug.cgi?id=157166">https://bugs.eclipse.org/bugs/show_bug.cgi?id=157166</a>
and <a href="https://bugs.eclipse.org/bugs/show_bug.cgi?id=161382">https://bugs.eclipse.org/bugs/show_bug.cgi?id=161382</a>
and there is a panel discussion about it at EclipeCon <a
href="http://www.eclipsecon.org/2007/index.php?page=sub/&id=3593">http://www.eclipsecon.org/2007/index.php?page=sub/&id=3593</a>.
OCL uses EMF models that are graphs and even XML has IDREF and anyURI
to represent non-containment links. Whether model instances use UUIDs
or not is independent of OCL itself, so some will and some won't. Even
when you have UUIDs, you might still want to do structural comparison...<br>
<br>
<br>
Zaid wrote:
<blockquote cite="mideqnk5o$h7a$1@utils.eclipse.org" type="cite">
<pre wrap="">This is assuming that each element is given an Name/ID, but I think I gave a
bad example. What I had in mind is more of model comparison, i.e., finding
the correspondence between two graphs. For example, querying a state diagram
(Target) if it has a certain pattern (Source).
There seems to be two ways to represent models, XML and graphs. I assume OCL
engine is using XML.
In Graphs representation, without the use of a Universal Unique Identifier
(UUID) we will have an isomorphic problem.
Does OCL also overcomes this problem by assigning UUID to all elements, OR
this problem doesn't exist at all in XML even w/o UUID?
Regards,
Zaid.
"Ed Merks" <a class="moz-txt-link-rfc2396E"
href="mailto:merks@ca.ibm.com"><merks@ca.ibm.com></a> wrote in message
<a class="moz-txt-link-freetext"
href="news:eqn7as$ci6$1@utils.eclipse.org">news:eqn7as$ci6$1@utils.eclipse.org</a>...
</pre>
<blockquote type="cite">
<pre wrap="">Zaid,
What you describe doesn't sound NP-complete. You need to search n states
for one named X; that's takes O(n). Once you have that state, you can
look at all it's in coming transitions to know all the other states that
have a transition to X. Perhaps there's more to the problem than you've
described...
Zaid wrote:
</pre>
<blockquote type="cite">
<pre wrap="">Hi, was there any work done on measuring OCL performance?
What I'm interested in is not actually performance numbers but how OCL
works under the hood.
For example if I'm writing an OCL query for a state diagram to check if
there is a transition from any state to a state named X.
The OCL engine would need to check all states in the system and check for
a name match and then check its transitions?
In a discussion I had with one of my professors at the school is that
this would be a subgraph isomorphism problem(
<a class="moz-txt-link-freetext"
href="http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem">http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem</a> )which is an
NP-Complete.
Does anyone know if this is the case or direct me to any literature on or
near this matter.
Regards,
Zaid.
</pre>
</blockquote>
</blockquote>
<pre wrap=""><!---->
</pre>
</blockquote>
<br>
</blockquote>
</blockquote>
<br>
</body>
</html>
--------------090404070804000808070707--
|
|
|
| Re: OCL Performance [message #5143 is a reply to message #4798] |
Mon, 12 February 2007 12:20 |
| Eclipse User |
|
|
|
Originally posted by: cdamus.ca.ibm.com
Hi, Zaid,
If I understand your query correctly, you want to determine whether from
state A there is any sequence of transitions that will end up at state B?
You could try something like this in OCL:
uml::State.allInstances()->any(name='A')->
closure(outgoing.target)->exists(name='B')
The "closure" iterator defined by the MDT OCL implementation is particularly
convenient, here: it finds the closure of all vertices reachable from A
via outgoing transitions. So, we just check that one of these is B. Note
that there may be more specific criteria to determine which vertex is state
A and which is B.
The constraint above shouldn't actually perform too badly, as it only has to
iterate all of the states to find the one named 'A' and then follow edges
in the EMF object graph to find the reachable vertices.
HTH,
Christian
Ed Merks wrote:
> Zaid,
>
> It doesn't sound to me like what you express below would result in
> non-polynomial time performance. It doesn't even seem like UUIDs would
> even be involved. UUIDs are typically used to express and resolve cross
> resource references, so while the underlying model might be using them
> for that purpose, OCL likely won't care nor notice that. You should
> just try it and see how it goes...
>
|
|
|
| Re: OCL Performance [message #5279 is a reply to message #5143] |
Tue, 13 February 2007 12:41 |
| Eclipse User |
|
|
|
Originally posted by: Zaid.Altahat.gmail.com
Hi Christian,
assume "(A)" represents a state named A, "||" means OR, and --> represents
a transition. My query would look like this:
(A) { (C)-->(D) || (C) --> (E) }* (B)
In english:
State A, followed by 0 or more of {...}, followd by state B.
where {...} means: State C followd by either state D or state E.
So the query should return all elements between A & B, inclusive, that
satisfy the query above.
Your query below is missing {...} and that's what I'm looking for. I will be
writing many queries of this form.
If the query doesn't start with a * element, like the one above, this will
improve the performance. Because you can eleminate all states that aren't
named 'A', Like you explained below.
But if the query is something like:
{ (C)-->(D) || (C) --> (E) }* (B)
Or Even:
{ (C)-->(D) || (C) --> (E) }*
This would make things more complicated.
I hope my notations are clear enough.
Thanks,
Zaid.
"Christian W. Damus" <cdamus@ca.ibm.com> wrote in message
news:eqq7kv$tca$1@utils.eclipse.org...
>
> Hi, Zaid,
>
> If I understand your query correctly, you want to determine whether from
> state A there is any sequence of transitions that will end up at state B?
>
> You could try something like this in OCL:
>
> uml::State.allInstances()->any(name='A')->
> closure(outgoing.target)->exists(name='B')
>
> The "closure" iterator defined by the MDT OCL implementation is
> particularly
> convenient, here: it finds the closure of all vertices reachable from A
> via outgoing transitions. So, we just check that one of these is B. Note
> that there may be more specific criteria to determine which vertex is
> state
> A and which is B.
>
> The constraint above shouldn't actually perform too badly, as it only has
> to
> iterate all of the states to find the one named 'A' and then follow edges
> in the EMF object graph to find the reachable vertices.
>
> HTH,
>
> Christian
>
>
> Ed Merks wrote:
>
>> Zaid,
>>
>> It doesn't sound to me like what you express below would result in
>> non-polynomial time performance. It doesn't even seem like UUIDs would
>> even be involved. UUIDs are typically used to express and resolve cross
>> resource references, so while the underlying model might be using them
>> for that purpose, OCL likely won't care nor notice that. You should
>> just try it and see how it goes...
>>
>
|
|
|
| Re: OCL Performance [message #6845 is a reply to message #5279] |
Tue, 13 February 2007 18:31 |
| Eclipse User |
|
|
|
Originally posted by: cdamus.ca.ibm.com
Hi, Zaid,
Do you mean that your query would look something like this?
State.allInstances()->product(State.allInstances())->select(pair |
pair.first <> pair.second and
pair.first->closure(outgoing.target)->includes(pair.second))
This selects all pairs (first, second) of states such that first is not
second and second is reachable by transitions from first.
I'm not sure that I understand your query. Are (A), (C), (D), etc. known
states? Or are they variables?
In any case, if the problem you are solving is proven to be NP-complete,
then I don't suppose that there's anything in our OCL engine that will
reduce its complexity. That is, after all, what NP-completeness is about.
It is only simplifying assumptions such as identifying a particular state
as A that would reduce the complexity.
Cheers,
Christian
Zaid wrote:
> Hi Christian,
> assume "(A)" represents a state named A, "||" means OR, and -->
> represents a transition. My query would look like this:
>
> (A) { (C)-->(D) || (C) --> (E) }* (B)
>
> In english:
> State A, followed by 0 or more of {...}, followd by state B.
> where {...} means: State C followd by either state D or state E.
>
> So the query should return all elements between A & B, inclusive, that
> satisfy the query above.
>
> Your query below is missing {...} and that's what I'm looking for. I will
> be writing many queries of this form.
>
> If the query doesn't start with a * element, like the one above, this will
> improve the performance. Because you can eleminate all states that aren't
> named 'A', Like you explained below.
> But if the query is something like:
> { (C)-->(D) || (C) --> (E) }* (B)
> Or Even:
> { (C)-->(D) || (C) --> (E) }*
>
> This would make things more complicated.
>
> I hope my notations are clear enough.
>
> Thanks,
> Zaid.
>
<snip>
|
|
|
| Re: OCL Performance [message #6871 is a reply to message #6845] |
Tue, 13 February 2007 22:06 |
| Eclipse User |
|
|
|
Originally posted by: Zaid.Altahat.gmail.com
Christian,
I appreciate your help and Ed's.
I don't think I should run into NP-complete scenario because after all what
OCL engine is doing is Name/Id comparison, O(N).
My problem should still be polynomial, but coffiecient might be little high.
Regards,
Zaid.
"Christian W. Damus" <cdamus@ca.ibm.com> wrote in message
news:eqthoa$349$1@utils.eclipse.org...
>
> Hi, Zaid,
>
> Do you mean that your query would look something like this?
>
> State.allInstances()->product(State.allInstances())->select(pair |
> pair.first <> pair.second and
> pair.first->closure(outgoing.target)->includes(pair.second))
>
> This selects all pairs (first, second) of states such that first is not
> second and second is reachable by transitions from first.
>
> I'm not sure that I understand your query. Are (A), (C), (D), etc. known
> states? Or are they variables?
>
> In any case, if the problem you are solving is proven to be NP-complete,
> then I don't suppose that there's anything in our OCL engine that will
> reduce its complexity. That is, after all, what NP-completeness is about.
> It is only simplifying assumptions such as identifying a particular state
> as A that would reduce the complexity.
>
> Cheers,
>
> Christian
>
>
> Zaid wrote:
>
>> Hi Christian,
>> assume "(A)" represents a state named A, "||" means OR, and -->
>> represents a transition. My query would look like this:
>>
>> (A) { (C)-->(D) || (C) --> (E) }* (B)
>>
>> In english:
>> State A, followed by 0 or more of {...}, followd by state B.
>> where {...} means: State C followd by either state D or state E.
>>
>> So the query should return all elements between A & B, inclusive, that
>> satisfy the query above.
>>
>> Your query below is missing {...} and that's what I'm looking for. I will
>> be writing many queries of this form.
>>
>> If the query doesn't start with a * element, like the one above, this
>> will
>> improve the performance. Because you can eleminate all states that aren't
>> named 'A', Like you explained below.
>> But if the query is something like:
>> { (C)-->(D) || (C) --> (E) }* (B)
>> Or Even:
>> { (C)-->(D) || (C) --> (E) }*
>>
>> This would make things more complicated.
>>
>> I hope my notations are clear enough.
>>
>> Thanks,
>> Zaid.
>>
>
> <snip>
|
|
|
Goto Forum:
Current Time: Tue Nov 04 02:40:03 EST 2025
Powered by FUDForum. Page generated in 0.55968 seconds |
Home