Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Software and Systems Modeling
Published in: Software and Systems Modeling 2/2015

01-05-2015 | Special Section Paper

An algorithm for generating model-sensitive search plans for pattern matching on EMF models

Authors: Gergely Varró, Frederik Deckwerth, Martin Wieber, Andy Schürr

Published in: Software and Systems Modeling | Issue 2/2015

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper, we propose a new model-sensitive search plan generation algorithm to speed up the process of graph pattern matching. This dynamic-programming-based algorithm, which is able to handle general n-ary constraints in an integrated manner, collects statistical data from the underlying EMF model and uses this information for optimization purposes. Additionally, the search plan generation algorithm itself and its runtime effects on the pattern matching engine have been evaluated by complexity analysis techniques and by quantitative performance measurements, respectively.
previous article Constraint-driven modeling through transformation
next article Specification-driven model transformation testing

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
By using caching mechanisms, the search plan generation algorithm can be executed in a just-in-time manner.
 
2
Note that past and present check operations need not be stored as they will be immediately processed by the algorithm.
 
3
The runtime value is an average of 20 wall clock time measurements performed on a computer with 1.57 GHz Intel Core2 Duo CPU and 2.96 GB RAM. Windows XP Professional SP 3 and Java 1.7 served as the underlying operating system and virtual machine, respectively.
 
4
This means that the execution of the optimal search plan does not necessarily result in the traversal of the smallest state space.
 
