{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T17:30:58Z","timestamp":1782754258379,"version":"3.54.5"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,2,17]],"date-time":"2020-02-17T00:00:00Z","timestamp":1581897600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000093","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["1R01EB025021-01"],"award-info":[{"award-number":["1R01EB025021-01"]}],"id":[{"id":"10.13039\/100000093","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1552538,IIS-1703431"],"award-info":[{"award-number":["IIS-1552538,IIS-1703431"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1295\/15"],"award-info":[{"award-number":["1295\/15"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2020,3,31]]},"abstract":"<jats:p>We investigate the complexity of computing an optimal repair of an inconsistent database, in the case where integrity constraints are Functional Dependencies (FDs). We focus on two types of repairs: an optimal subset repair (optimal S-repair), which is obtained by a minimum number of tuple deletions, and an optimal update repair (optimal U-repair), which is obtained by a minimum number of value (cell) updates. For computing an optimal S-repair, we present a polynomial-time algorithm that succeeds on certain sets of FDs and fails on others. We prove the following about the algorithm. When it succeeds, it can also incorporate weighted tuples and duplicate tuples. When it fails, the problem is NP-hard and, in fact, APX-complete (hence, cannot be approximated better than some constant). Thus, we establish a dichotomy in the complexity of computing an optimal S-repair. We present general analysis techniques for the complexity of computing an optimal U-repair, some based on the dichotomy for S-repairs. We also draw a connection to a past dichotomy in the complexity of finding a \u201cmost probable database\u201d that satisfies a set of FDs with a single attribute on the left-hand side; the case of general FDs was left open, and we show how our dichotomy provides the missing generalization and thereby settles the open problem.<\/jats:p>","DOI":"10.1145\/3360904","type":"journal-article","created":{"date-parts":[[2020,2,17]],"date-time":"2020-02-17T12:34:30Z","timestamp":1581942870000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["Computing Optimal Repairs for Functional Dependencies"],"prefix":"10.1145","volume":"45","author":[{"given":"Ester","family":"Livshits","sequence":"first","affiliation":[{"name":"Technion\u2013Israel Institute of Technology, Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benny","family":"Kimelfeld","sequence":"additional","affiliation":[{"name":"Technion\u2013Israel Institute of Technology, Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sudeepa","family":"Roy","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,2,17]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Kolaitis","author":"Afrati Foto N.","year":"2009"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00158-3"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.04.028"},{"key":"e_1_2_2_4_1","volume-title":"Miller","author":"Andritsos Periklis","year":"2006"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303983"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.199"},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Giorgio Ausiello M. Protasi A. Marchetti-Spaccamela G. Gambosi P. Crescenzi and V. Kann. 1999. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties (1st ed.). Springer-Verlag Berlin.  Giorgio Ausiello M. Protasi A. Marchetti-Spaccamela G. Gambosi P. Crescenzi and V. Kann. 1999. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties (1st ed.). Springer-Verlag Berlin.","DOI":"10.1007\/978-3-642-58412-1_1"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90020-1"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213006"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824096"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00461-3_26"},{"key":"e_1_2_2_12_1","volume-title":"Repair-based degrees of database inconsistency: Computation and complexity. CoRR abs\/1809.10286","author":"Bertossi Leopoldo E.","year":"2018"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367920"},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the ICDT (LIPIcs)","volume":"68","author":"Burdick Douglas","year":"2017"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90075-8"},{"key":"e_1_2_2_16_1","first-page":"1","article-title":"Minimal-change integrity maintenance using tuple deletions. Info","volume":"197","author":"Chomicki Jan","year":"2005","journal-title":"Comput."},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of the Conference on Data: Its Use, Organization, and Management (ACM Pacific\u201975)","author":"Codd E. F.","year":"1975"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.1997.612321"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465327"},{"key":"e_1_2_2_20_1","volume-title":"Dalvi and Dan Suciu","author":"Nilesh","year":"2004"},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of the VLDB. VLDB Endowment, 2--12","author":"Date C. J.","year":"1981"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-012-0478-9"},{"key":"e_1_2_2_23_1","volume-title":"Kolaitis","author":"Fagin Ronald","year":"2015"},{"key":"e_1_2_2_24_1","unstructured":"Wenfei Fan and Floris Geerts. 2012. Foundations of Data Quality Management. Morgan 8 Claypool Publishers.  Wenfei Fan and Floris Geerts. 2012. Foundations of Data Quality Management. Morgan 8 Claypool Publishers."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00962280"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536363"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2016.04.004"},{"key":"e_1_2_2_28_1","volume-title":"Proceedings of the BUDA.","author":"Gribkoff Eric","year":"2014"},{"key":"e_1_2_2_29_1","volume-title":"Inapproximability results for set splitting and SatisfiabilityProblems with no mixed clauses. Algorithmica 38, 3 (1","author":"Guruswami Venkatesan","year":"2004"},{"key":"e_1_2_2_30_1","volume-title":"Proceedings of the 12th Annual IEEE Conference on Computational Complexity. 282--296","author":"Khanna S."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213584"},{"key":"e_1_2_2_32_1","first-page":"1","article-title":"Detecting ambiguity in prioritized database repairing","volume":"17","author":"Kimelfeld Benny","year":"2017","journal-title":"Proceedings of the ICDT."},{"key":"e_1_2_2_33_1","volume-title":"Lakshmanan","author":"Kolahi Solmaz","year":"2009"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"e_1_2_2_35_1","volume-title":"Principles of progress indicators for database repairing. CoRR abs\/1904.06492","author":"Livshits Ester","year":"2019"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056107"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196980"},{"key":"e_1_2_2_38_1","volume-title":"Bertossi","author":"Lopatenko Andrei","year":"2007"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137631"},{"key":"e_1_2_2_40_1","first-page":"1","article-title":"A formal framework for probabilistic unclean databases","volume":"6","author":"Sa Christopher De","year":"2019","journal-title":"Proceedings of the ICDT."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-012-9288-8"},{"key":"e_1_2_2_42_1","volume-title":"Probabilistic Databases","author":"Suciu Dan","edition":"1"},{"key":"e_1_2_2_43_1","volume-title":"Complexity Theory: Exploring the Limits of Efficient Algorithms","author":"Wegener Ingo","year":"2005"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3360904","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3360904","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3360904","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:37Z","timestamp":1750203877000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3360904"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,17]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,3,31]]}},"alternative-id":["10.1145\/3360904"],"URL":"https:\/\/doi.org\/10.1145\/3360904","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,17]]},"assertion":[{"value":"2018-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}