On the complexity of division and set joins in the relational algebra

Summary: Proves that any relational-algebra (∪,−,π,σ,⋈) expression for division or set‑equality join forces quadratic-size intermediates, yielding a dichotomy: either every intermediate is linear or at least one is quadratic. Identifies linear RA with semijoin-only/guarded-fragment, justifying special set-join operators or sorting/aggregation (O(n log n) for division), while set-containment joins remain apparently inherently quadratic. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1341
Venue: PODS
Year: 2005
Pagerank: 5.5564984e-05
Overall Rank: 7,732 | 46.96%
DOI: 10.1145/1065167.1065178

Incoming Non-self Citations Over Time

Authors

1. Dirk Leinders (Limburgs Universitair Centrum)
2. Jan Van den Bussche (Limburgs Universitair Centrum)

BibTeX Citation

@inproceedings{leinders_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{On the complexity of division and set joins in the relational algebra}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065178},
        doi = {10.1145/1065167.1065178},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Leinders, Dirk and Van den Bussche, Jan},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,996	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	6.0150613e-05
12,289	Efficient Implementation of Generalized Quantification in Relational Query Languages	2013	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
200	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025597287
1,151	Set Containment Joins: The Good, The Bad and The Ugly	2000	VLDB	0.00011938186
1,568	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.0001034191
1,592	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD	0.00010253457
3,708	Providing Better Support for a Class of Decision Support Queries	1996	SIGMOD	7.1814701e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,151	Set Containment Joins: The Good, The Bad and The Ugly	2000	VLDB
2	6,072	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD
3	7,286	Efficient Computation of Quantiles over Joins	2023	PODS
4	8,294	On the Optimality of Strategies for Multiple Joins	1990	PODS
5	7,467	On the Complexity of Join Predicates	2001	PODS
6	7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD
7	1,592	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD
8	3,617	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
9	1,479	Computing Joins Of Relations	1975	SIGMOD
10	1,467	The Complexity of Evaluating Relational Queries	1983	PODS