Indexing techniques for queries on nested objects

In relational databases, an attribute of a relation may only have a single primitive value, making it cumbersome to model complex artifacts of interest to a wide variety of applications. An object-oriented and nested relational model of data removes this difficulty by introducing the notion of nested objects, that is, by allowing the value of an object to be another object or a set of other objects. This means that a class (relation) consists of a set of attributes, and the values of the attributes are objects that belong to other classes (relations); that is, the definition of a class (relation) forms a hierarchy of classes (relations). All attributes of the nested classes are nested attributes of the root of the hierarchy. Just as a secondary index on an attribute or a combination of attributes is useful for expediting the evaluation of a query on a relation, a secondary index is useful for evaluating queries on a nested class in an object-oriented database or a nested relation in a nested relational database. In this paper, we introduce three index organizations for use in the evaluation of a query in an object-oriented or nested relational database. We develop detailed models of the three indexes. Using the models, we evaluate the storage cost, retrieval cost, and update cost of these indexes, and make a number of observations about the use of these indexes for evaluating queries for object-oriented or nested relational databases.