Query evaluation in deductive and object-oriented databases
Zhaohui Xie · Summit (Simon Fraser University) · 1995
The development of deductive and object-oriented database (DOOD) systems by integration of the object-oriented paradigm with the deductive paradigm represents a promising direction in the construction of the next generation of database systems.This thesis addresses the issues of query evaluation in DOOD systems and presents some promising approaches to the problems in DOOD query evaluation.First, a DOOD data model and its query language are presented to demonstrate the salient features supported by DOOD and to serve as research vehicles for the investigation of DOOD query evaluation.After a comparative survey on query evaluation methods for relational databases, deductive databases and object-oriented databases, the impact of DOOD models and languages on query evaluation is discussed.A list of open and not well-solved problems is identified as a research guide towards DOOD query evaluation, which in turn motivates the research efforts presented in this thesis.An efficient navigation structure, called the join index hierarchy, is proposed to handle the problem of "pointer-chasing" or "gotos' on disks" in exploring logical relationships among complex objects.Effective optimization strategies are introduced to employ the constraint conditions expressed in the form of complex selection and join conditions for efficient set-oriented navigations and to exploit the common navigations among a query and encapsulated methods for efficient query evaluation.The query-independent compilation and chain-based evaluation, developed for deductive recursive query evaluation, are extended to process a class of DOOD recursions.