Search Trees for Distributed Graph Transformation Systems

Abstract

Graph transformation systems, like PROGRES and Fujaba, can be used for modeling software systems of various domains, and support the automatic generation of executable code. A graph transformation rule is executed only if the pattern of the transformation's left-hand side is found in the graph. The search for the pattern has an exponential worst-case complexity. In many cases, the average complexity can be reduced using search tree algorithms in the code generation phase. When modeling distributed graph transformations, the communication overhead between the coupled applications largely affects the pattern matching performance. Therefore, we present an approach for adapting existing search tree algorithms for the efficient search of distributed graph patterns. Our algorithm divides the distributed graph pattern into several sub-patterns such that every sub-pattern affects solely the graph of exactly one coupled application. The results of these sub-patterns are used to determine the match for the entire graph pattern.