Abstract
Sequential model synchronisation is the task of propagating changes from one model to another correlated one to restore consistency. It is challenging to perform this propagation in a least-changing way that avoids unnecessary deletions (which might cause information loss). From a theoretical point of view, so-called short-cut (SC) rules have been developed that enable provably correct propagation of changes while avoiding information loss. However, to be able to react to every possible change, an infinite set of such rules might be necessary. Practically, only small sets of pre-computed basic SC rules have been used, severely restricting the kind of changes that can be propagated without loss of information. In this work, we close that gap by developing an approach to compute more complex required SC rules on-the-fly during synchronisation. These higher-order SC rules allow us to cope with more complex scenarios when multiple changes must be handled in one step. We implemented our approach in the model transformation tool eMoflon. An evaluation shows that the overhead of computing higher-order SC rules on-the-fly is tolerable and at times even improves the overall performance. Above that, completely new scenarios can be dealt with without the loss of information.
This work was partially funded by the German Research Foundation (DFG), project “Triple Graph Grammars (TGG) 3.0”.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
These markings are not needed for the original TGG rules.
- 2.
- 3.
References
Anjorin, A., Leblebici, E., Kluge, R., Schürr, A., Stevens, P.: A systematic approach and guidelines to developing a triple graph grammar. In: Proceedings of the 4th International Workshop on Bidirectional Transformations. CEUR Workshop Proceedings, vol. 1396, pp. 81–95 (2015). http://tubiblio.ulb.tu-darmstadt.de/76241/
Anjorin, A., Weidmann, N., Oppermann, R., Fritsche, L., Schürr, A.: Automating test schedule generation with domain-specific languages: a configurable, model-driven approach. In: MoDELS 2020: ACM/IEEE 23rd International Conference on Model Driven Engineering Languages and Systems, Virtual Event, Canada, 18–23 October 2020, pp. 320–331. ACM (2020). https://doi.org/10.1145/3365438.3410991
Becker, S.M., Westfechtel, B.: Incremental integration tools for chemical engineering: an industrial application of triple graph grammars. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 46–57. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39890-5_5
Behr, N., Krivine, J.: Compositionality of rewriting rules with conditions. Compositionality 3 (2021). https://doi.org/10.32408/compositionality-3-2
Blouin, D., Plantec, A., Dissaux, P., Singhoff, F., Diguet, J.-P.: Synchronization of models of rich languages with triple graph grammars: an experience report. In: Di Ruscio, D., Varró, D. (eds.) ICMT 2014. LNCS, vol. 8568, pp. 106–121. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08789-4_8
Brambilla, M., Cabot, J., Wimmer, M.: Model-Driven Software Engineering in Practice, 2nd edn. Synthesis Lectures on Software Engineering. Morgan & Claypool Publishers (2017). https://doi.org/10.2200/S00751ED2V01Y201701SWE004
Ehrig, H., Ehrig, K., Ermel, C., Hermann, F., Taentzer, G.: Information preserving bidirectional model transformations. In: Dwyer, M.B., Lopes, A. (eds.) FASE 2007. LNCS, vol. 4422, pp. 72–86. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71289-3_7
Ehrig, H., Ehrig, K., Prange, U., Taentzer, G.: Fundamentals of Algebraic Graph Transformation. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2006). https://doi.org/10.1007/3-540-31188-2
Fritsche, L.: Local consistency restoration methods for triple graph grammars. Ph.D. thesis, Technical University of Darmstadt, Germany (2022). http://tuprints.ulb.tu-darmstadt.de/21443/
Fritsche, L., Kosiol, J., Möller, A., Schürr, A., Taentzer, G.: A precedence-driven approach for concurrent model synchronization scenarios using triple graph grammars. In: Lämmel, R., Tratt, L., de Lara, J. (eds.) Proceedings of the 13th ACM SIGPLAN International Conference on Software Language Engineering, SLE 2020, Virtual Event, USA, 16–17 November 2020, pp. 39–55. ACM (2020). https://doi.org/10.1145/3426425.3426931
Fritsche, L., Kosiol, J., Schürr, A., Taentzer, G.: Short-cut rules –sequential composition of rules avoiding unnecessary deletions. In: Mazzara, M., Ober, I., Salaün, G. (eds.) STAF 2018. LNCS, vol. 11176, pp. 415–430. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-04771-9_30
Fritsche, L., Kosiol, J., Schürr, A., Taentzer, G.: Avoiding unnecessary information loss: correct and efficient model synchronization based on triple graph grammars. Int. J. Softw. Tools Technol. Transfer 23(3), 335–368 (2020). https://doi.org/10.1007/s10009-020-00588-7
Giese, H., Hildebrandt, S., Neumann, S., Wätzoldt, S.: Industrial case study on the integration of SysML and AUTOSAR with triple graph grammars. Technical report, 57 (2012)
Giese, H., Wagner, R.: From model transformation to incremental bidirectional model synchronization. Softw. Syst. Model. 8(1), 21–43 (2009). https://doi.org/10.1007/s10270-008-0089-9
Greenyer, J., Pook, S., Rieke, J.: Preventing information loss in incremental model synchronization by reusing elements. In: France, R.B., Kuester, J.M., Bordbar, B., Paige, R.F. (eds.) ECMFA 2011. LNCS, vol. 6698, pp. 144–159. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21470-7_11
Hermann, F., Ehrig, H., Golas, U., Orejas, F.: Formal analysis of model transformations based on triple graph grammars. Math. Struct. Comput. Sci. 24(4), 240408 (2014). https://doi.org/10.1017/S0960129512000370
Hermann, F., et al.: Model synchronization based on triple graph grammars: correctness, completeness and invertibility. Softw. Syst. Model. 14(1), 241–269 (2013). https://doi.org/10.1007/s10270-012-0309-1
Kosiol, J.: Formal foundations for information-preserving model synchronization processes based on triple graph grammars. Ph.D. thesis, University of Marburg, Germany (2022). https://archiv.ub.uni-marburg.de/diss/z2022/0224
Kosiol, J., Taentzer, G.: A generalized concurrent rule construction for double-pushout rewriting: generalized concurrency theorem and language-preserving rule applications. J. Log. Algebraic Methods Program. 130, 100820 (2023). https://doi.org/10.1016/j.jlamp.2022.100820
Lauder, M., Anjorin, A., Varró, G., Schürr, A.: Efficient model synchronization with precedence triple graph grammars. In: Ehrig, H., Engels, G., Kreowski, H.-J., Rozenberg, G. (eds.) ICGT 2012. LNCS, vol. 7562, pp. 401–415. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33654-6_27
Leblebici, E.: Inter-model consistency checking and restoration with triple graph grammars. Ph.D. thesis, Darmstadt University of Technology, Germany (2018). http://tuprints.ulb.tu-darmstadt.de/7426/
Leblebici, E., Anjorin, A., Fritsche, L., Varró, G., Schürr, A.: Leveraging incremental pattern matching techniques for model synchronisation. In: de Lara, J., Plump, D. (eds.) ICGT 2017. LNCS, vol. 10373, pp. 179–195. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-61470-0_11
Orejas, F., Pino, E.: Correctness of incremental model synchronization with triple graph grammars. In: Di Ruscio, D., Varró, D. (eds.) ICMT 2014. LNCS, vol. 8568, pp. 74–90. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08789-4_6
Orejas, F., Pino, E., Navarro, M.: Incremental concurrent model synchronization using triple graph grammars. In: FASE 2020. LNCS, vol. 12076, pp. 273–293. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45234-6_14
Schürr, A.: Specification of graph translators with triple graph grammars. In: Mayr, E.W., Schmidt, G., Tinhofer, G. (eds.) WG 1994. LNCS, vol. 903, pp. 151–163. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-59071-4_45
Weidmann, N., Anjorin, A.: Schema compliant consistency management via triple graph grammars and integer linear programming. In: FASE 2020. LNCS, vol. 12076, pp. 315–334. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45234-6_16
Weidmann, N., Fritsche, L., Anjorin, A.: A search-based and fault-tolerant approach to concurrent model synchronisation. In: Lämmel, R., Tratt, L., de Lara, J. (eds.) Proceedings of the 13th ACM SIGPLAN International Conference on Software Language Engineering, SLE 2020, Virtual Event, USA, 16–17 November 2020, pp. 56–71. ACM (2020). https://doi.org/10.1145/3426425.3426932
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Fritsche, L., Kosiol, J., Möller, A., Schürr, A. (2023). Advanced Consistency Restoration with Higher-Order Short-Cut Rules. In: Fernández, M., Poskitt, C.M. (eds) Graph Transformation. ICGT 2023. Lecture Notes in Computer Science, vol 13961. Springer, Cham. https://doi.org/10.1007/978-3-031-36709-0_10
Download citation
DOI: https://doi.org/10.1007/978-3-031-36709-0_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-36708-3
Online ISBN: 978-3-031-36709-0
eBook Packages: Computer ScienceComputer Science (R0)