VIATRA/Query/UserDocumentation/AdvancedPatterns

Advanced query language topics in EMF-IncQuery

Working with EMaps in EMF-IncQuery

The eclipse.org EMF wiki gives a proper FAQ about the various modeling related issues, including the usage of EMap-s in your metamodel. With EMF-IncQuery you can even write your own queries to extract the key-value pairs from your instance model.

EMaps in your metamodel

1. Creating the actual EMap type Create an EClass with the name [Type1]To[Type2]Map where [Type1] represents the key's type and the [Type2] represents the value's type.
   
2. Set the Instance Type Name property of the newly created EClass to java.util.Map$Entry.
   
3. Create an EAttribute or EReference named "key" and set the EDataType or EClass for it.
   
4. Create an EAttribute or EReference called "value" and set the EDataType or EClass for it.

For example for an <EString, EString> EMap you would have an EClass named EStringToEStringMap if you follow the mentioned scheme.

To actually use this newly created type follow these steps:

1. Create an EReference with its EClass set to be the map-entry class you created above.
2. Set the Containment property of your EReference to be true.
3. Set the upper-bound of your EReference to be -1 (unbounded).
   

For example an <EString, EString> map would result an EClass named EStringToEStringMap, if you follow the mentioned scheme.

EMaps in your instance model

The contents of the EMap instances can be modified like in every other instance model. One EStringToEstringMap instance will be used an a map entry (key-value pair).

Querying EMaps from EMF-IncQuery patterns

Here is an example query to extract the key-value pairs from an EMap

pattern emapPattern(K : EString, V : EString) {
   EMapTestElement(M);
   EMapTestElement.map(M, Map);
   EStringToEStringMap.key(Map, K);
   EStringToEStringMap.value(Map, V);
}

Parts of this overview are based on the http://wiki.eclipse.org/index.php/EMF-FAQ#How_do_i_create_a_Map_in_EMF.3F page.

Recursive queries in EMF-IncQuery

As explained on the query language introduction page, EMF-IncQuery supports pattern composition via the find keyword. Does it support recursive composition, i.e. a pattern calling itself, or multiple patterns cyclically referencing each other? Yes, it does, albeit with limits. The situation is complicated, as described below; see #Summary and suggestions for an executive summary.

Motivating positive recursion

First of all, there are cases where recursion is plain nonsense, such as this query:

pattern meaningless(x) = { neg find meaningless(x); } 

For every choice of value of the variable x, it is a match of pattern meaningless if and only if it is not a match of the same pattern. It is easy to see that this is a contradiction - do not expect EMF-IncQuery to be useful for evaluating such queries.

To avoid such contradictions, EMF-IncQuery supports positive recursion only, i.e. patterns referencing themselves or each other cyclically, solely by positive find pattern calls, never by negation (neg find) or aggregation (count find). (In mathematics, this property is called stratification.) Positively recursive queries are always meaningful - unfortunately, they still will not work in all cases, as explained below.

From this point onward, the discussion will be restricted to stratified / positive recursion.

Well-founded recursion

Suppose that we have elements of type Node forming a containment hierarchy of parents and children, and we want to assign them qualified names composed from their simple names and and the name of their parent. Let's see the following recursive pattern:

 pattern qualifiedName(node : Node, name) = { 
   // for a child element, compose from parent's qualified name
   find parent(node, parentNode);
   Node.simpleName(node, simpleName);
   find qualifiedName(parent, partentName); // recursive call
   name == eval (partentName + "." + simpleName);
 } or { 
   // for a root element, just use the simple name
   neg find parent(node, _anyParent);  // has no parents
   Node.simpleName(node, name);
 } 

This is an example of correct usage of recursion in EMF-IncQuery.

Take a minute to observe

This is actually a pretty good observation.

Summary and suggestions

In summary, EMF-IncQuery supports positive (stratified) recursion only. Even for positive recursion, correct (minimal fixpoint) results are only guaranteed if the recursion is well-founded (e.g. moves along a containment hierarchy or acyclic graph); otherwise, the results are OK only if the model is guaranteed to only ever change by monotonously inserting new stuff, never deleting, moving or changing.

Note that in many typical cases, the transitive closure operator is sufficient to expressed the desired query, without having to resort to recursions. Transitive closures are successfully evaluated and incrementally maintained by EMF-IncQuery even in cases where recursion would be ill-founded and fail (e.g. reachability along relationships that may contain cycles). Even in case the recursion is well-founded, the transitive closure operator may or may not lead to better performance. Therefore our primary recommendation is to use transitive closure instead of recursion if possible.