Design of a new indexing organization for a class-aggregation hierarchy in object-oriented databases

Abstract

In an object-oriented database, a class consists of a set of attributes, and the values of the attributes are objects that belong to other classes; that is, the definition of a class forms a class-aggregation hierarchy of classes. A branch of such a hierarchy is called a path. Several index organizations have been proposed to support object-oriented query languages, including multiindex, join index, nested index and path index. All the proposed index organizations are helpful only for a query which retrieves the objects of the root class of a given path using a predicate which specifies the value of the attribute at the end of the path. In this paper, we propose a new index organization for evaluating queries, called full index, where an index is allocated for each class and its attribute (or nested attribute) along the path. From the analysis results, we show that a full index can support any type of query along a given path with a lower retrieval cost than all the other index organizations. Moreover, to reduce the high update cost for a long given path, we split the path into several subpaths and allocate a separate index to each subpath. Given a path, the number of subpaths and the index organization of each subpath define an index configuration. Since a low retrieval cost and a low update cost are always a trade-off in index organizations, we also propose cost formulas to determine the index configuration which can provide the best performance for various applications by taking into account various types of queries along a given path and a set of queries with more than one nested predicate along a given path.