DBScholar

Back to papers

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
h77e2847434070de4
Venue
PODS
Year
2006
Pagerank
0.0001123733
Overall Rank
1,276 | 91.43%
DOI
10.1145/1142351.1142363

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{jayram_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{The Containment Problem for Real Conjunctive Queries with Inequalities}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142363},
        doi = {10.1145/1142351.1142363},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Jayram, T.S. and Kolaitis, Phokion G. and Vee, Erik},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank Citing Paper Year Venue Pagerank
461 Query-based Workload Forecasting for Self-Driving Database Management Systems 2018 SIGMOD 0.00017841988
790 Cosette: An Automated Prover for SQL 2017 CIDR 0.00013971102
1,680 Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries 2018 VLDB 9.9000396e-05
2,963 Proving Query Equivalence Using Linear Integer Arithmetic 2023 SIGMOD 7.8035846e-05
3,297 Automated Verification of Query Equivalence Using Satisfiability Modulo Theories 2019 VLDB 7.4421962e-05
3,526 Bag Query Containment and Information Theory 2020 PODS 7.2287658e-05
3,572 Attacking Diophantus: Solving a Special Case of Bag Containment 2019 PODS 7.194371e-05
5,189 Equivalence of Queries Combining Set and Bag-Set Semantics 2006 PODS 6.2342247e-05
6,233 The Impact of Virtual Views on Containment 2010 VLDB 5.8412765e-05
6,303 Classification of Annotation Semirings over Query Containment 2012 PODS 5.8162889e-05
6,670 Determinacy of Real Conjunctive Queries. The Boolean Case 2022 PODS 5.7130266e-05
6,842 Efficient Auditing For Complex SQL queries 2011 SIGMOD 5.665163e-05
8,972 GEqO: ML-Accelerated Semantic Equivalence Detection 2023 SIGMOD 5.2469075e-05
8,981 Qr-Hint: Actionable Hints Towards Correcting Wrong SQL Queries 2024 SIGMOD 5.2433963e-05
10,134 Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability. 2024 PODS 5.0727027e-05
10,404 Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories 2026 PODS 4.9769913e-05
11,752 Collective Grounding: Applying Database Techniques to Grounding Templated Models 2023 VLDB 4.9769913e-05
12,788 Equivalence of SQL Queries In Presence of Embedded Dependencies 2009 PODS 4.9769913e-05
Previous Page 1 / 1 Next

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
310 Optimization of Real Conjunctive Queries 1993 PODS 0.00021364898
880 Rewriting Aggregate Queries Using Views 1999 PODS 0.00013274554
2,271 Deciding Equivalences among Aggregate Queries 1998 PODS 8.7155798e-05
3,871 On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates 1998 PODS 6.9520505e-05
Previous Page 1 / 1 Next

Semantically Similar Papers