×

Granularity of conflicts and dependencies in graph transformation systems: a two-dimensional approach. (English) Zbl 1417.68078

Summary: Conflict and dependency analysis (CDA) is a static analysis for the detection of conflicting and dependent rule applications in a graph transformation system. The state-of-the-art CDA technique, critical pair analysis, provides all potential conflicts and dependencies in minimal context as critical pairs, for each pair of rules. Yet, critical pairs can be hard to understand; users are mainly interested in core information about conflicts and dependencies occurring in various combinations. In this paper, we present an approach to conflicts and dependencies in graph transformation systems based on two dimensions of granularity. The first dimension refers to the overlap considered between the rules of a given rule pair; the second one refers to the represented amount of context information about transformations in which the conflicts occur. We introduce a variety of new conflict notions, in particular, conflict atoms, conflict reasons, and minimal conflict reasons, relate them to the existing conflict notions of critical pairs and initial conflicts, and position all of these notions within our granularity approach. Finally, we introduce dual concepts for dependency analysis. As we discuss in a running example, our approach paves the way for an improved CDA technique.

MSC:

68Q42 Grammars and rewriting systems

Software:

AGG; Henshin; RuleMerger
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baresi, L.; Heckel, R., Tutorial introduction to graph transformation: a software engineering perspective, (International Conference on Graph Transformation (2002), Springer), 402-429 · Zbl 1028.68509
[2] Finger, S.; Dixon, J. R., A review of research in mechanical engineering design. Part II: Representations, analysis, and design for the life cycle, Res. Eng. Des., 1, 2, 121-137 (1989)
[3] Rosselló, F.; Valiente, G., Graph transformation in molecular biology, (Formal Methods in Software and Systems Modeling (2005)), 116-133 · Zbl 1075.68610
[4] Hausmann, J. H.; Heckel, R.; Taentzer, G., Detection of conflicting functional requirements in a use case-driven approach: a static analysis technique based on graph transformation, (22rd Int. Conf. on Software Engineering (ICSE) (2002), ACM), 105-115
[5] Mens, T.; Van Der Straeten, R.; D’Hondt, M., Detecting and resolving model inconsistencies using transformation dependency analysis, (Int. Conf. on Model Driven Engineering Languages and Systems (MoDELS) (2006), Springer), 200-214
[6] Mens, T.; Taentzer, G.; Runge, O., Analysing refactoring dependencies using graph transformation, Softw. Syst. Model., 6, 3, 269-285 (2007)
[7] Jayaraman, P.; Whittle, J.; Elkhodary, A. M.; Gomaa, H., Model composition in product lines and feature interaction detection using critical pair analysis, (Int. Conf. on Model Driven Engineering Languages and Systems (MoDELS) (2007), Springer), 151-165
[8] Küster, J. M.; Gerth, C.; Engels, G., Dependent and conflicting change operations of process models, (European Conf. on Model Driven Architecture - Foundations and Applications (ECMDA-FA), vol. 5562 (2009), Springer), 158-173
[9] Mehner-Heindl, K.; Monga, M.; Taentzer, G., Analysis of aspect-oriented models using graph transformation systems, (Aspect-Oriented Requirements Engineering (2013), Springer), 243-270
[10] Baresi, L.; Heckel, R.; Thöne, S.; Varró, D., Modeling and validation of service-oriented architectures: application vs. style, (Symp. on Foundations of Software Engineering/European Software Engineering Conf. (FSE/ESEC) (2003), ACM), 68-77
[11] Ermel, C.; Gall, J.; Lambers, L.; Taentzer, G., Modeling with plausibility checking: inspecting favorable and critical signs for consistency between control flow and functional behavior, (Int. Conf. on Fundamental Approaches to Software Engineering (FASE) (2011), Springer), 156-170
[12] Strüber, D.; Taentzer, G.; Jurack, S.; Schäfer, T., Towards a distributed modeling process based on composite models, (Int. Conf. on Fundamental Approaches to Software Engineering (FASE) (2013), Springer), 6-20
[13] Heckel, R.; Küster, J. M.; Taentzer, G., Confluence of typed attributed graph transformation systems, (First Int. Conf. on Graph Transformation (ICGT) (2002), Springer), 161-176 · Zbl 1028.68031
[14] Ehrig, H.; Ehrig, K.; Prange, U.; Taentzer, G., Fundamentals of Algebraic Graph Transformation, Monographs in Theoretical Computer Science (2006), Springer · Zbl 1095.68047
[15] Lambers, L.; Born, K.; Orejas, F.; Strüber, D.; Taentzer, G., Initial conflicts and dependencies: critical pairs revisited, (Heckel, R.; Taentzer, G., Graph Transformation, Specifications, and Nets. Graph Transformation, Specifications, and Nets, Lecture Notes in Computer Science, vol. 10800 (2018), Springer), 105-123 · Zbl 1383.68045
[16] Lambers, L.; Strüber, D.; Taentzer, G.; Born, K.; Hübert, J., Multi-granular conflict and dependency analysis in software engineering based on graph transformation, (Proceedings of the 40th International Conference on Software Engineering (2018), ACM: ACM New York, NY, USA), 716-727
[17] Born, K.; Lambers, L.; Strüber, D.; Taentzer, G., Granularity of conflicts and dependencies in graph transformation systems, (International Conference on Graph Transformation (ICGT) (2017)), 125-141 · Zbl 1425.68155
[18] Fowler, M., Refactoring: Improving the Design of Existing Code (1999), Addison-Wesley: Addison-Wesley Boston, MA, USA · Zbl 1020.68632
[19] Lambers, L.; Ehrig, H.; Orejas, F., Efficient conflict detection in graph transformation systems by essential critical pairs, Electron. Notes Theor. Comput. Sci., 211, 17-26 (2008) · Zbl 1283.68185
[20] Lambers, L., Certifying Rule-Based Models Using Graph Transformation (2010), Berlin Institute of Technology, Ph.D. thesis
[21] Ehrig, H.; Padberg, J.; Prange, U.; Habel, A., Adhesive high-level replacement systems: a new categorical framework for graph transformation, Fundam. Inform., 74, 1, 1-29 (2006) · Zbl 1106.68056
[22] Azzi, G. G.; Corradini, A.; Ribeiro, L., On the essence and initiality of conflicts, (Lambers, L.; Weber, J., Graph Transformation - 11th International Conference, ICGT 2018, Held as Part of STAF. Graph Transformation - 11th International Conference, ICGT 2018, Held as Part of STAF, 2018, Toulouse, France, June 25-26, 2018, Proceedings. Graph Transformation - 11th International Conference, ICGT 2018, Held as Part of STAF. Graph Transformation - 11th International Conference, ICGT 2018, Held as Part of STAF, 2018, Toulouse, France, June 25-26, 2018, Proceedings, Lecture Notes in Computer Science, vol. 10887 (2018), Springer), 99-117 · Zbl 1394.68195
[23] Gabriel, K.; Braatz, B.; Ehrig, H.; Golas, U., Finitary \(M\)-adhesive categories, Math. Struct. Comput. Sci., 24, 4, Article 240403 pp. (2014) · Zbl 1342.68177
[24] Plump, D., Critical pairs in term graph rewriting, (Mathematical Foundations of Computer Science (1994)), 556-566 · Zbl 1493.68177
[25] Ehrig, H.; Golas, U.; Habel, A.; Lambers, L.; Orejas, F., \(M\)-adhesive transformation systems with nested application conditions. Part 2: Embedding, critical pairs and local confluence, Fundam. Inform., 118, 1-2, 35-63 (2012) · Zbl 1242.68128
[26] Kulcsár, G.; Deckwerth, F.; Lochau, M.; Varró, G.; Schürr, A., Improved conflict detection for graph transformation with attributes, (Rensink, A.; Zambon, E., Proceedings Graphs as Models, GaM@ETAPS 2015. Proceedings Graphs as Models, GaM@ETAPS 2015, London, UK, 11-12 April 2015. Proceedings Graphs as Models, GaM@ETAPS 2015. Proceedings Graphs as Models, GaM@ETAPS 2015, London, UK, 11-12 April 2015, EPTCS, vol. 181 (2015)), 97-112
[27] Hristakiev, I.; Plump, D., Towards critical pair analysis for the graph programming language gp 2, (James, P.; Roggenbach, M., Recent Trends in Algebraic Development Techniques - 23rd IFIP WG 1.3 International Workshop. Recent Trends in Algebraic Development Techniques - 23rd IFIP WG 1.3 International Workshop, WADT 2016, Gregynog, UK, September 21-24, 2016. Recent Trends in Algebraic Development Techniques - 23rd IFIP WG 1.3 International Workshop. Recent Trends in Algebraic Development Techniques - 23rd IFIP WG 1.3 International Workshop, WADT 2016, Gregynog, UK, September 21-24, 2016, Lecture Notes in Computer Science, vol. 10644 (2016), Springer), 153-169, Revised Selected Papers · Zbl 1496.68081
[28] Taentzer, G., AGG: a graph transformation environment for modeling and validation of software, (Int. Workshop on Applications of Graph Transformations with Industrial Relevance (AGTIVE) (2003), Springer), 446-453
[29] Verigraph, Verigraph
[30] Arendt, T.; Biermann, E.; Jurack, S.; Krause, C.; Taentzer, G., Henshin: advanced concepts and tools for in-place EMF model transformations, (Int. Conf. on Model-Driven Engineering Languages and Systems (MoDELS) (2010)), 121-135
[31] Corradini, A.; Duval, D.; Löwe, M.; Ribeiro, L.; Machado, R.; Costa, A.; Azzi, G. G.; Bezerra, J. S.; Rodrigues, L. M., On the essence of parallel independence for the double-pushout and sesqui-pushout approaches, (Heckel, R.; Taentzer, G., Graph Transformation, Specifications, and Nets: in Memory of Hartmut Ehrig (2018), Springer International Publishing: Springer International Publishing Cham), 1-18 · Zbl 1383.68042
[32] Orejas, F.; Lambers, L., Lazy graph transformation, Fundam. Inform., 118, 1-2, 65-96 (2012) · Zbl 1242.68139
[33] Deckwerth, F.; Kulcsár, G.; Lochau, M.; Varró, G.; Schürr, A., Conflict detection for edits on extended feature models using symbolic graph transformation, (Int. Workshop on Formal Methods and Analysis in Software Product Line Engineering. Int. Workshop on Formal Methods and Analysis in Software Product Line Engineering, EPTCS, vol. 206 (2016)), 17-31
[34] Strüber, D.; Rubin, J.; Arendt, T.; Chechik, M.; Taentzer, G.; Plöger, J., Rulemerger: automatic construction of variability-based model transformation rules, (Int. Conf. on Fundamental Approaches to Software Engineering (2016), Springer), 122-140 · Zbl 1378.68024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.