ACM SIGMOD Anthology VLDB dblp.uni-trier.de

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

Alin Deutsch, Lucian Popa, Val Tannen: Physical Data Independence, Constraints, and Optimization with Universal Plans. VLDB 1999: 459-470
@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

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Malcolm P. Atkinson, Maria E. Orlowska, Patrick Valduriez, Stanley B. Zdonik, Michael L. Brodie (Eds.): VLDB'99, Proceedings of 25th International Conference on Very Large Data Bases, September 7-10, 1999, Edinburgh, Scotland, UK. Morgan Kaufmann 1999, ISBN 1-55860-615-7
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
...
[7]
Malcolm P. Atkinson, Christophe Lécluse, Paul Philbrow, Philippe Richard: Design Issues in a Map Language. DBPL 1991: 20-32 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Catriel Beeri, Yoram Kornatzky: Algebraic Optimization of Object-Oriented Query Languages. Theor. Comput. Sci. 116(1&2): 59-94(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Catriel Beeri, Moshe Y. Vardi: A Proof Procedure for Data Dependencies. J. ACM 31(4): 718-741(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Elisa Bertino: A Survey of Indexing Techniques for Object-Oriented Database Management Systems. Query Processing for Advanced Database Systems, Dagstuhl 1991: 383-418 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Elisa Bertino, Won Kim: Indexing Techniques for Queries on Nested Objects. IEEE Trans. Knowl. Data Eng. 1(2): 196-214(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
R. G. G. Cattell (Ed.): The Object Database Standard: ODMG 2.0. Morgan Kaufmann 1997
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Upen S. Chakravarthy, John Grant, Jack Minker: Logic-Based Approach to Semantic Query Optimization. ACM Trans. Database Syst. 15(2): 162-207(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
Mitch Cherniack, Stanley B. Zdonik: Rule Languages and Internal Algebras for Rule-Based Optimizers. SIGMOD Conference 1996: 401-412 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
...
[19]
Sophie Cluet, Claude Delobel: A General Framework for the Optimization of Object-Oriented Queries. SIGMOD Conference 1992: 383-392 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
Leonidas Fegaras, David Maier: An Algebraic Framework for Physical OODB Design. DBPL 1995: 9 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
John Grant, Jarek Gryz, Jack Minker, Louiqa Raschid: Semantic Query Optimization for Object Databases. ICDE 1997: 444-453 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[25]
Yannis E. Ioannidis, Eugene Wong: Query Optimization by Simulated Annealing. SIGMOD Conference 1987: 9-22 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[26]
B. Paul Jenq, Darrell Woelk, Won Kim, Wan-Lik Lee: Query Processing in Distributed ORION. EDBT 1990: 169-187 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[27]
Arthur M. Keller, Julie Basu: A Predicate-based Caching Scheme for Client-Server Database Architectures. PDIS 1994: 229-238 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[28]
Alfons Kemper, Guido Moerkotte: Access Support in Object Bases. SIGMOD Conference 1990: 364-374 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[29]
Alfons Kemper, Guido Moerkotte: Advanced Query Processing in Object Bases Using Access Support Relations. VLDB 1990: 290-301 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[30]
Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[32]
Leonid Libkin, Rona Machlin, Limsoon Wong: A Query Language for Multidimensional Arrays: Design, Implementation, and Optimization Techniques. SIGMOD Conference 1996: 228-239 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[34]
David Maier, Jacob Stein: Indexing in an Object-Oriented DBMS. OODBS 1986: 171-182 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[35]
Yannis Papakonstantinou, Hector Garcia-Molina, Jennifer Widom: Object Exchange Across Heterogeneous Information Sources. ICDE 1995: 251-260 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[36]
Yannis Papakonstantinou, Ashish Gupta, Laura M. Haas: Capabilities-Based Query Rewriting in Mediator Systems. Distributed and Parallel Databases 6(1): 73-110(1998) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[37]
Lucian Popa, Val Tannen: An Equational Chase for Path-Conjunctive Queries, Constraints, and Views. ICDT 1999: 39-57 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[38]
Xiaolei Qian: Query Folding. ICDE 1996: 48-55 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[39]
Anand Rajaraman, Yehoshua Sagiv, Jeffrey D. Ullman: Answering Queries Using Templates with Binding Patterns. PODS 1995: 105-112 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[40]
Raghu Ramakrishnan: Database Management Systems. WCB/McGraw-Hill 1998, ISBN 0-07-050775-9
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[42]
Gail M. Shaw, Stanley B. Zdonik: Object-Oriented Queries: Equivalence and Optimization. DOOD 1989: 281-295 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[43]
Gail M. Shaw, Stanley B. Zdonik: An Object-Oriented Query Algebra. DBPL 1989: 103-112 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[44]
Michael Steinbrunn, Guido Moerkotte, Alfons Kemper: Heuristic and Randomized Optimization for the Join Ordering Problem. VLDB J. 6(3): 191-208(1997) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[45]
Odysseas G. Tsatalos, Marvin H. Solomon, Yannis E. Ioannidis: The GMAP: A Versatile Tool for Physical Data Independence. VLDB 1994: 367-378 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[46]
Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[47]
Gio Wiederhold: Mediators in the Architecture of Future Information Systems. IEEE Computer 25(3): 38-49(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[48]
H. Z. Yang, Per-Åke Larson: Query Transformation for PSJ-Queries. VLDB 1987: 245-254 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:22:08 2010 by Michael Ley (ley@uni-trier.de)