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.00011524911
Overall Rank: 1,520 | 89.44%
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
704	Query-based Workload Forecasting for Self-Driving Database Management Systems	2018	SIGMOD	0.00017785557
1,056	Cosette: An Automated Prover for SQL	2017	CIDR	0.00014391317
2,097	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB	9.5439744e-05
3,311	Attacking Diophantus: Solving a Special Case of Bag Containment	2019	PODS	7.2361776e-05
3,782	Bag Query Containment and Information Theory	2020	PODS	6.7691169e-05
3,903	Automated Verification of Query Equivalence Using Satisfiability Modulo Theories	2019	VLDB	6.6439695e-05
4,385	Proving Query Equivalence Using Linear Integer Arithmetic	2023	SIGMOD	6.2247394e-05
5,196	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS	5.6311982e-05
6,272	Classification of Annotation Semirings over Query Containment	2012	PODS	5.1271971e-05
6,273	Determinacy of Real Conjunctive Queries. The Boolean Case	2022	PODS	5.1270241e-05
6,504	Efficient Auditing For Complex SQL queries	2011	SIGMOD	5.0283716e-05
7,272	The Impact of Virtual Views on Containment	2010	VLDB	4.7760673e-05
8,780	GEqO: ML-Accelerated Semantic Equivalence Detection	2023	SIGMOD	4.4485568e-05
9,623	Qr-Hint: Actionable Hints Towards Correcting Wrong SQL Queries	2024	SIGMOD	4.3120302e-05
9,794	Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.	2024	PODS	4.2777144e-05
10,001	Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories	2026	PODS	4.1905499e-05
11,234	Collective Grounding: Applying Database Techniques to Grounding Templated Models	2023	VLDB	4.1905499e-05
12,305	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS	4.1905499e-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.00027012705
971	Rewriting Aggregate Queries Using Views	1999	PODS	0.00014915911
2,105	Deciding Equivalences among Aggregate Queries	1998	PODS	9.5309231e-05
4,055	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	6.4906839e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,273	Determinacy of Real Conjunctive Queries. The Boolean Case	2022	PODS	5.1270241e-05
401	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024281448
3,311	Attacking Diophantus: Solving a Special Case of Bag Containment	2019	PODS	7.2361776e-05
1,489	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011687823
1,959	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.958725e-05
4,055	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	6.4906839e-05
335	Optimization of Real Conjunctive Queries	1993	PODS	0.00027012705
10,001	Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories	2026	PODS	4.1905499e-05
3,782	Bag Query Containment and Information Theory	2020	PODS	6.7691169e-05
9,794	Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.	2024	PODS	4.2777144e-05