Termination of High-Level Replacement Units with Application to Model Transformation

Visual rewriting techniques, in particular graph transformations, are increasingly used to model transformations of systems specified through diagrammatic sentences. Several rewriting models have been proposed, differing in the expressivity of the types of rules and in the complexity of the rewriting mechanism; yet basic results concerning the formal properties of these models are still missing for many of them. In this paper, we propose a contribution towards solving the termination problem for rewriting systems with external control mechanisms. In particular, we obtain results of more general validity by extending the concept of transformation unit to high-level replacement systems, a generalization of graph transformation systems. For high-level replacement units, we state and prove several abstract properties based on termination criteria. Then, we instantiate the high-level replacement systems by attributed graph transformation systems and present concrete termination criteria. These are used to show the termination of some replacement units needed to express model transformations as a consequence of software refactoring.     

Formal foundation of consistent EMF model transformations by algebraic graph transformation

Model transformation is one of the key activities in model-driven software development. An increasingly popular technology to define modeling languages is provided by the Eclipse Modeling Framework (EMF). Several EMF model transformation approaches have been developed, focusing on different transformation aspects. To validate model transformations with respect to functional behavior and correctness, a formal foundation is needed. In this paper, we define consistent EMF model transformations as a restricted class of typed graph transformations using node type inheritance. Containment constraints of EMF model transformations are translated to a special kind of graph transformation rules such that their application leads to consistent transformation results only. Thus, consistent EMF model transformations behave like algebraic graph transformations and the rich theory of algebraic graph transformation can be applied to these EMF model transformations to show functional behavior and correctness. Furthermore, we propose parallel graph transformation as a suitable framework for modeling EMF model transformations with multi-object structures. Rules extended by multi-object structures can specify a flexible number of recurring structures. The actual number of recurring structures is dependent on the application context of such a rule. We illustrate our approach by selected refactorings of simplified statechart models. Finally, we discuss the implementation of our concepts in a tool environment for EMF model transformations.     

High-level replacement units and their termination properties

Visual rewriting techniques, in particular graph transformations, are increasingly used to model transformations of systems specified through diagrammatic sentences. Several rewriting models have been proposed, differing in the expressivity of the types of rules and in the complexity of the rewriting mechanism; yet, for many of them, basic results concerning the formal properties of these models are still missing. In this paper, we give a contribution towards solving the termination problem for rewriting systems with external control mechanisms. In particular, we obtain results of more general validity by extending the concept of transformation unit to high-level replacement systems, a generalization of graph transformation systems. For high-level replacement units, we state and prove several abstract properties based on termination criteria. Then, we instantiate the high-level replacement systems by attributed graph transformation systems and present concrete termination criteria. We explore some types of rules and replacement units for which the criterion can be established. These are used to show the termination of some replacement units needed to express model transformations formalizing refactoring.     

Termination Criteria for DPO Transformations with Injective Matches

Reasoning about graph and model transformation systems is an important means to underpin model-driven software engineering, such as Model-Driven Architecture (MDA) and Model Integrated Computing (MIC). Termination criteria for graph and model transformation systems have become a focused area recently. This paper provides termination criteria for graph and model transformation systems with injective matches and finite input structure. It proposes a treatment for infinite sequences of rule applications, and takes attribute conditions, negative application conditions, and type constraints into account. The results are illustrated on case studies excerpted from real-world transformations, which show the termination properties of the frequently used "transitive closure" and "leaf collector" transformation idioms. An intuitive comparison with other approaches is also given.     

An Efficient Solution for Model Checking Graph Transformation Systems

This paper presents an efficient solution for modeling checking graph transformation systems. The approach transforms AGG specifications into Bogor models and supports both attributed typed graphs and layered transformations. Resulting models are amenable to check interesting properties expressed as combinations of LTL (Linear Temporal Logic) and graph transformation rules. The first experimental results are encouraging and show that in most cases our proposal improves existing approaches, both in terms of performance and expressiveness.     

Specification-driven model transformation testing

Testing model transformations poses several challenges, among them the automatic generation of appropriate input test models and the specification of oracle functions. Most approaches for the generation of input models ensure a certain coverage of the source meta-model or the transformation implementation code, whereas oracle functions are frequently defined using query or graph languages. However, these two tasks are usually performed independently regardless of their common purpose, and sometimes, there is a gap between the properties exhibited by the generated input models and those considered by the transformations. Recently, we proposed a formal specification language for the declarative formulation of transformation properties (by means of invariants, pre-, and postconditions) from which we generated partial oracle functions used for transformation testing. Here, we extend the usage of our specification language for the automated generation of input test models by SAT solving. The testing process becomes more intentional because the generated models ensure a certain coverage of the transformation requirements. Moreover, we use the same specification to consistently derive both the input test models and the oracle functions. A set of experiments is presented, aimed at measuring the efficacy of our technique.     

