Complexity Results for Probabilistic Datalog+/-

İsmail İlkan Ceylanİsmail İlkan Ceylan, Thomas LukasiewiczThomas Lukasiewicz, Rafael Peñaloza NyssenRafael Peñaloza Nyssen

Download

İ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

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    = {{\.{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}
}