Hypergraph based reorderings of outer join queries with complex predicates

Summary: Proposes a hypergraph abstraction to reorder outer-join queries with complex predicates and duplicates, addressing inadequacies of traditional query-graph models. Enables a larger, DP-friendly plan space and cost-based optimization, yielding plans. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h2fb7a18a7cb20b65
Venue: SIGMOD
Year: 1995
Pagerank: 7.4510308e-05
Overall Rank: 3,279 | 78.03%
DOI: 10.1145/223784.223847

Incoming Non-self Citations Over Time

Authors

1. Gautam Bhargava (IBM)
2. Piyush Goel (IBM)
3. Bala Iyer (IBM)

BibTeX Citation

@inproceedings{bhargava_sigmod95,
        title = {{Hypergraph based reorderings of outer join queries with complex predicates}},
        author = {Bhargava, Gautam and Goel, Piyush and Iyer, Bala},
        series = {{SIGMOD} '95},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/223784.223847},
        url = {https://dl.acm.org/doi/10.1145/223784.223847},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
881	Dynamic Programming Strikes Back	2008	SIGMOD	0.0001324243
1,164	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD	0.0001170903
2,261	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.7351549e-05
4,486	On the Correct and Complete Enumeration of the Core Search Space	2013	SIGMOD	6.5638966e-05
6,395	View Matching for Outer-Join Views	2005	VLDB	5.7850662e-05
7,371	SQL Query Optimization: Reordering for a General Class of Queries	1996	SIGMOD	5.5257045e-05
9,828	Computing Full Disjunctions	2003	PODS	5.1074821e-05
12,258	Improving Join Reorderability with Compensation Operators	2018	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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
99	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00034024478
109	Extensible/Rule Based Query Rewrite Optimization in Starburst	1992	SIGMOD	0.00032702871
133	Optimization of Nested SQL Queries Revisited	1987	SIGMOD	0.0003015194
1,063	Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins	1990	SIGMOD	0.00012198695
1,201	Outerjoins as Disjunctions	1994	SIGMOD	0.00011523243
2,538	Supporting Flat Relations by a Nested Relational Kernel	1987	VLDB	8.3052522e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,739	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS
2	8,064	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD
3	3,708	Canonical Abstraction for Outerjoin Optimization	2004	SIGMOD
4	3,807	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD
5	1,353	Reverse Engineering Complex Join Queries	2013	SIGMOD
6	1,945	Extending the Algebraic Framework of Query Processing to Handle Outerjoins	1984	VLDB
7	1,063	Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins	1990	SIGMOD
8	881	Dynamic Programming Strikes Back	2008	SIGMOD
9	12,258	Improving Join Reorderability with Compensation Operators	2018	SIGMOD
10	7,371	SQL Query Optimization: Reordering for a General Class of Queries	1996	SIGMOD