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
1378
Venue
PODS
Year
2006
Pagerank
0.000113935
Overall Rank
1,269 | 91.30%
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.00018068441
910 Cosette: An Automated Prover for SQL 2017 CIDR 0.00013285905
1,829 Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries 2018 VLDB 9.6671311e-05
3,327 Automated Verification of Query Equivalence Using Satisfiability Modulo Theories 2019 VLDB 7.518491e-05
3,457 Bag Query Containment and Information Theory 2020 PODS 7.3981641e-05
3,498 Attacking Diophantus: Solving a Special Case of Bag Containment 2019 PODS 7.3629798e-05
3,769 Proving Query Equivalence Using Linear Integer Arithmetic 2023 SIGMOD 7.1403543e-05
5,062 Equivalence of Queries Combining Set and Bag-Set Semantics 2006 PODS 6.3799383e-05
6,098 The Impact of Virtual Views on Containment 2010 VLDB 5.9778168e-05
6,166 Classification of Annotation Semirings over Query Containment 2012 PODS 5.952604e-05
6,542 Determinacy of Real Conjunctive Queries. The Boolean Case 2022 PODS 5.8466322e-05
6,705 Efficient Auditing For Complex SQL queries 2011 SIGMOD 5.7970786e-05
8,798 GEqO: ML-Accelerated Semantic Equivalence Detection 2023 SIGMOD 5.3698781e-05
8,834 Qr-Hint: Actionable Hints Towards Correcting Wrong SQL Queries 2024 SIGMOD 5.3599176e-05
9,946 Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability. 2024 PODS 5.1915905e-05
10,175 Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories 2026 PODS 5.093636e-05
11,432 Collective Grounding: Applying Database Techniques to Grounding Templated Models 2023 VLDB 5.093636e-05
12,492 Equivalence of SQL Queries In Presence of Embedded Dependencies 2009 PODS 5.093636e-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
309 Optimization of Real Conjunctive Queries 1993 PODS 0.00021768596
869 Rewriting Aggregate Queries Using Views 1999 PODS 0.00013503594
2,238 Deciding Equivalences among Aggregate Queries 1998 PODS 8.8882317e-05
3,801 On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates 1998 PODS 7.1130194e-05
Previous Page 1 / 1 Next

Semantically Similar Papers