Physical Data Independence, Constraints, and Optimization with Universal Plans.

@inproceedings{DBLP:conf/vldb/DeutschPT99,
  author    = {Alin Deutsch and
               Lucian Popa and
               Val Tannen},
  editor    = {Malcolm P. Atkinson and
               Maria E. Orlowska and
               Patrick Valduriez and
               Stanley B. Zdonik and
               Michael L. Brodie},
  title     = {Physical Data Independence, Constraints, and Optimization with
               Universal Plans},
  booktitle = {VLDB'99, Proceedings of 25th International Conference on Very
               Large Data Bases, September 7-10, 1999, Edinburgh, Scotland,
               UK},
  publisher = {Morgan Kaufmann},
  year      = {1999},
  isbn      = {1-55860-615-7},
  pages     = {459-470},
  ee        = {db/conf/vldb/DeutschPT99.html},
  crossref  = {DBLP:conf/vldb/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We present an optimization method and algorithm designed for three objectives: physical data independence, semantic optimization, and generalized tableau minimization. The method relies on generalized forms of chase and "backchase" with constraints (dependencies). By using dictionaries (finite functions) in physical schemas we can capture with constraints useful access structures such as indexes, materialized views, source capabilities, access support relations, gmaps, etc.

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.

Copyright © 1999 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[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 Conference 1996: 137-148

[4]

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

[5]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions. ACM Trans. Database Syst. 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. Theor. Comput. Sci. 116(1&2): 59-94(1993)

[9]

Catriel Beeri, Moshe Y. Vardi: A Proof Procedure for Data Dependencies. J. ACM 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: 383-418

[11]

Elisa Bertino, Won Kim: Indexing Techniques for Queries on Nested Objects. IEEE Trans. Knowl. Data Eng. 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. ACM Trans. Database Syst. 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 Conference 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. Int. J. Cooperative Inf. Syst. 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: 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. J. Intell. Inf. Syst. 5(2): 121-143(1995)

[32]

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

[33]

Guy M. Lohman, Bruce G. Lindsay, Hamid Pirahesh, K. Bernhard Schiefer: Extensions to Starburst: Objects, Types, Functions, and Rules. Commun. ACM 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 J. 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. ACM Trans. Database Syst. 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