# «Abstract. Model-driven software engineering promotes the use of models and transformations as primary artifacts. Several formalisms can be used for ...»

On the Use of Graph Transformations

for Model Refactoring

Tom Mens1

Service de Génie Logiciel

Université de Mons-Hainaut, Belgium

tom.mens@umh.ac.be

http://w3.umh.ac.be/genlog

Abstract. Model-driven software engineering promotes the use of models and

transformations as primary artifacts. Several formalisms can be used for the spec-

iﬁcation of model transformations. In this tutorial, we introduce and discuss such

a formalism that is based on graphs and graph transformations. In particular, we focus on the activity of model refactoring, and show how graph transformation can provide formal support for this activity. We also show how such support can be implemented in state-of-the-art graph transformation tools such as AGG and Fujaba.

1 Introduction Model-driven engineering is a software engineering approach that promotes the usage of models and transformations as primary artifacts. Its goal is to tackle the problem of developing, maintaining and evolving complex software systems by raising the level of abstraction from source code to models. As such, model-driven engineering promises reuse at the domain level, increasing the overall software quality. Model transformation is the heart and soul of this approach [1].

Graph transformation seems to be a suitable technology and associated formalism

**to specify and apply model transformations for the following reasons:**

– Graphs are a natural representation of models that are intrinsically graph-based in nature (e.g., statecharts, activity diagrams, collaboration diagrams, class diagrams, Petri nets), as opposed to source code for which a tree-based approach is likely to be more appropriate. In Bézivin’s tutorial on model-driven engineering [2], this link between models and graphs is explained as follows: “... we will give a more limited deﬁnition of a model, in the context of MDE only, as a graph-based structure representing some aspects of a given system and conforming to the deﬁnition of another graph called a metamodel.” – Graph transformation theory provides a formal foundation for the automatic appli- cation of model transformations. As such, one can reason about many interesting formal properties such as conﬂuence, sequential and parallel dependence, and so on.

– Tool support for model-driven development based on graph transformation engines is starting to emerge (e.g., GReAT [3], MOLA [4] and VIATRA [5]).

2 T. Mens An important activity within the domain of model transformation is model refac- toring. The term refactoring was originally introduced by Opdyke in his seminal PhD dissertation[6] in the context of object-oriented programming. Martin Fowler [7] denes this activity as ”the process of changing a software system in such a way that it does not alter the external behavior of the code, yet improves its internal structure”.

Recently, research interest has shifted from program refactoring to model refactoring [8,9,10,11,12], which aims to apply refactoring techniques at model level as opposed to source code.

**The objectives of this tutorial are threefold:**

– To introduce the notion of model refactoring as a special kind of model transformation activity, and to motivate the importance of this activity in the MDE process;

– To introduce graph transformation as a promising technique (covering both theoretical foundations and tool support) for software transformation;

– To show how graph transformation can provide formal support to automate the activity of model refactoring, and to compare graph transformation to related approaches.

The rest of this tutorial is structured as follows. Section 2 provides a high-level overview of model transformation and model refactoring, and introduces the necessary terminology. Section 3 introduces some theory on graph transformation. Section 4 discusses and compares AGG [13] and Fujaba [14,15], two general-purpose graph transformation tools, and shows how these tools can be used to implement support for model refactoring. Finally, section 7 concludes.

2 Model transformation The aim of this section is to give a general high-level overview of model transformation, and to show where model refactoring ﬁts in. In order to do this, it is important to be aware of the fact that model refactoring represents only a very speciﬁc kind of model transformation. To illustrate this, we brieﬂy discuss a taxonomy of model transformation in the ﬁrst subsection.

2.1 Taxonomy [16] presented a detailed taxonomy of model transformation and showed how it could be applied to graph transformation. We will summarise some important ideas of the model transformation taxonomy here. Applying graph transformations to model transformation in general, however, is outside the scope of this paper.

In order to transform models, these models need to be expressed in some modeling language, the syntax of which is expressed by a metamodel. Based on the metamodels that are used for expressing the source and target models of a transformation, a distinction can be made between endogenous and exogenous transformations. Endogenous transformations are transformations between models expressed in the same metamodel.

Exogenous transformations are transformations between models expressed in different metamodels. A typical example of an exogenous transformation is migration of a model Graph transformations for model refactoring 3 a program written in one particular language to another one. A typical example of an endogenous transformation is refactoring, where the internal structure of a model is improved (with respect to a certain software quality characteristic) without changing its observable behaviour [7].

Besides this distinction between endogenous and exogenous model transformations, we can also distinguish horizontal and vertical model transformations. A horizontal transformation is a transformation where the source and target models reside at the same abstraction level. A typical examples is again refactoring (an endogenous transformation). A vertical transformation is a transformation where the source and target models reside at different abstraction levels. A typical example of a vertical transformation is synthesis of a higher-level, more abstract, speciﬁcation (e.g., a UML design model) into a lower-level, more concrete, one (e.g, a Java program).

Table 1 illustrates that the dimensions horizontal versus vertical and endogenous versus exogenous are truly orthogonal, by giving a concrete example of all possible combinations. As a clariﬁcation for the Formal reﬁnement mentioned in the table, a speciﬁcation in ﬁrst-order predicate logic or set theory can be gradually reﬁned such that the end result uses exactly the same language as the original speciﬁcation (e.g., by adding more axioms).

Table 1. Orthogonal dimensions of model transformations

Exercise 1. Identify some other types of model transformation (besides the four mentioned in Table 1) and classify them according to the taxonomy presented above.

2.2 Model refactoring An emerging research trend is to port the idea of refactoring to the modeling level, for example by applying refactoring techniques to UML models [8,9,10].

