-Model-Driven Engineering (MDE) promises an increase in the maintainability and extensibility of modern software systems. Furthermore, it encourages the usage of multiple models of the same system to simplify the involvement of different stakeholders, tools, and domains. The concurrent engineering of such multiple models requires, however, support for consistency management including consistency restoration and consistency checking of and between existing models. Bidirectional transformation (bx) approaches are able to address these challenges with various paradigms that come along with different dis/advantages. Rule-based techniques, as one of these paradigms, provide a declarative approach to implementing such consistency management solutions. However, rule-based approaches rely on finding an appropriate sequence of rule applications, e.g., such that the transformation process does not lead to a dead-end. In case of a wrong choice of rule applications, backtracking (of arbitrary depth) is in general not a satisfactory solution as it has exponential runtime in the number of rule applications. We, therefore, propose a novel look-ahead strategy for rulebased bx approaches that governs the rule application process by generating additional application conditions based on the current and possible future state of relevant edges in the model. We demonstrate and evaluate our approach on a compact yet nontrivial scenario that requires careful decision making among rule applications.
Model-Driven Engineering (MDE) has become an
important technique to cope with the increasing complexity
of modern software systems. Its consequent use is said to
improve both the quality of developed software as well as
the effectiveness of the development process. However, as
a software system evolves and becomes more complex, so
do the underlying models that represent different views onto
the system. While each view has its own characteristics
and priorities, they normally share information that may
be altered and changed such that it no longer complies
with other related models. To cope with these changes and
keep those related models consistent to each other is of
particular interest for an integrated development process.
Hence, tools are needed that analyse models for compliance
with their correlated counterparts and, in case consistency
has been violated, are able to transform the models into
an updated consistent version without incurring unintended
loss of information. As different models are maintained by
different stakeholders, model transformations often have
to be ”bidirectional”, i.e., executable in either direction.
In general, a pair of transformations in reverse directions
(usually referred to as forward and backward transformations)
as well as consistency checking between two given models
are needed to tackle consistency challenges in an MDE
landscape. These tasks are addressed by bidirectional model
transformation (bx) approaches. Bx implementations can
be categorized into three paradigms, namely, bidirectional
programming languages (e.g., BiGUL [
The rest of the paper is organized as follows: In Chapter II we will introduce our running example and TGGs. Chapter III introduces a novel look-ahead strategy that brings a minor overhead for forward (and analogously backward) transformations for the sake of more reliable transformations. In case of more rule application-intensive tasks such as consistency checking, the strategy even yields a substantial performance gain by reducing the search space of rule applications. In Chapter IV we present the results of our approach with respect to success rates and performance. Subsequently, in Chapter V we will discuss related work. Finally, in the last chapter we will summarize the results and give an overview over future work.
Our running example is depicted in Figure 1. It is
inspired by an example from the example zoo provided
by [
EPackage
Employee :
EClass interface = false
Person :
EClass interface = false Observable :
EClass interface = true
Serializable:
EClass interface = true
Serializable
Observable
Employee
Person
speaking, it is highly beneficial to be able to automatically
extract a meaningful documentation from an existing project
and furthermore, to keep it consistent. It might also make
sense to first define a documentation structure and to extract
an EMF skeleton that conforms to the documentation so that
developers may work more purposively. Last but not least,
for given projects and documentations in ongoing software
projects it is often not clear which parts are still consistent to
each other and which are not. To discover (in-)consistencies
and return a valid mapping, that covers as many elements
of both sides as possible, is sometimes crucial when the
alternative would be to start the documentation from scratch.
These scenarios may be handled by bx approaches in general;
however, we will focus on Triple Graph Grammars (TGGs)
as our tool of choice which is a rule-based bx technique.
TGGs [
++ :P2F :P2F
++ :P2F ++ ++:Folder one EClass. In contrast, R5 also defines correspondence for an inherits link but together with the EClass from which it origins. In summary, we demand that generalization can only be translated once together with the originating node. Furthermore, we allow multiple realizations as long as the targeted EClass is an interface.
A TGG is a consistency specification for which operations such as forward and backward transformations or even consistency checks can be derived. This means that in order to perform those operations, we have to operationalize the TGG rules first. In the following we will explain how to operationalize TGG rules to perform forward transformations; backward transformations are handled analogously. For a forward transformation, the source side is given as an input model and the target side is to be derived. Hence, in contrast to model generation, we do not create new elements on the source side, but rather mark those elements that have already been translated. This implies that elements on the source side of a TGG rule are all context elements for a forward operationalization. Figure 3 depicts all ”forward rules” for F4: EClass-To-Doc Rule marked by ’++’, define which structural features are to be created in conformance to the pattern in case that the pre-requisite of the pattern is fulfilled. A major goal of defining patterns is to find matches, where a match is defined as a valid mapping of pattern elements to model elements. Thus, a match defines an occurrence of the pattern in a model. In the following, we will explain each of the five rules in detail: 1) The first rule R1 is axiomatic, due to the lack of context elements. It does not define any pre-requisites but creates an instance of type EPackage and a corresponding instance of type Folder. This correspondence is expressed as an instance of type E2F which is visualized by a hexagon and connects both of EPackage with Folder. 2) Given an existing correspondence between elements as defined in R1, R2 creates a sub-EPackage with a corresponding sub-Folder under the pre-requisite that a parent EPackage and Folder have been found previously. 3) The other rules can be read analogously, where R3 creates an inherits link on the source domain and a corresponding realizes link on the target domain if the target EClass of the inherits link is an interface. 4) R4 creates an EClass and a corresponding Doc given already processed EPackage and Folder instances. 5) Last but not least, R5 defines that an EClass and an inherits link on source side are created together with a corresponding Doc and a generalizes link on target side, under the condition that the context EClass node is not an interface.
Note that the distinction between R3 and R5 is made due to the EMF specification of EClass that internally describes whether it is an interface or a real class. In Java a class may generalise only one other class which prohibits multiple inheritance using the extends directive. It is, however, possible to mimic multiple inheritance using interfaces and the implements directive which is extensively used by EMF. For this reason R3, in combination with R1, is able to define correspondence of multiple inherits links originating from F5: Inherits-To-Generalization Rule
Fig. 3. EMF To Doc Example: Forward Rules our given TGG. Note that all former created nodes on source side have been converted to context elements. The difference between those elements that are context in the plain TGG rule and those we converted is depicted as marking signs on each node and edge on source side. X indicates that this element has to have a marking which in turn means that it must be already translated. ! X indicates that this rule marks an unmarked element to be translated if it is applied. These forward rules are able to transform a given source model into a corresponding target model in accordance with the original TGG rules.
With the given forward rules this process is not deterministic as is demonstrated in Figure 4. It depicts a source model with two EPackages, namely root and sub where sub is a sub-package of root. Given this model and our forward rules, there are two rule application sequences that are
F1: Package-To-Folder Rule
:EPackage
:EPackage
subpackage
:Folder
subfolder
possible and are depicted at the bottom of the Figure. The
sequence of the left is an application of the axiomatic F1 rule
on both EPackages; however, this results in a state where
the subpackage edge can no longer be translated with any
forward rule. The reason for this is that there are no forward
rules that will enable us to translate the edge after we applied
F1 to sub. The second sequence on the right depicts a
valid rule application sequence that does indeed translate all
elements. It translates both EPackages plus the subpackage
link between them if we apply F1 to root and F2 to sub
and the link. The choice of which rule application sequence to
use is not trivial, but may be solved through backtracking by
revoking former application, if a dead-end has been detected.
However, backtracking can result in exponential runtime in
model size which quickly becomes infeasible [
For forward and backward transformations, the challenge is
how to find a sequence of rule applications that does not lead
to a dead-end where certain elements remain untranslatable.
To cope with this, advanced static analysis techniques [
To prevent this, Herman et al. [
These NACs are called ”filter NACs” as their intention is to filter those rule applications that would otherwise certainly lead the model transformation process into a deadend. An example of this is given in Figure 5. It depicts the F1 rule which is extended by a NAC that prohibits the existence of an incoming subpackage edge for the p1 element, such an edge would always remain untranslated in case that this rule is applied. This solves the previously encountered problem as for now there will never be an F1 match that translates sub leaving the only translating forward rule to be the one that does not lead to a dead-end.
Now, if we extend our example model as depicted in Figure 6, we will very likely encounter a new dead-end case. The example consists of the sub EPackage plus two EClasses in sub, namely Employee and Person. p1:EPackage ++
++ :P2F ++ ++
F1: Package-To-Folder Rule Additionally, Employee inherits from Person. Translating this model requires translating the EPackage first which is handled the same way as before and may be disregarded, which leads us to the translation of both EClasses. Now, we have to use F3, F4 and F5 to translate the remaining elements and the inherits edge between them but, as in the previous example, we may end up in a dead-end depending on which forward rules we apply. A valid rule sequence would be to apply F4 to Person following the application of F5 to Employee and the remaining inherits edge. But, starting with F4 applied to Employee would lead to an untranslated inherits edge as there would never again be any rule able to process the edge. The reason why the previous analysis does not hold in this case is that the F3 rule is theoretically able to translate an inherits edge wherever it originates from. Thus, there won’t be any NAC generated for the F4 rule that would guide the translation process safely. :Folder files Person:Doc
Employee:Doc
Person:Doc generalises Employee:Doc
To rule out these cases we propose a more sophisticated look-ahead strategy which also takes into account that context and attribute constraints might prevent a false ”saving” rule from later application, thus, leaving elements untranslated. The steps are described in the following: 1) Similar to the previous analysis we extend the given rules such that for every created element we search for existing edges that are not translated by this rule. 2) If such an edge does not exist, the rule may be applied directly. 3) However, in case there are such potential edges, the analysis demands that there also exists a valid match of the source1 side of a saving rule. Hence, we demand that after applying this rule, the edge is still translatable in the future. This concept of demanding the existence of a certain pattern C, that extends a match of another pattern P, is called positive application condition (PAC) which intuitively represents an ”if-then” relationship. Figure 7 depicts the approach applied to F4. Analogously to the former analysis, we inspect ec1 as a node whose translation might lead to an untranslated inherits edge. In contrast to the former approach, the possibility that the edge might be translated by F3 no longer suffices. We, thus, demand that in case the inherits with ec2 as target exists, there must also exist a concrete match of the source side of the F3 rule. This ensures that the edge can be translated by F3 in the future, which means that we have a real look-ahead for specific edges to prevent them from not being translatable later on.
In case there are no such saving rules, this approach is equivalent to the former static analysis because the Premise may be true but the Conclusion will always be false. This means that the resulting Premise and Conclusion are reduced to a (filter) NAC forbidding the existence of a certain edge as it would remain untranslatable. Hence, if no saving rules are found, the PAC-based look-ahead strategy falls back to filter NACs. This means, however, that filter NACs are a subset of our new PAC-based look-ahead strategy. The PAC-based look-ahead strategy can also be used to improve the performance of consistency check. As was explained in the previous chapter, consistency checking relies on the discovery of matches of the source and target side of each rule. By applying our strategy on both source and target side, we can filter matches analogously to the forward transformation case. Hence, by decreasing the number of possible matches, we decrease the search space of possible pairings. This, finally, increases the efficiency as the number of possible candidates increases quadratically in the number of matches. The experimental results that support this conclusion are presented in the next chapter.
The implementation of this strategy appears computationally more expensive at a first glance as for every rule which is applied, we have to find also occurrences for those patterns that have been added by the analysis. However, given a closer look specifically at the generated PAC, the matches for all saving rules must have already been collected before, which is in general the bottleneck of rule-based bx tools. Thus, before applying a certain match, we only have to check for the existence of these pre-calculated matches regarding possible saving rules.
There are cases when this analysis does not suffice and the translation process still ends up in a dead-end. Any scenario which requires an analysis of a sequence of future rule applications of length greater than one to avoid a dead-end is not considered here. Handling these scenarios requires a look-ahead greater than one; however, this requires the generation of nested application conditions. For a lookahead of k, a nesting level of k+1 is needed, which is not covered by our implementation that only supports simple application conditions with a Premise and a Conclusion pattern for a look-ahead of one. Nonetheless, the extension to nested application conditions can be handled analogously by generating PACs for every Conclusion.
Another scenario is connected to our assumption that dead-ends in a transformation process correspond to single untranslatable edges. This means that we always identify such cases when there is a possibly untranslatable edge; however, the current implementation may underestimate the rule application sequence needed to translate all adjacent edges. It does not incorporate that there are dependencies between Conclusion patterns (saving rules) where the translation of one remaining edge contradicts the translation of another, yet, untranslated edge.
In the preceding chapter we presented both filter NACs and
our novel PAC-based look-ahead strategy. Both approaches
were shown on a TGG specification based on our running
example. In the following, we will evaluate the new approach
by comparing it to filter NACs and an implementation that
does not use any context analysis techniques. We, therefore,
state three research questions that are investigated with our
experiments: RQ1: For each approach, how does consistency
check scale with increasing model size? RQ2: Does the new
approach introduce an advantage to model transformations
regarding success rates? RQ3: How is the performance of
model transformations comparing all three approaches and
does the new analysis technique introduce any noticeable
overhead?
As our tool of choice we use eMoflon [
For consistency check, we will measure the time to highlight performance differences between a naive approach, filter NACs and our PAC-based look-ahead strategy. Since consistency check is handled as a constraint solving problem, we do not have to measure the success rate because even if irrelevant matches are processed, the optimal solution of the problem does not change.
RQ1: Figure 8 depicts the measured times for consistency check, including the search for rule occurrences on both source and target model and the constraint solving to find an 4000 6000 model complexity 0 2000 8000 10000 1 3 5 7 9 optimal mapping. The biggest model size2 using the naive approach is 360 with a runtime of ~6 minutes. Using filter NACs, consistency check is able to process a maximal model size of 3000 in slightly more than 6 minutes. Finally, the PAC-based look-ahead enables consistency check to process a maximal model size of 10000 within approximately one minute.
The results show a significant performance gain of the PAC-based look-ahead and filter NACs compared to an implementation without analysis. The naive approach tends to be impractical for even moderate model sizes as the runtime increases too steeply. The filter NACs perform better in comparison to the naive approach; however, for models bigger than 2000 the runtime increases substantially. Finally, the runtime of PAC-based look-ahead rises very slightly and stays close to one minute for model sizes of 10000. These measurements show that both filter NACs and our PAC-based look-ahead are able to decrease the complexity of the consistency check task. Regarding the PAC-based look-ahead, we can even further increase the performance and process a multiple of the maximal model size of filter NACs. Regarding forward transformation, we are interested in two measurements. First, the success rate of the transformation where an execution is considered as failed if not all elements were translated3. Second, pattern matching is usually the bottleneck of modern rule-based tools and both filter NACs and our PAC-based look-ahead strategy introduced new patterns that have to be found in the input model. Thus, we are interested in how expensive the new approach is with respect to the runtime performance.
RQ2: Figure 9 depicts the success rate of each experiment. All three plots start at a success rate of 100 percent for a model size of one as this is equivalent to a model with one single package and dead-ends are not to be expected. However, after adding a sub-EPackage or a new EClass the success rate for the naive approach drops to 60 percent and it 120 100 ][s 80 ien 60 itm40 20 0 2Equivalent to the number of rule applications used to generate the model 3Note that each input model is by construction fully translatable The measurements indicate that all three approaches have a very similar performance. The naive implementation almost reaches 0 percent for model sizes bigger than 30. In comparison to the former plot, filter NACs tend to perform much better as long as we transform solely EPackages, since filter NACs can not cope with dead-ends that occur during translation of an EClass hierarchy. The success rate drops from almost 100 percent to 80 for a model size of 6 and rapidly falls down to almost 0 percent for model sizes 10 to 40. In contrast, the PAC-based look-ahead strategy is always able to translate all elements such that no nodes or edges stay untranslated.
The success rates of filter NACs and an implementation without analysis drop rapidly until they reach ~0 percent at a model size of 40. In contrast, the PAC-based look-ahead strategy remains constantly at 100 percent. This means that the transformation does not end up in a dead-end and that all elements were translated.
RQ3: Given those results, we now want to take a look at the runtime performance which is depicted in Figure 10. As can be seen, all three plots are not easy to keep apart as they lie very closely. The maximum times for a maximal model size of 4500 are 89 seconds for the naive approach, 97 seconds for filter NACs, and 97 seconds for the PAC-based look-ahead strategy.
500 1000 1500 2000 2500 3000 3500 4000 4500
model complexity No Analysis
Filter NACs
Look-Ahead Fig. 10. Forward transformation - Measured times using no analysis tends to be slightly faster; however, the performance gain comes at the price of a very low success rate. Comparing filter NACs with the PAC-based look-ahead, there is no considerable difference of performance. Note, however, that the naive approach and filter NACs leave certain elements untranslated. This means that the runtime may be affected such that it appears slightly faster than it would if all elements were processed. Nonetheless, since the runtime of our PAC-based look-ahead strategy does not differ noticeable from the other approaches, we conclude that the introduced overhead is not relevant and may be disregarded. Threads to Validity. External validity is of major interest but it requires investigation of further non-trivial case studies. We argue, however, that the presented example represents a significant challenge that emerges frequently with increasing case complexity. Furthermore, the results are based on an incremental pattern matching framework and a constraint solver. It remains to be investigated if the performance changes considerably with the use of other frameworks and solvers. Internal validity has to be investigated further as the generation of test cases was not deterministic. This means that, despite of the number of repetitions and variations for each model size, the results have a certain variance of around +/- 15 percent.
V. RELATED WORK
In this paper we proposed a PAC-based look-ahead strategy
for rule-based bx approaches. This strategy was inspired by
predictive string parsing techniques which use a variable
look-ahead to resolve issues that arise while parsing. Early
approaches that tried to adapt string parsing techniques to
graph grammars were inspired by the Early-Style-Parser [
Our implementation is based on eMoflon as our tool of
choice; however, there are other TGG tools such as TGG
Interpreter [
In this paper we introduced a novel PAC-based look-ahead strategy for rule-based bx techniques. Although the approach was explained and exemplary implemented for a TGG specification, it is not limited to TGGs. In fact, it offers a strategy for rule-based approaches in general to govern the transformation process in order to avoid dead-ends or even enhance the performance. To evaluate our approach, we chose a compact excerpt of the Eclipse Modeling Framework together with a corresponding documentation structure as our running example. We conducted experiments using a naive TGG implementation, an existing statical analysis called filter NACs and our PAC-based look-ahead strategy. In the case of forward transformations, we showed that the new approach is able to avoid dead-ends that both other approaches encounter. Furthermore, the results indicate that the costs of the new strategy do not raise significantly regarding the performance. For consistency check we showed that the new approach is able to greatly increase the performance with respect to runtime and maximal model size as it reduces the overall number of possible rule applications in the search space. For future work, it remains open to investigate more challenging scenarios, e.g., more complex models and consistency specifications with intensive look-ahead requirements. Another important topic is the extensibility of this approach. Examples for such extensions might be, a look-ahead factor of more than one, or a generalisation of this approach to also handle conflicts that do not only arise from adjacent edges of nodes but also from nodes themselves. Last but not least, the evaluated implementations are based on an external incremental pattern matcher framework and an ILP solver. For future work, we would like to investigate how the performance changes with respect to other frameworks.