Ontology-mediated queries for probabilistic databases

Conference item

Probabilistic databases (PDBs) are usually incomplete, e.g., containing only the facts that have been extracted from the Web with high confidence. However, missing facts are often treated as being false, which leads to unintuitive results when querying PDBs. Recently, open-world probabilistic databases (OpenPDBs) were proposed to address this issue by allowing probabilities of unknown facts to take any value from a fixed probability interval. In this paper, we extend OpenPDBs by Datalog± ontologies, under which both upper and lower probabilities of queries become even more informative, enabling us to distinguish queries that were indistinguishable before. We show that the dichotomy between P and PP in (Open)PDBs can be lifted to the case of first-order rewritable positive programs (without negative constraints); and that the problem can become NPPP-complete, once negative constraints are allowed. We also propose an approximating semantics that circumvents the increase in complexity caused by negative constraints.

Authors: Borgwardt, S; Ceylan, İ; Lukasiewicz, T

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: AAAI Press
• Host title: Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI'17)
• Pages: 1063–1069
• Publication date: 2017-01-01
• Acceptance date: 2016-11-12
• Event location: San Francisco, California, USA
• Event start date: 2017-02-04
• Event end date: 2017-02-09
• ISSN: 2159-5399
• Keywords: open-world reasoning; imprecise probabilities; ontology based data access; data complexity dichotomy; probabilistic databases