Boger et al. developed a refactoring browser integrated with a UML modeling tool [9]. It supports refactoring of class diagrams, statechart diagrams, and activity diagrams.

For each of these diagrams, the user can apply refactorings that cannot easily or naturally be expressed in other diagrams or in the source code.

Sunyé et al. formally deﬁned some statechart refactorings using OCL pre- and postconditions [8]. Similarly, Van Gorp et al. propose a UML extension to express the preand postconditions of source code refactorings using OCL [10]. The proposed extension allows an OCL empowered CASE tool to verify nontrivial pre and postconditions, to compose sequences of refactorings, and to use the OCL query engine to detect bad code smells. Such an approach is desirable as a way to refactor designs independent of 4 T. Mens the underlying programming language. Correa and Werner built further on these ideas, and implemented the refactorings in OCL-script, an extension of OCL [17].

An alternative approach is followed by Porres [18], who implements model refactorings as rule-based update transformations in SMW, a scripting language based on Python.

Zhang et al. developed a model transformation engine that integrates a model refactoring browser that automates and customises various refactoring methods for either generic models or domain-speciﬁc models [12].

Exercise 2. For each type of UML diagram you are familar with, try to come up with one or more examples of a model refactoring, i.e., a transformation that improves the structure of a UML model yet preserves its behaviour.

In the remainder of this tutorial, we will mainly restrict ourselves to model refactoring of UML class diagrams for various reasons. However, most of the ideas explained in this tutorial are directly applicable to refactorings of other kinds of models as well.

Even domain-speciﬁc models and non-UML-compliant models (e.g. database schemas in ER notation) can be targeted. The primary restriction is that the models have to be expressible in a diagrammatic, graph-like notation.

**2.3 Model consistency**

Another crucial aspect of model transformation, and model refactoring in particular, is model consistency. It will not be treated in this tutorial, but we brieﬂy mention some relevant related work here.

Spanoudakis and Zisman [19] provided an excellent survey on inconsistency management in software engineering. According to them, an inconsistency is “a state in which two or more overlapping elements of different software models make assertions about aspects of the system they describe which are not jointly satisﬁable". They claim that the following activities are essential for inconsistency management: detection of overlaps, detection of inconsistencies, diagnosis of inconsistencies, handling of inconsistencies, tracking, speciﬁcation and application of an inconsistency management policy.

Since a UML model is typically composed of many different diagrams, the consistency between all these diagrams needs to maintained when any of them evolves. Sunyé et al. explored how the integrity of class diagrams and statecharts could be maintained after refactorings [8]. Van Der Straeten et al. explored the use of description logics as a way to specify and implement consistency rules and behaviour preservation rules [20,11].

Exercise 3. Give some examples of consistency problems that can occur in a UML model consisting of different kinds of UML diagrams. Consider only class diagrams, state transition diagrams (describing the internal behaviour of a class) and sequence diagrams (describing the message interations between class instances). Inconsistencies between these diagrams can arise when any of these diagrams is modiﬁed.

Graph transformations for model refactoring 5 The problem of consistency maintenance becomes even more problematic when we acknowledge the obvious fact that models are only an intermediate step in the software development life-cycle, where the actual executable program is the most important deliverable. In this context, consistency should be maintained between the modeling level and the implementation level. Modiﬁcations to the models should be automatically reected in the source code and vice versa. Again, this is a far from trivial problem that is outside the scope of this paper.

Exercise 4. Give an example of a consistency problem that can arise between UML design models and their generated source code when a small change is made to either the design models or the source code.

If you have a CASE tool available that allows you to generate programs from UML models, or to extract UML models from source code, verify whether this consistency problem is addressed by the CASE tool.

**3 Graph transformation theory**

Since the aim of this tutorial is to study the use of graph transformation for the purpose of model refactoring, in this section we will introduce the necessary theory and terminology about graph transformation. In Section 4 we will try to put this theory into practice by using two concrete graph transformation tools, AGG and Fujaba.

**3.1 Introduction**

Graph transformation theory has been developed over the last three decades as a suite of techniques and tools for formal modeling and very high-level visual programming.

Graph transformations can typically be found in two ﬂavours: graph grammars and graph rewriting.

Graph grammars are the natural extension of Chomsky’s generative string grammars into the domain of graphs. Production rules for (string-) grammars are generalized into production rules on graphs, which generatively enumerate all the sentences (i.e., the “graphs”) of a graph grammar. Similarly, string rewriting can be generalized into graph rewriting. A string rewriting consists of a pattern and a replacement string. The pattern is matched against an input string, and the matched substring is replaced with the replacement string of the rule. In analogy, a graph rewriting consists of a pattern graph and a replacement graph. The application of a graph rewriting rule matches the pattern graph in an input graph, and replaces the matched subgraph with the replacement graph.

Many tools, even full-ﬂedged programming environments (e.g., AGG [13] and Fujaba [15]), have been developed that illustrate the practical applicability of the graph transformation approach. These environments have demonstrated that (1) complex transformations can be expressed in the form of rewriting rules, and (2) graph rewriting rules can be compiled into efﬁcient code. In recent years, a number of model transformation tools have emerged that use graph transformation as an underlying transformation engine. Concrete examples are GReAT [3], MOLA [4] and VIATRA [5]).

6 T. Mens

**3.2 Graphs**

According to Bézivin and many others, a model can naturally be represented as a graphbased structure. Figure 1 clariﬁes this idea, and shows the correspondence between models and their graph representation. In this subsection, we will formally deﬁne the notions of graph and type graph, as well as how they are related.