Dissertations / Theses on the topic 'Triple Graph Grammar'

During the overall development of complex engineering systems different modeling notations are employed. For example, in the domain of automotive systems system engineering models are employed quite early to capture the requirements and basic structuring of the entire system, while software engineering models are used later on to describe the concrete software architecture. Each model helps in addressing the specific design issue with appropriate notations and at a suitable level of abstraction. However, when we step forward from system design to the software design, the engineers have to ensure that all decisions captured in the system design model are correctly transferred to the software engineering model. Even worse, when changes occur later on in either model, today the consistency has to be reestablished in a cumbersome manual step. In this report, we present in an extended version of [Holger Giese, Stefan Neumann, and Stephan Hildebrandt. Model Synchronization at Work: Keeping SysML and AUTOSAR Models Consistent. In Gregor Engels, Claus Lewerentz, Wilhelm Schäfer, Andy Schürr, and B. Westfechtel, editors, Graph Transformations and Model Driven Enginering - Essays Dedicated to Manfred Nagl on the Occasion of his 65th Birthday, volume 5765 of Lecture Notes in Computer Science, pages 555–579. Springer Berlin / Heidelberg, 2010.] how model synchronization and consistency rules can be applied to automate this task and ensure that the different models are kept consistent. We also introduce a general approach for model synchronization. Besides synchronization, the approach consists of tool adapters as well as consistency rules covering the overlap between the synchronized parts of a model and the rest. We present the model synchronization algorithm based on triple graph grammars in detail and further exemplify the general approach by means of a model synchronization solution between system engineering models in SysML and software engineering models in AUTOSAR which has been developed for an industrial partner. In the appendix as extension to [19] the meta-models and all TGG rules for the SysML to AUTOSAR model synchronization are documented.
Bei der Entwicklung komplexer technischer Systeme werden verschiedene Modellierungssprachen verwendet. Zum Beispiel werden bei der Entwicklung von Systemen in der Automobilindustrie bereits früh im Entwicklungsprozess Systemmodelle verwendet, um die Anforderungen und die grobe Struktur des Gesamtsystems darzustellen. Später werden Softwaremodelle verwendet, um die konkrete Softwarearchitektur zu modellieren. Jedes Modell stellt spezifische Entwurfsaspekte mit Hilfe passender Notationen auf einem angemessenen Abstraktionsniveau dar. Wenn jedoch vom Systementwurf zum Softwareentwurf übergegangen wird, müssen die Entwicklungsingenieure sicherstellen, dass alle Entwurfsentscheidungen, die im Systemmodell enthalten sind, korrekt auf das Softwaremodell übertragen werden. Sobald danach auch noch Änderungen auftreten, muss die Konsistenz zwischen den Modellen in einem aufwändigen manuellen Schritt wiederhergestellt werden. In diesem Bericht zeigen wir, wie Modellsynchronisation und Konsistenzregeln zur Automatisierung dieses Arbeitsschrittes verwendet und die Konsistenz zwischen den Modellen sichergestellt werden können. Außerdem stellen wir einen allgemeinen Ansatz zur Modellsynchronisation vor. Neben der reinen Synchronisation umfasst unsere Lösung weiterhin Tool-Adapter, sowie Konsistenzregeln, die sowohl die Teile der Modelle abdecken, die synchronisiert werden können, als auch die restlichen Teile. Der Modellsynchronisationsalgorithmus basiert auf Tripel-Graph-Grammatiken und wird im Detail erläutert. An Hand einer konkreten Transformation zwischen SysML- und AUTOSAR-Modellen, die im Rahmen eines Industrieprojektes entwickelt wurde, wird der Ansatz demonstriert. Im Anhang des Berichts sind alle TGG-Regeln für die SysML-zu-AUTOSAR-Transformation dokumentiert.

The correctness of model transformations is a crucial element for the model-driven engineering of high quality software. A prerequisite to verify model transformations at the level of the model transformation specification is that an unambiguous formal semantics exists and that the employed implementation of the model transformation language adheres to this semantics. However, for existing relational model transformation approaches it is usually not really clear under which constraints particular implementations are really conform to the formal semantics. In this paper, we will bridge this gap for the formal semantics of triple graph grammars (TGG) and an existing efficient implementation. Whereas the formal semantics assumes backtracking and ignores non-determinism, practical implementations do not support backtracking, require rule sets that ensure determinism, and include further optimizations. Therefore, we capture how the considered TGG implementation realizes the transformation by means of operational rules, define required criteria and show conformance to the formal semantics if these criteria are fulfilled. We further outline how static analysis can be employed to guarantee these criteria.

