Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Efficient Model Transformations by Combining Pattern Matching Strategies

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNPSE,volume 5563))

  • 689Accesses

Abstract

Recent advances in graph pattern matching techniques have demonstrated at various tool contests that graph transformation tools can scale up to handle very large models in model transformation problems. In case oflocal-search based techniques, pattern matching is driven by a search plan, which provides an optimal ordering for traversing and matching nodes and edges of a graph pattern. In case ofincremental pattern matching, matches of a pattern are explicitly stored and incrementally maintained upon model manipulation, which frequently provides significant speed-up but with increased memory consumption. In the current paper, we present ahybrid pattern matching approach, which is able to combine local-search and incremental techniques on a per-pattern basis. Based upon experimental evaluation, we identify scenarios when such combination is highly beneficial, and provide guidelines for transformation designers for optimal selection of pattern matching strategy.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Ehrig, H., Engels, G., Kreowski, H.J., Rozenberg, G. (eds.): Handbook on Graph Grammars and Computing by Graph Transformation. Applications, Languages and Tools, vol. 2. World Scientific, Singapore (1999)

    MATH  Google Scholar 

  2. The AGTIVE Tool Contest: official website (2007),http://www.informatik.uni-marburg.de/~swt/agtive-contest

  3. GraBaTs - Graph-Based Tools: The Contest: official website (2008),http://www.fots.ua.ac.be/events/grabats2008/

  4. Geiss, R., Batz, G.V., Grund, D., Hack, S., Szalkowski, A.M.: GrGen: A Fast SPO-Based Graph Rewriting Tool. In: Corradini, A., Ehrig, H., Montanari, U., Ribeiro, L., Rozenberg, G. (eds.) ICGT 2006. LNCS, vol. 4178, pp. 383–397. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  5. Nickel, U., Niere, J., Zündorf, A.: Tool demonstration: The FUJABA environment. In: The 22nd International Conference on Software Engineering (ICSE), Limerick, Ireland. ACM Press, New York (2000)

    Google Scholar 

  6. Varró, G., Horváth, Á., Varró, D.: Recursive Graph Pattern Matching With Magic Sets and Global Search Plans. In: Schürr, A., Nagl, M., Zündorf, A. (eds.) AGTIVE 2007. LNCS, vol. 5088. Springer, Heidelberg (2008)

    Google Scholar 

  7. Varró, G., Varró, D., Schürr, A.: Incremental Graph Pattern Matching: Data Structures and Initial Experiments. In: Karsai, G., Taentzer, G. (eds.) Graph and Model Transformation (GraMoT 2006). Electronic Communications of the EASST, vol. 4. EASST (2006)

    Google Scholar 

  8. Bergmann, G., Ökrös, A., Ráth, I., Varró, D., Varró, G.: Incremental pattern matching in the VIATRA transformation system. In: GRaMoT 2008, 3rd International Workshop on Graph and Model Transformation, 30th International Conference on Software Engineering (2008)

    Google Scholar 

  9. Matzner, A., Minas, M., Schulte, A.: Efficient Graph Matching with Application to Cognitive Automation. In: Schürr, A., Nagl, M., Zündorf, A. (eds.) AGTIVE 2007. LNCS, vol. 5088. Springer, Heidelberg (2007)

    Google Scholar 

  10. Hearnden, D., Lawley, M., Raymond, K.: Incremental Model Transformation for the Evolution of Model-Driven Systems. In: Nierstrasz, O., Whittle, J., Harel, D., Reggio, G. (eds.) MoDELS 2006. LNCS, vol. 4199, pp. 321–335. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  11. Mészáros, T., Madari, I., Mezei, G.: VMTS AntWorld submission. In: GraBaTs - 4th International Workshop on Graph-Based Tools: The Contest (September 2008)

    Google Scholar 

  12. Bergmann, G., Horvath, A., Ráth, I., Varr, D.: A Benchmark Evaluation of Incremental Pattern Matching in Graph Transformation. In: Ehrig, H., Heckel, R., Rozenberg, G., Taentzer, G. (eds.) ICGT 2008. LNCS, vol. 5214. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  13. Varró, D., Balogh, A.: The Model Transformation Language of the VIATRA2 Framework. Science of Computer Programming 68(3), 214–234 (2007)

    Article MathSciNet MATH  Google Scholar 

  14. Börger, E., Stärk, R.: Abstract State Machines. A method for High-Level System Design and Analysis. Springer, Heidelberg (2003)

    Book MATH  Google Scholar 

  15. Varró, G., Schürr, A., Varró, D.: Benchmarking for Graph Transformation. Technical Report TUB-TR-05-EE17, Budapest University of Technology and Economics (March 2005),http://www.cs.bme.hu/~gervarro/publication/TUB-TR-05-EE17.pdf

  16. Schürr, A., Winter, A.J., Zündorf, A.: The PROGRES Approach: Language and Environment. In: [1], pp. 487–550. World Scientific, Singapore (1999)

    Google Scholar 

  17. ATLAS Group: The ATLAS Transformation Language,http://www.eclipse.org/gmt

  18. Zündorf, A.: Graph Pattern Matching in PROGRES. In: Selected papers from the 5th International Workshop on Graph Gramars and Their Application to Computer Science, London, UK, pp. 454–468. Springer, Heidelberg (1996)

    Chapter  Google Scholar 

  19. Varró, G., Varró, D., Friedl, K.: Adaptive Graph Pattern Matching for Model Transformations using Model-sensitive Search Plans. In: Karsai, G., Taentzer, G. (eds.) Proc. of Int. Workshop on Graph and Model Transformation (GraMoT 2005), Tallinn, Estonia. ENTCS, vol. 152, pp. 191–205. Elsevier, Amsterdam (2005)

    Google Scholar 

  20. Rudolf, M.: Utilizing constraint satisfaction techniques for efficient graph pattern matching. In: Ehrig, H., Engels, G., Kreowski, H.-J., Rozenberg, G. (eds.) TAGT 1998. LNCS, vol. 1764, pp. 238–252. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  21. El-Boussaidi, G., Mili, H.: Detecting patterns of poor design solutions using constraint propagation. In: Czarnecki, K., Ober, I., Bruel, J.-M., Uhl, A., Völter, M. (eds.) MODELS 2008. LNCS, vol. 5301, pp. 189–203. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  22. Wright, I., Marshall, J.: The execution kernel of RC++: RETE*, a faster RETE with TREAT as a special case. International Journal of Intelligent Games and Simulation 2(1), 36–48 (2003)

    Google Scholar 

  23. Kovács, M., Lollini, P., Majzik, I., Bondavalli, A.: An Integrated Framework for the Dependability Evaluation of Distributed Mobile Applications. In: Proc. Int. Workshop on Software Engineering for Resilient Systems (SERENE 2008), Newcastle upon Tyne, UK, November 17-19, pp. 29–38 (2008)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Measurement and Information Systems, Budapest University of Technology and Economics, H-1117, Magyar tudósok krt. 2, Budapest, Hungary

    Gábor Bergmann, Ákos Horváth, István Ráth & Dániel Varró

Authors
  1. Gábor Bergmann

    You can also search for this author inPubMed Google Scholar

  2. Ákos Horváth

    You can also search for this author inPubMed Google Scholar

  3. István Ráth

    You can also search for this author inPubMed Google Scholar

  4. Dániel Varró

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, Heslington, University of York, YO10 5DD, York, United Kingdom

    Richard F. Paige

Rights and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bergmann, G., Horváth, Á., Ráth, I., Varró, D. (2009). Efficient Model Transformations by Combining Pattern Matching Strategies. In: Paige, R.F. (eds) Theory and Practice of Model Transformations. ICMT 2009. Lecture Notes in Computer Science, vol 5563. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02408-5_3

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp