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,902 | The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication | 2015 | PODS | 5.2796864e-05 |
| 12,092 | Efficient Implementation of Generalized Quantification in Relational Query Languages | 2013 | VLDB | 4.1945683e-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 |
|---|---|---|---|---|
| 250 | Efficient set joins on similarity predicates | 2004 | SIGMOD | 0.00030661988 |
| 1,048 | Set Containment Joins: The Good, The Bad and The Ugly | 2000 | VLDB | 0.00014457009 |
| 1,562 | Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates | 1997 | VLDB | 0.00011356744 |
| 1,763 | Efficient Processing of Joins on Set-valued Attributes | 2003 | SIGMOD | 0.00010638276 |
| 3,676 | Providing Better Support for a Class of Decision Support Queries | 1996 | SIGMOD | 6.8547125e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,048 | Set Containment Joins: The Good, The Bad and The Ugly | 2000 | VLDB | 0.00014457009 |
| 8,061 | Efficient Computation of Quantiles over Joins | 2023 | PODS | 4.5943269e-05 |
| 6,090 | Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited | 1989 | SIGMOD | 5.2148332e-05 |
| 7,976 | On the Optimality of Strategies for Multiple Joins | 1990 | PODS | 4.613363e-05 |
| 5,553 | On the Complexity of Join Predicates | 2001 | PODS | 5.439162e-05 |
| 7,162 | Computing the Difference of Conjunctive Queries Efficiently | 2023 | SIGMOD | 4.8132423e-05 |
| 1,763 | Efficient Processing of Joins on Set-valued Attributes | 2003 | SIGMOD | 0.00010638276 |
| 3,515 | Scalable Computation of Acyclic Joins (Extended Abstract) | 2006 | PODS | 7.0220813e-05 |
| 441 | Computing Joins Of Relations | 1975 | SIGMOD | 0.00023058395 |
| 915 | The Complexity of Evaluating Relational Queries | 1983 | PODS | 0.0001538509 |