{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T14:16:43Z","timestamp":1774621003455,"version":"3.50.1"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,11,10]]},"abstract":"<jats:p>Codd's Theorem, a fundamental result of database theory, asserts that relational algebra and relational calculus have the same expressive power on relational databases. We explore Codd's Theorem for databases over semirings and establish two different versions of this result for such databases: the first version involves the five basic operations of relational algebra, while in the second version the division operation is added to the five basic operations of relational algebra. In both versions, the difference operation of relations is given semantics using semirings with monus, while on the side of relational calculus a limited form of negation is used. The reason for considering these two different versions of Codd's theorem is that, unlike the case of ordinary relational databases, the division operation need not be expressible in terms of the five basic operations of relational algebra for databases over an arbitrary positive semiring; in fact, we show that this inexpressibility result holds for bag databases, as well as for databases over the tropical semiring.<\/jats:p>","DOI":"10.1145\/3767713","type":"journal-article","created":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T15:06:02Z","timestamp":1762959962000},"page":"1-26","source":"Crossref","is-referenced-by-count":1,"title":["Codd's Theorem for Databases over Semirings"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5597-6794","authenticated-orcid":false,"given":"Guillermo","family":"Badia","sequence":"first","affiliation":[{"name":"University of Queensland, Brisbane, Queensland, Australia"}],"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, Santa Cruz, California, USA and IBM Research, San Jose, California, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4910-599X","authenticated-orcid":false,"given":"Carles","family":"Noguera","sequence":"additional","affiliation":[{"name":"University of Siena, Siena, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,11,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/551350"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41660-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01182254"},{"key":"e_1_2_1_4_1","volume-title":"3rd Workshop on the Theory and Practice of Provenance, TaPP'11","author":"Amsterdamer Yael","year":"2011","unstructured":"Yael Amsterdamer, Daniel Deutch, and Val Tannen. On the limitations of provenance for queries with difference. In Peter Buneman and Juliana Freire, editors, 3rd Workshop on the Theory and Practice of Provenance, TaPP'11, Heraklion, Crete, Greece, June 20-21, 2011. USENIX Association, 2011. URL https:\/\/www.usenix.org\/conference\/tapp11\/limitationsprovenance-queries-difference."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-24117-8_17"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3721855"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of 6th Courant Computer Science Symposium (May 24-25, 1971","author":"Codd Edgar F.","year":"1972","unstructured":"Edgar F. Codd. Relational completeness of data base sublanguages. In R. Rustin, editor, Proceedings of 6th Courant Computer Science Symposium (May 24-25, 1971: New York, N.Y.), pages 65-98. Prentice-Hall, 1972."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CSL.2021.17"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jal.2009.09.001"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/114325.103712"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19810270803"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9327-6"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_15_1","volume-title":"Semiring provenance for first-order model checking.","author":"Gr\u00e4del Erich","year":"2017","unstructured":"Erich Gr\u00e4del and Val Tannen. Semiring provenance for first-order model checking. Available at https:\/\/arxiv.org\/abs\/1712.01980, 2017."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-86319-6_21"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5772\/36656"},{"key":"e_1_2_1_18_1","first-page":"42","volume-title":"Die formalen regeln der intuitionistischen logik. Sitzungsbericht PreuBische Akademie der Wissenschaften Berlin, physikalisch-mathematische Klasse II","author":"Heyting Arend","year":"1930","unstructured":"Arend Heyting. Die formalen regeln der intuitionistischen logik. Sitzungsbericht PreuBische Akademie der Wissenschaften Berlin, physikalisch-mathematische Klasse II, pages 42-56, 1930."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3643027"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556524"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2307\/2268715"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969038"},{"key":"e_1_2_1_23_1","volume-title":"Example of a naturally ordered semiring which is not an m-semiring. https:\/\/math.stackexchange.com\/questions\/1966858\/example-of-a-naturally-ordered-semiring-which-is-notan-m-semiring","author":"Monet Mika\u00ebl","year":"2016","unstructured":"Mika\u00ebl Monet. Example of a naturally ordered semiring which is not an m-semiring. https:\/\/math.stackexchange.com\/questions\/1966858\/example-of-a-naturally-ordered-semiring-which-is-notan-m-semiring, 2016. StackExchange."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-83-3-219-249"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.2307\/2271931"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4230\/OASICS.TANNEN.10"},{"key":"e_1_2_1_27_1","volume-title":"Principles of Database Systems","author":"Ullman Jeffrey D.","year":"1980","unstructured":"Jeffrey D. Ullman. Principles of Database Systems, 1st Edition. Computer Science Press, 1980.","edition":"1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651591"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3767713","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T16:08:51Z","timestamp":1762963731000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3767713"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,10]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,11,10]]}},"alternative-id":["10.1145\/3767713"],"URL":"https:\/\/doi.org\/10.1145\/3767713","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,10]]}}}