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: 2493
Venue: SIGMOD
Year: 1990
Pagerank: 0.00015487777
Overall Rank: 901 | 93.74%
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
106	Extensible/Rule Based Query Rewrite Optimization in Starburst	1992	SIGMOD	0.00048400734
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022734812
990	Improved Unnesting Algorithms for Join Aggregate SQL Queries	1992	VLDB	0.00014809094
1,032	Outerjoins as Disjunctions	1994	SIGMOD	0.00014544529
1,341	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012486285
3,339	Hypergraph based reorderings of outer join queries with complex predicates	1995	SIGMOD	7.2038026e-05
3,850	Canonical Abstraction for Outerjoin Optimization	2004	SIGMOD	6.7059122e-05
4,938	On the Correct and Complete Enumeration of the Core Search Space	2013	SIGMOD	5.8184655e-05
5,141	Full Disjunctions: Polynomial-Delay Iterators in Action	2006	VLDB	5.6673499e-05
6,806	Query Optimization over Crowdsourced Data	2013	VLDB	4.9218336e-05
7,079	Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases	1997	VLDB	4.8418318e-05
8,784	SQL Query Optimization: Reordering for a General Class of Queries	1996	SIGMOD	4.4527694e-05
11,705	Improving Join Reorderability with Compensation Operators	2018	SIGMOD	4.1945683e-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.0011248121
100	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00049624696
1,451	Extending the Algebraic Framework of Query Processing to Handle Outerjoins	1984	VLDB	0.00011922302
2,468	Supporting Flat Relations by a Nested Relational Kernel	1987	VLDB	8.7416405e-05
2,719	Optimization and Dataflow Algorithms for Nested Tree Queries	1989	VLDB	8.2398923e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00041510555
8,966	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4193184e-05
1,572	Reverse Engineering Complex Join Queries	2013	SIGMOD	0.00011298251
1,032	Outerjoins as Disjunctions	1994	SIGMOD	0.00014544529
4,738	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9600502e-05
421	Query Optimization in the Presence of Foreign Functions	1993	VLDB	0.00023711553
3,339	Hypergraph based reorderings of outer join queries with complex predicates	1995	SIGMOD	7.2038026e-05
8,784	SQL Query Optimization: Reordering for a General Class of Queries	1996	SIGMOD	4.4527694e-05
1,451	Extending the Algebraic Framework of Query Processing to Handle Outerjoins	1984	VLDB	0.00011922302
11,705	Improving Join Reorderability with Compensation Operators	2018	SIGMOD	4.1945683e-05