Declarative model transformation languages require that the underlying reasoning engine synthesises an execution plan that guarantees correctness while also providing reasonable performance. Optimization of these execution plans is a hard problem and for languages such as QVT Core, finding an optimal solution is still unsolved. By understanding how a brute force execution plan guarantees correctness, we can find an algorithm to construct the complete solution space of correct execution plans and from it find an optimal solution. In this paper we explore how the complete solution space of execution plans can be constructed, how data dependency analysis can be used to evaluate these plans for correctness and how their performance can be estimated. The results show that our performance estimates are correlated to the observed performance.
Model to model transformations are usually expressed in dedicated domain specific languages, commonly referred to as model transformation languages (MTLs). MTLs express algorithms that describe how elements in a model (or models) are transformed into elements in another model (or models). Declarative MTLs (DTL) only provide logic constructs to express relations between elements in these candidate models and the execution engine is responsible for synthesising an execution plan that uses these relations to perform the model transformation.
DTLs are attractive because “particular services such as source model
traversal, traceability management and automatic bi-directionality can be ofered by
an underlying reasoning engine” [
A declarative transformation program (DTP) is a specification written in a DTL. The relations expressed in a DTP can be considered as a set of constraints that must hold for all the candidate models. The execution plan, as a minimum, must check and enforce (by modifying if necessary) the candidate models to ensure that the constraints are satisfied. This paper focuses on the problem of computing an eficient execution plan for a DTP. The correctness problem is also considered, since the lack of correctness will result in models that do not satisfy the constraints. Finding an optimal execution plan for DTPs is a hard problem and well known for other declarative languages such as logic programs, relational query languages and triple graph grammars (TGG). On those domains several approaches have been proposed in the past.
However, DTL optimization problem presents unique challenges. Mainly, the lack of explicit relations between rules and the guarantee for correctness. To understand and overcome these challenges we first propose a representation for DTPs, presented in Sect. 2. Next, Sect. 3 presents how the lack of explicit relations between rules results in solution spaces of considerable size. Following, we show how data dependency analysis can be used to find implicit relations between rules and as a result reduce the solution space by filtering incorrect plans. In Sect. 4 we discus how the execution plans can be evaluated and a cost function derived and Sect. 5 evaluates the cost function against performance results. Finally, Sect. 6 presents related work and Sect. 7 concludes with a summary and future work. 2
In this section we present how an execution plan can be represented by a model and how all possible execution plans for a given DTP can be constructed. Our execution plan model is defined for rule-based DTLs, where the relations are grouped into rules, but can be easily adjusted for other kind of DTLs. In a rule-based DTL, each rule defines a set of types of interest, and relations in the rule are restricted to relations between instances of those types. In this sense, each rule can be viewed as a procedure with a set of parameters (each with a type from the types of interest) and a set of statements. The direction of these parameters, e.g. input or output, is defined by the semantics and syntax of each particular DTL.
Example Our running example is a transformation that creates a copy of a
graph, written in QVTc, as presented in Listing 1. The complete QVTc
semantics and syntax can be found in [
(a) Graph Domain (b) Graph2Graph Domain Line 8 states that the target graph must have the same name as the source graph. Rules n2n for Node (line 10) and e2e for Edge (24) elements, exhibit a similar pattern, with additional conditions to verify that we are keeping the correct references throughout. For example, in rule n2n we are interested in a G2G that is the trace element for the source graph and the target graph (lines 17 and 18). The predicates in the guard of the where (lines 35 to 40) of rule e2e guarantee that the source and target nodes of e2 (target model edge) match the source and target nodes of e1 (source model edge).
According to the semantics of QVTc all variables in guard patterns are input parameters. For realized variables it depends on the execution direction, i.e. realized variables in the target domain (which represents the target model) are output parameters. Realized variables in the middle model are always considered as output parameters. Thus, for example, in rule g2g the input parameter is: g1:SGraph, and the output parameters are: g2:TGraph and g2g:G2G. 2.1
Transformation Execution We propose a definition of correctness based on the constraint satisfaction requirements: an execution of the DTP results in all the relations holding for all the candidate models.
Definition 1. A transformation execution is correct, if after execution the relations stated in the DTP are satisfied by the candidate models.
Using the procedure analogy, execution of a transformation can be
accomplished by invoking all the rules it consists of. Thus, the reasoning engine must
produce an execution plan that invokes the rules in such a way that the execution
is correct. Aspects of the execution plan that afect correctness are: invocation
order, number of invocations and how arguments are bound for invocation.
Algorithm 1 Naïve declarative transformation execution
1: procedure execute(Transformation)
2: repeat
3: forEach rule r in Rules do
4: forEach combination of P⊙E do
5: if canBeExecuted(r) then
6: executeRule(r)
7: end if
8: End for
9: End for
10: until no changes in candidate models
11: end procedure
◃ R times
◃ P E times
◃ D times
Naïve Execution Plan. The simplest, naïve execution plan we can conceive
can be represented by Algorithm 1. Since there are no explicit relations between
rules, the algorithm iteratively invokes all rules until no more changes are
observed in the candidate models. If relations existed, the rules could be invoked
following these relations. For example in QVT Relations[
Procedure canBeExecuted (line 5) tests if the binding process (line 4) bound an element for each of the input parameters, i.e. all elements needed by the rule are available. Procedure executeRule (line 6) invokes the rule and modifies the candidate models (i.e. adds or modifies elements).
The reasons this algorithm will correctly execute a QVTc transformation (and possibly any rule-based DTP) are as follows. (i) All possible invocation orders are considered (execution can start at any rule) by invoking all the rules. (ii) Since all rules are invoked indefinitely they are invoked as many times as necessary. (iii) All possible combinations of candidate model elements and rule parameters are used for argument binding. New elements (realized) by a rule execution will be available for binding in the next iteration.
Based on these reasons we introduce an additional constraint for execution plans: completeness: Definition 2. An execution plan is complete if all the rules in the transformation are invoked at least once. 2.2
Execution Plan Model
A complete execution of the naïve algorithm can be represented by a list of rules,
that starts with the first executed rule and ends at the last one, with elements in
the list representing the order in which rules were executed. An execution plan is
then any of such lists. We propose to model execution plans as directed graphs,
adopting the representation of execution paths used in compiler optimization [
In an execution plan graph each node represents a rule. Directed edges are used to represent rule calls. There is a specially designated root node that represents the initial execution point. Outgoing edges of a node are ordered, such that lower order edges are called before higher order ones. As such the execution plan can be regarded as an ordered tree, rooted at the root node. This model is language agnostic, as the references from nodes to rules can be made generic in order to point to rules in any transformation language. A significant diference with the list representation, is that in the execution plan graph, rules are allowed to invoke other rules. We say that the invoked rules are nested in the caller rule. However, nesting in this case does not entitle containment as a rule may be invoked from many rules. This representation also allows modelling of loops, for example those from recursive invocations.
Execution plan graphs are executable, with execution semantics defined by outgoing edge order and call edge traversing, i.e. the execution follows a depthifrst traversal. For this, our execution plan graph guarantees outgoing edge traversal order. As a result, the execution plan model can be easily used for interpreted execution or as a structure for code generation. The purpose of the complete solution space exploration is to generate all possible execution plans that produce the same results as the naïve plan. Building the complete solution space is clearly impractical and not scalable. However, this exploratory setup will allow us to identify desired characteristics of execution plans that will lead to correct transformations. The next step of this research will use these characteristics to develop a heuristic approach for eficient synthesis of execution plans.
In the naïve algorithm it is impossible to statically determine how many times a rule should be invoked. Hence, any representation as an execution plan graph would require an infinite number of nodes. One possible way of constructing finite execution plans is to delegate the outer loop control to the reasoning engine and allow the execution plan graph to have loops. Loops allow invocation sequences to be repeated, making it possible to represent any execution with a finite list. Loops in the execution plan that result in infinite loops during execution can be broken by the reasoning engine. With these premises, Algorithm 1 can be represented with our execution plan model, with calls from the root to each of the transformation rules and a loop call from the root to itself after all the rule calls.
Given a DTP, the solution space is constructed by creating execution plans that (collectively) invoke all the rules in all possible orders and nestings. Note that although we can now construct finite execution plans, we still have no way of knowing how many times each rule should be invoked or in what order. This results in an infinite solution space. Next we show that by identifying optimizations in Algorithm 1 it is possible to produce a finite solution space of execution plans that produce the same outcome.
There are two ways of optimizing an algorithm [
Since Algorithm 1 is bound to terminate (no changes in candidate models), any execution of the algorithm can be represented by a finite set of rule invocations. If the invocation order can be statically computed or the correctness of a given order it can be proved, then the outer loop can be eliminated. Finding all the combinations of parameters and model elements for each rule is impractical. This search can be optimized be reducing the search space, for example by limiting the search to the elements consumed and produced by a rule.
(a) Step 1
(b) Step 2 root g2g ② e2e g2g n2n root
root g2g
To eliminate the outer loop, we must make sure that all possible executions plans are constructed. Construction of the plans is guided by all permutations of a set of the DTP rules. Although the permutations of a finite set are also finite, the number of possible execution plans grows exponentially as the number of rules increases. We present how this can be achieved, but reiterate that in a real-world scenario this is impractical. The initial plans created will include each rule once. At a later stage, we will add missing invocations that guarantee that the plan is correct.
Example Given the rule permutation {g2g, e2e, n2n}, solutions for this permutation can be created as presented in Fig. 2. The first step, Fig. 2a, consists in adding an edge from the root to the first rule ( g2g) in the permutation. For the next rule, e2e, we can create two diferent trees by adding invocations from root and from g2g, as presented in Fig. 2b. Selecting n2n next, new trees are created by adding edges from all existing nodes in the tree in all existing trees. For example, if we select tree ① in Fig. 2b, the three trees in Fig. 2c will be created. The process will be repeated for the next permutation of rules, e.g {e2e, n2n, g2g} and so on and so forth until all trees for all possible execution plans (where each rule is invoked once) are created. 3.3
Data Dependency Analysis A rule might not be executed due to missing bindings (conditional in Algorithm 1 at line 5). The outer loop guarantees that the rule is attempted at a later time when new elements have been created and the bindings might be complete.
The failed attempt to execute a rule due to the lack of valid input parameters can be understood as a producer-consumer problem. Execution of a rule that consumes a set of types may fail if the rules that produce those types have not been executed. We will use the term starvation to refer to a rule that fails to execute due to a lack of elements of its consumed types. Next we present how data dependency analysis can be used to validate and/or complete the permutation solutions to produce execution plans that do not present starvation while ensuring that rules are called as seldom as necessary, and which will result in correct transformation executions.
The producer-consumer relations can be easily derived from the types of the input and output parameters. If a rule has an input parameter of type A, then it will have a data dependency on all rules that have output parameters of type A. These dependencies can be represented in a dependency graph. A dependency graph is a directed graph in which nodes represent rules and types involved in the transformation, and edges represent the data dependencies. Outgoing and incoming edges of a rule represent the types of the output and input parameters respectively. The dependency analysis information can be used to detect starvation in an execution plan. If there is a path in the dependency graph from rule A to rule B, then we say that rule B is a consumer of rule A. Conversely, rule A is a producer of rule B.
The outer loop of Algorithm 1 also guarantees that all elements created during execution are taken into consideration in the binding process. We introduce the concept of thoroughness to validate that an execution plan satisfies this constraint.
Definition 3. A transformation execution is thorough if all the created elements of a rule are consumed by the rule’s consumers.
Example The dependency graph of the QVTc graph to graph transformation of Listing 1 is presented in Fig. 3a. It is important to note that we have made a distinction for multi-consumer edges to represent consumer edges for types that are used by more than one parameter. The data dependency analysis is used to evaluate the plans to the right in Fig. 3. The plan in Fig. 3b will present starvation when rule e2e is called from rule g2g as rule n2n would not have been executed yet and hence there would be no existing elements of types SNode and N2N to bind rule e2e parameters. On the other hand, the plan in Fig. 3c presents starvation due to multi-consumer relations: the call from n2n to e2e will starve because in the first execution rule n2n will have only produced one SNode and one N2N, and rule e2e consumes two of each. Regarding thoroughness, the plan in Fig. 3b is not thorough as elements produced by rule n2n are not consumed by any rule despite e2e being a consumer.
SEdge E2E
TEdge TGraph
G2G
Source Model Types
Trace Model Types g2g TNode Target Model Types
Producer Edge
Consumer Edge
SGraph n2n SNode Multi-Consumer Edge (a) Dependency Graph for the graph to graph transformation. root g2g e2e
n2n (b) Case A The set of permutations plans is filtered to eliminate plans that result in starvation and the remaining plans are amended to guarantee that they are thorough. The amendment process involves adding missing calls for all the producer-consumer relations. As a result, the solution space of all correct execution plans for a given transformation is constructed.
Example Rule n2n is a consumer of rule g2g and hence plans ① and ② in Fig. 4 are missing invocations from rule g2g to rule n2n. In Fig. 4a the invocation is added to plan ① resulting in the plan to the right. For plan ② since invocation order matters, the invocation to n2n can be either done before or after the existing invocation to e2e. For one invocation we can modify the existing plan, for the other(s) we need to create an additional plan. The resulting plans are shown to the right of Fig. 4b. root g2g n2n e2e (c) Case B g2g root ① e2e n2n g2g n2n root e2e n2n root ② g2g e2e n2n root g2g root g2g n2n
n2n e2e n2n e2e n2n (a) Modify
(b) Modify and create 3.5 Input Variable Relations and Binding Solutions Finally, we consider the case of binding during invocation. If n2n is being invoked, we need to bind four input variables. In practice, the rule guards define precise restrictions on these variables. For example, the predicate n1.graph = g1 indicates that n1 and g1 are related through the SN ode :: graph attribute. Hence, if we have one it is possible to derive the other. Due to the expressive power of OCL we limit our analysis to predicates of the form < var > . < property >=< var >. From this, it is possible to identify primary and secondary variables, where secondary variables are derived from primary ones. In most cases it is possible to pick one primary and derive the rest from this one. By using the context information and exploiting derivations we are reducing the number of possible input element combinations that are attempted for each rule.
Consider the case in which rule n2n is being invoked from g2g. In this case, we can either choose g2:TGraph or g22:G2G as the primary variable. This results in two versions of the invocation. By adding all possible binding alternatives for all rules, we can produce a new set of solutions that represent all possible plans with all possible bindings.
As the number of rules and the number of edges in the dependency graph increases, the proposed approach to generating the complete execution space becomes infeasible. This issue can be resolved by applying search-based algorithms to find a good enough solution without requiring to do the exhaustive execution space search. This is a topic for future research. 4
To express starvation and multi-consumer requirements we introduce the concept of feasibility and from it we can define execution plan correctness: Definition 4. An execution plan is feasible if all producers of a rule have been called before the rule is called, and if all rules with multi-consumer relations are not invoked from the producer of the multi-consumer relation.
Definition 5. An execution plan is correct if it is complete and feasible and results in a thorough execution.
Notice that we express thoroughness as a property of the result and not the plan itself. The reason for this is that, in practice, thoroughness cannot be evaluated on a plan unless details of the particular DTL and modelling technology are known.
This definition of execution plan correctness overlaps with the correctness and
completeness definitions formulated in [
Example Consider the plan in Fig. 5a. Depending on the modelling technology it is possible that not all SNode elements are contained in a SGraph, in which case this plan will not be thorough, i.e. there are missing calls from other places where SNodes can exist. Indeed, a particular language may allow elements to be created outside rules, e.g. helper methods, in which case we would need to analyse such methods and add additional calls to consume those elements. 4.1 Performance Evaluation From the set of correct execution plans, we are interested in selecting the best plan in terms of performance. In particular, we are interested in execution time since it is one of the key performance aspects noticed by users. The key factors that afect execution time are the number of times a rule is invoked and the binding process.
Consider the plans in Fig. 5, both of which are correct. We are interested in evaluating their performance, in order to select the optimal one. (a) Case A
(b) Case B
When a rule is invoked from the root, the binding process must query the candidate models for all elements of each of the input types and produce all possible combinations. For P parameters and E elements for each parameter type, each rule is invoked P E times. When a rule is invoked from a rule diferent from the root, it obeys a producer-consumer relation and thus a model search is not required for elements of the types of the producer-consumer relation. For example, if rule A and rule B have a producer consumer relation via type X, and A produces one element of type X, then when invoking B from A, we only need to invoke it once: to consume the new element.
Inspecting the plans in Fig. 5 we can then say that the plan in Fig. 5a has a total of 2 × P E invocations, because rule n2n is only invoked once per invocation of rule g2g. On the other hand, the plan in Fig. 5b has a total of 3 × P E invocations. From this it is possible to conclude that the plan in Fig. 5b would have a worse execution time than the plan in Fig. 5a.
“The experience with relational system has shown that the main purpose
of a cost model is to diferentiate between good and bad executions, in fact, it
is known, from the relational experience, that even an inexact cost model can
achieve this goal reasonably well.” [
∑ ( ϕ β(r′) + ϕ (r′)) r′∈O(r) (1)
Where X(r) is the number of times a rule is invoked and ϕ β(r) is the cost of binding the parameters of the invoked rule. In general X(r) = P E, but for static analysis we can select an arbitray value, e.g. 100, that is suficiently larger that the binding cost to discourage the use of loops as we know they afect performance adversly. The binding cost ϕ β(r) accounts for the binding of input types that don’t belong to the producer-consumer relation. For example, when n2n is invoked from g2g, g2:TGraph can be bound directly from the produced TGraph, but n1 and g1 must be bound separately. If any of the secondary variables is derived via a multi-value property, then the binding will also include the cost of a loop. For static analysis we consider property loops less expensive than all instances loops (P E) and have defined them as an order of magnitude cheaper. Finally, the binding cost depends on the underlying modelling technology. For example in EMF, navigating an undefined opposite relation is more expensive than a direct one. Since the cost of a rule depends on all the rules it invokes, the cost of a plan is ϕ (root). 5
The described approach has been implemented in Java, using the JGraphT3 graph library for modelling the Dependency Graph and the Execution Plan Graph. For the Graph2Graph transformation the complete solution space consists of 240 possible execution plans. We took a sample of 20 plans and executed the transformation using a test model with 100k elements. For this evaluation, each graph has the same number of nodes and edges and the model has as many graphs as a graph has nodes. The idea was that loops for either all instances or multi-value properties where comparable.
Figure 6 shows the execution time for the 20 sample plans. The series
represent the groups identified by the Honest Significant Diferences (HSD) using
the statistical software R. Since the ANOVA[
It is important to note that the diference in execution times between Group c and the others is around two orders of magnitude. By inspecting the plans with longer executions times we found that those plans where the cases in which the binding resulted in derivations that used multiplicity attributes, for example deriving nodes from a graph. This sort of derivations insert additional loops during execution, which translate into higher costs, i.e. higher X(r). The results show that our cost function is good enough to diferentiate good and bad executions. 3 Available online, http://jgrapht.org (viewed April 2016)
Although the results are statistically significant, the HSD results also suggest that bigger sample sizes are needed. This is the objective of future work. 6
Data dependency analysis has been used for instruction scheduling, constant
propagation [
In the case of other DTL such as ETL [
Data dependency analysis is also used in the QVTc compiler[
An important diference with functional languages is that since there exists
an explicit relation between functions (i.e. one function is computed by invoking
a set of other functions), there is an initial invocation structure and the
optimization problem is related to finding the correct set of function invocations to
obtain a result as opposed to finding an order in which to invoke these
functions. The same can be said for declarative queries languages. In the case of
DryadLINQ, a declarative queries system, in [
As stated previously, we are interested in providing optimizations based on
static analysis where the execution plan is determined at compile time. In [
Data dependency analysis is also used in [
In the domain of graph transformations, [
In this paper we proposed a novel model to represent execution plans of declarative model transformations and presented how the complete solution space of execution plans for a given transformation program can be constructed. Further, we introduced a method for determining the correctness of execution plans based on data dependency analysis. We showed how the correctness criteria can be used to synthesise eficient execution plans that guarantee correct transformation execution while minimizing the number of rule invocations. Finally, we presented how predicted runtime performance could be evaluated by computing the cost of the execution plans and validated the results by execution a sample of the plans in the execution space. The ideas for constructing the complete solution space can be incorporated into a search-based algorithm that would result in a suficiently good solution without requiring a complete solution space exploration. These contributions were presented in a language-agnostic level that facilitates its incorporation to other declarative model transformation languages.
The authors would like to acknowledge the contributions of Edward Willink in the establishment of some fundamental concepts of this work.