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: 1880
Venue: PODS
Year: 2022
Pagerank: 5.6135032e-05
Overall Rank: 7,451 | 48.89%
DOI: 10.1145/3517804.3524156

Incoming Non-self Citations Over Time

Authors

1. Mahmoud Abo Khamis (RelationalAI)
2. George Chichirim (University of Oxford)
3. Antonia Kormpa (University of Oxford)
4. Dan Olteanu (University of Zurich)

BibTeX Citation

@inproceedings{khamis_pods22,
        address = {New York, NY, USA},
        series = {{PODS} '22},
        title = {{The Complexity of Boolean Conjunctive Queries with Intersection Joins}},
        url = {https://dl.acm.org/doi/10.1145/3517804.3524156},
        doi = {10.1145/3517804.3524156},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Khamis, Mahmoud Abo and Chichirim, George and Kormpa, Antonia and Olteanu, Dan},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,732	Insert-Only versus Insert-Delete in Dynamic Query Evaluation	2024	PODS	5.7885064e-05
7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.6852987e-05
11,141	Optimal (Multiway) Spatial Joins	2024	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021283186
728	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014542772
994	Spatial Hash-Joins	1996	SIGMOD	0.00012764684
1,109	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012142685
1,857	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.6047945e-05
1,880	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5562066e-05
2,266	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	8.8391372e-05
2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.7650894e-05
2,462	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.5487602e-05
3,066	Size Separation Spatial Join	1997	SIGMOD	7.7941163e-05
4,268	Joining Interval Data in Relational Databases	2004	SIGMOD	6.7925685e-05
6,106	A Forward Scan based Plane Sweep Algorithm for Parallel Interval Joins	2017	VLDB	5.973703e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,121	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS
2	4,401	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS
3	1,857	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS
4	7,558	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS
5	6,678	Output-sensitive Conjunctive Query Evaluation	2024	PODS
6	5,593	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB
7	1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
8	7,467	On the Complexity of Join Predicates	2001	PODS
9	3,617	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
10	8,235	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD