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: 2494
Venue: SIGMOD
Year: 1990
Pagerank: 0.00015476243
Overall Rank: 898 | 93.77%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Arnon Rosenthal
2. César Galindo-Legaria

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
107	Extensible/Rule Based Query Rewrite Optimization in Starburst	1992	SIGMOD	0.00048363446
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022796106
991	Improved Unnesting Algorithms for Join Aggregate SQL Queries	1992	VLDB	0.00014797083
1,034	Outerjoins as Disjunctions	1994	SIGMOD	0.00014532543
1,344	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012477274
3,338	Hypergraph based reorderings of outer join queries with complex predicates	1995	SIGMOD	7.1990012e-05
3,849	Canonical Abstraction for Outerjoin Optimization	2004	SIGMOD	6.7000711e-05
4,939	On the Correct and Complete Enumeration of the Core Search Space	2013	SIGMOD	5.8131374e-05
5,137	Full Disjunctions: Polynomial-Delay Iterators in Action	2006	VLDB	5.6653126e-05
6,801	Query Optimization over Crowdsourced Data	2013	VLDB	4.9175463e-05
7,075	Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases	1997	VLDB	4.8371887e-05
8,778	SQL Query Optimization: Reordering for a General Class of Queries	1996	SIGMOD	4.4486677e-05
11,710	Improving Join Reorderability with Compensation Operators	2018	SIGMOD	4.1905499e-05

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
12	The Functional Data Model and the Data Language DAPLEX	1979	SIGMOD	0.0011268747
102	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00049592627
1,455	Extending the Algebraic Framework of Query Processing to Handle Outerjoins	1984	VLDB	0.00011912375
2,466	Supporting Flat Relations by a Nested Relational Kernel	1987	VLDB	8.734134e-05
2,722	Optimization and Dataflow Algorithms for Nested Tree Queries	1989	VLDB	8.232489e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
144	Optimization of Nonrecursive Queries	1986	VLDB	0.00041430126
8,972	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4150824e-05
1,575	Reverse Engineering Complex Join Queries	2013	SIGMOD	0.00011288804
1,034	Outerjoins as Disjunctions	1994	SIGMOD	0.00014532543
4,734	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9553181e-05
418	Query Optimization in the Presence of Foreign Functions	1993	VLDB	0.0002372277
3,338	Hypergraph based reorderings of outer join queries with complex predicates	1995	SIGMOD	7.1990012e-05
8,778	SQL Query Optimization: Reordering for a General Class of Queries	1996	SIGMOD	4.4486677e-05
1,455	Extending the Algebraic Framework of Query Processing to Handle Outerjoins	1984	VLDB	0.00011912375
11,710	Improving Join Reorderability with Compensation Operators	2018	SIGMOD	4.1905499e-05