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 requirement is one salient feature of object orientation. Access to a complex object involves true 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