Open-world probabilistic databases: Semantics, algorithms, complexity
Open-world probabilistic databases: Semantics, algorithms, complexity
复制标题
开放世界的概率数据库：语义、算法、复杂性
DOI：
10.1016/j.artint.2021.103474
复制
发表时间：
2021
影响因子：
14.4
通讯作者：
Van den Broeck, Guy
中科院分区：
文献类型：
--
作者：
Ceylan, İsmail İlkan;Darwiche, Adnan;Van den Broeck, Guy
大规模的概率知识库在学术界和工业界正变得越来越重要。在现代信息提取工具的支持下，它们不断地使用新数据进行扩展，这些工具将概率与知识库事实相关联。存储和处理这种数据的最新技术是基于概率数据库的。然而，许多基于概率数据库的系统仍然存在一定的语义缺陷，这限制了它们的潜在应用。我们重新审视了概率数据库的语义，认为概率数据库的封闭世界假设，即没有出现在数据库中的事实的概率为零的假设，与大规模概率知识库的日常使用相冲突。为了解决这种差异，我们提出了开放世界概率数据库，作为一种新的概率数据模型。在这个新的数据模型中，未知事实的概率，也称为开放事实，可以从默认的概率区间中分配任何概率值。我们的分析表明，我们的模型更好地符合许多现实世界的任务，如查询回答、关系学习、知识库完成和规则挖掘。我们做出了各种技术贡献。我们证明了用于计算概率数据库上的合取查询的数据复杂性在多项式时间和之间的二分法可以提升到我们的开放世界模型。这一结果得到了有效计算所谓安全序列的概率的算法的支持。在此基础上，在合理的假设条件下，证明了对概率数据库安全查询的评估是非线性时间。在开放世界的概率数据库中，对于更受限的安全查询类别，这一点仍然成立。我们将我们的数据复杂性分析扩展到合取查询的联合之外，并获得了经典和开放世界概率数据库的一系列复杂性结果。我们通过深入研究各个模型中的组合复杂性来结束我们的分析。
Large-scale probabilistic knowledge bases are becoming increasingly important in academia and industry. They are continuously extended with new data, powered by modern information extraction tools that associate probabilities with knowledge base facts. The state of the art to store and process such data is founded on probabilistic databases. Many systems based on probabilistic databases, however, still have certain semantic deficiencies, which limit their potential applications. We revisit the semantics of probabilistic databases, and argue that theclosed-world assumptionof probabilistic databases, i.e., the assumption that facts not appearing in the database have the probabilityzero, conflicts with the everyday use of large-scale probabilistic knowledge bases. To address this discrepancy, we proposeopen-world probabilistic databases, as a new probabilistic data model. In this new data model, the probabilities of unknown facts, also calledopen facts, can be assigned any probability value from a default probability interval. Our analysis entails that our model aligns better with many real-world tasks such asquery answering,relational learning,knowledge base completion, andrule mining. We make various technical contributions. We show that thedata complexity dichotomy, between polynomial time and , for evaluating unions of conjunctive queries on probabilistic databases can be lifted to our open-world model. This result is supported by an algorithm that computes the probabilities of the so-calledsafequeries efficiently. Based on this algorithm, we prove that evaluating safe queries is inlinear timefor probabilistic databases, under reasonable assumptions. This remains true in open-world probabilistic databases for a more restricted class of safe queries. We extend our data complexity analysis beyond unions of conjunctive queries, and obtain a host of complexity results for both classical and open-world probabilistic databases. We conclude our analysis with an in-depth investigation of thecombined complexityin the respective models.
登录
查看更多内容
贝叶斯和 Credal 网络的推理复杂性
DOI：
--
发表时间：
2005
期刊：
International Joint Conference on Artificial Intelligence
影响因子：
--
作者：
Cassio Polpo de Campos;Fabio Gagliardi Cozman
通讯作者：
Fabio Gagliardi Cozman
开放世界概率数据库：精简报告
DOI：
10.24963/ijcai.2017/669
发表时间：
2017
期刊：
Proceedings of the 2018 International Conference on Management of Data
影响因子：
--
作者：
I. Ceylan;Adnan Darwiche;Guy Van den Broeck
通讯作者：
Guy Van den Broeck
基于哈希的近似 DNF 计数方法
影响因子：
3.1
作者：
Kuldeep S. Meel;Aditya A. Shrotri;Moshe Y. Vardi
通讯作者：
Moshe Y. Vardi
SPROUT2：用于不确定网络数据的平方查询引擎
DOI：
10.1145/1989323.1989481
发表时间：
2011
期刊：
ACM Trans. Database Syst.
影响因子：
--
作者：
Robert Fink;A. Hogue;Dan Olteanu;Swaroop Rath
通讯作者：
Swaroop Rath
DOI：
10.1609/aaai.v34i04.5705
发表时间：
2019-04
期刊：
--
影响因子：
--
作者：
Ralph Abboud;I. Ceylan;Thomas Lukasiewicz
通讯作者：
Ralph Abboud;I. Ceylan;Thomas Lukasiewicz