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,038 | Weighted Hypertree Decompositions and Optimal Query Plans | 2004 | PODS | 0.00014492414 |
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 |
|---|---|---|---|---|
| 76 | Spatial Query Processing in an Object-Oriented Database System | 1986 | SIGMOD | 0.00057303551 |
| 925 | Partition Based Spatial-Merge Join | 1996 | SIGMOD | 0.00015264328 |
| 1,048 | Set Containment Joins: The Good, The Bad and The Ugly | 2000 | VLDB | 0.00014457009 |
| 1,562 | Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates | 1997 | VLDB | 0.00011356744 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,159 | Computing Complex Temporal Join Queries Efficiently | 2022 | SIGMOD | 4.5729025e-05 |
| 502 | Worst-case Optimal Join Algorithms | 2012 | PODS | 0.00021526612 |
| 7,724 | On the complexity of division and set joins in the relational algebra | 2005 | PODS | 4.6673705e-05 |
| 4,194 | On the Complexity of Approximate Query Optimization | 2002 | PODS | 6.3697822e-05 |
| 7,332 | The Complexity of Boolean Conjunctive Queries with Intersection Joins | 2022 | PODS | 4.7606012e-05 |
| 3,929 | Maximally Joining Probabilistic Data | 2007 | PODS | 6.6248763e-05 |
| 3,515 | Scalable Computation of Acyclic Joins (Extended Abstract) | 2006 | PODS | 7.0220813e-05 |
| 4,953 | On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms | 2023 | PODS | 5.8085795e-05 |
| 4,048 | On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates | 1998 | PODS | 6.4968603e-05 |
| 915 | The Complexity of Evaluating Relational Queries | 1983 | PODS | 0.0001538509 |