Queries and Query Processing in Object-Oriented Database Systems

• Author(s) / Creator(s)

  • Straube, Dave D.

• Technical report TR90-33. Object-oriented database systems have been proposed as an effective solution for providing the data management facilities of complex applications. Proving the veracity of this claim and the investigation of related issues such as query processing have been hampered by the absence of a formal object-oriented data and query model. This thesis presents a model of queries for object-oriented databases and uses it to develop a query processing methodology. Two formal query languages are developed: a declarative object calculus and a procedural object algebra. The query processing methodology assumes that queries are initially specified as object calculus expressions. Algorithms are developed to prove the safety of calculus expressions and to translate them to their object algebra equivalents. Object algebra expressions represent sets of objects which may not all be of the same type. This can cause type violations when the expressions are nested. A set of type inference rules is presented which determines the type consistency of algebra expressions. The next step of the query processing methodology is logical optimization. Algebra expressions are optimized by applying equivalence preserving rewrite rules. Both algebraic and semantic rewrite rules are developed. Applicability conditions for algebraic rules are determined by pattern matching of query subexpressions while semantic rules additionally require that various conditions on the database schema be met. Thus the semantic rewrite rules are unique to a specific application. The final step in query processing is generation of access plans. The interface to an object manager subsystem which performs primitive operations on streams of objects is defined. Join enumeration algorithms from the relational model are adapted and extended to translate algebra expressions into access plans which are sequences of object manager operations. | TRID-ID TR90-33

• Date created

  1990

• Subjects / Keywords

  • Database Systems

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3ST89

• License

  Attribution 3.0 International