{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:43:35Z","timestamp":1755999815391,"version":"3.44.0"},"reference-count":14,"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\/501100011033","name":"Agencia Estatal de Investigaci\u00f3n","doi-asserted-by":"crossref","award":["PID2022-128606NB-C22 (PROOFS BEYOND), Severo Ochoa and Mar\u00eda de Maeztu Program for Centers and Units of Excellence in R\\&D (CEX2020-001084-M)"],"award-info":[{"award-number":["PID2022-128606NB-C22 (PROOFS BEYOND), Severo Ochoa and Mar\u00eda de Maeztu Program for Centers and Units of Excellence in R\\&D (CEX2020-001084-M)"]}],"id":[{"id":"10.13039\/501100011033","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100006374","name":"Generalitat de Catalunya","doi-asserted-by":"publisher","award":["ICREA Academia Programme 2022, CERCA Programme"],"award-info":[{"award-number":["ICREA Academia Programme 2022, CERCA Programme"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"NSF","doi-asserted-by":"publisher","award":["1814152"],"award-info":[{"award-number":["1814152"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>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 paper, we carry out a systematic study of local vs. global consistency for relations over positive commutative monoids, which is a common generalization of ordinary relations and bags. Let K 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 K-relations to hold. Unlike the case of ordinary relations and bags, however, we show that acyclicity is not always sufficient. After this, 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 transportation property. 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 K-relations, which we call pairwise consistency up to the free cover. We prove that, for all positive commutative monoids K, even those without the transportation property, acyclicity is both necessary and sufficient for every family of K-relations that is pairwise consistent up to the free cover to be globally consistent.<\/jats:p>","DOI":"10.1145\/3651608","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-15","source":"Crossref","is-referenced-by-count":1,"title":["Consistency of Relations over Monoids"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3732-1989","authenticated-orcid":false,"given":"Albert","family":"Atserias","sequence":"first","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya &amp; Centre de Recerca Matem\u00e0tica, Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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 &amp; IBM Research, Santa Cruz, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320091"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458329"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-24117-8_17"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322389"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8130-3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9327-6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90114-3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556524"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.78.052119"},{"key":"e_1_2_1_12_1","first-page":"115","volume-title":"Structures in Constructive Mathematics and Mathematical Logic","author":"Tseitin G. S.","year":"1968","unstructured":"G. S. Tseitin. On the complexity of derivation in propositional calculus. Structures in Constructive Mathematics and Mathematical Logic, pages 115--125, 1968."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the ACM Symposium on Principles of Database Systems, March 29--31, 1982","author":"Ullman Jeffrey D.","year":"1982","unstructured":"Jeffrey D. Ullman. The U.R. strikes back. In Jeffrey D. Ullman and Alfred V. Aho, editors, Proceedings of the ACM Symposium on Principles of Database Systems, March 29--31, 1982, Los Angeles, California, USA, pages 10--22. ACM, 1982."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1107014"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651608","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651608","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:41:02Z","timestamp":1755898862000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651608"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651608"],"URL":"https:\/\/doi.org\/10.1145\/3651608","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}