{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:40:02Z","timestamp":1755906002954,"version":"3.44.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"DFG","award":["VI 1045-1\/1"],"award-info":[{"award-number":["VI 1045-1\/1"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,9]]},"abstract":"<jats:p>We embark on a study of the consistent answers of queries over databases annotated with values from a naturally ordered positive semiring. In this setting, the consistent answers of a query are defined as the minimum of the semiring values that the query takes over all repairs of an inconsistent database. The main focus is on self-join free conjunctive queries and key constraints, which is the most extensively studied case of consistent query answering over standard databases. We introduce a variant of first-order logic with a limited form of negation, define suitable semiring semantics, and then establish the main result of the paper: the consistent query answers of a self-join free conjunctive query under key constraints are rewritable in this logic if and only if the attack graph of the query contains no cycles. This result generalizes an analogous result of Koutris and Wijsen for ordinary databases, but also yields new results for a multitude of semirings, including the bag semiring, the tropical semiring, and the fuzzy semiring. Further, for the bag semiring, we show that computing the consistent answers of any self-join free conjunctive query whose attack graph has a strong cycle is not only NP-hard but also it is NP-hard to even approximate the consistent answers with a constant relative approximation guarantee.<\/jats:p>","DOI":"10.1145\/3725247","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T15:20:31Z","timestamp":1749482431000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["Rewriting Consistent Answers On Annotated Data"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8407-8563","authenticated-orcid":false,"given":"Phokion","family":"Kolaitis","sequence":"first","affiliation":[{"name":"University of California Santa Cruz, Santa Cruz, CA, USA and IBM Research, Santa Cruz, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5150-6947","authenticated-orcid":false,"given":"Nina","family":"Pardal","sequence":"additional","affiliation":[{"name":"University of Huddersfield, Huddersfield, United Kingdom and University of Sheffield, Buenos Aires, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1582-3718","authenticated-orcid":false,"given":"Jonni","family":"Virtema","sequence":"additional","affiliation":[{"name":"University of Sheffield, Sheffield, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8216-273X","authenticated-orcid":false,"given":"Jef","family":"Wijsen","sequence":"additional","affiliation":[{"name":"University of Mons, Mons, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"volume-title":"Foundations of Databases","author":"Abiteboul Serge","key":"e_1_2_1_1_1","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3695836"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303983"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304--3975(02)00737-5"},{"key":"e_1_2_1_5_1","volume-title":"Proc. of IFIP World Computer Congress. 580-583","author":"Armstrong William W.","year":"1974","unstructured":"William W. Armstrong. 1974. Dependency Structures of Data Base Relationships.. In Proc. of IFIP World Computer Congress. 580-583."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651608"},{"key":"e_1_2_1_7_1","first-page":"75","article-title":"Unified Foundations of Team Semantics via Semirings","author":"Barlag Timon","year":"2023","unstructured":"Timon Barlag, Miika Hannula, Juha Kontinen, Nina Pardal, and Jonni Virtema. 2023. Unified Foundations of Team Semantics via Semirings. In KR. 75-85.","journal-title":"KR."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-030--88853--4_2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90022-D"},{"volume-title":"Complexity and Real Computation","author":"Blum Lenore","key":"e_1_2_1_10_1","unstructured":"Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. 1997. Complexity and Real Computation. Springer-Verlag, Berlin, Heidelberg."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CSL.2021.17"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/ICDT.2014.22"},{"volume-title":"Mathematical logic","author":"Ebbinghaus Heinz-Dieter","key":"e_1_2_1_13_1","unstructured":"Heinz-Dieter Ebbinghaus, J\u00f6rg Flum, and Wolfgang Thomas. 1984. Mathematical logic. Springer."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2023.24"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCSS.2006.10.013"},{"key":"e_1_2_1_16_1","volume-title":"Johnson","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_1_17_1","volume-title":"Semiring Provenance for First-Order Model Checking. CoRR","author":"Gr\u00e4del Erich","year":"1980","unstructured":"Erich Gr\u00e4del and Val Tannen. 2017. Semiring Provenance for First-Order Model Checking. CoRR, Vol. abs\/1712.01980 (2017)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00224-011-9327-6"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Erich Gr\u00e4del and Val Tannen. 2024. Provenance analysis and semiring semantics for first-order logic. (2024). To appear in a volume in honor of J\u00e1nos Makowsky published by Birkh\u00e4user.","DOI":"10.1007\/978-3-031-86319-6_21"},{"volume-title":"Tropical Circuit Complexity: Limits of Pure Dynamic Programming","author":"Jukna S.","key":"e_1_2_1_21_1","unstructured":"S. Jukna. 2023. Tropical Circuit Complexity: Limits of Pure Dynamic Programming. Springer International Publishing. https:\/\/books.google.co.uk\/books?id=sLUO0AEACAAJ"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524140"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213590"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458334"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651139"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3068334"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196982"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387654"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00224-020-09985-6"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651137"},{"volume-title":"Computational complexity","author":"Papadimitriou Christos H.","key":"e_1_2_1_32_1","unstructured":"Christos H. Papadimitriou. 1994. Computational complexity. Addison-Wesley."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00224-007--2011--1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807111"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2188349.2188351"},{"key":"e_1_2_1_38_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\/3725247","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:17:39Z","timestamp":1755904659000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725247"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,9]]}},"alternative-id":["10.1145\/3725247"],"URL":"https:\/\/doi.org\/10.1145\/3725247","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}