TU Darmstadt / ULB / TUbiblio

Local Consistency Restoration Methods for Triple Graph Grammars

Fritsche, Lars (2022)
Local Consistency Restoration Methods for Triple Graph Grammars.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00021443
Dissertation, Erstveröffentlichung, Verlagsversion

Kurzbeschreibung (Abstract)

Modern software systems are becoming increasingly complex and are created by different stakeholders that commit to one vision. Yet, these stakeholders differ in their requirements that they pose on the software system and also do not necessarily share all competencies. Therefore, they require views onto the system tailored to their needs and abstracting from details outside their domain. Model-Driven Engineering (MDE) provides a methodology to achieve this by using models to abstract from different aspects of the same system. Yet, these models may overlap (partially), and more importantly, they may change throughout their life-cycle. Hence, changes to one model may have to be synchronised with other models that share the same information to restore consistency w.r.t. the overall system. The bidirectional transformations (BX) community aims at providing the means to specify and restore consistency between two models. A popular BX approach are Triple Graph Grammars (TGGs), where models are interpreted as graph-like structures and consistency is expressed via a set of grammar rules. These rules describe how to create consistent pairs of models from scratch. Furthermore, they can be transformed automatically to obtain advanced consistency restoration operations such as synchronisers that propagate changes between models. Most synchronisers are sequential meaning that only one model is changed at a time and the opposite model is updated. To date, most TGG-based approaches solve this task by deconstructing parts of the opposite model that are no longer consistent w.r.t. the TGG and then synchronising the now untranslated elements of the changed model. Yet, this retranslation often leads to very similar structures like the ones that were deleted. Hence, this strategy is inefficient and, above that, can even cause information loss when some information is only contained in one model but not the other. Therefore, we introduce short-cut rules as a new kind of TGG rule that describes how complex changes can be applied to both models at once in a consistency and information preserving way. Like normal TGG rules, these rules can then be transformed to obtain synchronisers, restoring consistency and preserving information more efficiently. In practice, sequential synchronisers are too limited to be employed in a truly collaborative scenario where both models may be changed concurrently by different stakeholders. The challenge of this task lies in the fact that some changes may conflict and have to be resolved. Former concurrent synchronisation solutions solved this by performing a sequential synchronisation step in one direction, followed by another in the opposite direction, detecting and resolving conflicts along the way. Others explored the vast space of (most of) all concurrent synchronisation solutions. While the first kind’s conflict detection was shown to depend on the order in which the synchronisation steps are executed, the latter is only applicable to small models. In this thesis, we introduce a novel TGG-based concurrent model synchronisation technique, which finds (most) conflicts before any synchronisation activities take place and detects conflicts more reliably. Also, our approach is highly configurable and provides the means for modellers to implement their own synchronisation goals. Finally, we implemented and evaluated both the short-cut rule framework and the TGG-based concurrent synchronisation framework demonstrating their promising scalability and comparing our solution to another state-of-the-art BX tool.

Typ des Eintrags: Dissertation
Erschienen: 2022
Autor(en): Fritsche, Lars
Art des Eintrags: Erstveröffentlichung
Titel: Local Consistency Restoration Methods for Triple Graph Grammars
Sprache: Englisch
Referenten: Schürr, Prof. Dr. Andy ; Engels, Prof. Dr. Gregor
Publikationsjahr: 2022
Ort: Darmstadt
Kollation: xiii, 215 Seiten
Datum der mündlichen Prüfung: 30 März 2022
DOI: 10.26083/tuprints-00021443
URL / URN: https://tuprints.ulb.tu-darmstadt.de/21443
Kurzbeschreibung (Abstract):

