DBScholar

Back to papers

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

Summary: Introduces a unified framework for SQL-like queries with nested subqueries, aggregates, and quantifiers, using new algebraic operators beyond Restrict-Project-Join and reducing reliance on tuple substitution. Derives optimization tactics from these algebraic properties to broaden the optimizer’s search space and enable distributed-friendly integration with existing architectures. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
hfc1739f6a5f01f2b
Venue
VLDB
Year
1987
Pagerank
0.00034024478
Overall Rank
99 | 99.34%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{dayal_vldb87,
        title = {{Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers}},
        author = {Dayal, Umeshwar},
        journal = {PVLDB},
        series = {{VLDB} '87},
        pages = {197--208},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 49 of 49 citing papers.

Rank Citing Paper Year Venue Pagerank
73 Including Group-By in Query Optimization 1994 VLDB 0.00037420958
109 Extensible/Rule Based Query Rewrite Optimization in Starburst 1992 SIGMOD 0.00032702871
125 Predicate Migration: Optimizing Queries with Expensive Predicates 1993 SIGMOD 0.00030398363
204 Aggregate-Query Processing in Data Warehousing Environments 1995 VLDB 0.0002516936
216 Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing 1998 VLDB 0.00024446892
259 An Overview of Query Optimization in Relational Systems 1998 PODS 0.00022881075
275 Extensible Query Processing in Starburst 1989 SIGMOD 0.000224395
554 Orthogonal Optimization of Subqueries and Aggregation 2001 SIGMOD 0.00016487919
712 Sequence Query Processing 1994 SIGMOD 0.00014588907
896 Froid: Optimization of Imperative Programs in a Relational Database 2018 VLDB 0.00013164545
1,015 Improved Unnesting Algorithms for Join Aggregate SQL Queries 1992 VLDB 0.00012468327
1,063 Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins 1990 SIGMOD 0.00012198695
1,122 Query Optimization by Predicate Move-Around 1994 VLDB 0.00011915958
1,201 Outerjoins as Disjunctions 1994 SIGMOD 0.00011523243
1,276 Rewriting Procedures for Batched Bindings 2008 VLDB 0.00011210489
1,443 Magic is Relevant 1990 SIGMOD 0.00010618161
1,711 Algorithms for Materialized View Design in Data Warehousing Environment 1997 VLDB 9.7964912e-05
1,827 Deciding Containment for Queries with Complex Objects (Extended Abstract) 1997 PODS 9.5417632e-05
2,054 WinMagic : Subquery Elimination Using Window Aggregation 2003 SIGMOD 9.1030561e-05
2,122 Enhanced Subquery Optimizations in Oracle 2009 VLDB 8.9938885e-05
2,132 Reusing Invariants: A New Strategy for Correlated Queries 1998 SIGMOD 8.9837489e-05
2,449 Groupwise Processing of Relational Queries 1997 VLDB 8.4346851e-05
2,555 A Transformation-Based Approach to Optimizing Loops in Database Programming Languages 1992 SIGMOD 8.2817782e-05
2,634 WideTable: An Accelerator for Analytical Data Processing 2014 VLDB 8.1797149e-05
2,874 Optimization and Dataflow Algorithms for Nested Tree Queries 1989 VLDB 7.898744e-05
3,279 Hypergraph based reorderings of outer join queries with complex predicates 1995 SIGMOD 7.4510308e-05
3,702 Implementation of Magic-sets in a Relational Database System 1994 SIGMOD 7.0617354e-05
3,794 Providing Better Support for a Class of Decision Support Queries 1996 SIGMOD 6.9962851e-05
3,857 EROC: A Toolkit for Building NEATO Query Optimizers 1996 VLDB 6.9553827e-05
3,874 Optimizing Nested Queries with Parameter Sort Orders 2005 VLDB 6.9367667e-05
4,067 Event-Join Optimization in Temporal Relational Databases 1989 VLDB 6.8086897e-05
4,197 Rule Languages and Internal Algebras for Rule-Based Optimizers 1996 SIGMOD 6.7307148e-05
4,486 On the Correct and Complete Enumeration of the Core Search Space 2013 SIGMOD 6.5638966e-05
5,033 Optimizing View Queries in ROLEX to Support Navigable Result Trees 2002 VLDB 6.2936532e-05
5,279 Online Feedback for Nested Aggregate Queries with Multi-Threading 1999 VLDB 6.1848178e-05
5,974 Factorizing Complex Predicates in Queries to Exploit Indexes 2003 SIGMOD 5.9109943e-05
6,211 Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited 1989 SIGMOD 5.8315199e-05
7,166 The Generalized Pre-Grouping Transformation: Aggregate Query Optimization in the Presence of Dependencies 2003 VLDB 5.5796659e-05
7,319 Optimization of Nested Queries using the NF2 Algebra 2016 SIGMOD 5.5410915e-05
7,346 Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases 1997 VLDB 5.5314259e-05
7,927 A Practical Approach to Groupjoin and Nested Aggregates 2021 VLDB 5.4082473e-05
8,286 User-Optimizer Communication using Abstract Plans in Sybase ASE 2001 VLDB 5.3449621e-05
9,166 Equivalence of Nested Queries with Mixed Semantics 2009 PODS 5.2031263e-05
9,687 Window Function Expression: Let the Self-join Enter 2024 VLDB 5.1258854e-05
11,199 Query Decorrelation in the Fabric Data Warehouse 2025 SIGMOD 4.9605343e-05
11,541 Query Optimization by Quantifier Elimination 2024 PODS 4.9605343e-05
12,258 Improving Join Reorderability with Compensation Operators 2018 SIGMOD 4.9605343e-05
13,065 A Nested Relational Approach to Processing SQL Subqueries 2005 SIGMOD 4.9605343e-05
13,432 A Uniform Approach to Processing Temporal Queries 1992 VLDB 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
1 Access Path Selection in a Relational Database Management System 1979 SIGMOD 0.0023948467
10 Extending the Data Base Relational Model to Capture More Meaning 1979 SIGMOD 0.00075677079
16 The Functional Data Model and the Data Language DAPLEX 1979 SIGMOD 0.00059778867
118 The EXODUS Optimizer Generator 1987 SIGMOD 0.00031320165
133 Optimization of Nested SQL Queries Revisited 1987 SIGMOD 0.0003015194
345 R* Optimizer Validation and Performance Evaluation for Distributed Queries 1986 VLDB 0.00020445813
396 R* Optimizer Validation and Performance Evaluation for Local Queries 1986 SIGMOD 0.00019119719
633 A Rule-Based View of Query Optimization 1987 SIGMOD 0.00015365563
772 Access Paths in the "Abe" Statistical Query Facility 1982 SIGMOD 0.00014078923
1,116 An Extended Relational Algebra with Control Over Duplicate Elimination 1982 PODS 0.00011931158
1,945 Extending the Algebraic Framework of Query Processing to Handle Outerjoins 1984 VLDB 9.3059376e-05
2,320 Optimization of Nested Queries in a Distributed Relational Database 1984 VLDB 8.6359247e-05
3,021 Query Processing Strategies in the PASCAL/R Relational Database Management System 1982 SIGMOD 7.7265285e-05
4,648 Processing Queries with Quantifiers: A Horticultural Approach 1983 PODS 6.4724782e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 9,346 From Nested-Loop to Join Queries in OODB 1994 VLDB
2 1,102 A General Framework for the Optimization of Object-Oriented Queries 1992 SIGMOD
3 1,015 Improved Unnesting Algorithms for Join Aggregate SQL Queries 1992 VLDB
4 11,541 Query Optimization by Quantifier Elimination 2024 PODS
5 6,064 Query Unnesting in Object-Oriented Databases 1998 SIGMOD
6 2,163 A Recursive Algebra and Query Optimization for Nested Relations 1989 SIGMOD
7 7,319 Optimization of Nested Queries using the NF2 Algebra 2016 SIGMOD
8 2,874 Optimization and Dataflow Algorithms for Nested Tree Queries 1989 VLDB
9 133 Optimization of Nested SQL Queries Revisited 1987 SIGMOD
10 13,065 A Nested Relational Approach to Processing SQL Subqueries 2005 SIGMOD