Applying traceability and cloning techniques to compose input-destructive model transformations into an input-preserving chain

1st Workshop on Composition and Evolution of Model Transformations, September 30, 2011, King's College, London, UK

Pieter Van Gorp

Abstract: Special purpose translation algorithms have been developed for mature modeling languages and formalisms. It is desirable to reuse these algorithms when developing translations for new modeling languages. When reusing transformation algorithms that destroy the input model while producing the output model, special techniques are needed for the development of the composite transformation. This paper discusses two previously unpublished techniques that we have applied for reusing an input-destructive translation from petri-nets to statecharts when realizing a new translation from activity diagrams to statecharts.

1  Introduction

Recent years have seen a rise of interest in object- and data-centric modeling approaches for business processes [5]. The promise of these new modeling approaches is that they are more flexible than traditional (process-oriented) information systems. Our interest is in integrating the object- and process-oriented modeling approaches by providing transformations for translating from one modeling style to the other one. Recently, we have investigated for example how executable object lifecycles (expressed as statecharts) can be derived automatically from conceptual process models (expressed as UML activity diagrams) [1]. We have realized the supportive model transformation as a composition of three more primitive transformations: in a first step, nodes that are not relevant for the object life cycle are pruned from the process model. Secondly, the remaining activity diagram elements are mapped to a petri-net elements. Finally, these petri-net elements are mapped to statechart elements.

The implementation of this modular transformation chain is non-trivial since two of its subtransformations are input-destructive (i.e., while producing target domain elements, the transformations destroy at least part of the input model). Since we aimed at providing a transformation chain that preserved the input-model and that even provided traceability links from activity diagram elements to statechart elements, we had to apply special transformation techniques.

Input-destructive transformations are common in literature: for example, Heckel and Bisztray realize the mapping from UML activity diagrams to CSP also using input-destructive transformation rules [8]. Clearly, it is desirable to have reuse mechanisms for input-destructive transformations in general. Therefore, this paper describes the key lessons that can be learned from our example.

The remainder of this paper is structured as follows: Section 2 introduces the transformation from petri-nets to statecharts (i.e., PN2SC) that we aim to reuse. Section 3 introduces the transformation from activity diagrams to statecharts (i.e., AD2SC) that reuses the first transformation. Section 4 describes the techniques that we have applied for realizing the composition without intrusively changing the definition of the reused transformation.

2  Input-destructive transformation: PN2SC

Figure 1: Petri-net and statechart models for an insurance handling claim process.

Fig. 1 shows the input and output model of the example petri-net to statechart transformation for a simple insurance claim process1. The petri-net is shown at the top of the figure and illustrates that such models are flat: the elements that represent the process activities are never embedded into each other. The statechart example is shown at the bottom of the figure and illustrates that such models are hierarchical: both the damage checked and the policy checked states are part of subprocess lanes that are visually embedded in a so-called AND node. A discussion of the advantages of hierarchical models are outside the scope of this paper and can be found among others in [1]. Instead, this paper focusses on the input-destructive nature of the transformation and on the reuse of the rules that define the transformation implementation. Fig. 2 illustrates the input-destructive nature of the transformation: The figure shows 12 rows, each of which represents a transformation step. On the left side, the input petri-net elements are shown whereas on the right side, the output statechart elements are shown. In the first step, all petri-net elements are mapped to direct counter-parts in the statechart domain. Although hidden from Fig. 2 for the sake of readability, this step also involves generating traceability links between related elements.

The subsequent 11 steps introduce hierarchy in an iterative manner. Without elaborating to the details of the underlying rule applications it is clear from the figure that the input petri-net is destroyed gradually as the output statechart is being constructed. This so-called reduction approach is also applied for process model analysis [6] and has the advantage here that it combines property checking with model transformation: if the input petri-net can be reduced to exactly one element, then the output model is guaranteed to satisfy the constraints of the statechart syntax.

Remark that the statechart model shown at the bottom right of Fig. 2 requires some rather straightforward post-processing: the black bars (so-called hyper-edges) need to be removed and their edges need to be redirected accordingly. Moreover, initial and final states need to be added in the two concurrent lanes of the hierarchical AND node. Finally, decision and merge node need to be made explicit. These post-processing tasks are handled by separate steps in the overall PN2SC transformation [7].

Figure 2: Execution trace for an application of the PN2SC transformation that illustrates the input-destructive nature.

3  Composite transformation that reuses PN2SC: AD2SC

The transformation from Sect. 2 (i.e., PN2SC) can be reused for the development of a transformation of activity diagrams to statecharts (i.e., AD2SC). In this section we illustrate the input/output behavior of this extended transformation by means of our running example (i.e., the insurance claim process).

Figure 3: Activity diagram input corresponding to the models from Fig. 1.

