Indexing OODB instances based on access proximity

Abstract

Queries in Object-Oriented Databases (OODBs) may be asked with respect to different class scopes: a query may either request for object-instances which belong exclusively to a given class c, or those which belong to any class in the hierarchy rooted at c. To facilitate retrieval of objects both from a single class, as well as from multiple classes in a class hierarchy, we propose a multi-dimensional class hierarchy index called the χ-tree. The χ-tree dynamically partitions the data space using both the class and indexed attribute dimensions by taking into account the semantics of the class dimension as well as access patterns of queries. Experimental results show that it is an efficient index.