{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,11]],"date-time":"2026-09-11T05:57:16Z","timestamp":1789106236013,"version":"build-2803163510"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T00:00:00Z","timestamp":1747180800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"name":"Severo Ochoa and Mar\u00eda de Maeztu Program for Centers and Units of Excellence in R&D","award":["PID2022-138506NB-C22"],"award-info":[{"award-number":["PID2022-138506NB-C22"]}]},{"name":"NSF","award":["1814152"],"award-info":[{"award-number":["1814152"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>\n            The interplay between local consistency and global consistency has been the object of study in several different areas, including probability theory, relational databases, and quantum information. For relational databases, Beeri, Fagin, Maier, and Yannakakis showed that a database schema is acyclic if and only if it has the local-to-global consistency property for relations, which means that every collection of pairwise consistent relations over the schema is globally consistent. More recently, the same result has been shown under bag semantics. In this article, we carry out a systematic study of local versus global consistency for relations over positive commutative monoids, which is a common generalization of ordinary relations and bags. Let\u00a0\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathbb {K}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            be an arbitrary positive commutative monoid. We begin by showing that acyclicity of the schema is a necessary condition for the local-to-global consistency property for\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathbb {K}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -relations to hold. Unlike the case of ordinary relations and bags, however, we show that acyclicity is not always sufficient. Then, we characterize the positive commutative monoids for which acyclicity is both necessary and sufficient for the local-to-global consistency property to hold. This characterization involves a combinatorial property of monoids, which we call the\n            <jats:italic>transportation property<\/jats:italic>\n            . We then identify several different classes of monoids that possess the transportation property. As our final contribution, we introduce a modified notion of local consistency of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathbb {K}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -relations, which we call\n            <jats:italic>pairwise consistency up to the free cover<\/jats:italic>\n            . We prove that, for all positive commutative monoids\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathbb {K}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , even those without the transportation property, acyclicity is both necessary and sufficient for every family of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathbb {K}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -relations that is pairwise consistent up to the free cover to be globally consistent.\n          <\/jats:p>","DOI":"10.1145\/3721855","type":"journal-article","created":{"date-parts":[[2025,4,2]],"date-time":"2025-04-02T11:19:03Z","timestamp":1743592743000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Consistency of Relations over Monoids"],"prefix":"10.1145","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3732-1989","authenticated-orcid":false,"given":"Albert","family":"Atserias","sequence":"first","affiliation":[{"name":"Universitat Politecnica de Catalunya, Barcelona, Spain, and Centre de Recerca Matem\u00e0tica, Bellaterra Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8407-8563","authenticated-orcid":false,"given":"Phokion G.","family":"Kolaitis","sequence":"additional","affiliation":[{"name":"University of California Santa Cruz, Santa Cruz, United States, and Almaden Research Center, IBM Research, San Jose, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,5,14]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320091"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01300131"},{"key":"e_1_3_1_4_2","volume-title":"Numerical Semigroups and Applications","author":"Assi Abdallah","year":"2020","unstructured":"Abdallah Assi, Marco D\u2019Anna, and Pedro A. Garc\u00eda-S\u00e1nchez. 2020. Numerical Semigroups and Applications. Vol. 3. Springer Nature."},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458329"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-24117-8_17"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_33"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322389"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195"},{"key":"e_1_3_1_10_2","series-title":"North-Holland Mathematical Library","volume-title":"Hypergraphs - Combinatorics of Finite Sets","author":"Berge Claude","year":"1989","unstructured":"Claude Berge. 1989. Hypergraphs - Combinatorics of Finite Sets. North-Holland Mathematical Library, Vol. 45. North-Holland."},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100013463"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.IC.2009.02.003"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2983573"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8130-3"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-18098-9_34"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9327-6"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90114-3"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2556524"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.89.052126"},{"key":"e_1_3_1_21_2","article-title":"The computational complexity of the Frobenius problem","volume":"1602","author":"Matsubara Shunichi","year":"2016","unstructured":"Shunichi Matsubara. 2016. The computational complexity of the Frobenius problem. CoRR abs\/1602.05657 (2016). arXiv:1602.05657http:\/\/arxiv.org\/abs\/1602.05657","journal-title":"CoRR"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.78.052119"},{"key":"e_1_3_1_23_2","article-title":"Numerical Semigroups","volume":"20","author":"Rosales J. C.","year":"2009","unstructured":"J. C. Rosales and P. A. Garc\u00eda-S\u00e1nchez. 2009. Numerical Semigroups. Developments in Mathematics 20 (2009). Springer.","journal-title":"Developments in Mathematics"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/0205021"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139195218"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.5555\/17634"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.2307\/2369536"},{"key":"e_1_3_1_28_2","first-page":"115","article-title":"On the complexity of derivation in propositional calculus","author":"Tseitin G. S.","year":"1968","unstructured":"G. S. Tseitin. 1968. On the complexity of derivation in propositional calculus. In Structures in Constructive Mathematics and Mathematical Logic (1968), 115\u2013125. https:\/\/ci.nii.ac.jp\/naid\/10030021172\/en\/","journal-title":"Structures in Constructive Mathematics and Mathematical Logic"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/588111.588114"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/1107014"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3721855","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3721855","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:48Z","timestamp":1750295388000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3721855"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,14]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3721855"],"URL":"https:\/\/doi.org\/10.1145\/3721855","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,14]]},"assertion":[{"value":"2024-10-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-14","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}