nach oben

Erschienen in:

01.02.2015 | Special Section Paper

Model synchronization based on triple graph grammars: correctness, completeness and invertibility

verfasst von: Frank Hermann, Hartmut Ehrig, Fernando Orejas, Krzysztof Czarnecki, Zinovy Diskin, Yingfei Xiong, Susann Gottmann, Thomas Engel

Erschienen in: Software and Systems Modeling | Ausgabe 1/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Triple graph grammars (TGGs) have been used successfully to analyze correctness and completeness of bidirectional model transformations, but a corresponding formal approach to model synchronization has been missing. This paper closes this gap by providing a formal synchronization framework with bidirectional update propagation operations. They are generated from a given TGG, which specifies the language of all consistently integrated source and target models. As our main result, we show that the generated synchronization framework is correct and complete, provided that forward and backward propagation operations are deterministic. Correctness essentially means that the propagation operations preserve and establish consistency while completeness ensures that the operations are defined for all possible inputs. Moreover, we analyze the conditions under which the operations are inverse to each other. All constructions and results are motivated and explained by a running example, which leads to a case study, using concrete visual syntax and abstract syntax notation based on typed attributed graphs.

Vorheriger Artikel A repository for scalable model management

Nächster Artikel Automatically reasoning about metamodeling

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

The backward case is similar.

Arendt, T., Biermann, E., Jurack, S., Krause, C., Taentzer, G.: Henshin: Advanced concepts and tools for in-place EMF model transformations. In: Petriu, D.C., Rouquette, N., Haugen, Ø. (eds.) Proc. of the ACM/IEEE 13th Intern. Conf. on Model Driven Engineering Languages and Systems (MoDELS’10). LNCS, vol. 6394, pp. 121–135. Springer, Berlin (2010)

