mto@GTE.COM (Tamer Ozsu) (01/18/91)
The following Ph.D. thesis is available as a technical report from Department of Computing Science, University of Alberta (Canada). Technical Report TR90-33 QUERIES AND QUERY PROCESSING IN OBJECT-ORIENTED DATABASE SYSTEMS by Dave D. Straube ABSTRACT Object-oriented database systems have been proposed as an effective solution for providing the data management facilities of complex applications. Proving 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. To obtain a copy of this report, either (1) send email to britta@cs.ualberta.ca, or (2) write to Britta Nielsen Department of Computing Science University of Alberta Edmonton, Alberta Canada T6G 2H1 (3) via anonymous ftp from menaik.cs.ualberta.ca (129.128.4.241). Instead of password, you will be asked for an "ident" which should be the id of the machine you are ftp'ing from. Enter directory ~ftp/pub/dbms There are two compressed files: TR90-33.dvi.Z and TR90-33.ps.Z. The dvi file is larger but may be easier to print at other sites. You have to uncompress these files after you have ftp'ed them. -- M. Tamer Ozsu Telephone: (617) 466-2098 GTE Laboratories Fax: (617) 290-0628 40 Sylvan Road Internet: mto@gte.com Waltham, MA 02254
mto@gte.com (Tamer Ozsu) (01/18/91)
The following Ph.D. thesis is available as a technical report from University of Alberta, Department of Computing Science. Technical Report TR90-33 QUERIES AND QUERY PROCESSING IN OBJECT-ORIENTED DATABASE SYSTEMS by Dave D. Straube ABSTRACT Object-oriented database systems have been proposed as an effective solution for providing the data management facilities of complex applications. Proving 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. To obtain a copy of this report, either (1) send email to britta@cs.ualberta.ca, or (2) write to Britta Nielsen Department of Computing Science University of Alberta Edmonton, Alberta Canada T6G 2H1 (3) via anonymous ftp from menaik.cs.ualberta.ca (129.128.4.241). Instead of password, you will be asked for an "ident" which should be the id of the machine you are ftp'ing from. Enter directory ~ftp/pub/dbms There are two compressed files: TR90-33.dvi.Z and TR90-33.ps.Z. The dvi file is larger but may be easier to print at other sites. You have to uncompress these files after you have ftp'ed them. -- M. Tamer Ozsu Telephone: (617) 466-2098 GTE Laboratories Fax: (617) 290-0628 40 Sylvan Road Internet: mto@gte.com Waltham, MA 02254