Skip to main content

Complexity Results for Probabilistic Datalog+⁄−

İsmail İlkan Ceylan‚ Thomas Lukasiewicz and Rafael Peñaloza


We study the query evaluation problem in probabilistic databases in the presence of probabilistic existential rules. Our focus is on the 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 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. Thereafter, we introduce a probabilistic inconsistency-tolerant semantics, which we call inconsistency-tolerant possible world semantics. For both of these cases, we provide a thorough complexity analysis relative to different languages, drawing a complete picture of the complexity of probabilistic query answering in this family.

Book Title
Proceedings of the 22nd European Conference on Artificial Intelligence‚ ECAI 2016‚ The Hague‚ The Netherlands‚ August 29 − September 2‚ 2016
Maria S. Fox and Gal A. Kaminka
IOS Press