Fig. 3 shows a UML activity diagram for which the extended transformation would yield again the statechart from our running example. Remark that the activity diagram is more than just another representation of the control flow information from the previously shown petri-net and statechart models: besides encoding the lifecycle of the underlying data, the activity diagram also incorporates workflow tasks that are unrelated to the underlying data. For example, the task update client contribution is unrelated to the lifecycle of the underlying insurance claim data. Therefore, it should not be reflected in the statechart that synthesizes the lifecycle of claim objects.

Figure 4: Application of rules for pruning object lifecycle-unrelated nodes.

Fig. 4 shows a fragment from the first part of an execution trace for the extended transformation. The fragment illustrates that besides the reused PN2SC part, also other parts of the AD2SC transformation are input-destructive. The fragment shows that the parts of the input activity diagram are changed in two steps: first, the object lifecycle related nodes are integrated in the overall flow. Secondly, the nodes that do not relate to the object lifecycle are pruned from the activity diagram. Together, these steps destroy the input activity diagram.

The composite AD2SC transformation thus consists of the following steps:

  1. apply an input-destructive transformation on the input activity diagram to prune irrelevant nodes without breaking the overall flow of events,
  2. translate activity diagram elements into petri-net elements,
  3. apply the translation from petri-nets to statecharts (PN2SC from Sect. 2).

Note that in the second step, traceability links are generated between activity diagram elements and their corresponding petri-net elements.

4  Composition Details: composing traceability links and creating intermediate copies when needed

The transformation chain under consideration raises two general challenges that are interesting from a transformation reuse perspective:

  1. “How can a composite transformation support traceability across the complete transformation chain when intermediate models are destroyed during the transformation process?”.
  2. “How can a composite transformation preserve the complete input activity diagram even if intermediate models are destroyed during the transformation process?”

Remark that since the goal is transformation composition, it is clearly not appropriate to tackle these challenges by intrusively changing the transformations that are reused. In the context of AD2SC, we have tackled the two challenges by respectively:

  1. composing traceability links right after the creation of statechart elements and right before the destructive reduction process on these elements, and
  2. creating a clone of the input activity diagram right before starting the input-destructive pruning process on this input model.

Note that the first challenge could also be resolved by cloning the intermediate petri-net (i.e., both challenges could be resolved using the second technique only). In that case, transformation users would have to navigate however from activity diagram elements to statechart elements by explicitly hopping over the cloned petri-net elements. Since this is arguably too white-box, we have applied the trace composition technique as a solution to the first challenge.

Both techniques are to some extent independent of the supportive transformation language or tool. However, in the following we illustrate that the first techniques is especially well supported by graph transformation languages and tools. Conversely, we illustrate that the second technique is not so well supported by graph transformation approaches. Dedicated model transformation approaches such as ATL [4] or ETL [3] support the technique better.

4.1  Composition of traceability links using graph transformation

Fig. 2 shows the transformation execution of PN2SC. The first row in that figure shows how initially all petri-net elements are mapped to statechart elements without caring yet about hierarchy. Right after that step (i.e., still before the second step shown on Fig. 1), the input petri-net is still intact. Moreover, the PN2SC transformation has provided at this point traceability links between the corresponding elements. In the context of the composite AD2SC transformation this is the only point at which traceability links can be composed. In the following, we elaborate on that point.

Figure 5: One match of graph transformation rule MergeLinks.

Fig. 5 shows in more detail which elements need to be connected for realizing traceability link composition for our running example. The figure shows all models at the aforementioned breakpoint but for the sake of readability it only shows the traceability links for one process element. The input activity diagram is shown at the top of the figure and the statechart is displayed at the bottom while the petri-net is shown in the middle. The dashed arrows represent the traceability links that have been generated by the subtransformations. The composite transformation should find such patterns and then establish composite link from the element labeled as src to the element labeled as trg. The following code fragment shows how we have implemented this behavior concisely as a graph transformation rule using the GrGen.NET platform [2]:

