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.00011242154
Overall Rank
1,275 | 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
460 Query-based Workload Forecasting for Self-Driving Database Management Systems 2018 SIGMOD 0.00017842695
790 Cosette: An Automated Prover for SQL 2017 CIDR 0.00013976438
1,680 Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries 2018 VLDB 9.9031411e-05
2,961 Proving Query Equivalence Using Linear Integer Arithmetic 2023 SIGMOD 7.8068219e-05
3,297 Automated Verification of Query Equivalence Using Satisfiability Modulo Theories 2019 VLDB 7.4452842e-05
3,526 Bag Query Containment and Information Theory 2020 PODS 7.2321894e-05
3,570 Attacking Diophantus: Solving a Special Case of Bag Containment 2019 PODS 7.1977783e-05
5,187 Equivalence of Queries Combining Set and Bag-Set Semantics 2006 PODS 6.2371772e-05
6,230 The Impact of Virtual Views on Containment 2010 VLDB 5.844043e-05
6,299 Classification of Annotation Semirings over Query Containment 2012 PODS 5.8190435e-05
6,666 Determinacy of Real Conjunctive Queries. The Boolean Case 2022 PODS 5.7157324e-05
6,838 Efficient Auditing For Complex SQL queries 2011 SIGMOD 5.6678362e-05
8,962 GEqO: ML-Accelerated Semantic Equivalence Detection 2023 SIGMOD 5.2493925e-05
8,972 Qr-Hint: Actionable Hints Towards Correcting Wrong SQL Queries 2024 SIGMOD 5.2458797e-05
10,130 Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability. 2024 PODS 5.0751052e-05
10,392 Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories 2026 PODS 4.9793485e-05
11,746 Collective Grounding: Applying Database Techniques to Grounding Templated Models 2023 VLDB 4.9793485e-05
12,782 Equivalence of SQL Queries In Presence of Embedded Dependencies 2009 PODS 4.9793485e-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.00021374145
880 Rewriting Aggregate Queries Using Views 1999 PODS 0.00013280642
2,269 Deciding Equivalences among Aggregate Queries 1998 PODS 8.7196256e-05
3,870 On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates 1998 PODS 6.9551842e-05
Previous Page 1 / 1 Next

Semantically Similar Papers