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.9293185e-05
Overall Rank: 3,883 | 73.98%
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,279	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS	0.00011207548
2,701	On Improving User Response Times in Tableau	2015	SIGMOD	8.0959949e-05
2,897	On the minimization of XPath queries	2003	VLDB	7.8835751e-05
4,257	On the Efficiency of Checking Perfect Privacy	2006	PODS	6.6841081e-05
4,482	Semantic Query Optimization in the Presence of Types	2010	PODS	6.5653184e-05
5,516	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.0859896e-05
6,224	Efficient Detection of Empty-Result Queries	2006	VLDB	5.828372e-05
6,964	Querying Big Data by Accessing Small Data	2015	PODS	5.617412e-05
8,850	Scalable Delivery of Stream Query Result	2009	VLDB	5.2489348e-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.00037421163
301	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00021612162
1,508	The Complexity of Evaluating Relational Queries	1983	PODS	0.00010416537

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,667	On the Decidability of Query Containment under Constraints	1998	PODS
2	391	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS
3	1,747	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
4	645	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,076	Polynomial-time program transformations in deductive databases	1990	PODS
7	13,466	Complexity of Query Processing in Databases with OR-Objects	1989	PODS
8	1,508	The Complexity of Evaluating Relational Queries	1983	PODS
9	1,827	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS
10	1,279	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS