The search space for query plans is defined and enumerated in a novel manner: the chase phase rewrites the original query into a "universal" plan that integrates all the access structures and alternative pathways that are allowed by applicable constraints. Then, the backchase phase produces optimal plans by eliminating various combinations of redundancies, again according to constraints.

This method is applicable (sound) to a large class of queries, physical access structures, and semantic constraints. We prove that it is in fact complete for "path-conjunctive" queries and views with complex objects, classes and dictionaries, going beyond previous theoretical work on processing queries using materialized views.

[1]

Serge Abiteboul , Paris C. Kanellakis : Object Identity as a Query Language Primitive. SIGMOD Conference 1989 : 159-173

[2]

Serge Abiteboul , Richard Hull , Victor Vianu : Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents

[3]

Sibel Adali , K. Selçuk Candan , Yannis Papakonstantinou , V. S. Subrahmanian : Query Caching and Optimization in Distributed Mediator Systems. SIGMOD Conf. 1996 : 137-148

[4]

Alfred V. Aho , Catriel Beeri , Jeffrey D. Ullman : The Theory of Joins in Relational Databases. TODS 4(3) : 297-314(1979)

[5]

Alfred V. Aho , Yehoshua Sagiv , Jeffrey D. Ullman : Efficient Optimization of a Class of Relational Expressions. TODS 4(4) : 435-454(1979)

[6]

...

[7]

Malcolm P. Atkinson , Christophe Lécluse , Paul Philbrow , Philippe Richard : Design Issues in a Map Language. DBPL 1991 : 20-32

[8]

Catriel Beeri , Yoram Kornatzky : Algebraic Optimization of Object-Oriented Query Languages. TCS 116(1&2) : 59-94(1993)

[9]

Catriel Beeri , Moshe Y. Vardi : A Proof Procedure for Data Dependencies. JACM 31(4) : 718-741(1984)

[10]

Elisa Bertino : A Survey of Indexing Techniques for Object-Oriented Database Management Systems. Query Processing for Advanced Database Systems, Dagstuhl 1991/1994 : 383-418

[11]

Elisa Bertino , Won Kim : Indexing Techniques for Queries on Nested Objects. TKDE 1(2) : 196-214(1989)

[12]

R. G. G. Cattell (Ed.): The Object Database Standard: ODMG 2.0. Morgan Kaufmann 1997

[13]

Upen S. Chakravarthy , John Grant , Jack Minker : Logic-Based Approach to Semantic Query Optimization. TODS 15(2) : 162-207(1990)

[14]

Ashok K. Chandra , Philip M. Merlin : Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977 : 77-90

[15]

Surajit Chaudhuri , Ravi Krishnamurthy , Spyros Potamianos , Kyuseok Shim : Optimizing Queries with Materialized Views. ICDE 1995 : 190-200

[16]

Chung-Min Chen , Nick Roussopoulos : The Implementation and Performance Evaluation of the ADMS Query Optimizer: Integrating Query Result Caching and Matching. EDBT 1994 : 323-336

[17]

Mitch Cherniack , Stanley B. Zdonik : Rule Languages and Internal Algebras for Rule-Based Optimizers. SIGMOD Conf. 1996 : 401-412

[18]

...

[19]

Sophie Cluet , Claude Delobel : A General Framework for the Optimization of Object-Oriented Queries. SIGMOD Conference 1992 : 383-392

[20]

Leonidas Fegaras , David Maier : An Algebraic Framework for Physical OODB Design. DBPL 1995 : 9

[21]

...

[22]

Daniela Florescu , Louiqa Raschid , Patrick Valduriez : A Methodology for Query Reformulation in CIS Using Semantic Knowledge. IJCIS 5(4) : 431-468(1996)

[23]

Goetz Graefe , Richard L. Cole , Diane L. Davison , William J. McKenna , Richard H. Wolniewicz : Extensible Query Optimization and Parallel Execution in Volcano. Query Processing for Advanced Database Systems, Dagstuhl 1991/1994 : 305-335

[24]

