Index Data Structures In Object Oriented Databases PDF Download

Abstract: "Object-oriented databases have been developed to allow applications to store persistent data in the form of objects. As in conventional databases, object-oriented databases need to support queries that allow associative access to data by describing a property of the data of interest. In particular, they should support queries over user-defined sets based on user-defined functions that compute the property of interest. To make such function-based queries run faster, we must support function- based indexes where the keys are these computed properties. Function-based indexes are harder to maintain than indexes in conventional databases because mutations that affect keys can be done without accessing an element of the indexed set. This dissertation presents a new function-based indexing scheme for object-oriented databases. The indexes are maintained by recording registration information for objects that indicate when index entries are affected and having operations that modify objects check for registrations to determine if an index needs to be updated. Our approach uses a combination of declared information that indicates how object methods affect each other and runtime information gathered during key computation, so that we register only the objects whose modifications can affect an index and only the operations that might affect an index entry check for registration information. Recomputing index entries only when there is a modification that might affect an index comes at the cost of extra space for the registration information and extra time to check registration information during modifications. To quantify these costs, we simulated three implementations of our scheme on various performance benchmarks and analyzed several others. We show that function-based indexes are very useful in oject-oriented databases and do not adversely affect system performance, but they do have a high space cost. This work is being done in the context of the Thor distributed, object-oriented database system [42,43]. Thor has features that complicate index use and maintenance. It has a client-server architecture with caching at both clients and servers. It also uses an optimistic concurrency control scheme. This dissertation presents a design for integrating index use and maintenance into Thor. We discuss the impact of adding indexes on Thor's system architecture and the impact that Thor's system architecture has on the performance of our indexing scheme, and we present predicate validation, a new optimistic concurrency control scheme."