Restrict Input Ranges
This is an optimisation pattern.
Summary
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).
Solution
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.
Benefits
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 &
p.name < q.name &
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.