Modern software systems are becoming increasingly complex and are created by different stakeholders that commit to one vision. Yet, these stakeholders differ in their requirements that they pose on the software system and also do not necessarily share all competencies. Therefore, they require views onto the system tailored to their needs and abstracting from details outside their domain. Model-Driven Engineering (MDE) provides a methodology to achieve this by using models to abstract from different aspects of the same system. Yet, these models may overlap (partially), and more importantly, they may change throughout their life-cycle. Hence, changes to one model may have to be synchronised with other models that share the same information to restore consistency w.r.t. the overall system. The bidirectional transformations (BX) community aims at providing the means to specify and restore consistency between two models. A popular BX approach are Triple Graph Grammars (TGGs), where models are interpreted as graph-like structures and consistency is expressed via a set of grammar rules. These rules describe how to create consistent pairs of models from scratch. Furthermore, they can be transformed automatically to obtain advanced consistency restoration operations such as synchronisers that propagate changes between models. Most synchronisers are sequential meaning that only one model is changed at a time and the opposite model is updated. To date, most TGG-based approaches solve this task by deconstructing parts of the opposite model that are no longer consistent w.r.t. the TGG and then synchronising the now untranslated elements of the changed model. Yet, this retranslation often leads to very similar structures like the ones that were deleted. Hence, this strategy is inefficient and, above that, can even cause information loss when some information is only contained in one model but not the other. Therefore, we introduce short-cut rules as a new kind of TGG rule that describes how complex changes can be applied to both models at once in a consistency and information preserving way. Like normal TGG rules, these rules can then be transformed to obtain synchronisers, restoring consistency and preserving information more efficiently. In practice, sequential synchronisers are too limited to be employed in a truly collaborative scenario where both models may be changed concurrently by different stakeholders. The challenge of this task lies in the fact that some changes may conflict and have to be resolved. Former concurrent synchronisation solutions solved this by performing a sequential synchronisation step in one direction, followed by another in the opposite direction, detecting and resolving conflicts along the way. Others explored the vast space of (most of) all concurrent synchronisation solutions. While the first kind’s conflict detection was shown to depend on the order in which the synchronisation steps are executed, the latter is only applicable to small models. In this thesis, we introduce a novel TGG-based concurrent model synchronisation technique, which finds (most) conflicts before any synchronisation activities take place and detects conflicts more reliably. Also, our approach is highly configurable and provides the means for modellers to implement their own synchronisation goals. Finally, we implemented and evaluated both the short-cut rule framework and the TGG-based concurrent synchronisation framework demonstrating their promising scalability and comparing our solution to another state-of-the-art BX tool.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

