Restrict Input Ranges

This is an optimisation pattern.


Restrict the ranges of input variables in a rule, based upon necessary conditions which these must satisfy, in order to optimize the rule's implementation.

Application conditions

The pattern is relevant if there are one or more quantifier range expressions in the antecedent of a rule which can be made more restrictive because of further matching conditions which the variables must satisfy for the rule to be applied. By restricting the quantifier ranges the rule can be made more efficient.

An indication that the pattern is relevant is if there are two or more input variables ranging over entity types:

for s1 : S1; s2 : S2 satisfying P

Such a rule will have worst case time complexity at least card(S1) * card(S2).


A range expression a : R which selects an element a of an entity type or collection R can be replaced by a : e, where e is a small subset of R, if the remainder P of the matching conditions implies that e->includes(a). In the above example, s2 : S2 could be replaced by s2 : s1.f where f is a feature or composition of features based on s1.


The number of elements that are searched for a match for a in the optimized version is less than in the original. Only elements that can possibly be a match are considered, irrelevant elements are not evaluated, reducing expression evaluation time.

Applications and examples

The pattern is applicable to all categories of transformation.

In the movies database case study solution using UML-RSDS (Lano et al, 2014), the rule to find pairs of actors who have appeared in at least 3 movies together has the unoptimized form:

p : Person & q : Person & < &
comm = p.movies /\ q.movies & comm.size > 2 =>
Couple->exists( c | p : c.p1 & q : c.p2 & c.commonMovies = comm )

This can be optimized by restricting the range of q from Person to p.movies.persons because the conditions comm = p.movies /\ q.movies & comm.size > 2 imply that q : p.movies.persons.

Related patterns

The Decompose Complex Navigations pattern also aims to reduce the cost of searching input ranges, and both patterns can be applied together. The usual programming tactic of placing more restrictive conditions earlier in a series of conjuncts can also be used for the antecedents of rules, under the assumption that a `shortcut' evaluation policy for conjunction is used in the implementation.

The pattern could evolve to Filter Before Processing: a pre-filter could be introduced to discard from the input model all elements which could not satisfy any of the transformation rule conditions.

(Lano et al., 2014) K. Lano, S. Yassipour-Tehrani, Solving the Movie Database Case with UML-RSDS, TTC 2014.