论文标题
功能依赖性不一致度量的莎普利价值
The Shapley Value of Inconsistency Measures for Functional Dependencies
论文作者
论文摘要
量化数据库的不一致性是由各种目标的动机，包括新数据集的可靠性估计以及数据清洁中的进度指示。另一个目标是将单元归因于整体不一致的责任水平，从而在污垢的解释或检查中优先考虑元组。因此，不一致的量化和归因已成为知识表示方面的大量研究，最近在数据库中。与许多其他领域一样，常规责任共享机制是合作游戏理论的莎普利价值。在本文中，我们对造成功能依赖性（FD）违规的常见不一致度量中的沙普利价值的复杂性进行了系统的研究。对于几项衡量标准，我们将FD集的完整分类用于Shapley-Value计算中。我们还研究了棘手的情况下近似的复杂性。
Quantifying the inconsistency of a database is motivated by various goals including reliability estimation for new datasets and progress indication in data cleaning. Another goal is to attribute to individual tuples a level of responsibility to the overall inconsistency, and thereby prioritize tuples in the explanation or inspection of dirt. Therefore, inconsistency quantification and attribution have been a subject of much research in Knowledge Representation and, more recently, in Databases. As in many other fields, a conventional responsibility sharing mechanism is the Shapley value from cooperative game theory. In this paper, we carry out a systematic investigation of the complexity of the Shapley value in common inconsistency measures for functional-dependency (FD) violations. For several measures we establish a full classification of the FD sets into tractable and intractable classes with respect to Shapley-value computation. We also study the complexity of approximation in intractable cases.
