Graph pattern matching by lookahead search

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 key part of the model driven develpoment process is the mapping of models between different abstraction levels, which can be achieved through various model transofrmation frameworks. Many industrial and academic tools have arisen till today, including the Viatra2 model transformation framework developed at Department of Measurement and Information Systems, which has been applied in various research projects.

Graph transformation is a possible approach for model transformation, allowing for declarative and rule-based definition of mappings. The application of a graph transformation rule consists of searching for a left-hand-side graph pattern and replacing it by the image of a right-hand-side pattern. Searching for left-hand side pattern matchings in the model space is the most performance demanding task. There are several different approaches for the pattern matching process, which exhibit different efficiency in different scenarios. One of the suggested strategies is the look-ahead pattern matcher, which adjusts its searching process adaptively to the local specialties of the model.

I researched the literature (amongst others) of the chosen subject of this thesis. I adapted the concept to the specialities of the pattern definition language of the Viatra2 framework. I designed the basics and implementation details of the pattern compositions, negative application conditions and attribute checks, paying special attention to the efficient framework cooperation. The look-ahead pattern matcher was implemented as a plug-in module to the Viatra2 framework, which is now fully compatible with the other components of the system. To evaluate the efficiency and benefits of the delivered solution, various comparative performance measurements were made against other pattern matching strategies.


Please sign in to download the files of this thesis.