Literature
1.
Anjorin, A., Varró, G., Schürr, A.: Complex attribute manipulation in TGGs with constraint-based programming techniques. In: Hermann, F., Voigtländer, J. (eds.) Proceedings of the 1st International Workshop on Bidirectional Transformations. Electronic Communications of the EASST, vol. 49, (March 2012)
2.
Balogh, A., Varró, D.: Advanced model transformation language constructs in the VIATRA2 framework. In: Proceedings of the 21st ACM Symposium on Applied Computing. pp. 1280–1287. ACM Press, Dijon (April 2006)
3.
Batz, G.V., Kroll, M., Geiß, R.: A first experimental evaluation of search plan driven graph pattern matching. In: Schürr, A., Nagl, M., Zündorf, A. (eds.) Proceedings of the 3rd International Symposium on the Applications of Graph Transformation with Industrial Relevance. LNCS, vol. 5088, pp. 471–486. Springer (2008)
4.
Buchmann, T., Westfechtel, B., Winetzhammer, S.: The added value of programmed graph transformations—a case study from software configuration management. In: Schürr, A., Varró, D., Varró, G. (eds.) Proceedings of the 4th International Symposium on Applications and Graph Transformations with Industrial Relevance. LNCS, vol. 7233, pp. 198–209. Springer, Budapest (Oct 2012)
5.
Byröd, M., Lennartson, B., Vahidi, A., Åkesson, K.: Efficient reachability analysis on modular discrete-event systems using binary decision diagrams. In: Proceedings of the 8th International Workshop on Discrete Event Systems. pp. 288–293. IEEE (2006)
6.
Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: An improved algorithm for matching large graphs. In: Proceedings of the 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition. pp. 149–159 (May 2001)
7.
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)MATH
8.
9.
Fischer, T., Niere, J., Torunski, L., Zündorf, A.: Story diagrams: a new graph rewrite language based on the unified modeling language. In: Engels, G., Rozenberg, G. (eds.) Proceedings of the 6th International Workshop on Theory and Application of Graph Transformation. LNCS, vol. 1764, pp. 296–309. Springer (1998)
10.
Foggia, P., Sansone, C., Vento, M.: A performance comparison of five algorithms for graph isomorphism. In: Proceedings of the 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition. pp. 188–199 (May 2001)
11.
12.
Geiß, R., Batz, 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.) Proceedings of the 3rd International Conference on Graph Transformation. LNCS, vol. 4178, pp. 383–397. Springer (2006)
13.
Giese, H., Hildebrandt, S., Seibel, A.: Improved flexibility and scalability by interpreting story diagrams. In: Margaria, T., Padberg, J., Taentzer, G. (eds.) Proceedings of the 8th International Workshop on Graph Transformation and Visual Modeling Techniques. ECEASST, vol. 18 (2009)
14.
Horváth, Á., Varró, G., Varró, D.: Generic search plans for matching advanced graph patterns. In: Ehrig, K., Giese, H. (eds.) Proceedings of the 6th International Workshop on Graph Transformation and Visual Modeling Techniques. Electronic Communications of the EASST, vol. 6. Braga, Portugal (March 2007)
15.
Jouault, F., Kurtev, I.: Transforming models with ATL. In: Bézivin, J., Rumpe, B., Schürr, A., Tratt, L. (eds.) Proceedings of the International Workshop on Model Transformation in Practice. LNCS, vol. 3844, pp. 128–138. Springer (2005)
16.
Lambers, L., Hildebrandt, S., Giese, H., Orejas, F.: Attribute handling for bidirectional model transformations: the triple graph grammar case. In: Hermann, F., Voigtländer, J. (eds.) Proceedings of the 1st International Workshop on Bidirectional Transformations. Electronic Communications of the EASST, vol. 49. Tallinn, Estonia (March 2012)
17.
Lauder, M.: Incremental Model Synchronization with Precedence-Driven Triple Graph Grammars. Ph.D. thesis, Technische Universität Darmstadt (Feb 2013)
18.
Le, W., Kementsietsidis, A., Duan, S., Li, F.: Scalable multi-query optimization for SPARQL. In: Gehrke, J., Ooi, B.C., Pitoura, E. (eds.) Proceedings of the 2012 IEEE 28th International Conference on Data Engineering. pp. 666–677. IEEE Computer Society, Arlington, Virginia (2012)
19.
Lee, C., Shih, C.S., Chen, Y.H.: Optimizing large join queries using a graph-based approach. IEEE Trans. Knowl. Data Eng. 13(2), 298–315 (2001)
20.
Meinel, C., Theobald, T.: Algorithms and Data Structures in VLSI Design: OBDD Foundations and Applications. Springer, Berlin (1998)CrossRef
21.
Moerkotte, G., Neumann, T.: Analysis of two existing and one new dynamic programming algorithm for the generation of optimal bushy join trees without cross products. In: Proceedings of the 32nd International Conference on Very Large Data Bases. pp. 930–941. VLDB Endowment, Seoul, Korea (2006)
22.
Neumann, T., Weikum, G.: Scalable join processing on very large RDF graphs. In: Binnig, C., Dageville, B. (eds.) Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. pp. 627–640. ACM, Providence, Rhode Island (2009)
23.
Özsu, M.T., Blakeley, J.A.: Query processing in object-oriented database systems. ACM Trans. Inf. Syst. 8, 387–430 (1994)
24.
Rensink, A.: The GROOVE simulator: a tool for state space generation. In: Pfalz, J.L., Nagl, M., Böhlen, B. (eds.) Proceedings of the 2nd International Symposium on the Applications of Graph Transformations with Industrial Relevance. LNCS, vol. 3062, pp. 479–485. Springer (2004)
25.
Roebuck, K.: Object-Relational Mapping: High-Impact Strategies—What You Need to Know: Definitions, Adoptions, Impact, Benefits, Maturity. Vendors, Lightning Source Incorporated (2011)
26.
Rozenberg, G. (ed.): Handbook of Graph Grammars and Computing by Graph Transformation, vol. 1: Foundations. World Scientific, Singapore (1997)
27.
Selinger, P.G., Astrahan, M.M., Chamberlin, D.D., Lorie, R.A., Price, T.G.: Access path selection in a relational database management system. In: Bernstein, P.A. (ed.) Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data. pp. 23–34. ACM, Boston, Massachusetts (1979)
28.
Stocker, M., Seaborne, A., Bernstein, A., Kiefer, C., Reynolds, D.: SPARQL basic graph pattern optimization using selectivity estimation. In: Ma, W.Y., Tomkins, A., Zhang, X. (eds.) Proceedings of the 17th International Conference on World Wide Web. pp. 595–604. ACM, Beijing, China (April 2008)
29.
30.
31.
Varró, G., Anjorin, A., Schürr, A.: Unification of compiled and interpreter-based pattern matching techniques. In: Tolvanen, J.P., Vallecillo, A. (eds.) Proceedings of the 8th European Conference on Modelling Foundations and Applications. Lecture Notes in Computer Science, vol. 7349, pp. 368–383. Springer, Lyngby (July 2012)
32.
Varró, G., Deckwerth, F., Wieber, M., Schürr, A.: An algorithm for generating model-sensitive search plans for EMF models. In: Hu, Z., de Lara, J. (eds.) Proceedings of the 5th International Conference on Model Transformation. Lecture Notes in Computer Science, vol. 7307, pp. 224–239. Springer, Prague (May 2012)
33.
Varró, G., Varró, D., Friedl, K.: Adaptive graph pattern matching for model transformations using model-sensitive search plans. In: Karsai, G., Taentzer, G. (eds.) Proceedings of International Workshop on Graph and Model Transformation. Electronic Notes in Theoretical Computer Science, vol. 152, pp. 191–205. Elsevier, Tallinn (Sep 2005)
34.
Varró, G.: Advanced Techniques for the Implementation of Model Transformation Systems. Ph.D. thesis, Budapest University of Technology and Economics (April 2008)
35.
Wickes, W.E.: Logic Design with Integrated Circuits. Wiley, London (1968)MATH
36.
Zündorf, A.: Graph pattern matching in PROGRES. In: Cuny, J., Ehrig, H., Engels, G., Rozenberg, G. (eds.) Proceedings 5th Int. Workshop on Graph Grammars and Their Application to Computer Science. LNCS, vol. 1073, pp. 454–468. Springer (1996)
Metadata
Title
An algorithm for generating model-sensitive search plans for pattern matching on EMF models
Authors
Gergely Varró
Frederik Deckwerth
Martin Wieber
Andy Schürr
Publication date
01-05-2015
Publisher
Springer Berlin Heidelberg
Published in
Software and Systems Modeling / Issue 2/2015
Print ISSN: 1619-1366
Electronic ISSN: 1619-1374
DOI
https://doi.org/10.1007/s10270-013-0372-2

Other articles of this Issue 2/2015

Software and Systems Modeling 2/2015 Go to the issue

Regular Paper

Corpus-based analysis of domain-specific languages

Editorial

Special section of SoSyM dedicated to 50 years of Petri nets

Editorial

In memory of Robert B. France, Co-Founder and Editor-in-Chief of SoSyM from 1999 to 2015

Special Section Paper

Petri nets in systems biology

Regular Paper

Extending the UML use case metamodel with behavioral information to facilitate model analysis and interchange

Special Section Paper

Petri and how he saw the world

Premium Partner

    Image Credits