The Complexity of Boolean Conjunctive Queries with Intersection Joins

Summary: Reduce BCQs with intersection joins to disjunctions of equality-join BCQs, yielding ij-width that exactly captures their complexity. Define iota-acyclicity (alpha-acyclicity analogue) characterising near-linear evaluation; non-iota queries are triangle-hard. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1848
Venue: PODS
Year: 2022
Pagerank: 4.7560344e-05
Overall Rank: 7,328 | 49.08%
DOI: 10.1145/3517804.3524156

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	4.8086254e-05
8,428	Insert-Only versus Insert-Delete in Dynamic Query Evaluation	2024	PODS	4.5095504e-05
10,925	Optimal (Multiway) Spatial Joins	2024	PODS	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518
923	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015254021
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013490827
1,452	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011922523
2,119	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5036401e-05
2,298	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.0746479e-05
2,673	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.3323551e-05
3,009	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	7.7230513e-05
3,462	Size Separation Spatial Join	1997	SIGMOD	7.0683581e-05
3,831	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	6.7146681e-05
4,738	Joining Interval Data in Relational Databases	2004	SIGMOD	5.9526916e-05
6,232	A Forward Scan based Plane Sweep Algorithm for Parallel Interval Joins	2017	VLDB	5.1391814e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,903	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.1905499e-05
7,064	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS	4.8391823e-05
2,298	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.0746479e-05
4,430	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1879319e-05
8,972	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4150824e-05
5,963	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2485815e-05
2,246	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2039096e-05
5,561	On the Complexity of Join Predicates	2001	PODS	5.4346872e-05
3,519	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.0181381e-05
8,163	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	4.5685178e-05