From model transformation to incremental bidirectional model synchronization

The model-driven software development paradigm requires that appropriate model transformations are applicable in different stages of the development process. The transformations have to consistently propagate changes between the different involved models and thus ensure a proper model synchronization. However, most approaches today do not fully support the requirements for model synchronization and focus only on classical one-way batch-oriented transformations. In this paper, we present our approach for an incremental model transformation which supports model synchronization. Our approach employs the visual, formal, and bidirectional transformation technique of triple graph grammars. Using this declarative specification formalism, we focus on the efficient execution of the transformation rules and how to achieve an incremental model transformation for synchronization purposes. We present an evaluation of our approach and demonstrate that due to the speedup for the incremental processing in the average case even larger models can be tackled.

A sound and complete theory of graph transformations for service programming with sessions and pipelines

Graph transformation techniques, the Double-Pushout (DPO) approach in particular, have been successfully applied in the modeling of concurrent systems. In this area, a research thread has addressed the definition of concurrent semantics for process calculi. In this paper, we propose a theory of graph transformations for service programming with sophisticated features such as sessions and pipelines. Through graph representation of CaSPiS, a recently proposed process calculus, we show how graph transformations can cope with advanced features of service-oriented computing, such as several logical notions of scoping together with the interplay between linking and containment. We first exploit a graph algebra and set up a graph model that supports graph transformations in the DPO approach. Then, we show how to represent CaSPiS processes as hierarchical graphs in the graph model and their behaviors as graph transformation rules. Finally, we provide the soundness and completeness results of these rules with respect to the reduction semantics of CaSPiS.     

Change-driven model transformations

In this paper, we investigate change-driven model transformations, a novel class of transformations, which are directly triggered by complex model changes carried out by arbitrary transactions on the model (e.g. editing operation, transformation, etc). After a classification of relevant change scenarios, we identify challenges for change-driven transformations. As the main technical contribution of the current paper, we define an expressive, high-level language for specifying change-driven transformations as an extension of graph patterns and graph transformation rules. This language generalizes previous results on live model transformations by offering trigger events for arbitrarily complex model changes, and dedicated reactions for specific kinds of changes, making this way the concept of change to be a first-class citizen of the transformation language. We discuss how the underlying transformation engine needs to be adapted in order to use the same language uniformly for different change scenarios. The technicalities of our approach will be discussed on a (1) model synchronization case study with non-materialized target models and (2) a case study on detecting the violation of evolutionary (temporal) constraints in the security requirements engineering domain.     

Bridging the gap between formal semantics and implementation of triple graph grammars

The correctness of model transformations is a crucial element for 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 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 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. While 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 and runtime checks can be employed to guarantee these criteria.     

A transformation-based approach to context-aware modelling

Context-aware computing is a paradigm for governing the numerous mobile devices surrounding us. In this computing paradigm, software applications continuously and dynamically adapt to different “contexts” implying different software configurations of such devices. Unfortunately, modelling a context-aware application (CAA) for all possible contexts is only feasible in the simplest of cases. Hence, tool support verifying certain properties is required. In this article, we introduce the CAA model, in which context adaptations are specified explicitly as model transformations. By mapping this model to graphs and graph transformations, we can exploit graph transformation techniques such as critical pair analysis to find contexts for which the resulting application model is ambiguous. We validate our approach by means of an example of a mobile city guide, demonstrating that we can identify subtle context interactions that might go unnoticed otherwise.     

模型转换中特性保持的描述与验证

模型转换主要用于模型的演化、求精以及重构.模型转换需要遵循一定的约束规则以保持模型的某些特性.模型演化通常要求保持已有的接口;模型重构则必须保证重构前后的软件具有相同的外部行为特性.为了严格证明某个模型转换规则是否满足这些约束,特性保持约束必须形式化地加以描述.为了实现证明过程的自动化,需要总结通用的证明过程并给出实现算法.提出了一种基于图转换的特性保持约束描述机制,将模型演化与重构中的转换规则以及特性保持约束都描述为图转换规则.借助图转换的冲突检测机制,给出了严格证明转换规则是否满足特性保持约束的算法.     

