Complexity Results for Probabilistic Datalog+/-

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

Toggle side column

Complexity Results for Probabilistic Datalog+/-

İsmail İlkan Ceylanİsmail İlkan Ceylan,  Thomas LukasiewiczThomas Lukasiewicz,  Rafael Peñaloza NyssenRafael Peñaloza Nyssen
İsmail İlkan Ceylan, Thomas Lukasiewicz, Rafael Peñaloza Nyssen
Complexity Results for Probabilistic Datalog+/-
In Maria S. Fox, Gal A. Kaminka, eds., Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016), 1414–1422, 2016. IOS Press
  • KurzfassungAbstract
    We study the query evaluation problem in probabilistic databases in the presence of probabilistic existential rules. Our focus is on Datalog+/- family of languages for which we define the probabilistic counterpart using a flexible and compact encoding of probabilities. This formalism can be viewed as a generalization of probabilistic databases as it allows to generate new facts from the given ones using the so-called tuple generating dependencies, or existential rules. We study the computational cost of this additional expressiveness under two different semantics. First, we use a conventional approach and assume that the probabilistic knowledge base is consistent and employ the standard possible world semantics. Afterwards, we introduce a probabilistic inconsistency-tolerant semantics, which we refer as inconsistency-tolerant possible world semantics. For both of these cases, we provide a through complexity analysis relative to different languages; drawing a complete picture of the complexity of probabilistic query answering in this family.
  • Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{CLN2016,
  author    = {{\.{I}}smail {\.{I}}lkan Ceylan and Thomas Lukasiewicz and Rafael
               Pe{\~{n}}aloza Nyssen},
  title     = {Complexity Results for Probabilistic Datalog+/-},
  editor    = {Maria S. Fox and Gal A. Kaminka},
  booktitle = {Proceedings of the 22nd European Conference on Artificial
               Intelligence (ECAI 2016)},
  publisher = {IOS Press},
  year      = {2016},
  pages     = {1414{\textendash}1422}
}