{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T05:36:44Z","timestamp":1787031404364,"version":"build-2736575974"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2022,6,15]],"date-time":"2022-06-15T00:00:00Z","timestamp":1655251200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Quantifying the inconsistency of a database is motivated by various goals\nincluding reliability estimation for new datasets and progress indication in\ndata cleaning. Another goal is to attribute to individual tuples a level of\nresponsibility to the overall inconsistency, and thereby prioritize tuples in\nthe explanation or inspection of dirt. Therefore, inconsistency quantification\nand attribution have been a subject of much research in Knowledge\nRepresentation and, more recently, in Databases. As in many other fields, a\nconventional responsibility sharing mechanism is the Shapley value from\ncooperative game theory. In this paper, we carry out a systematic investigation\nof the complexity of the Shapley value in common inconsistency measures for\nfunctional-dependency (FD) violations. For several measures we establish a full\nclassification of the FD sets into tractable and intractable classes with\nrespect to Shapley-value computation. We also study the complexity of\napproximation in intractable cases.<\/jats:p>","DOI":"10.46298\/lmcs-18(2:20)2022","type":"journal-article","created":{"date-parts":[[2022,6,17]],"date-time":"2022-06-17T04:46:30Z","timestamp":1655441190000},"source":"Crossref","is-referenced-by-count":7,"title":["The Shapley Value of Inconsistency Measures for Functional Dependencies"],"prefix":"10.46298","volume":"Volume 18, Issue 2","author":[{"given":"Ester","family":"Livshits","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benny","family":"Kimelfeld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2022,6,15]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/9705\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/9705\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T16:20:27Z","timestamp":1687278027000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/8618"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,15]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-18(2:20)2022","relation":{"has-preprint":[{"id-type":"arxiv","id":"2009.13819v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2009.13819","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2009.13819","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,15]]},"article-number":"8618"}}