Object Indexing
This is a fundamental MT design pattern.
Summary
All instances of
an entity are
indexed by a primary key value, to permit efficient
lookup of instances by their key.
Application conditions
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.
Solution
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
v: cmap.get(v).
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.
Benefits
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
reduced.
This pattern also assists in the separation of a
transformation into phases.
Disadvantages
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
language/implementation.
The use of indexing increases
memory requirements.
Applications and examples
The
pattern is applicable to all
categories of transformation.
The concept of key
attribute in QVT-R is
an example
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
general applicability.
Related patterns
The pattern can be
regarded as an implementation-level application of
the Auxiliary Metamodel pattern.
It can
be used by Phased Construction and its
specialisations
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
ETL.
However, lookup using traces will be
less efficient unless specialized
support is provided by a transformation
language, since select/any
searches
over the set of traces are necessary.