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.9551842e-05
Overall Rank: 3,870 | 73.99%
DOI: 10.1145/275487.275510

Incoming Non-self Citations Over Time

Authors

1. Phokion G. Kolaitis (University of California Santa Cruz)
2. David L. Martin (SRI International)
3. Madhukar N. Thakur (Interbase Software Corporation)

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,275	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS	0.00011242154
2,700	On Improving User Response Times in Tableau	2015	SIGMOD	8.1188166e-05
2,881	On the minimization of XPath queries	2003	VLDB	7.9134117e-05
4,240	On the Efficiency of Checking Perfect Privacy	2006	PODS	6.7094069e-05
4,459	Semantic Query Optimization in the Presence of Types	2010	PODS	6.590177e-05
5,492	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.1086968e-05
6,208	Efficient Detection of Empty-Result Queries	2006	VLDB	5.8497045e-05
6,954	Querying Big Data by Accessing Small Data	2015	PODS	5.6350266e-05
8,823	Scalable Delivery of Stream Query Result	2009	VLDB	5.268676e-05

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.00037549176
301	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00021682744
1,503	The Complexity of Evaluating Relational Queries	1983	PODS	0.00010455233

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,660	On the Decidability of Query Containment under Constraints	1998	PODS
2	390	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS
3	1,735	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,053	Polynomial-time program transformations in deductive databases	1990	PODS
7	13,419	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,275	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS