AAAI Publications, Thirty-First AAAI Conference on Artificial Intelligence

Font Size: 
Ontology-Mediated Queries for Probabilistic Databases
Stefan Borgwardt, Ismail Ilkan Ceylan, Thomas Lukasiewicz

Last modified: 2017-02-12


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 NP^PP-complete, once negative constraints are allowed. We also propose an approximating semantics that circumvents the increase in complexity caused by negative constraints.


probabilistic databases; imprecise probabilities; ontology based data access; data complexity dichotomy; open-world reasoning

Full Text: PDF