The Complexity of Evaluating Relational Queries
Summary: Exact complexity for projection+natural-join queries: result-equality is DP-complete; containment/equivalence (w.r.t. a fixed relation or fixed query) is Pi_2^p-complete. Also shows cardinality estimation is hard and intermediate joins can blow up exponentially, so joins are combinatorially hard beyond known polynomial cases. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 6 of 6 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 494 | Data Exchange: Getting to the Core | 2003 | PODS | 0.00021805832 |
| 602 | On the Complexity of Bounded-Variable Queries | 1995 | PODS | 0.00019352415 |
| 827 | On the Representation and Querying of Sets of Possible Worlds | 1987 | SIGMOD | 0.00016220185 |
| 1,448 | Theory of Database Queries (Extended Abstract) | 1988 | PODS | 0.00011938045 |
| 4,048 | On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates | 1998 | PODS | 6.4968603e-05 |
| 6,509 | Representing and Querying XML with Incomplete Information | 2001 | PODS | 5.0331402e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 0 of 0 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next