A year's worth of research in retrospect
It's the end of the year according to both the calendar, as well as my research grant. I have spent some of this past year doing research on the connection of OCL and graph queries. I have also tried to explain and illustrate my research topic in previous posts of this very blog, and let the readers keep tabs on what I was up to all this time. Let's do a quick recap.
Dramatis personæ
Before I could start explaining my specific area and the focus of my investigations, I gave a very brief introduction to the paradigm of model-driven engineering in this first blog post, trying to present an overview of what "model-driven" means, and why people are using this approach.
The focus of a model-driven engineering process is on creating and analyzing abstract models, and deriving them from other models. This workflow can benefit from the help of automated tools for editing, storing, and processing models. Automated model processing in particular is very welcome in a wide rande of modeling environments. As discussed by my second blog post, developing such modeling tools is easier with the availability of declarative model queries, where the tool developer (or the modeler) can formulate a question in a query language, and a query evaluator mechanism delivers the answer automatically.
Query languages may differ in syntax and expressive power as well, not to mention tool support. Example query languages include the OCL standard, as well as the graph pattern-based language of the EMF-IncQuery tool. One of the posts compared these two languages against various notable logics, which are the fundamental mathematical constructs underlying model queries.
In realistic application scenarios, it is very common for models to have frequent updates during the design process. As discussed in a blog post, repeatedly processing a (large scale) model after each small change can lead to significant performance issues. It can be more advantageous to apply incremental evaluation techniques, taking into account the evolving nature of the model. In certain use cases (e.g. well-formedness checks) incremental queries have great performance advantage. The blog featured a very cursory outline of the procedure of incremental query evaluation in case of EMF-IncQuery, and gave a glimpse of how I extended the query language and the corresponding evaluation mechanism to support a new construct that was required for my research.
The story so far
The goal of my current research grant is 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. Following an intuitive description of the connection between the two languages, two consecutive blog posts demonstated my proposed method for translating simple OCL language elements and more advanced constructs to graph patterns. A further post reports on OCL2IQ, a partial experimental implementation of this translation that was realized as an Eclipse plug-in.
The final validation of the research is finding out whether there are any benefits that can be reaped in realistic application scenarios. I have published performance measurements to investigate whether my research fulfills its original promise: delivering efficient, incremental query evaluation for a subset of OCL expressions by transforming them to graph patterns of equivalent semantics, and applying EMF-IncQuery on them. While the graph queries automatically generated using the proposed OCL2IQ transformation did not perform quite as well as manually written EMF-IncQuery code, they do come close, and they definitely outperform pure Java as well as stateless or incremental OCL-based approaches.
All in all, I have reached the main goal of my research by providing a way to evaluate (a restricted set of) OCL expressions more efficiently than previously possible.
Related work
Research never stands in a vacuum, but rather forms part of a steady stream of scientific and technical investigations in various forms and topics. Therefore one must always try to find out whether others have previously tackled the same or similar problems. This is the case with my research: the 2008 ENTCS paper (original talk at GT-VMT 2006) by Jessica Winkelmann, Gabriele Taentzer, Karsten Ehrig, and Jochen M. Küster, titled Translation of Restricted OCL Constraints into Graph Constraints for Generating Meta Model Instances by Graph Grammars[Winkelmann et al] describes a similar translation procedure from OCL to graph patterns.
Despite the close similarity in contributions, the existence of this related work does not make my research unnecessary for a number of reasons: the earlier paper handles a smaller subset of OCL, translates it into a slightly different graph query language, and does not investigate query performance. All of these are largely due to the fact that the paper had different goals: instead of improving query performance, the focus was on providing a method that automatically generates large instance models of a modeling language (e.g. for testing), conforming to well-formedness constraints expressed by OCL invariants.
Particularly focusing on differences between the supported subsets of OCL, the cited paper has the following shortcomings compared to my proposed translation method:
- support is focused on Boolean-valued OCL expressions only (though non-Boolean navigations can be used in certain ways);
- set operations such as select(), collect(), union(), etc. are not supported;
- aggregations such as sum() are not supported;
- size() can only be compared against constants;
- the result of two paths of navigation, can only be compared for equality.
During 2014, I plan to submit a paper to a research conference that publishes a formal treatment of my translation method, as well as performance measurements.