摘要
Shapley值最初在合作博弈论中用于财富分配,现已用于知识表示和数据库中,用于根据公式和数据库元组对获取查询结果或不一致性的贡献来为其分配分数。本文探讨了Shapley值在本体介导查询回答 (OMQA) 中的应用,并对OMQA设置下的Shapley值计算 (SVC) 进行了详细的复杂性分析。特别是,我们为由本体T(用描述逻辑ELHI⊥公式化)和一个连通的无常量同态封闭查询q组成的本体介导查询(T,q)的SVC建立了一个PF/#P-hard二分法。我们进一步表明,二分法的#P-hard部分可以加强到涵盖可能不连通的包含常量的查询。我们的结果利用了最近发现的SVC和概率查询评估之间的联系,并使我们能够推广概率OMQA的现有结果。