The Containment Problem for Real Conjunctive Queries with Inequalities

Summary: Proves undecidability of conjunctive-query containment with inequalities under bag semantics (and bag-set), resolving a long-standing open problem about bag containment. Undecidability holds even with a single binary relation and a fixed bound on inequalities. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1379
Venue: PODS
Year: 2006
Pagerank: 0.0001153051
Overall Rank: 1,522 | 89.42%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
716	Query-based Workload Forecasting for Self-Driving Database Management Systems	2018	SIGMOD	0.00017723171
1,057	Cosette: An Automated Prover for SQL	2017	CIDR	0.0001439886
2,099	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB	9.5479391e-05
3,307	Attacking Diophantus: Solving a Special Case of Bag Containment	2019	PODS	7.2431594e-05
3,775	Bag Query Containment and Information Theory	2020	PODS	6.775636e-05
3,901	Automated Verification of Query Equivalence Using Satisfiability Modulo Theories	2019	VLDB	6.6499845e-05
4,388	Proving Query Equivalence Using Linear Integer Arithmetic	2023	SIGMOD	6.2303078e-05
5,195	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS	5.6366303e-05
6,274	Classification of Annotation Semirings over Query Containment	2012	PODS	5.1321227e-05
6,275	Determinacy of Real Conjunctive Queries. The Boolean Case	2022	PODS	5.1319495e-05
6,510	Efficient Auditing For Complex SQL queries	2011	SIGMOD	5.0326078e-05
7,275	The Impact of Virtual Views on Containment	2010	VLDB	4.7806552e-05
8,783	GEqO: ML-Accelerated Semantic Equivalence Detection	2023	SIGMOD	4.452825e-05
9,623	Qr-Hint: Actionable Hints Towards Correcting Wrong SQL Queries	2024	SIGMOD	4.3161663e-05
9,791	Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.	2024	PODS	4.2818172e-05
10,002	Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories	2026	PODS	4.1945683e-05
11,232	Collective Grounding: Applying Database Techniques to Grounding Templated Models	2023	VLDB	4.1945683e-05
12,297	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
335	Optimization of Real Conjunctive Queries	1993	PODS	0.00027036073
971	Rewriting Aggregate Queries Using Views	1999	PODS	0.00014925576
2,103	Deciding Equivalences among Aggregate Queries	1998	PODS	9.5385023e-05
4,048	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	6.4968603e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,275	Determinacy of Real Conjunctive Queries. The Boolean Case	2022	PODS	5.1319495e-05
407	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024004562
3,307	Attacking Diophantus: Solving a Special Case of Bag Containment	2019	PODS	7.2431594e-05
1,490	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011699154
1,952	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.9677831e-05
4,048	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	6.4968603e-05
335	Optimization of Real Conjunctive Queries	1993	PODS	0.00027036073
10,002	Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories	2026	PODS	4.1945683e-05
3,775	Bag Query Containment and Information Theory	2020	PODS	6.775636e-05
9,791	Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.	2024	PODS	4.2818172e-05