Barbosa, D.M., Cretin, J., Foster, N., Greenberg, M., Pierce, B.C.: Matching lenses: alignment and view update. SIGPLAN Not. 45(9), 193–204 (Sep 2010) (http://doi.acm.org/10.1145/1932681.1863572)

Becker, S., Nagl, M., Westfechtel, B.: Incremental and interactive integrator tools for design product consistency. In: Nagl, M., Marquardt, W. (eds.) Collaborative and Distributed Chemical Engineering. From Understanding to Substantial Design Process Support, LNCS, vol. 4970, pp. 224–267. Springer, Berlin (2008) (http://dx.doi.org/10.1007/978-3-540-70552-9_11)

Buneman, P., Fernandez, M., Suciu, D.: UnQL: A query language and algebra for semistructured data based on structural recursion. VLDB J. 9(1), 76–110 (2000)CrossRef

Czarnecki, K., Foster, J., Hu, Z., Lämmel, R., Schürr, A., Terwilliger, J.: Bidirectional Transformations: A Cross-Discipline Perspective. In: Proc. ICMT’09. LNCS, vol. 5563, pp. 260–283. Springer, Berlin (2009)

Diskin, Z., Xiong, Y., Czarnecki, K.: From state- to delta-based bidirectional model transformations: The asymmetric case. J. Object Technol. 10(6), 1–25 (2011)

Diskin, Z.: Algebraic Models for bidirectional model synchronization. In: Czarnecki, K., Ober, I., Bruel, J.M., Uhl, A., Völter, M. (eds.) Model Driven Engineering Languages and Systems, Lecture Notes in Computer Science, vol. 5301, pp. 21–36. Springer, Berlin (2008) (http://dx.doi.org/10.1007/978-3-540-87875-9_2)

Diskin, Z.: Model synchronization: Mappings, tiles, and categories. In: Generative and Transformational Techniques in Software Engineering III, LNCS, vol. 6491, pp. 92–165. Springer, Berlin (2011)

Diskin, Z., Xiong, Y., Czarnecki, K., Ehrig, H., Hermann, F., Orejas, F.: From State- to Delta-based Bidirectional Model Transformations: The Symmetric Case. In: Proc. MODELS 2011. Springer, Berlin (2011)

10.

Ehrig, H., Ehrig, K., Hermann, F.: From Model Transformation to Model Integration based on the Algebraic Approach to Triple Graph Grammars. EC-EASST 10 (2008)

11.

Ehrig, H., Ehrig, K., Prange, U., Taentzer, G.: Fundamentals of Algebraic Graph Transformation. Springer, EATCS Monographs in Theor. Comp. Science (2006)

12.

Ehrig, H., Ermel, C., Hermann, F., Prange, U.: On-the-fly construction, correctness and completeness of model transformations based on triple graph grammars. In: Proc. MODELS’09. LNCS, vol. 5795, pp. 241–255. Springer, Berlin (2009)

13.

Foster, J.N., Greenwald, M.B., Moore, J.T., Pierce, B.C., Schmitt, A.: Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem. ACM Trans. Program. Lang. Syst. 29(3) (May 2007) (http://doi.acm.org/10.1145/1232420.1232424)

14.

Giese, H., Hildebrandt, S.: Efficient Model Synchronization of Large-Scale Models. Tech. Rep. 28, Hasso Plattner Institute at the University of Potsdam (2009)

15.

Giese, H., Wagner, R.: From model transformation to incremental bidirectional model synchronization. Softw. Syst. Model. 8(1), 21–43 (2009)CrossRef

16.

Giese, H., Hildebrandt, S., Lambers, L.: Toward bridging the gap between formal semantics and implementation of triple graph grammars. Tech. Rep. 37, Hasso Plattner Institute at the University of Potsdam (2010)

17.

Golas, U., Ehrig, H., Habel, A.: Multi-amalgamation in adhesive categories. In: Proceedings of Intern. Conf. on Graph Transformation ( ICGT’ 10) (2010) (http://tfs.cs.tu-berlin.de/publikationen/Papers10/GEH10.pdf)

18.

Golas, U., Ehrig, H., Hermann, F.: Formal Specification of Model Transformations by Triple Graph Grammars with Application Conditions. EC-EASST 39 (2011)

19.

Greenyer, J., Kindler, E.: Comparing relational model transformation technologies: Implementing query/view/transformation with triple graph grammars. Softw. Syst. Model. (SoSyM) 9(1), 21–46 (2010)CrossRef

20.

Greenyer, J., Pook, S., Rieke, J.: Preventing information loss in incremental model synchronization by reusing elements. In: Proc. ECMFA 2011. LNCS, vol. 6698, pp. 144–159. Springer, Berlin (2011)

21.

Hermann, F., Ehrig, H., Ermel, C., Orejas, F.: Concurrent model synchronization with conflict resolution based on triple graph grammars. In: de Lara, J., Zisman, A. (eds.) Proc. Fundamental Aspects of Software Engineering (FASE’12). LNCS, vol. 7212, pp. 178–193. Springer, Berlin (2012)

22.

Hermann, F., Ehrig, H., Golas, U., Orejas, F.: Efficient analysis and execution of correct and complete model transformations based on triple graph grammars. In: Proc. MDI’10 (2010)

23.

Hermann, F., Ehrig, H., Orejas, F., Czarnecki, K., Diskin, Z., Xiong, Y.: Correctness of model synchronization based on triple graph grammars. In: Proc. Int. Conf. on Model Driven Engineering Languages and Systems (MoDELS’11). LNCS, vol. 6981. Springer, Berlin (2011)

24.

Hermann, F., Ehrig, H., Orejas, F., Czarnecki, K., Diskin, Z., Xiong, Y.: Correctness of Model Synchronization Based on Triple Graph Grammars—Extended Version. Tech. Rep. TR 2011–07, TU Berlin, Fak. IV (2011)

25.

Hermann, F., Ehrig, H., Orejas, F., Golas, U.: Formal analysis of functional behaviour of model transformations based on triple graph grammars. In: Proc. ICGT’10. LNCS, vol. 6372, pp. 155–170. Springer, Berlin (2010)

26.

Hidaka, S., Hu, Z., Inaba, K., Kato, H., Matsuda, K., Nakano, K.: Bidirectionalizing graph transformations. In: 15th ACM SIGPLAN International Conference on Functional Programming (ICFP 2010). pp. 205–216 (2010)

27.

Hofmann, M., Pierce, B., Wagner, D.: Symmetric lenses. SIGPLAN Not. 46(1), 371–384 (Jan 2011) (http://doi.acm.org/10.1145/1925844.1926428)

28.

Hofmann, M., Pierce, B., Wagner, D.: Edit lenses. SIGPLAN Not. 47(1), 495–508 (Jan 2012) (http://doi.acm.org/10.1145/2103621.2103715)

29.

Kindler, E., Wagner, R.: Triple graph grammars: Concepts, extensions, implementations, and application scenarios. Tech. Rep. TR-ri-07-284, Department of Computer Science, University of Paderborn, Germany (2007)

30.

Klar, F., Lauder, M., Königs, A., Schürr, A.: Extended triple graph grammars with efficient and compatible graph translators. In: Graph Transformations and Model Driven Enginering, LNCS, vol. 5765, pp. 141–174. Springer, Berlin (2010)

31.

Object Management Group: Meta Object Facility (MOF) 2.0 Query/View/Transformation Specification. Version 1.0 formal/08-04-03. (http://www.omg.org/spec/QVT/1.0/) (2008)

32.

Ottersten, B., Engel, T.: SPELL: Satellite communication’s ‘lingua franca’. In: Interdisciplinary Centre for Security, Reliability and Trust. Annual Report 2011. pp. 14–15. scienceRELATIONS, Dortmund, Germany (2012) (http://www.uni.lu/content/download/52106/624943/version/1/file/SnT_AR2011_final_web.pdf)

33.

Schürr, A.: Specification of graph translators with triple graph grammars. In: Proc. WG’94. LNCS, vol. 903, pp. 151–163. Springer, Heidelberg (1994)

34.

Schürr, A., Winter, A., Zündorf, A.: The PROGRES approach: Language and environment. In: Ehrig, H., Engels, G., Kreowski, H.J., Rozenberg, G. (eds.) Handbook of Graph Grammars and Computing by Graph Transformation, Volume 2: Applications, Languages and Tools. p. 487550. World Scientific (1999)

35.

Schürr, A., Klar, F.: 15 years of triple graph grammars. In: Proc. ICGT’08. LNCS, vol. 5214, pp. 411–425 (2008)

36.

Stevens, P.: Bidirectional model transformations in QVT: Semantic issues and open questions. Softw. Syst. Model. 9, 7–20 (2010)CrossRef

37.

TFS-Group, TU Berlin: AGG (2011) (http://tfs.cs.tu-berlin.de/agg)

Titel: Model synchronization based on triple graph grammars: correctness, completeness and invertibility
verfasst von: Frank Hermann
Hartmut Ehrig
Fernando Orejas
Krzysztof Czarnecki
Zinovy Diskin
Yingfei Xiong
Susann Gottmann
Thomas Engel
Publikationsdatum: 01.02.2015
Verlag: Springer Berlin Heidelberg
Erschienen in: Software and Systems Modeling / Ausgabe 1/2015
Print ISSN: 1619-1366
Elektronische ISSN: 1619-1374
DOI: https://doi.org/10.1007/s10270-012-0309-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2015

Runtime verification of component-based systems in the BIP framework with formally-proved sound and complete instrumentation

SEFM: software engineering and formal methods

Translating between Alloy specifications and UML class diagrams annotated with OCL

Guest editorial to the special issue on MODELS 2011

Model transformations for migrating legacy deployment models in the automotive industry

A fine-grained analysis of the support provided by UML class diagrams and ER diagrams during data model maintenance

Premium Partner