On the Complexity of Join Predicates
Summary: Graph-pebbling model to characterize equijoins, spatial-overlap, and set-containment joins by optimal pebbling length and the complexity of finding strategies. Equijoins admit linear-time optimal pebblings meeting global lower bounds; spatial-overlap and set-containment can reach global upper bounds and discovering optimal pebblings is NP-complete (set-containment MAX-SNP-complete and inapproximable). (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,039 | Weighted Hypertree Decompositions and Optimal Query Plans | 2004 | PODS | 0.00014488271 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 4 of 4 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 75 | Spatial Query Processing in an Object-Oriented Database System | 1986 | SIGMOD | 0.00057450043 |
| 923 | Partition Based Spatial-Merge Join | 1996 | SIGMOD | 0.00015254021 |
| 1,043 | Set Containment Joins: The Good, The Bad and The Ugly | 2000 | VLDB | 0.00014468616 |
| 1,559 | Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates | 1997 | VLDB | 0.00011368746 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,163 | Computing Complex Temporal Join Queries Efficiently | 2022 | SIGMOD | 4.5685178e-05 |
| 503 | Worst-case Optimal Join Algorithms | 2012 | PODS | 0.00021517145 |
| 7,722 | On the complexity of division and set joins in the relational algebra | 2005 | PODS | 4.6628934e-05 |
| 4,189 | On the Complexity of Approximate Query Optimization | 2002 | PODS | 6.3681294e-05 |
| 7,328 | The Complexity of Boolean Conjunctive Queries with Intersection Joins | 2022 | PODS | 4.7560344e-05 |
| 3,929 | Maximally Joining Probabilistic Data | 2007 | PODS | 6.620459e-05 |
| 3,519 | Scalable Computation of Acyclic Joins (Extended Abstract) | 2006 | PODS | 7.0181381e-05 |
| 4,926 | On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms | 2023 | PODS | 5.8184457e-05 |
| 4,055 | On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates | 1998 | PODS | 6.4906839e-05 |
| 912 | The Complexity of Evaluating Relational Queries | 1983 | PODS | 0.00015374685 |