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,520 | The Containment Problem for Real Conjunctive Queries with Inequalities | 2006 | PODS | 0.00011524911 |
| 2,318 | On Improving User Response Times in Tableau | 2015 | SIGMOD | 9.04679e-05 |
| 2,732 | Semantic Query Optimization in the Presence of Types | 2010 | PODS | 8.2137395e-05 |
| 3,089 | On the minimization of Xpath queries | 2003 | VLDB | 7.5938563e-05 |
| 4,569 | On the Efficiency of Checking Perfect Privacy | 2006 | PODS | 6.0721066e-05 |
| 5,496 | Answering Queries Using Views with Arithmetic Comparisons | 2002 | PODS | 5.4741922e-05 |
| 5,846 | Efficient Detection of Empty-Result Queries | 2006 | VLDB | 5.3052255e-05 |
| 7,061 | Querying Big Data by Accessing Small Data | 2015 | PODS | 4.8400281e-05 |
| 7,658 | Scalable Delivery of Stream Query Result | 2009 | VLDB | 4.6817213e-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.00054430106 |
| 288 | Answering Queries Using Templates With Binding Patterns (Extended Abstract) | 1995 | PODS | 0.00028885849 |
| 912 | The Complexity of Evaluating Relational Queries | 1983 | PODS | 0.00015374685 |
Previous
Page 1 / 1
Next