Decompose Complex Navigations

This is an optimisation pattern.


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.


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.


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,