Approximate Lifted Inference with Probabilistic Databases
Approximate Lifted Inference with Probabilistic Databases
复制标题
使用概率数据库进行近似提升推理
DOI：
10.14778/2735479.2735494
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Dan Suciu
中科院分区：
文献类型：
--
作者：
Wolfgang Gatterbauer;Dan Suciu
提出了一种利用概率数据库近似计算#P-Hard查询的新方法。在我们的方法中，通过评估固定数量的查询计划来完全在数据库引擎中评估每个查询，每个查询计划提供真实概率的上限，然后取其最小值。我们提供了一种算法，它考虑了重要的模式信息，在所有可能的计划中只枚举最小的必要计划。重要的是，该算法是ptime自连接自由合取查询所有已知结果的严格推广：当且仅当我们的算法返回单个计划时，查询是安全的。我们还应用了三种关系查询优化技术来非常快速地评估所有最小安全计划。我们对我们的方法进行了详细的实验评估，并在此过程中提供了一种新的思路，即概率方法相对于非概率方法对查询答案进行排序的价值。
This paper proposes a new approach for approximate evaluation of #P-hard queries with probabilistic databases. In our approach, every query is evaluated entirely in the database engine by evaluating a fixed number of query plans, each providing an upper bound on the true probability, then taking their minimum. We provide an algorithm that takes into account important schema information to enumerate only the minimal necessary plans among all possible plans. Importantly, this algorithm is a strict generalization of all known results of PTIME self-join-free conjunctive queries: A query is safe if and only if our algorithm returns one single plan. We also apply three relational query optimization techniques to evaluate all minimal safe plans very fast. We give a detailed experimental evaluation of our approach and, in the process, provide a new way of thinking about the value of probabilistic methods over non-probabilistic methods for ranking query answers.
影响因子：
14.4
作者：
Hoffart, Johannes;Suchanek, Fabian M.;Weikum, Gerhard
通讯作者：
Weikum, Gerhard