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 ...

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 CD and click on the path of your mount point:
/Anthology/smod9397 or /cdrom

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

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

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

, 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
[DAYA87]: Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208
[GANS87]: Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33
[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
[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)
[GALI94]: César A. Galindo-Legaria: Outerjoins as Disjunctions. SIGMOD Conference 1994: 348-358
[KOO94]: ...
[LAFO86]: Stéphane Lafortune, Eugene Wong: A State Transition Model for Distributed Query Processing. ACM Trans. Database Syst. 11(3): 294-322(1986)
[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)
[PIRA92]: Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan: Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD Conference 1992: 39-48
[PIRA93]: ...
[ROSE90]: Arnon Rosenthal, César A. Galindo-Legaria: Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins. SIGMOD Conference 1990: 291-299
[SCHO87]: Marc H. Scholl, H.-Bernhard Paul, Hans-Jörg Schek: Supporting Flat Relations by a Nested Relational Kernel. VLDB 1987: 137-146
[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
[ULLN82]: Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6

Last update Tue Sep 18 00:25:12 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page