Efficient model query evaluation

OData support
Dr. Bergmann Gábor
Department of Measurement and Information Systems

Nowadays model driven development gains wider and wider adoption in software engineering. The powerful advantage of this paradigm is that we can automatically perform several kinds of analysis before implementing the final software product. Thus the quality, reliability, improvability and maintainability of the delivered product can be significantly improved. A frequently occuring challenge in model driven development is that the user requires extra conditions, well-formedness rules or custom model queries against models. Based on these challenges, many industrial and academic tools have arisen till today, including Eclipse OCL and the Emf-IncQuery model query evaluation framework developed at Department of Measurement and Information Systems, which has been applied in various research and public projects.

Model queries can be interpreted as declarative graph patterns specifying the model query. Evaluating these queries can be performance-critical, including computation performance and significant memory consumption. Many different methods are developed and many solutions exist to answer these challenges.

One possible solution to evaluate queries efficiently is the incremental approach. Its main idea is based on the cache of the query result. When a new execution arrives, the query result cache can be immediately returned. However, more problems appear: result caches can consume significant memory and changes of the model must be carefully examined and the query result sets must be updated. This requires, that the incremental solution is able to monitor the model changes and must implement the update process. There is an implementation currently in the Emf-IncQuery system, the popular and widely used Rete algorithm, which is based on the Rete network. This method does not only cache the results, also stores additional partial information about the queries to speed up the update process, when the model changes. However, this means even more memory consumption, which can be significant against bigger models.

Another possible solution is the Treat algorithm I examined during my studies. On top of its incremental nature, its base idea is to store only the final results to consume less memory. In contradiction, the performance of the update process might be worse and more complicated and challenging to solve. The approach needs an internal search algorithm to search for the results of the query, and quickly identify the changes happening to them, after the model is modified. Our choice was the Lookahead algorithm implemented by me earlier. The Lookahead was written and tested over Viatra2's VPM model representation and later over EMF models. The main advantage of the Lookahead algorithm is that the query evaluation can be more efficient in many scenarios against other search algorithms. For example, when the query is bigger, or we need only one result (not the whole result set), and an another case is when part of the result is already known. The last one is essential when updating the result sets as part of the reaction of the model changes.

In my thesis I implemented the Lookahead search algorithm in the Emf-IncQuery framework, and designed and implemented the incremental Treat query evaluation approach. The Treat actively relies on the Lookahead algorithm using it for inital evaluation and maintenance of the stored result sets. Other challenges were the query compsitions, where different queries can refer to each other and updating the result sets requires attention and careful design. The results achieved were implemented into the TrainBenchmark benchmarking system developed also at Department of Measurement and Information Systems. After these steps I measured the performance and memory consumption of the Treat algorithm against the other incremental and search based solutions.


Please sign in to download the files of this thesis.