Inproceedings3093

PublikationenPublications

• Nach AutorBy Author
  • İsmail İlkan Ceylanİsmail İlkan Ceylan
  • Rafael Peñaloza NyssenRafael Peñaloza Nyssen
• Nach ForschungsgruppeBy Research Group
  • AutomatentheorieAutomata Theory

Toggle side column

Complexity of 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 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    = {{\.{I}}smail {\.{I}}lkan 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}
}