John Grant , Jarek Gryz , Jack Minker , Louiqa Raschid : Semantic Query Optimization for Object Databases. ICDE 1997 : 444-453

[25]

Yannis E. Ioannidis , Eugene Wong : Query Optimization by Simulated Annealing. SIGMOD Conference 1987 : 9-22

[26]

B. Paul Jenq , Darrell Woelk , Won Kim , Wan-Lik Lee : Query Processing in Distributed ORION. EDBT 1990 : 169-187

[27]

Arthur M. Keller , Julie Basu : A Predicate-based Caching Scheme for Client-Server Database Architectures. PDIS 1994 : 229-238

[28]

Alfons Kemper , Guido Moerkotte : Access Support in Object Bases. SIGMOD Conference 1990 : 364-374

[29]

Alfons Kemper , Guido Moerkotte : Advanced Query Processing in Object Bases Using Access Support Relations. VLDB 1990 : 290-301

[30]

Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv , Divesh Srivastava : Answering Queries Using Views. PODS 1995 : 95-104

[31]

Alon Y. Levy , Divesh Srivastava , Thomas Kirk : Data Model and Query Evaluation in Global Information Systems. JIIS 5(2) : 121-143(1995)

[32]

Leonid Libkin , Rona Machlin , Limsoon Wong : A Query Language for Multidimensional Arrays: Design, Implementation, and Optimization Techniques. SIGMOD Conf. 1996 : 228-239

[33]

Guy M. Lohman , Bruce G. Lindsay , Hamid Pirahesh , K. Bernhard Schiefer : Extensions to Starburst: Objects, Types, Functions, and Rules. CACM 34(10) : 94-109(1991)

[34]

David Maier , Jacob Stein : Indexing in an Object-Oriented DBMS. OODBS 1986 : 171-182

[35]

Yannis Papakonstantinou , Hector Garcia-Molina , Jennifer Widom : Object Exchange Across Heterogeneous Information Sources. ICDE 1995 : 251-260

[36]

Yannis Papakonstantinou , Ashish Gupta , Laura M. Haas : Capabilities-Based Query Rewriting in Mediator Systems. Distributed and Parallel Databases 6(1) : 73-110(1998)

[37]

Lucian Popa , Val Tannen : An Equational Chase for Path-Conjunctive Queries, Constraints, and Views. ICDT 1999 : 39-57

[38]

Xiaolei Qian : Query Folding. ICDE 1996 : 48-55

[39]

Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman : Answering Queries Using Templates with Binding Patterns. PODS 1995 : 105-112

[40]

Raghu Ramakrishnan : Database Management Systems. WCB/McGraw-Hill 1998, ISBN 0-07-050775-9

[41]

Patricia G. Selinger , Morton M. Astrahan , Donald D. Chamberlin , Raymond A. Lorie , Thomas G. Price : Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979 : 23-34

[42]

Gail M. Shaw , Stanley B. Zdonik : Object-Oriented Queries: Equivalence and Optimization. DOOD 1989 : 281-295

[43]

Gail M. Shaw , Stanley B. Zdonik : An Object-Oriented Query Algebra. DBPL 1989 : 103-112

[44]

Michael Steinbrunn , Guido Moerkotte , Alfons Kemper : Heuristic and Randomized Optimization for the Join Ordering Problem. VLDB Journal 6(3) : 191-208(1997)

[45]

Odysseas G. Tsatalos , Marvin H. Solomon , Yannis E. Ioannidis : The GMAP: A Versatile Tool for Physical Data Independence. VLDB 1994 : 367-378

[46]

Patrick Valduriez : Join Indices. TODS 12(2) : 218-246(1987)

[47]

Gio Wiederhold : Mediators in the Architecture of Future Information Systems. IEEE Computer 25(3) : 38-49(1992)

[48]

H. Z. Yang , Per-Åke Larson : Query Transformation for PSJ-Queries. VLDB 1987 : 245-254

Referenced by

1. Laura M. Haas : Review - Physical Data Independence, Constraints, and Optimization with Universal Plans. ACM SIGMOD Digital Review 1 : (1999)