Object Skeletons: An Efficient Navigation Structure For Object-Oriented Database Systems


One common requirement of object-oriented applications is the efficient support of complex objects. This requirements is one salient feature of object orientation. Access to a complex object involves two basic steps: (1) The predicate is evaluated to identify the complex object. (2) The qualified complex object is traversed to retrieve the required components. Over the past few years, several indexing schemes have been developed to support step 1. However, support structures for the efficient execution of step 2 has received little attention. To address this problem, we propose, in this paper, using networks of unique object identifiers (object skeletons) as a navigational structure to aid query processing of complex objects. In this approach, skeletons of complex objects contain only the semantic information. Once a skeleton has been loaded into memory, navigation along the complex object can be done with no further disk access. Furthermore, since the descriptive information of an object is stored separately from its object identifier, it is free to migrate anywhere in the database. To assess the efficiency of this approach, we built a prototype and compared its performance to some recently proposed indexing schemes. The results of our study indicate that this technique can provide very impressive savings of both space and time.

Publication Date


Publication Title

Proceedings - International Conference on Data Engineering

Number of Pages


Document Type

Article; Proceedings Paper



Personal Identifier


Socpus ID

0028292852 (Scopus)

Source API URL


This document is currently not available here.