The partial-order tree: a new structure for indexing on complex attributes in object-oriented databases

The paper focuses on the indexing of non-primitive (complex) values of attributes in an object management system. A new index structure for indexing on set (multivalued) attributes is proposed. This structure is based on a partial order imposed on the values of the indexed attribute, which are subsets of a set of primitive values. It is shown that the proposed index allows the system to efficiently perform typical set operators that are postulated to be applied in object query languages (is-equal, is-subset, is-superset), without performing any costly operations on lists of object identifiers that would be necessary in traditional index structures. The new index structure, called partial-order tree, is described and algorithms performing the set operators are outlined.