PATH DICTIONARY - A NEW ACCESS METHOD FOR QUERY-PROCESSING IN OBJECT-ORIENTED DATABASES

We present a new access method, called the path dictionary index (PDI) method, for supporting nested queries on object-oriented databases. P DI supports object traversal and associative search, respectively, wit h a path dictionary and a set of attribute indexes built on top of the path dictionary. We discuss issues on indexing and query processing i n object-oriented databases; describe the operations of the new mechan ism; develop cost models for its storage overhead and query and update costs; and compare the new mechanism to the path index method. The re sult shows that the path dictionary index method is significantly bett er than the path index method over a wide range of parameters in terms of retrieval and update costs and that the storage overhead grows slo wly with the number of indexed attributes.