Decompose Complex Navigations
This is an optimisation pattern.
Summary
Decompose complex navigation
expressions in antecedent tests
of a rule, into several simpler
navigations, in order to optimise the rule
implementation.
Application conditions
The pattern is relevant if there is a
quantifier range expression e : r
in the antecedent of a rule where r
involves composition of two or more
collection-valued association ends,
and only one element e needs to be
selected from the quantifier range.
A test
e : f1.f2 which selects an element e of the
composition of two or more collection-valued
association ends is potentially
inefficient to compute, because the
composition may involve
the construction of large collections of elements.
Solution
Decompose the test into two
or more simpler matching tests:
s : f1 and e : s.f2
where s is a new variable identifier, not occuring
elsewhere in the rule.
Benefits
If the size of f1 is typically
M and that of f2 is N, then only M + N
elements are searched for an initial match for e in
the optimised version, in contrast to M*N elements
in the unoptimised version.
Therefore, the optimisation is beneficial
particularly for rules for which there is a
high likelihood of finding a matching e in any
particular s.f2 set, and where only
one element needs to be selected: this
second condition
is typically the case for fixed-point
implementations of a rule.
Both execution time and memory usage
will potentially be reduced.
Applications and examples
The
pattern is applicable to all
categories of transformation, but is
particularly relevant to refactorings or
other update-in-place transformations
which modify some data that they also
read:
in such cases the implementation
is a fixed-point iteration
which selects an element from
a set of candidates,
applies the rule, and then selects
another element, from a possibly changed
set of candidates.
In the class diagram
rationalisation case study
solution using UML-RSDS (Kolahdouz-Rahimi et al, 2013),
two rules include
an antecedent test
att : specialization.specific.ownedAttribute
to select some attribute att
of a subclass of the current
class. This can be optimized by writing
s : specialization.specific and att : s.ownedAttribute.
Related patterns
The
Usage of iterators pattern in
(Cuadrado, 2009) considers the related
problem of selecting any value in a
collection that satisfies a condition,
without computing the entire collection
of such values. The Restrict Input
Ranges pattern is another technique for
reducing condition evaluation time,
and may be used together with Decompose
Complex Navigations.
(Cuadrado et al., 2009) J. Cuadrado, J. Molina,
Modularisation of model transformations
through a phasing mechanism, Software Systems
Modelling, Vol. 8, No. 3, pp. 325--345, 2009.
(Kolahdouz-Rahimi et al., 2013)
S. Kolahdouz-Rahimi, K. Lano,
S. Pillay, J. Troya, P. Van Gorp,
Evaluation of
model transformation approaches for
model refactoring, Science of
Computer Programming, 2013,
http://dx.doi.org/10.1016/j.scico.2013.07.013.