DBScholar

Back to papers

Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins

Summary: Determines when a join/outerjoin query is unambiguously a query graph and catalogs the implementing trees. Proves that for a graph class, all implementing trees yield identical results, enabling freely-reorderable languages and simpler optimization. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
2555
Venue
SIGMOD
Year
1990
Pagerank
0.00012405308
Overall Rank
1,052 | 92.79%
DOI
10.1145/93597.98738

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{rosenthal_sigmod90,
        title = {{Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins}},
        author = {Rosenthal, Arnon and Galindo-Legaria, César},
        series = {{SIGMOD} '90},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/93597.98738},
        url = {https://dl.acm.org/doi/10.1145/93597.98738},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank Citing Paper Year Venue Pagerank
110 Extensible/Rule Based Query Rewrite Optimization in Starburst 1992 SIGMOD 0.0003309592
290 An Overview of Query Optimization in Relational Systems 1998 PODS 0.0002227038
1,012 Improved Unnesting Algorithms for Join Aggregate SQL Queries 1992 VLDB 0.00012682631
1,013 Dynamic Programming Strikes Back 2008 SIGMOD 0.00012652549
1,176 Outerjoins as Disjunctions 1994 SIGMOD 0.00011809075
3,263 Hypergraph based reorderings of outer join queries with complex predicates 1995 SIGMOD 7.584572e-05
3,625 Canonical Abstraction for Outerjoin Optimization 2004 SIGMOD 7.2458252e-05
4,418 On the Correct and Complete Enumeration of the Core Search Space 2013 SIGMOD 6.7137462e-05
6,373 Full Disjunctions: Polynomial-Delay Iterators in Action 2006 VLDB 5.8946564e-05
6,548 Query Optimization over Crowdsourced Data 2013 VLDB 5.8443704e-05
7,183 Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases 1997 VLDB 5.6793385e-05
7,272 SQL Query Optimization: Reordering for a General Class of Queries 1996 SIGMOD 5.6594801e-05
11,909 Improving Join Reorderability with Compensation Operators 2018 SIGMOD 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank Cited Paper Year Venue Pagerank
15 The Functional Data Model and the Data Language DAPLEX 1979 SIGMOD 0.00061144858
95 Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers 1987 VLDB 0.00034607909
1,887 Extending the Algebraic Framework of Query Processing to Handle Outerjoins 1984 VLDB 9.5347906e-05
2,494 Supporting Flat Relations by a Nested Relational Kernel 1987 VLDB 8.5053229e-05
2,815 Optimization and Dataflow Algorithms for Nested Tree Queries 1989 VLDB 8.0964463e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 143 Optimization of Nonrecursive Queries 1986 VLDB
2 6,678 Output-sensitive Conjunctive Query Evaluation 2024 PODS
3 1,313 Reverse Engineering Complex Join Queries 2013 SIGMOD
4 1,176 Outerjoins as Disjunctions 1994 SIGMOD
5 3,813 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD
6 677 Query Optimization in the Presence of Foreign Functions 1993 VLDB
7 3,263 Hypergraph based reorderings of outer join queries with complex predicates 1995 SIGMOD
8 7,272 SQL Query Optimization: Reordering for a General Class of Queries 1996 SIGMOD
9 1,887 Extending the Algebraic Framework of Query Processing to Handle Outerjoins 1984 VLDB
10 11,909 Improving Join Reorderability with Compensation Operators 2018 SIGMOD