Query translation and optimisation for complex value databases
Abstract
This thesis considers the theory of database queries on the complex value data model
extended with external functions. In modern intelligent database systems, we expect
that query systems be able to handle a wide range of calculus formulas correctly and
efficiently. Accordingly, they will require general query translators and efficient optimisers.
Motivated by these concerns, this thesis undertakes a· comprehensive study of
query evaluation in the complex value model and investigates the following issues:
• identifying recursive sets of complex value formulas which define domain independent
queries;
• implementing complex value calculus queries with the incorporation of functions;
• solving the problem of how to process join operation in complex value databases;
and
• investigating some algebraic properties concerning nested relational operators.
The first part of this thesis extends some classical properties of the relational theory -
particularly those related to query safety - to the context of complex value databases
with fixed external functions and investigates the problem of how to implement calculus
queries. Two notions of syntactic criteria for queries which guarantee domain
independence, namely, embedded evaluable and embedded allowed, are generalised for
this data model. This thesis shows that all embedded-allowed calculus (or fix-point)
queries are external-function domain independent and continuous.
This thesis discusses the topic of "embedded allowed database programs" and proves
that embedded allowed stratified programs satisfying certain constraints are embedded
domain independent. It also develops an algorithm for translating embedded allowed
queries into equivalent algebraic expressions as a basis for evaluating safe queries in all
calculus-based query classes. The second part of this thesis considers the issue of query optimisation for nested
relational databases. Within a restricted set of nested schema trees, a join operator,
called P-join, is proposed. The P-join operator does not require as many restructuring
operators and combines the advantages of the extended natural join and recursive join
for efficient data access. A P-join algorithm which takes advantage of a decomposed
storage model and various join techniques available in the standard relational model
to reduce the cost of join operation in nested relational databases is also proposed.
Finally, this thesis investigates some algebraic properties of nested relational operators
which are useful for query optimisation in the nested relational model and outlines
a heuristic optimisation algorithm for nested relational expressions by adopting algebraic
transformation rules developed in this thesis and previous related work.