A QUERY PROCESSOR FOR OODB

Abstract

One of the essential properties of object-oriented database systems is encapsulation, whereby information in any class is hidden from users and the only way to access the information is through methods provided in that class. Methods are procedures written in a programming language. The computational completeness of the programming language makes methods significantly more expressive than the relational algebra. However, we still find it useful to provide an interface to object-oriented database management systems (OODBMS) that allows users to pose high level queries in a declarative language, much like SQL in the relational context. Such a language has limited expressive power but, on the other hand, allows users to interact with the OODBMS using the schema and is ideal for non-expert users. A query processor is required to support this query facility. The reason is, when low level procedural query languages are used, physical data access paths must be specified and the execution efficiency of a query depends on how well the user expressed it. On the other hand, high level declarative query languages allow users to express queries without reference to access paths. In this case the system is responsible for the efficient processing of queries. This function is performed by the query processor. In order not to circumvent the encapsulation property, queries have to be mapped to invocations of methods, the only authorized means to access information in the database. This thesis presents a query processor for an OODBMS. The essential task of the query processor is to translate declarative queries into query evaluation plans (QEP) - sequences of method invocations that can be evaluated directly by the OODBMS. When a query is received, object classes and relationships may be added to the query, based on the superclass-subclass and composite-component relationships involving the object classes requested. These modifications are necessary to ensure the correctness of the results. Four preprocessing rules are provided for this purpose. After that, semantic knowledge are used to transform the query into a new query that produces the same answer as the original query, but requires less resources to execute. This semantic optimization process is made possible by the provision of three optimization rules - restriction elimination, restriction introduction, and class elimination. As semantic optimization may increase the query processing overhead significantly, efficiency is one of the primary considerations in implementing it. An efficient algorithm for the implementation will be described. The final step involves the generation of the QEP, where the query is translated into a sequence of elementary operations and commands. Each elementary operation is subsequently replaced by a method invocation. Every class must provide at least one method to implement each elementary operation, and the method that is most efficient in the query context will be selected. The resulting sequence of method invocations makes up the QEP, and is sent to the OODBMS for evaluation. A prototype query processor has been built and preliminary simulation studies show that our design is feasible.