{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T05:22:23Z","timestamp":1783574543416,"version":"3.55.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T00:00:00Z","timestamp":1730678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Fonds de la Recherche Scientifique - FNRS"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,11,4]]},"abstract":"<jats:p>We consider the problem of answering conjunctive queries with aggregation on database instances that may violate primary key constraints. In SQL, these queries follow the SELECT-FROM-WHERE-GROUP BY format, where the WHERE-clause involves a conjunction of equalities, and the SELECT-clause can incorporate aggregate operators like MAX, MIN, SUM, AVG, or COUNT. Repairs of a database instance are defined as inclusion-maximal subsets that satisfy all primary keys. For a given query, our primary objective is to identify repairs that yield the lowest aggregated value among all possible repairs. We particularly investigate queries for which this lowest aggregated value can be determined through a rewriting in first-order logic with aggregate operators.<\/jats:p>","DOI":"10.1145\/3695836","type":"journal-article","created":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T17:26:35Z","timestamp":1731000395000},"page":"1-19","source":"Crossref","is-referenced-by-count":3,"title":["Computing Range Consistent Answers to Aggregation Queries via Rewriting"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-3286-7055","authenticated-orcid":false,"given":"Aziz","family":"Amezian El Khalfioui","sequence":"first","affiliation":[{"name":"University of Mons, Mons, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"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":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,11,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Consistent Query Answers in Inconsistent Databases","author":"Arenas Marcelo","unstructured":"Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. 1999. Consistent Query Answers in Inconsistent Databases. In PODS. ACM Press, 68--79."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44503-X_3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00737-5"},{"key":"e_1_2_1_4_1","volume-title":"Database Repairing and Consistent Query Answering","author":"Bertossi Leopoldo E.","unstructured":"Leopoldo E. Bertossi. 2011. Database Repairing and Consistent Query Answering. Morgan & Claypool Publishers."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Leopoldo E. Bertossi. 2019. Database Repairs and Consistent Query Answering: Origins and Further Developments. In PODS. ACM 48--58.","DOI":"10.1145\/3294052.3322190"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2008.01.005"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970398.1970400"},{"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. ACM 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. ACM 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. ACM 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. 2022. Counting Database Repairs Entailing a Query: The Case of Functional Dependencies. In PODS. ACM 403--412.","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. 2022. Uniform Operational Consistent Query Answering. In PODS. ACM 393--402.","DOI":"10.1145\/3517804.3526230"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1138394.1138400"},{"key":"e_1_2_1_14_1","volume-title":"Algorithms for Rewriting Aggregate Queries Using Views. In DMDW (CEUR Workshop Proceedings","volume":"9","author":"Cohen Sara","year":"1999","unstructured":"Sara Cohen, Werner Nutt, and Alexander Serebrenik. 1999. Algorithms for Rewriting Aggregate Queries Using Views. In DMDW (CEUR Workshop Proceedings, Vol. 19). CEUR-WS.org, 9."},{"key":"e_1_2_1_15_1","volume-title":"Kolaitis","author":"Dixit Akhil A.","year":"2019","unstructured":"Akhil A. Dixit and Phokion G. Kolaitis. 2019. A SAT-Based System for Consistent Query Answering. In SAT (Lecture Notes in Computer Science, Vol. 11628). Springer, 117--135."},{"key":"e_1_2_1_16_1","volume-title":"Kolaitis","author":"Dixit Akhil A.","year":"2022","unstructured":"Akhil A. Dixit and Phokion G. Kolaitis. 2022. Consistent Answers of Aggregation Queries via SAT. In ICDE. IEEE, 924--937."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588718"},{"key":"e_1_2_1_18_1","first-page":"1","article-title":"A Simple Algorithm for Consistent Query Answering Under Primary Keys. In ICDT (LIPIcs, Vol. 255)","volume":"24","author":"Figueira Diego","year":"2023","unstructured":"Diego Figueira, Anantha Padmanabha, Luc Segoufin, and Cristina Sirangelo. 2023. A Simple Algorithm for Consistent Query Answering Under Primary Keys. In ICDT (LIPIcs, Vol. 255). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 24:1--24:18.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699912"},{"key":"e_1_2_1_20_1","volume-title":"Efficient query processing over inconsistent databases. Ph.,D. Dissertation","author":"Fuxman Ariel","unstructured":"Ariel Fuxman. 2007. Efficient query processing over inconsistent databases. Ph.,D. Dissertation. University of Toronto."},{"key":"e_1_2_1_21_1","volume-title":"ConQuer: Efficient Management of Inconsistent Databases. In SIGMOD Conference. ACM, 155--166","author":"Fuxman Ariel","unstructured":"Ariel Fuxman, Elham Fazli, and Ren\u00e9e J. Miller. 2005 a. ConQuer: Efficient Management of Inconsistent Databases. In SIGMOD Conference. ACM, 155--166."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Ariel Fuxman Diego Fuxman and Ren\u00e9e J. Miller. 2005 b. ConQuer: A System for Efficient Querying Over Inconsistent Databases. In VLDB. ACM 1354--1357.","DOI":"10.1145\/1066157.1066176"},{"key":"e_1_2_1_23_1","volume-title":"Miller","author":"Fuxman Ariel","year":"2005","unstructured":"Ariel Fuxman and Ren\u00e9e J. Miller. 2005. First-Order Query Rewriting for Inconsistent Databases. In ICDT (Lecture Notes in Computer Science, Vol. 3363). Springer, 337--351."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Miika Hannula and Jef Wijsen. 2022. A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys. In PODS. ACM 437--449.","DOI":"10.1145\/3517804.3524157"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502100"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Aziz Amezian El Khalfioui Jonathan Joertz Dorian Labeeuw Ga\u00ebtan Staquet and Jef Wijsen. 2020. Optimization of Answer Set Programs for Consistent Query Answering by Means of First-Order Rewriting. In CIKM. ACM 25--34.","DOI":"10.1145\/3340531.3411911"},{"key":"e_1_2_1_27_1","first-page":"1","article-title":"Consistent Query Answering for Primary Keys and Conjunctive Queries with Counting. In ICDT (LIPIcs, Vol. 255)","volume":"23","author":"El Khalfioui Aziz Amezian","year":"2023","unstructured":"Aziz Amezian El Khalfioui and Jef Wijsen. 2023. Consistent Query Answering for Primary Keys and Conjunctive Queries with Counting. In ICDT (LIPIcs, Vol. 255). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 23:1--23:19.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_28_1","unstructured":"Aziz Amezian El Khalfioui and Jef Wijsen. 2024. Computing Range Consistent Answers to Aggregation Queries via Rewriting. arxiv: 2409.01648 [cs.DB] https:\/\/arxiv.org\/abs\/2409.01648"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3624717"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.05.016"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536341"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Paraschos Koutris Xiating Ouyang and Jef Wijsen. 2021. Consistent Query Answering for Primary Keys on Path Queries. In PODS. ACM 215--232.","DOI":"10.1145\/3452021.3458334"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651139"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3068334"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Paraschos Koutris and Jef Wijsen. 2018. Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms. In PODS. ACM 209--224.","DOI":"10.1145\/3196959.3196982"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Paraschos Koutris and Jef Wijsen. 2020. First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys. In PODS. ACM 113--129.","DOI":"10.1145\/3375395.3387654"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-020-09985-6"},{"key":"e_1_2_1_38_1","volume-title":"Elements of Finite Model Theory","author":"Libkin Leonid","unstructured":"Leonid Libkin. 2004. Elements of Finite Model Theory. Springer."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.011"},{"key":"e_1_2_1_40_1","unstructured":"Dany Maslowski and Jef Wijsen. 2014. Counting Database Repairs that Satisfy Conjunctive Queries with Self-Joins. In ICDT. OpenProceedings.org 155--164."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651137"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-012-9288-8"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Jef Wijsen. 2010. On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases. In PODS. ACM 179--190.","DOI":"10.1145\/1807085.1807111"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2188349.2188351"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3377391.3377393"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695836","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3695836","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T02:31:18Z","timestamp":1755916278000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695836"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,4]]},"references-count":45,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,11,4]]}},"alternative-id":["10.1145\/3695836"],"URL":"https:\/\/doi.org\/10.1145\/3695836","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,4]]}}}