ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Optimization of Nested SQL Queries Revisited.

Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33
@inproceedings{DBLP:conf/sigmod/GanskiW87,
  author    = {Richard A. Ganski and
               Harry K. T. Wong},
  editor    = {Umeshwar Dayal and
               Irving L. Traiger},
  title     = {Optimization of Nested SQL Queries Revisited},
  booktitle = {Proceedings of the Association for Computing Machinery Special
               Interest Group on Management of Data 1987 Annual Conference,
               San Francisco, California, May 27-29, 1987},
  publisher = {ACM Press},
  year      = {1987},
  pages     = {23-33},
  ee        = {http://doi.acm.org/10.1145/38713.38723, db/conf/sigmod/GanskiW87.html},
  crossref  = {DBLP:conf/sigmod/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Current methods of evaluating nested queries in the SQL language can be inefficient in a variety of query and data base contexts. Previous research in the area of nested query optimization which sought methods of reducing evaluation costs is summarized, including a classification scheme for nested queries, algorithms designed to transform each type of query to a logically equivalent form which may then be evaluated more efficiently, and a description of a major bug in one of these algorithms. Further examination reveals another bug in the same algorithm. Solutions to these bugs are proposed and incorporated into a new transformation algorithm, and extensions are proposed which will allow the transformation algorithms to handle a larger class of predicates. A recursive algorithm for processing a general nested query is presented and the action of this algorithm is demonstrated. This algorithm can be used to transform any nested query.

Copyright © 1987 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 2, SIGMOD '75-'92" and ...

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

Printed Edition

Umeshwar Dayal, Irving L. Traiger (Eds.): Proceedings of the Association for Computing Machinery Special Interest Group on Management of Data 1987 Annual Conference, San Francisco, California, May 27-29, 1987. ACM Press 1987 BibTeX , SIGMOD Record 16(3)
Contents

Online Edition: ACM Digital Library

References

[AST 75]
Morton M. Astrahan, Donald D. Chamberlin: Implementation of a Structured English Query Language. Commun. ACM 18(10): 580-588(1975) BibTeX
[AST 76]
Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
[COD 79]
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
[KIE 84]
...
[KIM 82]
Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX
[ORA 86]
...
[SEL 79]
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 BibTeX
[STO 76]
Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX

Referenced by

  1. Kian-Lee Tan, Cheng Hian Goh, Beng Chin Ooi: Online Feedback for Nested Aggregate Queries with Multi-Threading. VLDB 1999: 18-29
  2. Jun Rao, Kenneth A. Ross: Reusing Invariants: A New Strategy for Correlated Queries. SIGMOD Conference 1998: 37-48
  3. Leonidas Fegaras: Query Unnesting in Object-Oriented Databases. SIGMOD Conference 1998: 49-60
  4. Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43
  5. 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
  6. Pedro Celis, Hansjörg Zeller: Subquery Elimination: A Complete Unnesting Algorithm for an Extended Relational Algebra. ICDE 1997: 321
  7. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic Conditions. ACM Trans. Database Syst. 21(1): 107-155(1996)
  8. William J. McKenna, Louis Burger, Chi Hoang, Melissa Truong: EROC: A Toolkit for Building NEATO Query Optimizers. VLDB 1996: 111-121
  9. Sudhir Rao, Antonio Badia, Dirk Van Gucht: Providing Better Support for a Class of Decision Support Queries. SIGMOD Conference 1996: 217-227
  10. Piyush Goel, Balakrishna R. Iyer: SQL Query Optimization: Reordering for a General Class of Queries. SIGMOD Conference 1996: 47-56
  11. Mitch Cherniack, Stanley B. Zdonik: Rule Languages and Internal Algebras for Rule-Based Optimizers. SIGMOD Conference 1996: 401-412
  12. Praveen Seshadri, Hamid Pirahesh, T. Y. Cliff Leung: Complex Query Decorrelation. ICDE 1996: 450-458
  13. Gautam Bhargava, Piyush Goel, Balakrishna R. Iyer: Efficient Processing of Outer Joins and Aggregate Functions. ICDE 1996: 441-449
  14. Alon Y. Levy, Inderpal Singh Mumick: Reasoning with Aggregation Constraints. EDBT 1996: 514-534
  15. Surajit Chaudhuri, Kyuseok Shim: Optimizing Queries with Aggregate Views. EDBT 1996: 167-182
  16. Lars Bækgaard, Leo Mark: Incremental Computation of Nested Relational Query Expressions. ACM Trans. Database Syst. 20(2): 111-148(1995)
  17. Surajit Chaudhuri, Kyuseok Shim: An Overview of Cost-based Optimization of Queries with Aggregates. IEEE Data Eng. Bull. 18(3): 3-9(1995)
  18. Gautam Bhargava, Piyush Goel, Balakrishna R. Iyer: Hypergraph Based Reorderings of Outer Join Queries with Complex Predicates. SIGMOD Conference 1995: 304-315
  19. Qi Yang, Chengwen Liu, Jing Wu, Clement T. Yu, Son Dao, Hiroshi Nakajima: Efficient Processing of Nested Fuzzy SQL Queries. ICDE 1995: 131-138
  20. Sophie Cluet, Guido Moerkotte: Efficient Evaluation of Aggregates on Bulk Types. DBPL 1995: 8
  21. Gary C. K. Lam, Vincent Y. Lum, Kam-Fai Wong: On the Issues of Expressiveness and Portability of Chiql. DASFAA 1995: 164-171
  22. Hennie J. Steenhagen, Peter M. G. Apers, Henk M. Blanken, Rolf A. de By: From Nested-Loop to Join Queries in OODB. VLDB 1994: 618-629
  23. Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv: Query Optimization by Predicate Move-Around. VLDB 1994: 96-107
  24. Surajit Chaudhuri, Kyuseok Shim: Including Group-By in Query Optimization. VLDB 1994: 354-366
  25. Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: Sequence Query Processing. SIGMOD Conference 1994: 430-441
  26. Inderpal Singh Mumick, Hamid Pirahesh: Implementation of Magic-sets in a Relational Database System. SIGMOD Conference 1994: 103-114
  27. César A. Galindo-Legaria: Outerjoins as Disjunctions. SIGMOD Conference 1994: 348-358
  28. Weipeng P. Yan, Per-Åke Larson: Performing Group-By before Join. ICDE 1994: 89-100
  29. G. N. Paulley, Per-Åke Larson: Exploiting Uniqueness in Query Optimization. ICDE 1994: 68-79
  30. Hennie J. Steenhagen, Peter M. G. Apers, Henk M. Blanken: Optimization of Nested Queries in a Complex Object Model. EDBT 1994: 337-350
  31. Song Bong Yoo, Phillip C.-Y. Sheu: Evaluation and Optimization of Query Programs in an Object-Oriented and Symbolic Information System. IEEE Trans. Knowl. Data Eng. 5(3): 479-495(1993)
  32. Richard L. Cole, Mark J. Anderson, Robert J. Bestgen: Query Processing in the IBM Application System/400. IEEE Data Eng. Bull. 16(4): 19-28(1993)
  33. Sophie Cluet, Guido Moerkotte: Nested Queries in Object Bases. DBPL 1993: 226-242
  34. M. Muralikrishna: Improved Unnesting Algorithms for Join Aggregate SQL Queries. VLDB 1992: 91-102
  35. Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan: Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD Conference 1992: 39-48
  36. Daniel F. Lieuwen, David J. DeWitt: A Transformation-Based Approach to Optimizing Loops in Database Programming Languages. SIGMOD Conference 1992: 91-100
  37. Mauro Negri, Giuseppe Pelagatti, Licia Sbattella: Formal Semantics of SQL Queries. ACM Trans. Database Syst. 16(3): 513-534(1991)
  38. Leonore Neugebauer: Optimization and Evaluation of Database Queries Including Embedded Interpolation Procedures. SIGMOD Conference 1991: 118-127
  39. Daniel F. Lieuwen, David J. DeWitt: Optimizing Loops in Database Programming Languages. DBPL 1991: 287-305
  40. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic is Relevant. SIGMOD Conference 1990: 247-258
  41. M. Muralikrishna: Optimization and Dataflow Algorithms for Nested Tree Queries. VLDB 1989: 77-85
  42. Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388
  43. Sheldon J. Finkelstein, Mario Schkolnick, Paolo Tiberio: Physical Database Design for Relational Databases. ACM Trans. Database Syst. 13(1): 91-128(1988)
  44. Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:39:47 2009