{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T11:52:30Z","timestamp":1774871550439,"version":"3.50.1"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/S003800\/1, EP\/L016427\/1 and EP\/T022124\/1"],"award-info":[{"award-number":["EP\/S003800\/1, EP\/L016427\/1 and EP\/T022124\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Union - Next Generation EU","award":["P2022KHTX7"],"award-info":[{"award-number":["P2022KHTX7"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2026,9,30]]},"abstract":"<jats:p>Operational consistent query answering (CQA) is a recent framework for CQA, based on revised definitions of repairs and consistent answers, which opens up the possibility of efficient approximations with explicit error guarantees. The main idea is to iteratively apply operations (e.g., fact deletions), starting from an inconsistent database, until we reach a database that is consistent w.r.t.\u00a0the given set of constraints. This gives us the flexibility of choosing the probability with which we apply an operation, which in turn allows us to calculate the probability of an operational repair, and thus, the probability with which a consistent answer is entailed. A natural way of assigning probabilities to operations is by targeting the uniform probability distribution over a reasonable space such as the set of operational repairs, the set of sequences of operations that lead to an operational repair, and the set of available operations at a certain step of the repairing process. This leads to what we generally call uniform operational CQA. The goal of this work is to perform a data complexity analysis of both exact and approximate uniform operational CQA, focusing on functional dependencies (and subclasses thereof) and conjunctive queries. The main outcome of our analysis, among other positive and negative results, is that uniform operational CQA pushes the efficiency boundaries further by ensuring the existence of efficient approximation schemes in scenarios that go beyond the simple case of primary keys, which seems to be the limit of the classical approach to CQA.<\/jats:p>","DOI":"10.1145\/3774316","type":"journal-article","created":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T11:34:18Z","timestamp":1761996858000},"page":"1-65","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Uniform Operational Consistent Query Answering"],"prefix":"10.1145","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0921-4040","authenticated-orcid":false,"given":"Marco","family":"Calautti","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Milan","place":["Milano, Italy"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3485-9887","authenticated-orcid":false,"given":"Ester","family":"Livshits","sequence":"additional","affiliation":[{"name":"School of Informatics, The University of Edinburgh","place":["Edinburgh, United Kingdom of Great Britain and Northern Ireland"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4779-3469","authenticated-orcid":false,"given":"Andreas","family":"Pieris","sequence":"additional","affiliation":[{"name":"School of Informatics, The University of Edinburgh","place":["Edinburgh, United Kingdom of Great Britain and Northern Ireland"]},{"name":"Department of Computer Science, University of Cyprus","place":["Edinburgh, United Kingdom of Great Britain and Northern Ireland"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8338-5660","authenticated-orcid":false,"given":"Markus","family":"Schneider","sequence":"additional","affiliation":[{"name":"School of Informatics, The University of Edinburgh","place":["Edinburgh, United Kingdom of Great Britain and Northern Ireland"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,3,30]]},"reference":[{"key":"e_1_3_3_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303983"},{"key":"e_1_3_3_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1540612"},{"key":"e_1_3_3_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319703"},{"key":"e_1_3_3_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458309"},{"key":"e_1_3_3_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196966"},{"key":"e_1_3_3_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524147"},{"key":"e_1_3_3_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651600"},{"key":"e_1_3_3_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.04.007"},{"key":"e_1_3_3_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797315306"},{"key":"e_1_3_3_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265531"},{"key":"e_1_3_3_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W"},{"key":"e_1_3_3_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066176"},{"key":"e_1_3_3_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.013"},{"key":"e_1_3_3_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23540-0_24"},{"key":"e_1_3_3_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_3_3_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804678"},{"key":"e_1_3_3_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1519103.1519116"},{"key":"e_1_3_3_19_1","first-page":"165","volume-title":"ICDT","author":"Koutris Paraschos","year":"2014","unstructured":"Paraschos Koutris and Dan Suciu. 2014. A dichotomy on the complexity of consistent query answering for atoms with simple keys. In ICDT. 165\u2013176."},{"key":"e_1_3_3_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745769"},{"key":"e_1_3_3_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-020-09985-6"},{"key":"e_1_3_3_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.011"},{"key":"e_1_3_3_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90041-S"},{"key":"e_1_3_3_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.34"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3774316","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T10:51:24Z","timestamp":1774867884000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3774316"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,30]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9,30]]}},"alternative-id":["10.1145\/3774316"],"URL":"https:\/\/doi.org\/10.1145\/3774316","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,30]]},"assertion":[{"value":"2023-08-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-03-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}