Moderne Softwaresysteme werden zunehmend komplexer und sind das Ergebnis unterschiedlichster Interessensvertreter, die diese gemeinsam realisieren. Dabei stellen die verschiedenen Interessensvertreter unterschiedliche Anforderungen an das Softwaresystem und haben zum Teil unterschiedliche Kompetenzen. Aus diesem Grund werden unterschiedliche Sichten auf das Softwaresystem benötigt, die von Details abstrahieren, die außerhalb der Domäne einzelner Interessensvertreter liegen. Die modellgetriebene Softwareentwicklung bietet hierfür eine Methodologie, bei der Modelle verwendet werden, um verschiedene Aspekte eines Softwaresystems zu beschreiben. Diese Sichten können (teilweise) überlappen und sich stetig verändern. Aus diesem Grund müssen Änderungen zwischen Modellen, die sich Informationen teilen, synchronisiert werden, damit alle Modelle konsistent zum gesamten System sind. Um dies zu realisieren, lassen sich bidirektionale Transformationen (BX) einsetzen. Das Ziel von BX-Ansätzen ist es, Konsistenz zwischen zwei Modellen einerseits zu spezifizieren und andererseits Operationen zur Konsistenzwiederherstellung bereitzustellen. Ein populärer BX-Ansatz sind hierbei Tripel-Graph-Grammatiken (TGGen), bei denen Modelle als graphähnliche Strukturen interpretiert werden und Konsistenz durch eine Menge an Graphgrammatikregeln ausgedrückt wird. Die Regeln einer TGG beschreiben dabei, wie Paare von konsistenten Modellen von Grund auf erzeugt werden. Außerdem lassen sich diese Regeln automatisch transformieren, um aus ihnen Operationen abzuleiten, die Konsistenz wiederherstellen. Zum Beispiel lassen sich so Synchronisierer ableiten, die Änderungen zwischen Modellen propagieren. Die meisten Synchronisierer arbeiten sequentiell und erwarten daher, dass nur ein Modell geändert wird, während die Änderungen in das zweite gegenüberliegende Modell übertragen werden. Gängige TGG-basierte Ansätze realisieren dies, in dem die Teile des gegenüberliegenden Modells abgebaut werden, die nicht mehr konsistent zur TGG sind. Im Anschluss werden alle unübersetzten Elemente des geänderten Modells propagiert. Dabei ist jedoch oft zu beobachten, dass die neu erzeugten Strukturen denen ähneln, die im vorigen Schritt gelöscht wurden und es somit effizienter wäre diese Strukturen zu erhalten. Darüber hinaus kann diese Vorgehensweise zu Informationsverlust führen, wenn die gelöschten Elemente Informationen enthielten, die nicht im anderen Modell vorkommen. In dieser Dissertationsschrift stellen wir Short-Cut-Regeln als eine neue Form von TGG-Regeln vor. Short-Cut-Regeln beschreiben komplexe Änderungen, die angewandt auf beide Modelle deren Konsistenz sowie zusätzliche Informationen bewahren. Ebenso wie TGG-Regeln, lassen sich Short-Cut-Regeln transformieren, um aus ihnen effiziente konsistenzwiederherstellende Synchronisierer abzuleiten, die Informationen erhalten. Sequentielle Synchronisierer sind in der Praxis jedoch oft zu eingeschränkt, da in kollaborativen Szenarien beide Modelle simultan von verschiedenen Interessensvertretern verändert werden können. Dabei können Konflikte zwischen Änderungen entstehen, die aufgelöst werden müssen bevor ein konsistenter Zustand wiederhergestellt werden kann. Viele Ansätze implementieren simultane Synchronisierer, in dem die Änderungen von einem Modell in das andere durch einen sequentiellen Synchronisierungsschritt übertragen werden, gefolgt von einem Synchronisierungsschritt in die entgegengesetzte Richtung. Konflikte werden hierbei während der Synchronisierungsschritte detektiert. Jedoch hat sich gezeigt, dass bei dieser Vorgehensweise die Detektierung von Konflikten von der Reihenfolge abhängt, in der diese Synchronisationsschritte angewandt werden. Andere Ansätze basieren auf einer ausführlichen Erkundung des Suchraums (fast) aller möglichen Synchronisationslösungen und sind somit nur für relativ kleine Modelle anwendbar. Diese Probleme adressierend präsentieren wir einen neuartigen TGG-basierten Ansatz zur simultanen Modellsynchronisation. Unser Ansatz findet (die meisten) Konflikte ohne Synchronisationsschritte anwenden zu müssen und erkennt Konflikte zuverlässiger. Darüber hinaus ist er stark konfigurierbar und ermöglicht es Modellierern verschiedenste Synchronisationsziele umzusetzen. Die Evaluationsergebnisse unserer Implementierung der Short-Cut-Regeln und des TGG-basierten simultanen Modellsynchronisationsansatzes zeigen vielversprechende Skalierungseigenschaften, welche mit einem weiteren aktuellen BX-Werkzeug verglichen wurden.

Deutsch
Status: Verlagsversion
URN: urn:nbn:de:tuda-tuprints-214430
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 18 Fachbereich Elektrotechnik und Informationstechnik
18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Datentechnik > Echtzeitsysteme
18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Datentechnik
Hinterlegungsdatum: 03 Jun 2022 12:04
Letzte Änderung: 11 Nov 2022 09:34
PPN: 496555138
Referenten: Schürr, Prof. Dr. Andy ; Engels, Prof. Dr. Gregor
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 30 März 2022
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen