Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers.

Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208
  author    = {Umeshwar Dayal},
  editor    = {Peter M. Stocker and
               William Kent and
               Peter Hammersley},
  title     = {Of Nests and Trees: A Unified Approach to Processing Queries
               That Contain Nested Subqueries, Aggregates, and Quantifiers},
  booktitle = {VLDB'87, Proceedings of 13th International Conference on Very
               Large Data Bases, September 1-4, 1987, Brighton, England},
  publisher = {Morgan Kaufmann},
  year      = {1987},
  isbn      = {0-934613-46-X},
  pages     = {197-208},
  ee        = {db/conf/vldb/Dayal87.html},
  crossref  = {DBLP:conf/vldb/87},
  bibsource = {DBLP,}


Existing query optimizers focus on Restrict-Project-Join queries. In practice, however, query languages such as SQL and DAPLEX have many powerful features (eg., control over duplicates, nested subqueries, grouping, aggregates, and quantifiers) that are not expressible as sequences of Restrict, Project, and Join operations. Existing optimizers are severely limited in their strategies for processing such queries; typically they use only tuple substitution, and process nested subquery blocks top down. Tuple substitution, however, is generally inefficient and especially so when the database is distributed. Hence, it is imperative to develop alternative strategies. This paper introduces new operations for these difficult features, and describes implementation methods for them. From the algebraic properties of these operations, new query processing tactics are derived. It is shown how these new tactics can be deployed to greatly increase the space of interesting strategies for optimization, without seriously altering the architecture of existing optimizers. The contribution of the paper is in demonstrating the feasibility and desirability of developing an integrated framework for optimizing all of SQL or other query languages that have similiar features.

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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Peter M. Stocker, William Kent, Peter Hammersley (Eds.): VLDB'87, Proceedings of 13th International Conference on Very Large Data Bases, September 1-4, 1987, Brighton, England. Morgan Kaufmann 1987, ISBN 0-934613-46-X
Contents BibTeX


Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX
Stefano Ceri, Georg Gottlob: Translating SQL Into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries. IEEE Trans. Software Eng. 11(4): 324-345(1985) BibTeX
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
E. F. Codd: Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972) BibTeX
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
Umeshwar Dayal, Nathan Goodman, Randy H. Katz: An Extended Relational Algebra with Control over Duplicate Elimination. PODS 1982: 117-123 BibTeX
Umeshwar Dayal: Processing Queries with Quantifiers: A Horticultural Approach. PODS 1983: 125-136 BibTeX
Umeshwar Dayal: Query Processing in a Multidatabase System. Query Processing in Database Systems 1985: 81-108 BibTeX
Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172 BibTeX
Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180 BibTeX
Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33 BibTeX
Matthias Jarke, Joachim W. Schmidt: Query Processing Strategies in the PASCAL/R Relational Database Management System. SIGMOD Conference 1982: 256-264 BibTeX
Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX
Anthony C. Klug: Access Paths in the 'ABE' Statistical Query Facility. SIGMOD Conference 1982: 161-173 BibTeX
Guy M. Lohman, Dean Daniels, Laura M. Haas, Ruth Kistler, Patricia G. Selinger: Optimization of Nested Queries in a Distributed Relational Database. VLDB 1984: 403-415 BibTeX
Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Local Queries. SIGMOD Conference 1986: 84-95 BibTeX
Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Distributed Queries. VLDB 1986: 149-159 BibTeX
Arnon Rosenthal, David S. Reiner: Extending the Algebraic Framework of Query Processing to Handle Outerjoins. VLDB 1984: 334-343 BibTeX
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
David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) BibTeX
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX

Referenced by

  1. Surajit Chaudhuri: Review - Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. ACM SIGMOD Digital Review 2: (2000)
  2. Kian-Lee Tan, Cheng Hian Goh, Beng Chin Ooi: Online Feedback for Nested Aggregate Queries with Multi-Threading. VLDB 1999: 18-29
  3. Joseph M. Hellerstein: Optimization Techniques for Queries with Expensive Methods. ACM Trans. Database Syst. 23(2): 113-157(1998)
  4. Guido Moerkotte: Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing. VLDB 1998: 476-487
  5. Jun Rao, Kenneth A. Ross: Reusing Invariants: A New Strategy for Correlated Queries. SIGMOD Conference 1998: 37-48
  6. Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43
  7. Ahmed Mostefaoui, Jacques Kouloumdjian: Translating Relational Queries to Object-Oriented Queries According to ODMG-93. ADBIS 1998: 328-338
  8. César A. Galindo-Legaria, Arnon Rosenthal: Outerjoin Simplification and Reordering for Query Optimization. ACM Trans. Database Syst. 22(1): 43-73(1997)
  9. Venky Harinarayan: Issues in Interactive Aggregation. IEEE Data Eng. Bull. 20(1): 12-18(1997)
  10. Jian Yang, Kamalakar Karlapalem, Qing Li: Algorithms for Materialized View Design in Data Warehousing Environment. VLDB 1997: 136-145
  11. 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
  12. Damianos Chatziantoniou, Kenneth A. Ross: Groupwise Processing of Relational Queries. VLDB 1997: 476-485
  13. Alon Y. Levy, Dan Suciu: Deciding Containment for Queries with Complex Objects. PODS 1997: 20-31
  14. Pedro Celis, Hansjörg Zeller: Subquery Elimination: A Complete Unnesting Algorithm for an Extended Relational Algebra. ICDE 1997: 321
  15. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic Conditions. ACM Trans. Database Syst. 21(1): 107-155(1996)
  16. Myra Spiliopoulou, Michael Hatzopoulos, Yannis Cotronis: Parallel Optimization of Large Join Queries with Set Operators and Aggregates in a Parallel Environment Supporting Pipeline. IEEE Trans. Knowl. Data Eng. 8(3): 429-445(1996)
  17. William J. McKenna, Louis Burger, Chi Hoang, Melissa Truong: EROC: A Toolkit for Building NEATO Query Optimizers. VLDB 1996: 111-121
  18. Sudhir Rao, Antonio Badia, Dirk Van Gucht: Providing Better Support for a Class of Decision Support Queries. SIGMOD Conference 1996: 217-227
  19. Mitch Cherniack, Stanley B. Zdonik: Rule Languages and Internal Algebras for Rule-Based Optimizers. SIGMOD Conference 1996: 401-412
  20. Praveen Seshadri, Hamid Pirahesh, T. Y. Cliff Leung: Complex Query Decorrelation. ICDE 1996: 450-458
  21. Alon Y. Levy, Inderpal Singh Mumick: Reasoning with Aggregation Constraints. EDBT 1996: 514-534
  22. Surajit Chaudhuri, Kyuseok Shim: Optimizing Queries with Aggregate Views. EDBT 1996: 167-182
  23. Lars Bækgaard, Leo Mark: Incremental Computation of Nested Relational Query Expressions. ACM Trans. Database Syst. 20(2): 111-148(1995)
  24. Surajit Chaudhuri, Kyuseok Shim: An Overview of Cost-based Optimization of Queries with Aggregates. IEEE Data Eng. Bull. 18(3): 3-9(1995)
  25. Ashish Gupta, Venky Harinarayan, Dallan Quass: Aggregate-Query Processing in Data Warehousing Environments. VLDB 1995: 358-369
  26. Gautam Bhargava, Piyush Goel, Balakrishna R. Iyer: Hypergraph Based Reorderings of Outer Join Queries with Complex Predicates. SIGMOD Conference 1995: 304-315
  27. Qi Yang, Chengwen Liu, Jing Wu, Clement T. Yu, Son Dao, Hiroshi Nakajima: Efficient Processing of Nested Fuzzy SQL Queries. ICDE 1995: 131-138
  28. Mark W. W. Vermeer, Peter M. G. Apers: Reverse Engineering of Relational Database Applications. OOER 1995: 89-100
  29. Sophie Cluet, Guido Moerkotte: Efficient Evaluation of Aggregates on Bulk Types. DBPL 1995: 8
  30. Mark W. W. Vermeer, Peter M. G. Apers: Object-Oriented Views of Relational Databases Incorporating Behaviour. DASFAA 1995: 26-35
  31. Gary C. K. Lam, Vincent Y. Lum, Kam-Fai Wong: On the Issues of Expressiveness and Portability of Chiql. DASFAA 1995: 164-171
  32. Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv: Query Optimization by Predicate Move-Around. VLDB 1994: 96-107
  33. Surajit Chaudhuri, Kyuseok Shim: Including Group-By in Query Optimization. VLDB 1994: 354-366
  34. Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: Sequence Query Processing. SIGMOD Conference 1994: 430-441
  35. Inderpal Singh Mumick, Hamid Pirahesh: Implementation of Magic-sets in a Relational Database System. SIGMOD Conference 1994: 103-114
  36. César A. Galindo-Legaria: Outerjoins as Disjunctions. SIGMOD Conference 1994: 348-358
  37. Weipeng P. Yan, Per-Åke Larson: Performing Group-By before Join. ICDE 1994: 89-100
  38. G. N. Paulley, Per-Åke Larson: Exploiting Uniqueness in Query Optimization. ICDE 1994: 68-79
  39. Hennie J. Steenhagen, Peter M. G. Apers, Henk M. Blanken: Optimization of Nested Queries in a Complex Object Model. EDBT 1994: 337-350
  40. Richard T. Snodgrass, Santiago Gomez, L. Edwin McKenzie: Aggregates in the Temporal Query Language TQuel. IEEE Trans. Knowl. Data Eng. 5(5): 826-842(1993)
  41. Joseph M. Hellerstein, Michael Stonebraker: Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993: 267-276
  42. Sophie Cluet, Guido Moerkotte: Nested Queries in Object Bases. DBPL 1993: 226-242
  43. M. Muralikrishna: Improved Unnesting Algorithms for Join Aggregate SQL Queries. VLDB 1992: 91-102
  44. Umeshwar Dayal, Gene T. J. Wuu: A Uniform Approach to Processing Temporal Queries. VLDB 1992: 407-418
  45. Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan: Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD Conference 1992: 39-48
  46. Daniel F. Lieuwen, David J. DeWitt: A Transformation-Based Approach to Optimizing Loops in Database Programming Languages. SIGMOD Conference 1992: 91-100
  47. César A. Galindo-Legaria, Arnon Rosenthal: How to Extend a Conventional Optimizer to Handle One- and Two-Sided Outerjoin. ICDE 1992: 402-409
  48. Mauro Negri, Giuseppe Pelagatti, Licia Sbattella: Formal Semantics of SQL Queries. ACM Trans. Database Syst. 16(3): 513-534(1991)
  49. Daniel F. Lieuwen, David J. DeWitt: Optimizing Loops in Database Programming Languages. DBPL 1991: 287-305
  50. Ryohei Nakano: Translation with Optimization from Relational Calculus to Relational Algebra Having Aggregate Functions. ACM Trans. Database Syst. 15(4): 518-557(1990)
  51. Arnon Rosenthal, César A. Galindo-Legaria: Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins. SIGMOD Conference 1990: 291-299
  52. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic is Relevant. SIGMOD Conference 1990: 247-258
  53. Catriel Beeri, Yoram Kornatzky: Algebraic Optimization of Object-Oriented Query Languages. ICDT 1990: 72-88
  54. C. Mohan, Donald J. Haderle, Yun Wang, Josephine M. Cheng: Single Table Access Using Multiple Indexes: Optimization, Execution, and Concurrency Control Techniques. EDBT 1990: 29-43
  55. Arie Segev, Himawan Gunadhi: Event-Join Optimization in Temporal Relational Databases. VLDB 1989: 205-215
  56. M. Muralikrishna: Optimization and Dataflow Algorithms for Nested Tree Queries. VLDB 1989: 77-85
  57. Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388
  58. François Bry: Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited. SIGMOD Conference 1989: 193-204
  59. François Bry: Logical Rewritings for Improving the Evaluation of Quantified Queries. MFDBS 1989: 100-116
  60. Umeshwar Dayal: Queries and Views in an Object-Oriented Data Model. DBPL 1989: 80-102
  61. Catriel Beeri: Data Models and Languages for Databases. ICDT 1988: 19-40
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:34 2009