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)

Paper ID: h6fd8084730468b9f
Venue: PODS
Year: 2001
Pagerank: 5.4849468e-05
Overall Rank: 7,608 | 48.85%
DOI: 10.1145/375551.375592

Incoming Non-self Citations Over Time

Authors

1. Jin-Yi Cai (University of Wisconsin)
2. Venkatesan T. Chakaravarthy (University of Wisconsin)
3. Jeffrey F. Naughton (University of Wisconsin)
4. Raghav Kaushik (University of Wisconsin)

BibTeX Citation

@inproceedings{cai_pods01,
        address = {New York, NY, USA},
        series = {{PODS} '01},
        title = {{On the Complexity of Join Predicates}},
        url = {https://dl.acm.org/doi/10.1145/375551.375592},
        doi = {10.1145/375551.375592},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cai, Jin-Yi and Chakaravarthy, Venkatesan T. and Naughton, Jeffrey F. and Kaushik, Raghav},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,728	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	8.0895728e-05

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
101	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00033937215
752	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014246504
1,171	Set Containment Joins: The Good, The Bad and The Ugly	2000	VLDB	0.00011702886
1,594	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00010133792

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,609	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD
2	402	Worst-case Optimal Join Algorithms	2012	PODS
3	7,896	On the complexity of division and set joins in the relational algebra	2005	PODS
4	3,567	On the Complexity of Approximate Query Optimization	2002	PODS
5	6,955	The Complexity of Boolean Conjunctive Queries with Intersection Joins	2022	PODS
6	4,262	Maximally Joining Probabilistic Data	2007	PODS
7	3,660	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
8	3,494	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS
9	3,870	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS
10	1,503	The Complexity of Evaluating Relational Queries	1983	PODS