dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

Hypergraph Based Reorderings of Outer Join Queries with Complex Predicates.

Gautam Bhargava, Piyush Goel, Balakrishna R. Iyer: Hypergraph Based Reorderings of Outer Join Queries with Complex Predicates. SIGMOD Conference 1995: 304-315
@inproceedings{DBLP:conf/sigmod/BhargavaGI95,
  author    = {Gautam Bhargava and
               Piyush Goel and
               Balakrishna R. Iyer},
  editor    = {Michael J. Carey and
               Donovan A. Schneider},
  title     = {Hypergraph Based Reorderings of Outer Join Queries with Complex
               Predicates},
  booktitle = {Proceedings of the 1995 ACM SIGMOD International Conference on
               Management of Data, San Jose, California, May 22-25, 1995},
  publisher = {ACM Press},
  year      = {1995},
  pages     = {304-315},
  ee        = {http://doi.acm.org/10.1145/223784.223847},
  crossref  = {DBLP:conf/sigmod/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Complex queries containing outer joins are, for the most part, executed by commercial DBMS products in an ``as written" manner. Only a very few reorderings of the operations are considered and the benefits of considering comprehensive reordering schemes are not exploited. This is largely due to the fact there are no readily usable results for reordering such operations for relations with duplicates and/or outer join predicates that are other than "simple". Most previous approaches have ignored duplicates and complex predicates; the very few that have considered these aspects have suggested approaches that lead to a possibly exponential number of, and redundant intermediate joins. Since traditional query graph models are inadequate for modeling outer join queries with complex predicates, in this paper we present the needed hypergraph abstraction and algorithms for reordering such outer join queries. This allows the query optimizer to explore a significantly larger space of execution plans, and choose one with a low cost. Additionally, these algorithms are easily incorporated into well known and widely used enumeration methods such as dynamic programming.

Copyright © 1995 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

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

Printed Edition

Michael J. Carey, Donovan A. Schneider (Eds.): Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, San Jose, California, May 22-25, 1995. ACM Press 1995 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 24(2), June 1995
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1032 KB]

References

[BHAR94a]
...
[BHAR94b]
...
[CHEN90]
...
[DATE83]
C. J. Date: The Outer Join. ICOD 1983: 76-106 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DAYA87]
Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GANS87]
Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GALI92a]
César A. Galindo-Legaria, Arnon Rosenthal: How to Extend a Conventional Optimizer to Handle One- and Two-Sided Outerjoin. ICDE 1992: 402-409 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GALI92b]
...
[GALI93]
César A. Galindo-Legaria, Arnon Rosenthal: Outerjoin Simplification and Reordering for Query Optimization. ACM Trans. Database Syst. 22(1): 43-73(1997) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GALI94]
César A. Galindo-Legaria: Outerjoins as Disjunctions. SIGMOD Conference 1994: 348-358 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KOO94]
...
[LAFO86]
Stéphane Lafortune, Eugene Wong: A State Transition Model for Distributed Query Processing. ACM Trans. Database Syst. 11(3): 294-322(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LEE94]
Byung Suk Lee, Gio Wiederhold: Outer Joins and Filters for Instantiating Objects from Relational Databases Through Views. IEEE Trans. Knowl. Data Eng. 6(1): 108-119(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PIRA92]
Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan: Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD Conference 1992: 39-48 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PIRA93]
...
[ROSE90]
Arnon Rosenthal, César A. Galindo-Legaria: Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins. SIGMOD Conference 1990: 291-299 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SCHO87]
Marc H. Scholl, H.-Bernhard Paul, Hans-Jörg Schek: Supporting Flat Relations by a Nested Relational Kernel. VLDB 1987: 137-146 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SELI79]
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
[ULLN82]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Tue Sep 18 00:25:12 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page