| So far OODB query optimization is hampered by lacking a proper object algebra for laying the basis of equivalent query rewritings. Relational algebra is well-accepted as the foundation of relational query optimization. What should be the object algebra for OODB query processing?;There are several object algebras presented. The common feature of these algebras is that the operands are collections of complex objects or collections of complex values. This leads to complicated algebraic operators and algebraic laws. When these algebras are used as the internal representations for front-end queries, query processing can not be done efficiently due to the complexity of the algebras. In this dissertation we present an object algebra, called O-Algebra, for processing OODB queries. Operands of O-Algebra are collections of uniform internal objects whose components have only one level nesting-complex components are replaced by their substitutes, Oids. Due to uniform operands and simple operators, a small yet powerful set of O-Algebra laws can be obtained, which is important for query optimizations by algebraic rewritings. Converting front-end OODB queries to internal representations is also an important issue. However the systematic conversion method has not been reported in the literature. In this dissertation, we present a formal approach to transform OQL queries to O-Algebra queries.;Reducing OODB nested queries can lead to equivalent, but more efficient queries. Many researches have been done on the topic but so far no methods can reduce nested queries in all cases. We propose a complete solution which can reduce all OQL nested queries. This method is superior to other methods in three aspects: (1) completeness, (2) efficient unnesting results, and (3) simple reduction procedure. The method has been implemented.;Query optimizations using O-Algebra rewriting are also studied in this dissertation. Two unique features of O-Algebra, (1) the availability of virtual extents and (2) simple operands, make optimization rewritings more powerful, easier, and more efficient. Some typical OODB query optimizations by using O-Algebra rewriting rules are presented. Due to the complete solution of reducing nested queries, the optimizations can consider components not only from one query block, but from all query blocks. A general procedure for these optimizations is presented. |
