{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T21:11:05Z","timestamp":1762981865891,"version":"3.44.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["2022\/45\/B\/ST6\/00457"],"award-info":[{"award-number":["2022\/45\/B\/ST6\/00457"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>Query Containment Problem (QCP) is one of the most fundamental decision problems in database query processing and optimization.<\/jats:p>\n          <jats:p>Complexity of QCP for conjunctive queries has been fully understood since 1970s. But, as Chaudhuri and Vardi noticed in their classical 1993 paper this understanding is based on the assumption that query answers are sets of tuples, and it does not transfer to the situation when multi-set (bag) semantics is considered.<\/jats:p>\n          <jats:p>Now, 30 years later, decidability of QCP for bag semantics remains an open question, one of the most intriguing open questions in database theory.<\/jats:p>\n          <jats:p>\n            In this paper we show a series of undecidability results for some generalizations of this problem. We show, for example, that the problem whether, for given two boolean conjunctive queries \u03c6\n            <jats:sub>s<\/jats:sub>\n            and \u03c6\n            <jats:sub>b<\/jats:sub>\n            , and a linear function F, the inequality F(\u03c6\n            <jats:sub>s<\/jats:sub>\n            (D)) =&lt; \u03c6\n            <jats:sub>b<\/jats:sub>\n            (D) holds for each database instance D, is undecidable.\n          <\/jats:p>","DOI":"10.1145\/3651604","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-24","source":"Crossref","is-referenced-by-count":2,"title":["Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability."],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6539-6788","authenticated-orcid":false,"given":"Jerzy","family":"Marcinkowski","sequence":"first","affiliation":[{"name":"University of Wroc\u0142aw, Wroc\u0142aw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-6278-1548","authenticated-orcid":false,"given":"Mateusz","family":"Orda","sequence":"additional","affiliation":[{"name":"University of Wroc\u0142aw, Wroc\u0142aw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"59","volume-title":"PODS '93","author":"Chaudhuri S.","unstructured":"S. Chaudhuri and M. Y. Vardi, \"Optimization of real conjunctive queries,\" in Proceedings of the Twelfth ACM SIGACTSIGMOD-SIGART Symposium on Principles of Database Systems, PODS '93, (New York, NY, USA), p. 59--70, Association for Computing Machinery, 1993."},{"key":"e_1_2_1_2_1","first-page":"77","volume-title":"Boulder","author":"Chandra A. K.","year":"1977","unstructured":"A. K. Chandra and P. M. Merlin, \"Optimal implementation of conjunctive queries in relational data bases,\" in Proceedings of the 9th Annual ACM Symposium on Theory of Computing, May 4--6, 1977, Boulder, Colorado, USA, pp. 77--90, ACM, 1977."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322221"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/42267.42273"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1455"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/103516.103521"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.02.017"},{"key":"e_1_2_1_8_1","first-page":"237","volume-title":"PODS 2012","author":"Kostylev E. V.","year":"2012","unstructured":"E. V. Kostylev, J. L. Reutter, and A. Z. Salamon, \"Classification of annotation semirings over query containment,\" in Proc. of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20--24, 2012, pp. 237--248, ACM, 2012."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0122-1"},{"key":"e_1_2_1_10_1","first-page":"262","volume-title":"Conf. on Database Theory, ICDT '12","author":"Chirkova R.","year":"2012","unstructured":"R. Chirkova, \"Equivalence and minimization of conjunctive queries under combined semantics,\" in 15th Int. Conf. on Database Theory, ICDT '12, Berlin, Germany, March 26--29, 2012, pp. 262--273, ACM, 2012."},{"key":"e_1_2_1_11_1","first-page":"399","volume-title":"PODS 2019","author":"Konstantinidis G.","year":"2019","unstructured":"G. Konstantinidis and F. Mogavero, \"Attacking diophantus: Solving a special case of bag containment,\" in Proc. of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, pp. 399--413, ACM, 2019."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.03.009"},{"key":"e_1_2_1_13_1","first-page":"95","volume-title":"PODS'20","author":"Abo Khamis M.","unstructured":"M. Abo Khamis, P. G. Kolaitis, H. Q. Ngo, and D. Suciu, \"Bag query containment and information theory,\" in Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS'20, (New York, NY, USA), p. 95--112, Association for Computing Machinery, 2020."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/211414.211419"},{"key":"e_1_2_1_15_1","first-page":"80","volume-title":"PODS '06","author":"Jayram T. S.","unstructured":"T. S. Jayram, P. G. Kolaitis, and E. Vee, \"The containment problem for real conjunctive queries with inequalities,\" in Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS '06, (New York, NY, USA), p. 80--89, Association for Computing Machinery, 2006."},{"key":"e_1_2_1_16_1","first-page":"347","volume-title":"Determinacy of real conjunctive queries. the boolean case,\" in PODS '22: International Conference on Management of Data","author":"Kwiecien J.","year":"2022","unstructured":"J. Kwiecien, J. Marcinkowski, and P. Ostropolski-Nalewaja, \"Determinacy of real conjunctive queries. the boolean case,\" in PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022 (L. Libkin and P. Barcel\u00f3, eds.), pp. 347--358, ACM, 2022."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/060"},{"key":"e_1_2_1_18_1","volume-title":"North-Holland","author":"Davis M.","year":"1977","unstructured":"M. Davis, \"Unsolvable problems,\" in Handbook of Mathematical Logic (J. Barwise, ed.), pp. 567--594, North-Holland, Amsterdam, 1977."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651604","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651604","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:39:06Z","timestamp":1755898746000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651604"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651604"],"URL":"https:\/\/doi.org\/10.1145\/3651604","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}