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.00011207548
Overall Rank
1,279 | 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
458 Query-based Workload Forecasting for Self-Driving Database Management Systems 2018 SIGMOD 0.00017870238
787 Cosette: An Automated Prover for SQL 2017 CIDR 0.00013959502
1,678 Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries 2018 VLDB 9.8966017e-05
2,971 Proving Query Equivalence Using Linear Integer Arithmetic 2023 SIGMOD 7.7851336e-05
3,294 Automated Verification of Query Equivalence Using Satisfiability Modulo Theories 2019 VLDB 7.4297513e-05
3,533 Bag Query Containment and Information Theory 2020 PODS 7.204863e-05
3,584 Attacking Diophantus: Solving a Special Case of Bag Containment 2019 PODS 7.1705819e-05
5,214 Equivalence of Queries Combining Set and Bag-Set Semantics 2006 PODS 6.2136202e-05
6,244 The Impact of Virtual Views on Containment 2010 VLDB 5.8219706e-05
6,313 Classification of Annotation Semirings over Query Containment 2012 PODS 5.7970566e-05
6,683 Determinacy of Real Conjunctive Queries. The Boolean Case 2022 PODS 5.6941358e-05
6,859 Efficient Auditing For Complex SQL queries 2011 SIGMOD 5.6464901e-05
8,992 GEqO: ML-Accelerated Semantic Equivalence Detection 2023 SIGMOD 5.2295579e-05
9,001 Qr-Hint: Actionable Hints Towards Correcting Wrong SQL Queries 2024 SIGMOD 5.2260584e-05
10,171 Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability. 2024 PODS 5.0559291e-05
10,470 Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories 2026 PODS 4.9605343e-05
11,796 Collective Grounding: Applying Database Techniques to Grounding Templated Models 2023 VLDB 4.9605343e-05
12,831 Equivalence of SQL Queries In Presence of Embedded Dependencies 2009 PODS 4.9605343e-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
312 Optimization of Real Conjunctive Queries 1993 PODS 0.00021306615
882 Rewriting Aggregate Queries Using Views 1999 PODS 0.00013239752
2,284 Deciding Equivalences among Aggregate Queries 1998 PODS 8.6880978e-05
3,883 On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates 1998 PODS 6.9293185e-05
Previous Page 1 / 1 Next

Semantically Similar Papers