This is a fundamental MT design pattern.
All instances of
an entity are
indexed by a primary key value, to permit efficient
lookup of instances by their key.
The pattern is relevant when frequent access is
needed to instances or sets of
instances based upon some
unique identifier attribute (a primary key).
Lookup of instances
by means of an expression
of the form
E.allInstances()->select( id = v )->any(),
E.allInstances()->any( id = v )
or E.allInstances()->select( v->includes(id) )
can be inefficient,
with a worst case
time complexity proportional
to the number of elements of E.
Maintain an index map data structure cmap : Map(IndType, C)
that maps from the type IndType of
the primary key, to the entity C
to be indexed.
Access to a C object with key value
v is obtained by applying cmap to
When a new C object
c is created, add the mapping
c.ind = c to cmap. When
c is deleted, remove this mapping from cmap.
The pattern substantially improves the efficiency of
object lookup, making this a constant-time operation
independent of the size of the domain C. Syntactic complexity is also
This pattern also assists in the separation of a
transformation into phases.
The key value of an object
should not be changed after its creation: any such change
will require an update of cmap, including a check that
the new key value is not already used in another object.
Support for indexing needs to be
provided by the transformation
The use of indexing increases
Applications and examples
pattern is applicable to all
categories of transformation.
The concept of key
attribute in QVT-R is
of the use of this pattern.
The pattern is a good candidate for
inclusion as an inbuilt facility in any
transformation language, due to its
The pattern can be
regarded as an implementation-level application of
the Auxiliary Metamodel pattern.
be used by Phased Construction and its
to look up the target elements
corresponding to previously-processed source model
elements. It can be
used by Unique Instantiation
to look up
elements to avoid duplicating them.
It is related to the Cache Management pattern.
An alternative strategy to look up target model elements
is to use an explicit transformation trace facility, as
in Kermeta and Viatra,
or implicit traces as in ATL or
However, lookup using traces will be
less efficient unless specialized
support is provided by a transformation
language, since select/any
over the set of traces are necessary.