The relation between OCL and graph patterns (pun intended)

My previous introductory blog posts talked about the importance of modeling, the concept of model queries (with OCL and EMF-IncQuery) and model evolution. Now it is time to give a glimpse into my research: translating OCL expressions to graph patterns, so that incremental evaluation techniques (see EMF-IncQuery) developed for graph patterns can be applied to queries formulated in OCL.

Example model

Similarly to the previous posts starting from this one, I will use the school example as a toy domain to formulate my examples in. My very simple example model will consist of one school with two school years, three school classes and five students like this:

• school: Gunnerkrigg Court
  • year: 7
    • class: Q
      • student (name="Antimony")
      • student (name="Katerina")
      • student (name="Jack")
    • class: C
      • student (name="Zimmy")
  • year: 10
    • class: T
      • student (name="Parsley")

Let's ignore courses and teachers for now.

Anatomy of an OCL expression

Let's see an OCL expression that is to be evaluated on this model:

cl.students->select(s2 | s1 <> s2)

This is an almost verbatim part of the example OCL query from before, and means that from all students of "cl", we select all except "s1".

In order to be able to evaluate this expression, we need the value of OCL variable "cl". A closer inspection reveals that we need the value of "s1" as well. However, no value has to be assigned to the variable name "s2"; it is not a free variable, but rather introduced within the expression. Therefore the input variables of this expression will be "cl" and "s1". From the context of the expression, it is known that "cl" will be of type SchoolClass, while "s1" will be a Student.

When we evaluate the expression, the result is a set of things (students in this case), one for each value of "s2" that fits the selection criteria. The fact that the result will be a set of Students is discernible from the type of input variables (dependant on the context, as indicated above) and the OCL operations performed on these variables.

Altogether, we can say that this OCL expression is a function that maps input variables "cl" and "s1" to a set of Students. Let's now see the evaluation result for each possible combination of input values from the above instance model:

cl : SchoolClass

s1 : Student

Relationify!

Graph patterns are fundamentally different from OCL expressions. While variables in graph patterns can refer to model elements or attribute values, they are incapable of representing sets, sequences or other structures. On the other hand, graph patterns can have several matches, while an OCL expression has a single result only (though it can be e.g. a set of elements). A graph pattern therefore defines a mathematical relation (see e.g. relational algebra) between its variables.

The key to translating OCL expressions to graph patterns is interpreting the expression as a mathematical relation between its input variables. Let's see what combination of input values and result students there are in the results of the expression! This involves "flattening" each element "s2" of the result set to its separate line:

cl : SchoolClass

s1 : Student

Note however, that it is not possible to preserve the ordering of an OCL sequence in such an interpretation; graph patterns and mathematical relations are fundamentally unordered. Therefore there are some properties that are expressible in OCL but not using graph patterns.

Heureka!

Now all that's left is constructing a graph pattern whose match set will be the relation above.

Obviously, the parameter variables of the graph pattern will be cl: SchoolClass, s1: Student, s2: Student. The pattern needs pattern constraints as well, otherwise all combinations of students and classes would appera in the match set / relation. The pattern constraints are chosen such that they reflect the relationships encoded in the OCL expression, namely that "s2" can be chosen from the students of "cl", and that the two students have to be different.

pattern translated(cl: SchoolClass, s1: Student, s2: Student) = {
  SchoolClass.students(cl, s2);
  s1 != s2;
}

And that's where I call it a day. Next time, we will see how one should construct such a graph pattern.

Acknowledgement: this research was realized in the frames of TÁMOP 4.2.4. A/1-11-1-2012-0001 „National Excellence Program – Elaborating and operating an inland student and researcher personal support system”. The project was subsidized by the European Union and co-financed by the European Social Fund.