{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T16:51:07Z","timestamp":1783702267366,"version":"3.55.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,4,10]],"date-time":"2024-04-10T00:00:00Z","timestamp":1712707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["768\/19"],"award-info":[{"award-number":["768\/19"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["GR 1492\/16-1 and KI 2348\/1-1"],"award-info":[{"award-number":["GR 1492\/16-1 and KI 2348\/1-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>A common interpretation of soft constraints penalizes the database for every violation of every constraint, where the penalty is the cost (weight) of the constraint. A computational challenge is that of finding an optimal subset: a collection of database tuples that minimizes the total penalty when each tuple has a cost of being excluded. When the constraints are strict (i.e., have an infinite cost), this subset is a \u201ccardinality repair\u201d of an inconsistent database; in soft interpretations, this subset corresponds to a \u201cmost probable world\u201d of a probabilistic database, a \u201cmost likely intention\u201d of a probabilistic unclean database, and so on. Within the class of functional dependencies, the complexity of finding a cardinality repair is thoroughly understood. Yet, very little is known about the complexity of finding an optimal subset for the more general soft semantics. The work described in this manuscript makes significant progress in that direction. In addition to general insights about the hardness and approximability of the problem, we present algorithms for two special cases (and some generalizations thereof): a single functional dependency, and a bipartite matching. The latter is the problem of finding an optimal \u201calmost matching\u201d of a bipartite graph where a penalty is paid for every lost edge and every violation of monogamy. For these special cases, we also investigate the complexity of additional computational tasks that arise when the soft constraints are used as a means to represent a probabilistic database in the case of a probabilistic unclean database.<\/jats:p>","DOI":"10.1145\/3651156","type":"journal-article","created":{"date-parts":[[2024,3,4]],"date-time":"2024-03-04T12:23:02Z","timestamp":1709554982000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Database Repairing with Soft Functional Dependencies"],"prefix":"10.1145","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0673-5510","authenticated-orcid":false,"given":"Nofar","family":"Carmeli","sequence":"first","affiliation":[{"name":"Inria, LIRMM, Univ Montpellier, CNRS, Montpellier, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0292-9142","authenticated-orcid":false,"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7156-1572","authenticated-orcid":false,"given":"Benny","family":"Kimelfeld","sequence":"additional","affiliation":[{"name":"Technion \u2013 Israel Institute of Technology, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3485-9887","authenticated-orcid":false,"given":"Ester","family":"Livshits","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6017-3948","authenticated-orcid":false,"given":"Muhammad","family":"Tibi","sequence":"additional","affiliation":[{"name":"Technion \u2013 Israel Institute of Technology, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,4,10]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"Network Flows - Theory, Algorithms and Applications","author":"Ahuja Ravindra K.","year":"1993","unstructured":"Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. 1993. Network Flows - Theory, Algorithms and Applications. Prentice Hall."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.43"},{"key":"e_1_3_2_4_2","unstructured":"Nofar Carmeli Martin Grohe Benny Kimelfeld Ester Livshits and Muhammad Tibi. 2021. Database repairing with soft functional dependencies. In 24th International Conference on Database Theory (ICDT 2021) Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132700"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544854"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.3115\/1613715.1613746"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767833"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536262"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.compbiomed.2014.08.004"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_3_2_13_2","first-page":"2744","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","author":"Ermon Stefano","year":"2011","unstructured":"Stefano Ermon, Carla P. Gomes, Ashish Sabharwal, and Bart Selman. 2011. Accelerated adaptive markov chain for partition function computation. In Proceedings of the Advances in Neural Information Processing Systems. 2744\u20132752."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.14778\/3467861.3467876"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.15.3.430"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1201\/9781420010749"},{"key":"e_1_3_2_17_2","volume-title":"Proceedings of the First international workshop on Big Uncertain Data","author":"Gribkoff Eric","year":"2014","unstructured":"Eric Gribkoff, Guy Van den Broeck, and Dan Suciu. 2014. The most probable database problem. In Proceedings of the First international workshop on Big Uncertain Data. Retrieved from http:\/\/www.sigmod2014.org\/buda"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319888"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/0211045"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/42.2.100"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376934"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514901"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.14778\/3192965.3192968"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401966"},{"key":"e_1_3_2_25_2","doi-asserted-by":"crossref","unstructured":"Ester Livshits Rina Kochirgan Segev Tsur Ihab F. Ilyas Benny Kimelfeld and Sudeepa Roy. 2021. Properties of inconsistency measures for databases. In Proceedings of the 2021 International Conference on Management of Data. 1182\u20131194.","DOI":"10.1145\/3448016.3457310"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3360904"},{"key":"e_1_3_2_27_2","series-title":"Proceedings of the International Conference on Database Theory.","first-page":"179","volume":"4353","author":"Lopatenko Andrei","year":"2007","unstructured":"Andrei Lopatenko and Leopoldo E. Bertossi. 2007. Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics. In Proceedings of the International Conference on Database Theory.Lecture Notes in Computer Science, Vol. 4353. Springer, 179\u2013193."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74976-9_21"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407809"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368293"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403178"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137631"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-5833-1"},{"key":"e_1_3_2_34_2","unstructured":"Christopher De Sa Ihab F. Ilyas Benny Kimelfeld Christopher R\u00e9 and Theodoros Rekatsinas. 2019. A formal framework for probabilistic unclean databases. In ICDT (Leibniz International Proceedings in Informatics (LIPIcs)) Vol. 127. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik 6:1\u20136:18."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0153-2"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3389129"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3060586"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651156","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651156","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:49:53Z","timestamp":1750286993000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651156"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,10]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3651156"],"URL":"https:\/\/doi.org\/10.1145\/3651156","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,10]]},"assertion":[{"value":"2021-10-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-27","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}