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: 1145
Venue: PODS
Year: 1998
Pagerank: 7.1130194e-05
Overall Rank: 3,801 | 73.93%
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,269	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS	0.000113935
2,686	On Improving User Response Times in Tableau	2015	SIGMOD	8.25822e-05
2,817	On the minimization of XPath queries	2003	VLDB	8.0945626e-05
4,159	On the Efficiency of Checking Perfect Privacy	2006	PODS	6.8626218e-05
4,369	Semantic Query Optimization in the Presence of Types	2010	PODS	6.7390374e-05
5,361	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.2484907e-05
6,084	Efficient Detection of Empty-Result Queries	2006	VLDB	5.9830699e-05
6,841	Querying Big Data by Accessing Small Data	2015	PODS	5.7574257e-05
8,663	Scalable Delivery of Stream Query Result	2009	VLDB	5.3887668e-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
69	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00038090878
298	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00022138018
1,467	The Complexity of Evaluating Relational Queries	1983	PODS	0.00010687075

Semantically Similar Papers

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