Skip to main content

Complexity of Threshold Query Answering in Probabilistic Ontological Data Exchange

Thomas Lukasiewicz and Livia Predoiu


We study the complexity of threshold query answering in the logical framework for probabilistic ontological data exchange, which is an extension of the classical probabilistic data exchange framework with (1) probabilistic databases compactly encoded with several different annotations according to three different probability models used and (2) existential rules of different expressiveness. The ontological data exchange framework provides a logical formalization of exchanging probabilistic data and knowledge from one ontology to another via either deterministic or probabilistic mappings. We define the threshold query answering task in this framework and provide a thorough analysis of its computational complexity for different classes of existential rules and types of complexity. We also delineate several classes of existential rules and a probability model along with a compact encoding in which the threshold query answering problem can be solved in polynomial time in the data complexity.

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