On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates
Summary: Containment for safe conjunctive queries with != is Pi2^p-complete; the same syntactic threshold as pure CQs applies—each DB predicate occurring ≤2 in Q1 yields coNP, ≥3 yields Pi2^p. Q2 acyclicity doesn’t help, and fixed-query equivalence can be DP-complete. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 9 of 9 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,522 | The Containment Problem for Real Conjunctive Queries with Inequalities | 2006 | PODS | 0.0001153051 |
| 2,311 | On Improving User Response Times in Tableau | 2015 | SIGMOD | 9.0539767e-05 |
| 2,727 | Semantic Query Optimization in the Presence of Types | 2010 | PODS | 8.2216778e-05 |
| 3,084 | On the minimization of Xpath queries | 2003 | VLDB | 7.6011919e-05 |
| 4,570 | On the Efficiency of Checking Perfect Privacy | 2006 | PODS | 6.0780779e-05 |
| 5,471 | Answering Queries Using Views with Arithmetic Comparisons | 2002 | PODS | 5.4888202e-05 |
| 5,834 | Efficient Detection of Empty-Result Queries | 2006 | VLDB | 5.3103189e-05 |
| 7,085 | Querying Big Data by Accessing Small Data | 2015 | PODS | 4.8388174e-05 |
| 7,660 | Scalable Delivery of Stream Query Result | 2009 | VLDB | 4.6862657e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 3 of 3 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 82 | Answering Queries Using Views (Extended Abstract) | 1995 | PODS | 0.00054402763 |
| 291 | Answering Queries Using Templates With Binding Patterns (Extended Abstract) | 1995 | PODS | 0.00028831632 |
| 915 | The Complexity of Evaluating Relational Queries | 1983 | PODS | 0.0001538509 |
Previous
Page 1 / 1
Next