{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T23:29:09Z","timestamp":1774913349759,"version":"3.50.1"},"reference-count":21,"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\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["P2022KHTX7"],"award-info":[{"award-number":["P2022KHTX7"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/S003800\/1"],"award-info":[{"award-number":["EP\/S003800\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>Operational consistent query answering (CQA) is a recent framework for CQA based on revised definitions of repairs, which are built by applying a sequence of operations (e.g., fact deletions) starting from an inconsistent database until we reach a database that is consistent w.r.t. the given set of constraints. It has been recently shown that there is an efficient approximation for computing the percentage of repairs that entail a given query when we focus on primary keys, conjunctive queries, and assuming the query is fixed (i.e., in data complexity). However, it has been left open whether such an approximation exists when the query is part of the input (i.e., in combined complexity). We show that this is the case when we focus on self-join-free conjunctive queries of bounded generelized hypertreewidth. We also show that it is unlikely that efficient approximation schemes exist once we give up one of the adopted syntactic restrictions, i.e., self-join-freeness or bounding the generelized hypertreewidth. Towards the desired approximation, we introduce a counting complexity class, called SpanTL, show that each problem in it admits an efficient approximation scheme by using a recent approximability result about tree automata, and then place the problem of interest in SpanTL.<\/jats:p>","DOI":"10.1145\/3651600","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-16","source":"Crossref","is-referenced-by-count":2,"title":["Combined Approximations for Uniform Operational Consistent Query Answering"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0921-4040","authenticated-orcid":false,"given":"Marco","family":"Calautti","sequence":"first","affiliation":[{"name":"University of Milano, Milan, 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":"University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4779-3469","authenticated-orcid":false,"given":"Andreas","family":"Pieris","sequence":"additional","affiliation":[{"name":"University of Edinburgh &amp; University of Cyprus, Edinburgh, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8338-5660","authenticated-orcid":false,"given":"Markus","family":"Schneider","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}],"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.1016\/j.ejc.2007.04.013"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90252-O"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Marcelo Arenas Leopoldo E. Bertossi and Jan Chomicki. 1999. Consistent Query Answers in Inconsistent Databases. In PODS. 68--79.","DOI":"10.1145\/303976.303983"},{"key":"e_1_2_1_4_1","volume-title":"Rajesh Jayaram, and Cristian Riveros.","author":"Arenas Marcelo","year":"2019","unstructured":"Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros. 2019. Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation. In PODS. 59--73."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477045"},{"key":"e_1_2_1_6_1","volume-title":"Rajesh Jayaram, and Cristian Riveros.","author":"Arenas Marcelo","year":"2021","unstructured":"Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros. 2021b. When is approximate counting for conjunctive queries tractable?. In STOC. 1015--1027."},{"key":"e_1_2_1_7_1","volume-title":"Computational Complexity - A Modern Approach","author":"Arora Sanjeev","unstructured":"Sanjeev Arora and Boaz Barak. 2009. Computational Complexity - A Modern Approach. Cambridge University Press."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Marco Calautti Marco Console and Andreas Pieris. 2019. Counting Database Repairs under Primary Keys Revisited. In PODS. 104--118.","DOI":"10.1145\/3294052.3319703"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Marco Calautti Marco Console and Andreas Pieris. 2021. Benchmarking Approximate Consistent Query Answering. In PODS. 233--246.","DOI":"10.1145\/3452021.3458309"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Marco Calautti Leonid Libkin and Andreas Pieris. 2018. An Operational Approach to Consistent Query Answering. In PODS. 239--251.","DOI":"10.1145\/3196959.3196966"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Marco Calautti Ester Livshits Andreas Pieris and Markus Schneider. 2022a. Counting Database Repairs Entailing a Query: The Case of Functional Dependencies. In PODS. To appear.","DOI":"10.1145\/3517804.3524147"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Marco Calautti Ester Livshits Andreas Pieris and Markus Schneider. 2022b. Uniform Operational Consistent Query Answering. In PODS. 393--402.","DOI":"10.1145\/3517804.3526230"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Ariel Fuxman Elham Fazli and Ren\u00e9 e J. Miller. 2005. ConQuer: Efficient Management of Inconsistent Databases. In SIGMOD. 155--166.","DOI":"10.1145\/1066157.1066176"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.013"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Floris Geerts Fabian Pijcke and Jef Wijsen. 2015. First-Order Under-Approximations of Consistent Query Answers. In SUM. 354--367.","DOI":"10.1007\/978-3-319-23540-0_24"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_1_17_1","unstructured":"Paraschos Koutris and Dan Suciu. 2014. A Dichotomy on the Complexity of Consistent Query Answering for Atoms with Simple Keys. In ICDT. 165--176."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Paraschos Koutris and Jef Wijsen. 2015. The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints. In PODS. 17--29.","DOI":"10.1145\/2745754.2745769"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-020-09985-6"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.011"},{"key":"e_1_2_1_21_1","volume-title":"Meel","author":"van Bremen Timothy","year":"2023","unstructured":"Timothy van Bremen and Kuldeep S. Meel. 2023. Probabilistic Query Evaluation: The Combined FPRAS Landscape. In PODS. 339--347. io"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651600","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651600","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:38:54Z","timestamp":1755898734000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651600"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651600"],"URL":"https:\/\/doi.org\/10.1145\/3651600","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}