|
Vol: 55(69) No: 3 / September 2010 Overlapped Execution of Rewriting Rules in Graph Transformation Systems Tamás Mészáros Department of Automation and Applied Informatics, Budapest University of Technology and Economics, Budapest, Faculty of Electrical Engineering and Informatics, Goldmann György tér 3, 1111, Budapest, Hungary, phone: +36 1 463-2472, e-mail: mesztam@aut.bme.hu Márk Asztalos Department of Automation and Applied Informatics, Budapest University of Technology and Economics, Budapest, Faculty of Electrical Engineering and Informatics, Goldmann György tér 3, 1111, Budapest, Hungary, e-mail: asztalos@aut.bme.hu Gergely Mezei Department of Automation and Applied Informatics, Budapest University of Technology and Economics, Budapest, Faculty of Electrical Engineering and Informatics, Goldmann György tér 3, 1111, Budapest, Hungary, e-mail: gmezei@aut.bme.hu Keywords: model transformation, graph rewriting, model-driven engineering, overlapped matching Abstract Graph rewriting-based model transformation is a well-known technique with strong mathematical background to process arbitrary object structures represented as graphs. Since domain-specific visual models are usually represented as graphs, graph transformation is often used to process them. Unfortunately, the algorithmic complexity of graph transformations is NP-complete in general, thus, it is important to apply heuristics to reduce the execution time. Recent transformation tools place focus on the optimization of the execution of the individual rewriting rules of the transformation, and do not harness the structural similarity of consecutively executed rules. In this paper, we present a novel approach called overlapped matching that interleaves the matching phase of the consecutively executed rewriting rules by their common parts. The algorithm performs the matching phase for the common isomorphic subgraphs of the rules at once, and tries to extend the common matches with the remaining parts for each overlapped rule. The overlapping technique can be applied in a hierarchical way as well: overlapped rules can be overlapped again. We introduce specialized versions of the core algorithm for three kinds of rule execution : first-fit, iterative and exhaustive. We present satisfactory application conditions for the algorithms with formal analysis of their correctness. We illustrate the feasibility of the approach with a case study and measurement results. References [1] H. Ehrig, K. Ehrig, U. Prange, and G. Taentzer, Fundamentals of Algebraic Graph Transformation (Monographs in Theoretical Computer Science). An EATCS Series, Secaucus, NJ, USA: Springer-Verlag New York, Inc., 2006. [2] D. Varró, Automated Model Transformations for the Analysis of IT Systems. PhD thesis, Budapest University of Technology and Economics, Department of Measurement and Information Systems, May 2004. [3] R. Geiß_, G. V. Batz, D. Grund, S. Hack, and A. Szalkowski, “GrGen: A fast spo-based graph rewriting tool," in ICGT, pp. 383-397, 2006. [4] T. Klein, U. A. Nickel, J. Niere, and A. Zündorf, “From uml to java and back again," Tech. Rep. tr-ri-00-216, University of Paderborn, Paderborn, Germany, September 1999. [5] A. Zündorf, “Graph pattern matching in progres," in Selected papers from the 5th International Workshop on Graph Grammars and Their Application to Computer Science, (London, UK), pp. 454-468, Springer-Verlag, 1996. [6] OMG, Object Constraint Language, version 2.0, 2006. http://www.omg.org/technology/documents/formal/ocl.htm. [7] “Visual Modeling and Transformation System, version 3.0." http://vmts.aut.bme.hu. [8] G. Varró and D. Varró, “Graph transformation with incremental updates," in Proc. GT-VMT 2004, International Workshop on Graph Transformation and Visual Modelling Techniques, vol. 109 of ENTCS, pp. 71-83, Elsevier, 2004. [9] G. Varró, D. Varró, and A. Schürr, “Incremental graph pattern matching: Data structures and initial experiments," in Graph and Model Transformation (GraMoT 2006) (G. Karsai and G. Taentzer, eds.), vol. 4 of Electronic Communications of the EASST, EASST, 2006. [10] G. Varró, D. Varró, and K. Friedl, “Adaptive graph pattern matching for model transformations using model-sensitive search plans," in GraMoT 2005, International Workshop on Graph and Model Transformations (G. Karsai and G. Taentzer, eds.), vol. 152 of ENTCS, pp. 191-205, Elsevier, 2006. [11] J. Edmonds, “Optimum branchings," Journal of Research of the National Bureau of Standards, vol. 71B, pp. 233-240, 1967. [12] G. V. Batz, M. Kroll, and R. Geiß_, “A _first experimental evaluation of search plan driven graph pattern matching," in AGTIVE, pp. 471-486, 2007. [13] T. Fischer, J. Niere, L. Torunski, and A. Zündorf, “Story diagrams: A new graph rewrite language based on the unified modeling language and java," in TAGT'98: Selected papers from the 6th International Workshop on Theory and Application of Graph Transformations, (London, UK), pp. 296-309, Springer-Verlag, 2000. [14] T. Mészáros, M. Asztalos, and G. Mezei, “An Overlapped Execution Technique for Graph Rewriting Rules,” in Proc. ICCC-CONTI 2010, Timisoara, Romania, 2010. |