Complexity of Probabilistic Datalog+/-

Ismail Ilkan CeylanIsmail Ilkan Ceylan, Thomas LukasiewiczThomas Lukasiewicz, Rafael Peñaloza NyssenRafael Peñaloza Nyssen

Ismail Ilkan Ceylan, Thomas Lukasiewicz, Rafael Peñaloza Nyssen
Complexity of Probabilistic Datalog+/-
Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016), to appear

Details
Bibtex

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    = {Ismail Ilkan Ceylan and Thomas Lukasiewicz and Rafael
               Pe{\~{n}}aloza Nyssen},
  title     = {Complexity of Probabilistic Datalog+/-},
  booktitle = {Proceedings of the 22nd European Conference on Artificial
               Intelligence (ECAI 2016)},
  year      = {2016}
}