1 rule MergeLinks { 2 src:Node -:AD2PN-> . -:PN2SC-> trg:Node; // this is matching part of the GT rule 3 modify { 4 src -newCompositeLink:AD2SC-> trg; // this is the rewrite part of the GT rule 5 } 6 }
Figure 6: Code fragment of the graph transformation rule implementation.

Line 2 of Fig. 6 defines a pattern consisting of a node src in the activity diagram domain, a node trg in the statechart domain and a path with two traceability links between these nodes. Line 4 of Fig. 6 specifies how such patterns should be rewritten: a new traceability link (of type AD2SC) should be created between the matched src and trg elements. Besides these 6 lines of code for defining the extra rule, one line of code is needed to call this rule at the right time in the transformation script. We conclude that the graph transformation support the implementation of traceability link composition very well. The experienced reader may notice that model transformation languages like ATL and ETL do not provide a comparable declarative pattern specification mechanisms but a detailed comparison is outside the scope of this paper.

4.2  Cloning the activity diagram before the pruning steps

The activity diagram shown at the top of Fig. 5 is in fact the input activity diagram that has been manipulated directly by the pruning rules (cfr., Fig. 4). Besides these pruning rules, no other subtransformations further manipulate this activity diagram. Therefore, at the end of the composite transformation, at least a part of the input model is still available. The composed traceability links (cfr., the previous subsection) can therefore be traversed from all elements shown at the top of Fig. 5. To preserve the complete input model across the composite transformation process, we need to clone it at the start of that process.

Unfortunately, this technique exposes a technical limitation of the graph transformation approach that we have adopted so far: unless we provide special annotations on the activity diagram clone, the cloned elements will also be processed by subsequent steps in the transformation chain. Note again that in the context of transformation composition (and modular transformation design in general), it is clearly undesirable that the definitions of the subsequent subtransformations need to be extended with constraints that are specific to this transformation chain. Nonetheless, the definitions of the graph transformation rules of the reused PN2SC will have to be made more specific than their original version. Consider for example the following original version of a PN2SC rule:

1 rule trans_place { 2 p:Place; // match any Place element p in the host graph 3 modify { 4 p-tracelink:PN2SC->s:BasicState; // map p to its statechart counter-part s and add a link 5 p-tracelink2:PN2SC->lane:OrState-:Contains->s; // embed s in a lane and again add a link 6 eval { 7 =; // give s the name of p 8 } 9 } 10 }
Figure 7: Rule for mapping petri-net Place elements to statechart elements.

The rule definition clearly demonstrates that in the graph transformation approach, elements from different models are part of one large graph. When applying a rule such as the one shown on Fig. 7 on a host graph where the input model has been cloned one or more times, it will generate undesirably many output models correspondingly. Fortunately, this obstacle can be overcome: for example, one can create auxiliary nodes in the graph for representing the distinct models. Additionally, one then creates edges between the nodes representing the models and the nodes representing their owned model elements. Unfortunately, this will result in somewhat more verbose metamodel and rule definitions. This problem has been overcome in dedicated model transformation approaches such as ATL and ETL, since these approaches have dedicated scoping mechanisms.

5  Conclusions and Recommendations for Future Research

This paper demonstrates how two techniques enable the composition of input-destructive transformations into input-preserving transformation chains with traceability support: (1) composing traceability links based on the traceability links of the reused transformations and (2) creating intermediate copies of the input models of the subtransformations. We have evaluated how graph transformation approaches support these techniques by considering a complex transformation chain from the process modeling domain. The former technique is supported particularly well while the second technique reveals a point for improvement. Graph transformation languages should be extended with a dedicated mechanism for restricting the scope of a transformation to a specific model.


R. Eshuis and P. Van Gorp. Synthesising object life cycles from business process models. Submitted for publication.
E. Jakumeit, S. Buchwald, and M. Kroll. GrGen.NET. International Journal on Software Tools for Technology Transfer (STTT), 12(3):263–271, July 2010.
F. Jouault, F. Allilaire, J. Bézivin, and I. Kurtev. ATL: A model transformation tool. Science of Computer Programming, 72(1-2):31 – 39, 2008. Special Issue on Second issue of experimental software and toolkits (EST).
D. Kolovos, R. Paige, and F. Polack. The epsilon transformation language. In A. Vallecillo, J. Gray, and A. Pierantonio, editors, Theory and Practice of Model Transformations, volume 5063 of Lecture Notes in Computer Science, pages 46–60. Springer Berlin / Heidelberg, 2008.
D. Müller, M. Reichert, and J. Herbst. A new paradigm for the enactment and dynamic adaptation of data-driven process structures. In Proceedings of the 20th international conference on Advanced Information Systems Engineering, CAiSE ’08, pages 48–63, Berlin, Heidelberg, 2008. Springer-Verlag.
W. Sadiq and M. E. Orlowska. Analyzing process models using graph reduction techniques. Inf. Syst., 25:117–134, April 2000.
P. Van Gorp and R. Eshuis. Transforming process models: executable rewrite rules versus a formalized java program. In Proceedings of the 13th international conference on Model driven engineering languages and systems: Part II, MODELS’10, pages 258–272, Berlin, Heidelberg, 2010. Springer-Verlag.
D. Varró, M. Asztalos, D. Bisztray, A. Boronat, D.-H. Dang, R. Geiß, J. Greenyer, P. Van Gorp, O. Kniemeyer, A. Narayanan, E. Rencis, and E. Weinell. Applications of graph transformations with industrial relevance. chapter Transformation of UML Models to CSP: A Case Study for Graph Transformation Tools, pages 540–565. Springer-Verlag, Berlin, Heidelberg, 2008.

All images in this electronic paper are zoomable without quality loss and all case study artifacts (transformation platform, tranformation definitions, example models, etc.) are available on

This document was translated from LATEX by HEVEA.