Object Indexing

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.

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.


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.


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.


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.