DBScholar

Back to papers

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)

Paper ID
hfaba59b18932d628
Venue
PODS
Year
1998
Pagerank
6.9520505e-05
Overall Rank
3,871 | 73.99%
DOI
10.1145/275487.275510

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{kolaitis_pods98,
        address = {New York, NY, USA},
        series = {{PODS} '98},
        title = {{On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates}},
        url = {https://dl.acm.org/doi/10.1145/275487.275510},
        doi = {10.1145/275487.275510},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kolaitis, Phokion G. and Martin, David L. and Thakur, Madhukar N.},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank Citing Paper Year Venue Pagerank
1,276 The Containment Problem for Real Conjunctive Queries with Inequalities 2006 PODS 0.0001123733
2,697 On Improving User Response Times in Tableau 2015 SIGMOD 8.1166572e-05
2,883 On the minimization of XPath queries 2003 VLDB 7.9096688e-05
4,241 On the Efficiency of Checking Perfect Privacy 2006 PODS 6.7062376e-05
4,461 Semantic Query Optimization in the Presence of Types 2010 PODS 6.5870588e-05
5,496 Answering Queries Using Views with Arithmetic Comparisons 2002 PODS 6.1058078e-05
6,212 Efficient Detection of Empty-Result Queries 2006 VLDB 5.8469404e-05
6,948 Querying Big Data by Accessing Small Data 2015 PODS 5.6350267e-05
8,832 Scalable Delivery of Stream Query Result 2009 VLDB 5.2661819e-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
72 Answering Queries Using Views (Extended Abstract) 1995 PODS 0.0003753293
301 Answering Queries Using Templates With Binding Patterns (Extended Abstract) 1995 PODS 0.00021673683
1,503 The Complexity of Evaluating Relational Queries 1983 PODS 0.00010450365
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,661 On the Decidability of Query Containment under Constraints 1998 PODS
2 391 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS
3 1,737 The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints 2015 PODS
4 642 The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version) 1992 PODS
5 136 Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract) 1982 PODS
6 8,059 Polynomial-time program transformations in deductive databases 1990 PODS
7 13,425 Complexity of Query Processing in Databases with OR-Objects 1989 PODS
8 1,503 The Complexity of Evaluating Relational Queries 1983 PODS
9 1,818 Deciding Containment for Queries with Complex Objects (Extended Abstract) 1997 PODS
10 1,276 The Containment Problem for Real Conjunctive Queries with Inequalities 2006 PODS