Model-driven software development requires techniques to consistently propagate modifications between different related models to realize its full potential. For large-scale models, efficiency is essential in this respect. In this paper, we present an improved model synchronization algorithm based on triple graph grammars that is highly efficient and, therefore, can also synchronize large-scale models sufficiently fast. We can show, that the overall algorithm has optimal complexity if it is dominating the rule matching and further present extensive measurements that show the efficiency of the presented model transformation and synchronization technique.
Die Model-getriebene Softwareentwicklung benötigt Techniken zur Übertragung von Änderungen zwischen verschiedenen zusammenhängenden Modellen, um vollständig nutzbar zu sein. Bei großen Modellen spielt hier die Effizienz eine entscheidende Rolle. In diesem Bericht stellen wir einen verbesserten Modellsynchronisationsalgorithmus vor, der auf Tripel-Graph-Grammatiken basiert. Dieser arbeitet sehr effizient und kann auch sehr große Modelle schnell synchronisieren. Wir können zeigen, dass der Gesamtalgortihmus eine optimale Komplexität aufweist, sofern er die Ausführung dominiert. Die Effizient des Algorithmus' wird durch einige Benchmarkergebnisse belegt.

Nowadays, software and system development projects involve an increasing number of various CASE tools each of which is specialized in certain tasks or phases of the development process. This results in an unrelated distribution of the data of a project as a whole over the different data repositories of the considered tools. The task of manually keeping the data consistent is cumbersome, time consuming, and error prone. Therefore, there is an urgent need for automatic support in data consistency checking and consistency enforcement. OMG’s Query / View / Transformation (QVT) standard provides a model-based language for the specification of consistency checking and consistency enforcement rules. The QVT standard currently is implemented by a number of different groups but suffers from the fact that it lacks a proper formalization up to now. In contrast Triple Graph Grammars (TGGs) provide a declarative language for the specification of consistency checking and consistency enforcement rules based on the formal foundation of graph grammars. However, TGGs lack some concepts provided by the QVT standard which are needed in practice to be applicable. This work transfers TGGs into OMG’s world of metamodeling and extends them by the desired concepts from QVT. The result is an TGG-based implementation of the QVT standard based on the formalism of graph grammars. Furthermore, the presented approach will be supplemented by a framework for automatically checking and enforcing the consistency of distributed data of a considered development project as a whole.

Triple Graph Grammars (TGGs) are a rule-based technique with a formal background for specifying bidirectional model transformation and, hence, can be applied to transform a given model into another and vice versa. In practice, models are either created from scratch by using a single input model, or incrementally synchronized by propagating changes between integrated models. The outstanding property of incremental model synchronization is that in average only small portions of the whole model have to be retransformed as mostly only a subset of a model has been changed. Hence, we have the opportunity to (i) improve efficiency of model transformations and (ii) to retain as much information as possible. Regarding information preserving capabilities, this offers the chance to qualitatively improve the results of model transformations. This is because additional model content (e.g., model elements or user specific decision during the actual transformation process), which is not covered by the model transformation itself, will be mostly retained. In practical scenarios, unidirectional rules for incremental forward and incremental backward transformation are automatically derived from the specified TGG rules, and the overall transformation process is governed by a control algorithm. Current incremental approaches either have a runtime complexity that depends on the size of related models and not on the number of changes and their affected elements, or do not pursue formalization to give reliable predictions regarding the expected results, or impose such restrictions on the language of TGGs that the remaining expressiveness is not capable of certain real-world scenarios. For these reasons, the aim of this thesis is to develop a novel approach to incremental model synchronization with TGGs that (i) is efficient regarding the number of changes, (ii) retains as much information as possible, (iii) complies with important formal properties, and (iv) is expressive enough for real-world scenarios. Therefore, we introduce an incremental model synchronization algorithm for TGGs, which employs a static analysis on TGG specifications to efficiently determine the range of influence of model changes at runtime and, thus, to regard only these elements for synchronization. Together with further improvements and critical discussions we will be able to show that this approach is a suitable means for complex model synchronization tasks.

Software development is a complex task. The success of a software project highly relies on the involvement of domain experts in the development process. In recent years, therefore, the field of software engineering has been striving to elevate the level of abstraction towards domain-specific concepts (instead of the computation-oriented nature of classical programming languages). Model-Driven Engineering (MDE), a novel software development methodology, lies at the heart of these efforts. In MDE, a model represents an abstraction of a system with one specific goal in mind. Hence, the MDE strategy does not only deal with abstractions but also advocates the co-existence of related models capturing different aspects of the same system. While this supports separation of concerns, consistency management between related models becomes a crucial challenge as models are changed throughout their life cycle. Two basic building blocks of consistency management are (i) consistency checking to indicate whether or to what extent two related models are consistent and (ii) consistency restoration to suitably handle discrepancies between models. To address consistency management tasks in a formally-founded manner, bidirectional transformations (BX) have been established as a research area. Among the diverse BX approaches, Triple Graph Grammars (TGGs) represent a prominent technique with various implementations and industrial applications. In this setting, models are formalized as graphs and consistency is described as a grammar constructing two consistent models together with a correspondence model. Consistency management tools are then automatically derived from this description. Current TGG approaches (and in fact also BX approaches in general) focus on consistency scenarios where only one model is maintained by human intelligence at the same time and the other one is automatically updated by consistency restoration. Consistency management between two concurrently developed models, however, is not sufficiently supported as practical solutions for consistency checking are essentially missing. Strategies for consistency restoration, furthermore, range from heuristics to auxiliary model analyses which constitute the most complex and least understood part of TGGs. Despite sharing the same basic goal and the same formal foundation, it is difficult to exchange ideas amongst the different TGG approaches. In this thesis, therefore, we first establish consistency checking as a novel use case of TGGs. We identify search space problems in consistency checking and overcome them by combining TGGs with linear optimization techniques. Second, we propose a novel consistency restoration procedure that exploits incremental pattern matching techniques to address the intermediate steps of consistency restoration in a simplified manner. Furthermore, we present a TGG tool that implements our formal results and experimentally evaluate its scalability in real-world consistency scenarios. Finally, we report on an industrial project from the mechanical engineering domain where we applied this tool for maintaining consistency between computer-aided design and mechatronic simulation models.

