1 Introduction
-
Batch-mode execution, where an empty trg (or src) model is populated from a src (or trg) model in one complete execution.
-
Incremental-mode execution, where incremental changes to a src (or trg) model are propagated to changes to an already populated trg (or src) model. Changes can be: creation/deletion of elements; reassignment of 1-multiplicity features; addition/removal of elements from other features. In this paper, we address source-to-target incremental change propagation in the sense of [10].
-
Incompleteness in the semantics makes it difficult to verify transformations, or to systematically design bx [36].
-
Unclear semantics for update-in-place transformations makes it difficult to define and use such transformations. The combination of bx and update-in-place execution has not been developed [41].
-
Tool support is incomplete, with the only mature tool, Medini QVT [11], no longer actively maintained. The tool uses a restricted version of QVT-R, with a variant semantics which has not been formalised.
2 QVT-R
2.1 QVT-R transformation structure
2.2 QVT-R relation semantics
2.3 QVT-R relation dependencies
2.4 Specialised control of transformation behaviour
2.5 Overall QVT-R transformation semantics
3 Issues in QVT-R semantics
-
Incompleteness and inconsistencies in the standard [31]. For example, issue QVT14-55 identifies incompleteness in the check-before-enforce mechanism, and issue QVT14-57 identifies gaps and problems in the RelToCore mapping in the standard, which (partially) defines the semantics of QVT-R via a translation to QVT-C.
-
The state-based semantics and check-before-enforce mechanism are insufficient in some cases to support efficient or precise incremental updates of a target model in response to source model changes [37]. The mechanism can also have unintended effects in batch mode, e.g. performing n to 1 merging of elements which should not be identified.
-
Different transformation problems require different criteria for rule application conditions and for target element matching/creation/update. The standard does not provide any capability for such flexibility, leading to contrived and complex specifications when a variant semantics is needed [7, 36, 37].
3.1 Incompleteness and inconsistencies in the QVT standard
3.2 Issues with the RelToCore semantics
3.3 Issues with Medini QVT
4 UML-RSDS
4.1 UML-RSDS specification structure
4.2 UML-RSDS rule semantics
4.3 UML-RSDS transformation semantics
QVT-R facility | UML-RSDS facility |
---|---|
Check-before-enforce | Local check-before-enforce using \(stat_{LC}\) |
Single and compound keys for elements | Single keys |
Query operations | Query and update operations, including |
cached query operations | |
when clause (lookup of | Element lookup by key, including |
individual target elements) | lookup of multiple target elements |
Unspecified rule execution ordering | Explicit rule execution ordering |
Tool-dependent | Internal transformation decomposition |
transformation composition | via use case activities |
Rule inheritance and rule invocation | No rule–rule relations |
Transformation extension | Transformation import |
5 Translation from QVT-R to UML-RSDS
QVT-R language element | UML-RSDS language element |
---|---|
Relational transformation | Use case representing the transformation |
Top relation | Use case postcondition constraint |
Non-top relation | Update operation of use case |
Local variables | Auxiliary variables of constraint/operation |
Query | Query operation of use case |
Key | Identity attribute |
Domain | Property representing root variable, |
Properties for other domain variables, | |
expressions for template expression | |
assignments and where condition | |
when clause | Expressions including trace tests |
where clause | Expressions including update operation |
invocations |
5.1 Rationale for the semantics
Transformation | Size | Element mappings | Patterns/techniques |
---|---|---|---|
AbstractToConcrete | 47 | Update-in-place | |
hsm2nhsm (recursion) | 48 | \(n-1\), 1–1 using keys | Flattening |
ClassModelToClassModel | 85 | 1–1 using keys | Recursive descent, |
Map objects before links | |||
HSM2FlatSM | 85 | \(n-1\) using custom | Flattening |
strategy | |||
1–1 using keys | |||
UmlToRel | 98 | 1–1 using keys | |
SeqToStm | 104 | 1–1 using keys | |
pn2pnw | 115 | 1–1 using keys | (vertical) Entity splitting/merging, |
Map objects before links | |||
set2oset | 121 | 1–1 using keys | |
SeqToStmc | 149 | \(1-n\) | (vertical) Entity splitting |
bag12bag2/bag22bag1 | 157 | \(n-1\) using keys | |
ER2WebML/WebML2ER | 190 | 1–1 using keys | Map objects before links |
Ecore2copyQVT | 193 | \(1-n\) | (vertical) Entity splitting |
cdrat | 202 | update-in-place | Deletion by selective copy |
UmlToRdbms | 238 | 1–1 using keys | |
DNF_bbox | 263 | update-in-place | Guard against duplicate applications |
gantt2cpm | 378 | \(1-n\) | (horizontal, vertical) Entity splitting |
DNF | 396 | Update-in-place | Guard against duplicate applications |
families2personsconfig | 435 | 1–1 using custom | (horizontal) Entity |
Strategy | Splitting | ||
dag2ast | 439 | \(1-n\) using recursion | |
ast2dag | 439 | \(n-1\) using keys | Marker relation, |
Map objects before links | |||
f2p/p2f | 462 | 1–1 using procedural | |
Coding | |||
Bpmn2UseCase | 532 | \(1-n\) | (vertical) Entity splitting |
Communication2class | 1029 | 1–1 or \(n-1\) | Explicit checks to avoid |
Using keys | duplicate target elements | ||
ecore2sql1, | 1120 | 1–1 using keys, \(1-n\) | Guard against duplicate applications, |
ecore2sql2, | 956 | Marker relation, | |
ecore2sql3 | 960 | (vertical) Entity splitting | |
RelToCore | 2038 | 1–1 using keys, | (vertical) Entity splitting |
\(1-n\) |
Element mapping approach | # cases | Percentage |
---|---|---|
1–1 using keys | 14 | 52% |
\(1-n\) vertical entity splitting | 8 | 29% |
update-in-place | 4 | 15% |
\(n-1\) using keys | 3 | 11% |
\(n-1\) check-before-enforce | 2 | 7% |
\(n-1\) custom | 2 | 7% |
1–1 custom/procedural | 2 | 7% |
\(1-n\) recursion | 1 | 4% |
-
(a) “No secretly created objects”: Target data are write-only, and relations R can only refer to model elements e of source or target models which are explicitly declared in R as object variables (as the rootVariable of a RelationDomain, or bindsTo of a TemplateExp).
-
(b) “No inter-relation conflicts”: Different top relations do not have conflicting effects.
-
(c) “No intra-relation conflicts”: No relation has internal conflicts in its effects (i.e. conflicts between different applications or within one application of the relation).
-
(d) “No secretly deleted objects”: If \(\tau \) refers to a target element t, then any target element x from which deletion could propagate to t must also be referenced by \(\tau \).
-
(e) “Call graph is surjective and non-cyclic”: There are no unused non-top relations and no cycles in relation calling dependencies.
5.2 Translation for separate-models QVT-R transformations
Notation | Meaning |
---|---|
sdom | The source domains \(d \in R.domain\), including primitive domains |
tdom | The target domains d of R.domain |
\(ovars_d\) | Object variables of domain d, |
including the root variable | |
\(svars_R\) | \(\bigcup _{d \in sdom} ovars_d\) |
\(tvars_R\) | \(\bigcup _{d \in tdom} ovars_d\) |
\(ovars_R\) | \(svars_R \cup tvars_R\) |
\(sourcevars_R\) | All variables bound in any sdom |
Includes \(svars_R\) | |
\(targetvars_R\) | All variables bound in any tdom |
Includes \(tvars_R\) | |
\(avars_R\) | All variables of any sdom or tdom |
\(sourcevars_R \subseteq avars_R\) | |
\(whenvars_R\) | Variables free in when clause of R |
\(whenvars_R \subseteq avars_R\) | |
\(invars_R\) | Input elements of R. For top relations: |
\(svars_R \cup (whenvars_R \cap ovars_R)\) | |
For non-top relations: | |
\(svars_R \cup (whenvars_R \cap ovars_R) \cup R.domain.rootVariable\) | |
\(outvars_R\) | Output elements of R: |
\(ovars_R - invars_R\) | |
These are the object variables possibly instantiated | |
by a successful application of R |
Term | Meaning |
---|---|
Target element resolution | The process of inspecting the target model to identify if there are elements t which satisfy required constraints relative to source elements s, and binding the t to target object variables \(outvars_R\) if the t exist, or selecting or creating target elements to update and bind to target variables to establish the constraints |
Elements referenced by a rule application of relation R | Source or target elements x bound to some \(v \in ovars_R\) for a successful application of R. Equivalently, x occurs in some \(R\$trace\) tuple |
Elements referenced by a transformation execution | Elements referenced by any rule application in the transformation execution |
Application condition of relation R | Condition on \(svars_R\) determining if R can be applied to particular source model elements |
Effective for update in direction m | An expression e that has a defined stat(e), and with wr(e) a non-empty subset of the variables (\(targetvars_R\)) from enforce domains with model m |
-
Preservation constraints \(Pres_R(m)\) expresses the effect of R when applied to tuples elems of source and target elements which are linked to one \(R\$trace\) element, but which nonetheless may not satisfy the logical properties of R’s target domains—due to incremental changes of source or target model data. The effect of \(Pres_R(m)\) is to modify target model data linked to the trace, to re-establish the R target domain properties for elems relative to the source data. Traces which cannot be repaired are deleted.
-
Construction constraints \(Con_R(m)\) expresses the effect of R when applied to source elements/tuples selems which are not in any \(R\$trace\), and therefore have not yet had R applied to them. \(Con_R(m)\) establishes the logical properties of R’s target domains by looking up and updating target elements or by creating new target elements. It also creates a new trace instance for the selems and their matched target elements.
-
Cleanup constraints \(Cleanup_E(m)\) manages the deletion of target instances e : E that are not linked to any source instance via any valid trace \(R\$trace\) for any relation R that may create E instances.
5.2.1 Preservation constraints
5.2.2 Construction constraints
5.2.3 Cleanup constraints
5.2.4 Non-top relations
5.2.5 Overall transformation semantics
5.3 Example of the semantics
5.4 Properties of the semantics
-
(a) “No secretly created objects”: No target features/entity names of TL occur in the when clause or source domain patterns of any relation, and relations can only refer to target features/class names via explicitly declared object variables t : T and their features, in domain templates. Target data cannot be read, only written, in the parts of a relation that are effective for update in direction m;
-
(b) “No inter-relation conflicts”: If two top relations both write (directly or via called relations) to the same target features or entity types, these updates are non-conflicting (i.e. they create/update disjoint sets of elements of the same target entity type, or update disjoint sets of features of the same instances of the entity).If all updates to a reference feature f of *-multiplicity are additions, these are also non-conflicting. Similarly, if all updates to a 0..n or * multiplicity reference feature f are all removals, these are non-conflicting;
-
(c) “No intra-relation conflicts”: There are no self-conflicts or internal conflicts of a relation R, i.e. one application of R cannot invalidate the same or a different application, e.g. by defining contradictory values for the same target data (Sect. 6). The where clause should not conflict with target domain templates;
-
(d) “No secretly deleted objects”: If target element t : A is referenced by \(\tau \), so also is any target element b : B linked to t via a mandatory target reference A : : r (i.e. where r is of 1 or 1..n multiplicity at the B end), and so is any aggregation owner element b : B linked to t by an aggregation association (Fig. 7). Another way to express this is if t appears in any trace tuple of some \(\tau \) relation, b must also appear in a trace tuple, of the same or a different relation;
-
(e) “Call graph is surjective and non-cyclic”: Relation calls in when clauses must be positive (including disjunctions or conjunctions of positive calls). Any recursion in queries should be shown to be always terminating. There should be no recursion between relations via when or where clauses3. All non-top relations are called from at least one top relation directly or indirectly. No relation can be called via both when and where clauses starting from one relation. More precisely, it should be possible to order the top relations as \(R_1, \ldots , R_n\) such that:1.\(R_i~called~in~R_j.when\) \(i < j\)2.\(S~called~in~R_j.where*\) and \(R_i~called~in~S.when*\) \(i < j\)3.\(S~called~in~R_i.where*\) and \(S~called~in~R_j.when*\) \(i < j\).
-
If P and R are both top relations, then \(P < R\) and hence \(\lnot (R < P)\).
-
If P is top, R non-top, then any top S with \(R \in S.where*\) has \(P < S\). But \(R \ll P\) would imply that \(S < P\).
-
Likewise for non-top P, top R.
-
If both P, R are non-top, then any top S, T with \(P \in S.where*\), \(R \in T.where*\) has \(S < T\). But \(R \ll P\) would imply \(T < S\).
-
Rule 2: (2.1): the relation R when clause is represented in the \(guard_R\) predicate. (2.2): relation domains are either expressed in the source cpreds condition or target epreds constraint. (2.3): an instance of \(R\$trace\) is tested (in \(Pres_R\)) or created (in \(Con_R\)). (2.4): each source property template item becomes an equation/membership test in cpreds; each target property template item becomes an assignment/element addition in epreds. (2.5): when predicates become tests on the LHS of \(Pres_R\) and \(Con_R\). (2.6): predicates of the where clause become RHS predicates of \(Pres_R\) and \(Con_R\). In contrast to [30], we also express relation calls in the where clause as predicates (calls of operations).
-
Rule 3: We only consider relations with at least one enforceable domain.
-
Rule 4: (4.1, 4.2): We permit multiple enforced target domains. (4.3): Each such domain has a realised root variable (quantified by an exists or existsLC operator) in epreds, if it is not also an input to R. Property template items in enforced target domains become assignments/element additions in epreds. (4.4): where clause predicates are included in wherepx, which is within the scope of the epreds realised variable quantifiers. (4.5): source domains are mapped as in Rule 2. (4.6): we do not model black-box operations, but these could be formalised as updator operations in UML-RSDS.
-
Rule 5: (5.1): we represent an invoked relation S by an updator operation OpS, called from the constraints representing the relations that call S. (5.2, 5.3): The root variables of the S domains become parameters of OpS and are instantiated in the call.
-
Rule 6: As for rule 5, we treat relation calls as conventional procedure calls.
5.5 Incremental execution and change propagation
-
Addition of a new source element sx : ST—if this element satisfies some \(sguard_R(m)\) of a relation R with source domain s : SST for SST equal to ST or a supertype of ST, then sx will be processed by \(Con_R(m)\) and appropriate target and trace elements selected or created. Further top relations may consequently also become enabled and will be applied.
-
Changes to a 1-multiplicity reference f or non-key attribute att of an existing s : ST—if s occurs in some trace \(R\$trace\), and \(guard_R(m)\) remains true for s, then \(Pres_R(m)\) applies to update linked target elements appropriately. If s is in some \(tr : R\$trace\) but \(guard_R(m)\) is falsified by the change of f/att value, then tr is removed from \(R\$trace\) by \(Pres_\tau (m)\), and \(Cleanup_\tau (m)\) removes any target elements that depended exclusively on s. If s does not occur in any trace, but the change in f/att now validates some \(guard_R\), then \(Con_R(m)\) is applied to s.
-
Addition of an element to a collection-valued feature f of existing element s : ST—if s is in \(tr : R\$trace\) and \(guard_R(m)\) remains true, then \(Pres_R(m)\) propagates the change to corresponding target elements. The cases of \(guard_R(m)\) being falsified and s not in \(R\$trace\) are handled as for the previous case.
5.6 Variant semantics and extensions for QVT-R
5.6.1 Check-before-enforce semantics
5.6.2 Least-change semantics
5.6.3 Non-persistent traces
5.6.4 Propagation of element removal
5.6.5 Internal composition of transformations
6 Semantic analysis of QVT-R
7 Design patterns
-
Map objects before links: used to avoid mutual/cyclic dependencies between relations and to separate out the mapping of collection-valued references. The pattern relies on key-based or mandatory-create target resolution, in order to impose a 1–1 mapping of elements in the ‘map’ phase (e.g. Model2Program in Sect. 2).
-
Lens: used to provide incremental bidirectional execution in cases where the forward map ignores existing target data. This is used in cases where a target data feature g of instances t : T of entity type T can be computed in the forward direction as a function of source features \(f_1, \ldots , f_n\) of instances \(s_1, \ldots , s_n\) of source entity types \(S_1, \ldots , S_n\): In the reverse direction, \(put_i\) functions update the \(f_i\) based on the initial values \(f_i\)@pre of these features and on the target data g: In QVT-R, the equations can be placed in a relation where clause, the assignment to g will be effective for update only in the source-target execution direction, whilst the assignments to the \(f_i\) will be effective only in the target-source execution direction. The @pre suffix is used for the \(f_i\) so that correctness condition (a) is not violated in this direction. To avoid conflicting updates in the put assignments, each \(s : S_i\) for any i should be related to only one t : T.××
-
Entity splitting/merging: where the data of one class in SL are distributed to data of two or more classes in TL, or vice versa. Horizontal merging/splitting is the situation where two or more exclusive classes are merged into/split out from one class. Vertical merging/splitting is the situation where two or more non-exclusive classes are merged into/split out from one class.
-
Flattening/unflattening: various situations in which source model data structure corresponds to simplified or elaborated structure in the target model. For example, introduce intermediate class adds a new class C in TL between two classes derived from SL linked by an association: \(A \longrightarrow _r B\) in SL is elaborated to \(A1 \longrightarrow _{r1} C \longrightarrow _{r2} B1\) in TL, so that r is represented by the composition r1.r2. The reverse of this transformation is a flattening which discards the intermediate elements. A recursive *-accumulation is a flattening where the closure of a source association corresponds to a target association.Transformations involving flattening can be problematic for bidirectional execution because of the loss of information (e.g. the two cases where a bx is not definable in [36] both involve flattening).
-
Auxiliary metamodel: Introduce additional model structure in order to support bidirectionalisation, e.g. to introduce flag attributes in target classes to record the specific source class from which a target instance is derived, in the case of horizontal Entity merging.
-
Auxiliary models: in cases where there is substantial disparity between the structures of SL and TL, introduce an intermediate model and split \(\tau \) into a sequential composition of two transformations which use this model. Auxiliary models can also contain configuration information to restrict nondeterminism, as in the Families to Persons case [37].
-
Object indexing: Introduce identity attributes/keys for elements in order to enforce reuse of target elements (instead of creation of new elements) and to enforce 1–1 or \(n-1\) relations between source and target elements of corresponding classes.
-
Restrict input ranges: Use additional guards to prevent duplicated application of relations with source object variables s1 : S, s2 : S—so that each pair x1, x2 of distinct S elements is only bound in one way to the si, similarly for other situations where repeated application to the same input variables should be prevented. The additional guards should not involve relation tests.
-
Marker relation [6]: simple non-top relations with domains \(s : S \{\}; t : T \{\};\) with no explicit functionality, which are called from the where clause of more complex relations in order to store specific pairs or tuples of elements into a trace that can be queried in other relations. For example, the dag2ast/ast2dag and ecore2sql transformation versions of [36] use this idiom.
-
Test and update bidirectional 1-* or 1-0..n associations at the 1 end: as noted in Sect. 2, matching on 0..n multiplicity or * multiplicity association ends has semantic complications. Therefore, it is preferable to manipulate such associations via their opposite ends if these are 1-multiplicity.
-
Replace recursion by iteration: recursive relations can be a cause of semantic problems and can be avoided in many cases by using the Map Objects before Links pattern, by using the \({\rightarrow }closure(r)\) operator on a self-association r [28] or by using a \(\forall \) quantifier (e.g. the bag migration case in Sect. 8, defined in “Appendix E”).
Case | Original version | Revised version | Performance gain |
---|---|---|---|
Flaws/LOC | Flaws/LOC | ||
Tree to graph [14] | 1/15 | 0/17 | – |
UML to Python | – | 0/30 | – |
Hsm2nhsm [28] | 2/48 | 1/70 | – |
Person migration | 0/63 | 0/19 | 893 (forward) |
575 (reverse) | |||
Weighted/unweighted | 2/115 | 1/60 | 228 (forward) |
Petri nets | 182 (reverse) | ||
Unordered/ordered sets | 1/121 | 0/29 | 563 (reverse) |
Migration of bags | 1/157 | 0/66 | 45,404 (forward) |
Gantt2CPM | 10/378 | 1/54 | – |
Expression trees/dags | 8/439 | 0/80 | 8.1 (forward) |
34.5 (reverse) | |||
Total flaws/LOC | 25/1336 (0.019) | 3/425 (0.007) |
Case | Bidirectionality | Batch/incremental | Deterministic | Patterns used |
---|---|---|---|---|
Tree to graph | Bidirectional | Incremental | Yes | Introduce/remove |
intermediate class | ||||
Map objects | ||||
before links | ||||
UML to Python | Bidirectional | Incremental | Yes | Recursive |
*-accumulation | ||||
Auxiliary | ||||
metamodel | ||||
Map objects | ||||
before links | ||||
Hsm2nhsm | Partly separate | Incremental | Yes | Recursive |
forward/reverse | *-accumulation | |||
Entity merging/ | ||||
splitting (horizontal) | ||||
Map objects | ||||
before links | ||||
Person migration | Bidirectional | Incremental | Yes | Lens |
Weighted/ | Bidirectional | Incremental | Yes | Introduce/remove |
unweighted | intermediate classes | |||
Petri nets | Map objects | |||
before links | ||||
Unordered/ | Bidirectional | Incremental | Yes | Map objects |
ordered sets | before links | |||
Object indexing | ||||
Migration of bags | Bidirectional | Batch | Yes | Auxiliary models |
Object indexing | ||||
Lens; Introduce/ | ||||
remove intermediate | ||||
class; Map objects | ||||
before links | ||||
Expression trees/ | Mutually inverse | Batch | No | Deletion by |
dags | forward/reverse | selective copy | ||
Gantt2CPM | Bidirectional | Incremental | Yes | Entity merging |
splitting (horizontal) | ||||
Introduce/remove | ||||
intermediate class | ||||
Map objects | ||||
before links |
8 Evaluation
8.1 Comparison
9 Related work
Aspect | CPN [8] | Mu calculus [2] | UML-RSDS |
---|---|---|---|
Modes | batch, merging | batch, incremental | batch, incremental, update-in- |
supported | checkonly, enforce | checkonly, enforce | place, checkonly, enforce |
Target | Key-based | Key-based, | Key-based, least-change, |
resolution | check-before-enforce | mandatory create, | |
check-before-enforce | |||
Traces | Non-persistent | None | Persistent/non-persistent |
Execution | Simulation via | Simulation via | Code-generation |
CPN tools | model-checker | in 3GL | |
Analysis | Termination, | Debugging | Confluence, |
confluence, | consistency, | ||
consistency, | debugging | ||
debugging | |||
Precise | \(\times \) | ||
correctness | |||
criteria | |||
Restrictions | No calling | No element creation in | No calling |
cycles, OCL | non-top relations | cycles | |
restrictions |