Ontology-Mediated Queries for Probabilistic Databases

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column

Ontology-Mediated Queries for Probabilistic Databases

Stefan BorgwardtStefan Borgwardt,  İsmail İlkan Ceylanİsmail İlkan Ceylan,  Thomas LukasiewiczThomas Lukasiewicz
Stefan Borgwardt, İsmail İlkan Ceylan, Thomas Lukasiewicz
Ontology-Mediated Queries for Probabilistic Databases
In Satinder Singh, Shaul Markovitch, eds., Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI 2017), 1063–1069, 2017. AAAI Press
  • KurzfassungAbstract
    Probabilistic databases (PDBs) are usually incomplete, e.g., contain 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 (OPDBs) 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 OPDBs 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.
  • Projekt:Project: HAEC
  • Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{BCL2017,
  author    = {Stefan Borgwardt and {\.{I}}smail {\.{I}}lkan Ceylan and Thomas
               Lukasiewicz},
  title     = {Ontology-Mediated Queries for Probabilistic Databases},
  editor    = {Satinder Singh and Shaul Markovitch},
  booktitle = {Proceedings of the 31st {AAAI} Conference on Artificial
               Intelligence (AAAI 2017)},
  publisher = {AAAI Press},
  year      = {2017},
  pages     = {1063{\textendash}1069}
}