In modern, computer-aided engineering processes, restoring and maintaining the consistency of multiple, related artefacts is an important challenge. This is especially the case in multi-disciplinary domains such as manufacturing engineering, where complex systems are described using multiple artefacts that are concurrently manipulated by domain experts, each with their own established tools. Bidirectional languages address this challenge of consistency maintenance by supporting incremental change propagation with a clear and precise semantics. Triple Graph Grammars (TGGs) are a prominent rule-based and declarative bidirectional model transformation language with various implementations, and a solid formal foundation based on algebraic graph transformations. Although TGGs are well suited for synchronizing models that are already on an appropriate, high-level of abstraction, practical model synchronization chains typically require handling models on different levels of abstraction. This poses additional challenges including: (i) handling massive information loss typically incurred when abstracting from a low-level model to a high-level model, (ii) supporting complex attribute manipulation as low-level models are often simple trees extracted from textual or XML-files, with relevant information encoded in attribute values rather than structural relations, and (iii) enabling arbitrary structural constraints to cope with complex, often recursive structural context relations, which are usually not present as explicit links in low-level models. This thesis addresses these challenges by: (1) Establishing a general framework for organizing and structuring model synchronization chains. This framework is applied to an industrial case study in the domain of manufacturing engineering, which is used consequently throughout this thesis to identify requirements, formulate corresponding challenges, and evaluate the contributions of this thesis. (2) Identifying and formalizing new language extensions for TGGs: attribute conditions for complex attribute manipulation in TGG rules, and dynamic conditions for integrating arbitrary structural constraints. To guarantee the maintainability of large TGG specifications, a new modularity concept for TGGs, rule refinement is also introduced. Similar to inheritance and composition for programming languages, rule refinement enables the reuse and flexible combination of TGG rule fragments to form similar TGG rules without introducing redundancy in specifications. (3) Extending an existing TGG-based synchronization algorithm to cover these new features with formal proofs of correctness and completeness (well-behavedness) of derived TGG-based synchronizers. (4) Providing formal construction techniques and static analyses for all properties and restrictions required to guarantee the well-behavedness of derived synchronizers.

In the context of model-driven engineering, models play an important role in everyday life. Models are used to abstract from certain subjects and to describe artifacts and procedures. In software engineering, a system under development is often modeled on different levels of abstraction and from multiple perspectives which results in plenty of models. Moreover, the resulting models depend on each other and the need for automatically translating between related models arises in order to reduce costs, errors, and laborious manual work and to speed-up development processes. The model-driven engineering approach proposes model transformations as a key concept of model-based development which allows to automatically refine and transform models or translate between related models. Especially, bidirectional translators are often required which are able to automatically keep related models in a consistent state. The goal of bidirectional model transformations, which allow to execute transformations defined between a source and target model in both directions, is to assist in such situations. To be able to specify (bidirectional) model transformations the need for (bidirectional) model transformation languages arises. Triple graph grammars (TGGs) are a formally founded bidirectional transformation language based on graph transformations with precisely defined semantics. A TGG specification describes correspondence relationships between two languages and consists of a set of productions that declaratively specify the simultaneous evolution of both related models. The main advantage of triple graph grammars is the possibility to automatically derive bidirectionally working forward and backward translators from a TGG specification that fulfill the fundamental properties efficiency and compatibility. The grand challenge is to build translators that are efficient on the one hand and are compatible with respect to the TGG specification on the other hand. Compatibility means that translators are correct and complete with respect to the specification, i.e., pairs of models are in a consistent state after the translation operation and valid models are able to be translated into corresponding models. Moreover, the overall expressiveness of the triple graph grammar language has to be increased in order to create usable transformation specifications. But, it has to be ensured that derived translators still fulfill the fundamental properties. In this thesis, the expressiveness of triple graph grammars is increased by supporting negative application conditions (NACs) that allow to restrict the applicability of transformation rules, which is required in certain cases. In addition, we accept the challenge of providing an efficiently working translation algorithm that still fulfills the properties correctness and completeness. We extend the expressiveness of triple graph grammars by a precisely defined class of NACs together with a new translation algorithm such that for the first time the fundamental properties of TGG-based translators are still satisfied. The resulting translators nevertheless have a polynomial runtime complexity and, therefore, can be considered efficient. Moreover, they are compatible with their triple graph grammar, which makes these translators usable in practice. In conclusion, the extended triple graph grammar formalism is applicable in real world scenarios, where model transformations are bidirectionally executed to keep related models in a consistent state.