摘要 Abstract
Shapley值源于合作博弈论,已被用于定义量化数据库事实对获得特定查询答案贡献的责任度量。对于非数值型查询,这通过考虑一个合作博弈实现,其中玩家为数据库中的事实,财富函数为每个数据库子集分配1或0,具体取决于查询答案在该子集中是否成立。尽管概念简单,但这种方法存在显著缺陷:计算此类Shapley值的问题在数据复杂性下是#P-难的,即使对于简单的连接查询也是如此。这促使我们重新审视什么构成合理责任度量,并引入一组新的责任度量——最小支持加权和(WSMS),这些度量满足直观属性。有趣的是,虽然WSMS的定义简单且显然与Shapley值公式没有明显相似之处,但我们证明每个WSMS度量都可以等价地看作是经过适当定义的合作博弈的Shapley值。此外,对于包括所有连接查询并集的大类查询,WSMS度量具有可处理的数据复杂性。我们进一步探索了WSMS计算的组合复杂性,并针对各种连接查询子类建立了(不可)处理性结果。
The Shapley value, originating from cooperative game theory, has been employed to define responsibility measures that quantify the contributions of database facts to obtaining a given query answer. For non-numeric queries, this is done by considering a cooperative game whose players are the facts and whose wealth function assigns 1 or 0 to each subset of the database, depending on whether the query answer holds in the given subset. While conceptually simple, this approach suffers from a notable drawback: the problem of computing such Shapley values is #P-hard in data complexity, even for simple conjunctive queries. This motivates us to revisit the question of what constitutes a reasonable responsibility measure and to introduce a new family of responsibility measures -- weighted sums of minimal supports (WSMS) -- which satisfy intuitive properties. Interestingly, while the definition of WSMSs is simple and bears no obvious resemblance to the Shapley value formula, we prove that every WSMS measure can be equivalently seen as the Shapley value of a suitably defined cooperative game. Moreover, WSMS measures enjoy tractable data complexity for a large class of queries, including all unions of conjunctive queries. We further explore the combined complexity of WSMS computation and establish (in)tractability results for various subclasses of conjunctive queries.