Vertical class partitioning and complex object retrieval in object oriented databases

Next generation database applications require extra modeling supports, higher performance requirements and new design techniques. Object oriented database (OODB) technology has been introduced to support the next generation database applications, as it provides rich modeling features like, encapsulation of methods, inheritance, object identity, arbitrary data types and complex objects. For efficient processing of the next generation database applications, however, there is a need to research techniques for performance oriented OODB design, because we can not simply adopt conventional database design techniques which do not fully consider physical characteristics of the schema, the occurrences of the underlying database data and the application workload. Class partitioning is the process of clustering relevant data accessed by an application into a class. This is a relevant and important research topic for OODBs, because it allows to reduce the amount of irrelevant data accessed, thus reducing the number of disk accesses. In this thesis, the topic of vertical class partitioning in OODBs is thoroughly investigated through an analytical approach, and a number of experiments are conducted to evaluate and demonstrate the "goodness" of this design technique. Our experiments show that there exists an optimal number of vertical fragments for a class collection, and vertical partitioning can give rise to substantial savings in the number of disk accesses. A Cost-Driven Algorithm (CDA) has been developed, which guarantees to produce the cost optimal partitioning scheme based on exhaustive enumeration, but it has a high computational complexity. We have therefore developed a Hill-Climbing Heuristic Algorithm (HCHA) based on both the cost-based and affinity-based approaches. This algorithm uses the initial solution generated by affinity-based algorithm and incrementally evolves it to generate mostly optimal or near optimal vertical class partitioning scheme. As performance is a key factor for the success of OODB systems, efficient complex object retrieval in OODB systems has also become a relevant problem. This thesis further addresses the issue of complex object retrieval by introducing structural join index hierarchy (SJIH) mechanisms that mimic the class composition hierarchy of the complex objects to provide direct access to complex objects and their component objects. We show that SJIH can provide efficient and flexible access to complex objects, and also unify various previous indexing methods proposed for OODBs. Our analytical experimental results demonstrate the effectiveness of the SJIH mechanisms over pointer traversal and other indexing mechanisms, such as Multi-index and Nested index. An algorithm has been developed to select, for a given set of queries, optimal or near-optimal SJIH. Finally, we show how vertical class partitioning can be applied to further improve the effectiveness of SJIH mechanisms