The most probable database problem
The most probable database problem
复制标题
最有可能的数据库问题
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Dan Suciu
中科院分区：
文献类型：
--
作者：
Eric Gribkoff;Guy Van den Broeck;Dan Suciu
提出了一种新的概率数据库推理任务：最可能数据库(MPD)问题。在给定查询或约束为真的情况下，MPD是最可能的确定性数据库。我们强调了两个独特的应用，在键和依赖约束的数据库修复中，以及在统计关系学习中寻找最可能的解释。MPD问题提出了新的理论问题，例如MPD的二分性定理的可能性，将查询分类为ptime或NP-Hard。我们表明，这种二分法将与其他推理任务的二分法背道而驰。然后，我们证明了表示一元函数依赖约束的查询的二分法。最后，我们讨论了对称概率和提升推理的机会。
This paper proposes a novel inference task for probabilistic databases: the most probable database (MPD) problem. The MPD is the most probable deterministic database where a given query or constraint is true. We highlight two distinctive applications, in database repair of key and dependency constraints, and in finding most probable explanations in statistical relational learning. The MPD problem raises new theoretical questions, such as the possibility of a dichotomy theorem for MPD, classifying queries as being either PTIME or NP-hard. We show that such a dichotomy would diverge from dichotomies for other inference tasks. We then prove a dichotomy for queries that represent unary functional dependency constraints. Finally, we discuss symmetric probabilities and the opportunities for lifted inference.