Information Integration with Provenance on the Semantic Web via Probabilistic Datalog+/

The recently introduced Datalog+/– family of tractable ontology languages is suitable for representing and reasoning over lightweight ontologies, such as EL and the DL-Lite family of description logics. In this paper, we explore the use of Datalog+/– for information integration based on probabilistic data exchange. More specifically, we study the previously introduced probabilistic data exchange problem consisting of a probabilistic database as a source, source-to-target mappings in Datalog+/– and a target Datalog+/– ontology. We provide a complexity analysis for deciding the existence of (deterministic and probabilistic (universal)) solutions in the context of data exchange. In particular, we show that tractability is preserved for simple probabilistic representations, such as tuple-independent ones