Aspect-oriented model-driven skeleton code generation: A graph-based transformation approach

Model-driven code generation has been investigated in traditional and object-oriented design paradigms; significant progress has been made. It offers many advantages including the rapid development of high quality code. Errors are reduced and the consistency between the design and the code is retained, in comparison with a purely manual approach. Here, a model-driven code generation approach based on graph transformations for aspect-oriented development is proposed. The approach has two main transformation activities. The first activity transforms a visual (graphical) model of the design into a formal, text-based notation that can be readily processed. The graphical model is created by the software designer and uses a UML profile for aspect-oriented software (i.e., FDAF) to represent aspects and their components. XML is the target notation for this step; the transformation uses the XML meta-model to ensure that the output complies with the language. The second activity transforms the XML model into AspectJ source code. The transformation uses the AspectJ meta-model to ensure the output complies with the language. The transformations from the extended UML model to XML and from XML to AspectJ code are fully automated. The transformation algorithms are based on graph transformations; tool support has been developed. Key technical issues in the approach are discussed, including performance, the amount of code generated, correctness, and adaptability, in addition to a comparison of the proposal with existing alternative approaches. The approach has been validated on three example systems: a banking system, classroom scheduling system, and an insurance system. The banking system example is presented in the paper.     

Confluence of aspects for sequence diagrams

The last decade has seen several aspect language proposals for UML 2 sequence diagrams. Aspects allow the modeler to define crosscutting concerns of sequence diagrams and to have these woven with the sequence diagrams of a so-called base model, in order to create a woven model. In a real-world scenario, there may be multiple aspects applicable to the same base model. This raises the need to analyse the set of aspects to identify possible aspect interactions (dependencies and conflicts) between applications of aspects. We call a set of aspects terminating if they may not be applied infinitely many times for any given base model. Furthermore, we call a set of terminating aspects confluent, if they, for any given base model, always yield the same final result regardless of the order in which they are applied. Since confluence must hold for any base model, this is a much stronger result than many of the current approaches that have addressed detection of aspect interactions limited to a specific base model. Our aspects are specified using standard sequence diagrams with some extensions. In this paper, we present a confluence theory specialized for our highly expressive aspect language. For the most expressive aspects, we prove that confluence is undecidable. For another class of aspects with considerable expressiveness, we prescribe an algorithm to check confluence. This algorithm is based on what we call an extended critical pair analysis. These results are useful both for modelers and researchers working with sequence diagram aspects and for researchers wanting to establish a confluence theory for other aspect-oriented modelling or model transformation approaches.     

Towards language-to-language transformation

This paper proposes a simplicity-oriented approach and framework for language-to-language transformation of, in particular, graphical languages. Key to simplicity is the decomposition of the transformation specification into sub-rule systems that separately specify purpose-specific aspects. We illustrate this approach by employing a variation of Plotkin’s Structural Operational Semantics (SOS) for pattern-based transformations of typed graphs in order to address the aspect ‘computation’ in a graph rewriting fashion. Key to our approach are two generalizations of Plotkin’s structural rules: the use of graph patterns as the matching concept in the rules, and the introduction of node and edge types. Types do not only allow one to easily distinguish between different kinds of dependencies, like control, data, and priority, but may also be used to define a hierarchical layering structure. The resulting Type-based Structural Operational Semantics (TSOS) supports a well-structured and intuitive specification and realization of semantically involved language-to-language transformations adequate for the generation of purpose-specific views or input formats for certain tools, like, e.g., model checkers. A comparison with the general-purpose transformation frameworks ATL and Groove, illustrates along the educational setting of our graphical WebStory language that TSOS provides quite a flexible format for the definition of a family of purpose-specific transformation languages that are easy to use and come with clear guarantees.

     

Colouring: execution,debug and analysis of QVT-relations transformations through coloured Petri nets

