Combining Indexing Technique with Path Dictionary for Nested Object Queries Wang-Chien Lee Dik Lun Lee* Dept. of Computer & Information Science Department of Computer Science The Ohio State University Hong Kong University of Science & Technology Columbus, Ohio 43210-1277, USA Clear Water Bay, Hong Kong wleeQcis.ohio-state.edu, FAX: 614-292-2911 dleeQcs.ust.hk, FAX: 852-358-1477 Abstract A path dictionary encodes the connections among objects in the ag- gregation hierarchy. It has been shown to be an efficient mechanism for supporting nested object queries [6]. In this paper, we present a new method, called the path dictionary index method, which com- bines indexing techniques with the path dictionary method. We de- scribe the operations of the new mechanism and develop cost mod- eis for its storage overhead and query and update costs. Finally, we compare the new mechanism to the path index method 131. The result shows that the path dictionary index method is significantly better than the path index method over a wide range of parameters. 1 Introduction The concept of class allows object-oriented database sys- tems (OODBSs) to model complex data more precisely and conveniently than the relational data model. A class may consist of simple attributes (e.g., of domain integer or string) and complex attributes with user-defined classes as their domains. Since a class C may have a complex attribute with domain C’, an aggregation relationship can be established between C and C’. Using arrows connect- ing classes to represent aggregation relationship, a directed graph, called the aggregation hierarchy, may be built to show the nested structure of the classes. Figure 1 is an ex- ample of an aggregation hierarchy, which consists of four classes, Person, Vehicle, Person-Name, and Company. The class Person has three simple attributes, SSN, Residence and Age, and two complex attributes, Owns and Name. The domain classes of the attributes Owns and Name are Vehicle and Person-Name, respectively. The class Vehicle is de- fined by three simple attributes, Id, Color, and Model, and a complex attribute Manufacturer, which has Company as its domain. Company and Person&me each consists of two simple attributes. Every object in an OODBS is identified by an object identifier (OID). The OID of an object may be stored as attribute values of other objects. If an object 0 is refer- enced as an attribute of object O’, 0 is said to be nestedin Proceedings of the Fourth International Conference on Database Systems for Advanced Applications Ed. Tok Wang Ling and Yoshifumi Masunaga (DASFAA’BS) Singapore, April 10-13, 1995 @ World Scientific Publishing Co. Pte Ltd ~ Vohlcle Figure 1: Aggregation hierarchy. 0’ and 0’ is referred to as the parent object of 0. Objects are nested according to the aggregation hierarchy. OODBSs support queries involving nested objects. These queries are called nested queries. There are two ba- sic approaches to evaluating a nested query: top-down and bottom-up evaluations. The top-down approach traverses the objects starting from an ancestor class to a nested class. Since the OID in a parent object leads directly to a child object, this approach is also called a forward traversal ap- proach. On the other hand, the bottom-up method, also known as backward traversal, traverses up the aggregation hierarchy. A child object, in general, does not carry the OID of (or an inverse reference to) its parent object. There- fore, in order to identify the parent object(s) of an object, we have to compare the child object’s OID against the cor- responding complex attribute in the parent class. This is similar to a relational join when we have more than one child object to start with. Mixed evaluation is a combi- nation of the top-down and bottom-up approaches, which is often used for complex queries. Note that when ev- ery reference from an object 0 to another object 0’ (e.g., Owns) is accompanied with an inverse reference from 0’ to 0 (e.g., Owned-by), the aggregation hierarchy becomes bi- directional, resulting in no difference between the top-down and the bottom-up approaches. In this paper, however, we assume there is no inverse references. Many access methods have been proposed to support the complex queries in OODBSs. In particular, three tech- niques, namely, indexing [1,2,3], signature file [4,7] and path dictionary [6], have been proposed recently. (A simi- lar idea to path dictionary has also been used in [5]). In this paper, we further develop our previous implementation of the path dictionary approach [6] and combine it with index- *The author is on leave from the Department of Computer and Information Science, The Ohio State University, Columbus, OH 43210, USA. 107ing, resulting in a new object access mechanism, the path ‘dictionary index (PDI). We find that the storage overhead and the retrieval and update costs of PDI is better than that of the path index [3]. There are many kinds of nested queries. However, an ac- cess method doesn’t necessarily support all of them. Even with the same access method, different kinds of queries may be evaluated differently. To facilitate our discussion, we define target classes as the classes from which objects are retrieved and predicate classes as the classes involved in the predicates of the query. We classify nested queries by the folIowiug factors: 1. Relative positions of the target and predicate classes on the aggregation hierarchy: l TP: The target class is an ancestor class of the predicate classes. l PT: The target class is a nested class of the pred- icate classes. l MX: The target class is an ancestor class of some predicate class and a nested class of some predi- cate