Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins.

@inproceedings{DBLP:conf/sigmod/RosenthalG90,
  author    = {Arnon Rosenthal and
               C{\'e}sar A. Galindo-Legaria},
  editor    = {Hector Garcia-Molina and
               H. V. Jagadish},
  title     = {Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins},
  booktitle = {Proceedings of the 1990 ACM SIGMOD International Conference on
               Management of Data, Atlantic City, NJ, May 23-25, 1990},
  publisher = {ACM Press},
  year      = {1990},
  pages     = {291-299},
  ee        = {http://doi.acm.org/10.1145/93597.98738, db/conf/sigmod/RosenthalG90.html},
  crossref  = {DBLP:conf/sigmod/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We determine when a join/outerjoin query can be expressed unambiguously as a query graph, without an explicit specification of the order of evaluation. To do so, we first characterize the set of expression trees that implement a given join/outerjoin query graph, and investigate the existence of transformations among the various trees. Our main theorem is that a join/outerjoin query is freely reorderable if the query graph derived from it falls within a particular class, every tree that "implements" such a graph evaluates to the same result.

The result has applications to language design and query optimization. Languages that generate queries within such a class do not require the user to indicate priority among join operations, and hence may present a simpllfied syntax. And it is unnecessary to add extensive analyses to a conventional query optimizer in order to generate legal reorderings for a freely-reorderable language.

Copyright © 1990 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

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" 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/smod7592 or /cdrom

• 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

Online Edition: ACM Digital Library

References

[DATE83]

C. J. Date: The Outer Join. ICOD 1983: 76-106 BibTeX

[DAYA83]

Umeshwar Dayal: Processing Queries with Quantifiers: A Horticultural Approach. PODS 1983: 125-136 BibTeX

[DAYA87]

Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208 BibTeX

[GALI89]

...

[MURA89]

M. Muralikrishna: Optimization and Dataflow Algorithms for Nested Tree Queries. VLDB 1989: 77-85 BibTeX

[OZSO89]

Gultekin Özsoyoglu, Victor Matos, Z. Meral Özsoyoglu: Query Processing Techniques in the Summary-Table-by-Example Database Query Language. ACM Trans. Database Syst. 14(4): 526-573(1989) BibTeX

[ROSE84]

Arnon Rosenthal, David S. Reiner: Extending the Algebraic Framework of Query Processing to Handle Outerjoins. VLDB 1984: 334-343 BibTeX

[ROSE85]

...

[SCHO87]

Marc H. Scholl, H.-Bernhard Paul, Hans-Jörg Schek: Supporting Flat Relations by a Nested Relational Kernel. VLDB 1987: 137-146 BibTeX

[SHIP81]

David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) BibTeX

Referenced by

1. Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43
2. César A. Galindo-Legaria, Arnon Rosenthal: Outerjoin Simplification and Reordering for Query Optimization. ACM Trans. Database Syst. 22(1): 43-73(1997)
3. Jens Claußen, Alfons Kemper, Guido Moerkotte, Klaus Peithner: Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases. VLDB 1997: 286-295
4. Piyush Goel, Balakrishna R. Iyer: SQL Query Optimization: Reordering for a General Class of Queries. SIGMOD Conference 1996: 47-56
5. Gautam Bhargava, Piyush Goel, Balakrishna R. Iyer: Hypergraph Based Reorderings of Outer Join Queries with Complex Predicates. SIGMOD Conference 1995: 304-315
6. César A. Galindo-Legaria: Outerjoins as Disjunctions. SIGMOD Conference 1994: 348-358
7. Hennie J. Steenhagen, Peter M. G. Apers, Henk M. Blanken: Optimization of Nested Queries in a Complex Object Model. EDBT 1994: 337-350
8. Sophie Cluet, Guido Moerkotte: Nested Queries in Object Bases. DBPL 1993: 226-242
9. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
10. M. Muralikrishna: Improved Unnesting Algorithms for Join Aggregate SQL Queries. VLDB 1992: 91-102
11. Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan: Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD Conference 1992: 39-48
12. César A. Galindo-Legaria, Arnon Rosenthal: How to Extend a Conventional Optimizer to Handle One- and Two-Sided Outerjoin. ICDE 1992: 402-409