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)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,905 | The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication | 2015 | PODS | 5.2746158e-05 |
| 12,100 | Efficient Implementation of Generalized Quantification in Relational Query Languages | 2013 | VLDB | 4.1905499e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 248 | Efficient set joins on similarity predicates | 2004 | SIGMOD | 0.00030888982 |
| 1,043 | Set Containment Joins: The Good, The Bad and The Ugly | 2000 | VLDB | 0.00014468616 |
| 1,559 | Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates | 1997 | VLDB | 0.00011368746 |
| 1,757 | Efficient Processing of Joins on Set-valued Attributes | 2003 | SIGMOD | 0.00010659352 |
| 3,678 | Providing Better Support for a Class of Decision Support Queries | 1996 | SIGMOD | 6.8482668e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,043 | Set Containment Joins: The Good, The Bad and The Ugly | 2000 | VLDB | 0.00014468616 |
| 8,065 | Efficient Computation of Quantiles over Joins | 2023 | PODS | 4.5899218e-05 |
| 6,094 | Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited | 1989 | SIGMOD | 5.2099705e-05 |
| 7,979 | On the Optimality of Strategies for Multiple Joins | 1990 | PODS | 4.6089395e-05 |
| 5,561 | On the Complexity of Join Predicates | 2001 | PODS | 5.4346872e-05 |
| 7,161 | Computing the Difference of Conjunctive Queries Efficiently | 2023 | SIGMOD | 4.8086254e-05 |
| 1,757 | Efficient Processing of Joins on Set-valued Attributes | 2003 | SIGMOD | 0.00010659352 |
| 3,519 | Scalable Computation of Acyclic Joins (Extended Abstract) | 2006 | PODS | 7.0181381e-05 |
| 445 | Computing Joins Of Relations | 1975 | SIGMOD | 0.00023029279 |
| 912 | The Complexity of Evaluating Relational Queries | 1983 | PODS | 0.00015374685 |