QVT is the standard language sponsored by the OMG to specify model-to-model transformations. It includes three different languages, being QVT-relations (QVT-R) the one with higher-level of abstraction. Unfortunately, there is scarce tool support for it nowadays, with incompatibilities and disagreements between the few tools implementing it, and lacking support for the analysis and verification of transformations. Part of this situation is due to the fact that the standard provides only a semi-formal semantics for QVT-R. In order to alleviate this situation, this paper provides a semantics for QVT-R through its compilation into coloured Petri nets. The theory of coloured Petri nets provides useful techniques to analyse transformations (e.g. detecting relation conflicts, or checking whether certain structures are generated or not in the target model) as well as to determine their confluence and termination given a starting model. Our semantics is flexible enough to permit the use of QVT-R specifications not only for transformation and check-only scenarios, but also for model matching and model comparison, not covered in the original standard. As a proof of concept, we report on the use of CPNTools for the execution, debugging, verification and validation of transformations, and on a tool chain (named Colouring) to transform QVT-R specifications and their input models into the input format of CPNTools, as well as to export and visualize the transformation results back as models.     

Reusable model transformations

Model transformations written for an input metamodel may often apply to other metamodels that share similar concepts. For example, a transformation written to refactor Java models can be applicable to refactoring UML class diagrams as both languages share concepts such as classes, methods, attributes, and inheritance. Deriving motivation from this example, we present an approach to make model transformations reusable such that they function correctly across several similar metamodels. Our approach relies on these principal steps: (1) We analyze a transformation to obtain an effective subset of used concepts. We prune the input metamodel of the transformation to obtain an effective input metamodel containing the effective subset. The effective input metamodel represents the true input domain of transformation. (2) We adapt a target input metamodel by weaving it with aspects such as properties derived from the effective input metamodel. This adaptation makes the target metamodel a subtype of the effective input metamodel. The subtype property ensures that the transformation can process models conforming to the target input metamodel without any change in the transformation itself. We validate our approach by adapting well known refactoring transformations (Encapsulate Field, Move Method, and Pull Up Method) written for an in-house domain-specific modeling language (DSML) to three different industry standard metamodels (Java, MOF, and UML).     

Assessing and improving quality of QVTo model transformations

We investigate quality improvement in QVT operational mappings (QVTo) model transformations, one of the languages defined in the OMG standard on model-to-model transformations. Two research questions are addressed. First, how can we assess quality of QVTo model transformations? Second, how can we develop higher-quality QVTo transformations? To address the first question, we utilize a bottom–up approach, starting with a broad exploratory study including QVTo expert interviews, a review of existing material, and introspection. We then formalize QVTo transformation quality into a QVTo quality model. The quality model is validated through a survey of a broader group of QVTo developers. We find that although many quality properties recognized as important for QVTo do have counterparts in general purpose languages, a number of them are specific to QVTo or model transformation languages. To address the second research question, we leverage the quality model to identify developer support tooling for QVTo. We then implemented and evaluated one of the tools, namely a code test coverage tool. In designing the tool, code coverage criteria for QVTo model transformations are also identified. The primary contributions of this paper are a QVTo quality model relevant to QVTo practitioners and an open-source code coverage tool already usable by QVTo transformation developers. Secondary contributions are a bottom–up approach to building a quality model, a validation approach leveraging developer perceptions to evaluate quality properties, code test coverage criteria for QVTo, and numerous directions for future research and tooling related to QVTo quality.     

Grammar-based model transformations: Definition,execution, and quality properties

Model transformation is a key concept in model-driven software engineering. The definition of model transformations is usually based on meta-models describing the abstract syntax of languages. While meta-models are thereby able to abstract from superfluous details of concrete syntax, they often loose structural information inherent in languages, like information on model elements always occurring together in particular shapes. As a consequence, model transformations cannot naturally re-use language structures, thus leading to unnecessary complexity in their development as well as in quality assurance.In this paper, we propose a new approach to model transformation development which allows to simplify the developed transformations and improve their quality via the exploitation of the languages׳ structures. The approach is based on context-free graph grammars and transformations defined by pairing productions of source and target grammars. We show that such transformations have important properties: they terminate and are sound, complete, and deterministic.     

Specifying behavioral semantics of UML diagrams through graph transformations

The Unified Modeling Language (UML) has been widely accepted as a standard for modeling software systems from various perspectives. The intuitive notations of UML diagrams greatly improve the communication among developers. However, the lack of a formal semantics makes it difficult to automate analysis and verification. This paper offers a graphical yet formal approach to specifying the behavioral semantics of statechart diagrams using graph transformation techniques. It supports many advanced features of statecharts, such as composite states, firing priority, history, junction, and choice. In our approach, a graph grammar is derived automatically from a state machine to summarize the hierarchy of states. Based on the graph grammar, the execution of a set of non-conflict state transitions is interpreted by a sequence of graph transformations. This facilitates verifying a design model against system requirements. To demonstrate our approach, we present a case study on a toll-gate system.