Conjunctive Query Answering in Probabilistic Datalog+⁄− Ontologies

Abstract

Datalog+/- is a recently developed family of ontology languages that is especially useful for representing and reasoning over lightweight ontologies, and is set to play a central role in the context of query answering and information extraction for the Semantic Web. It has recently become apparent that it is necessary to develop a principled way to handle uncertainty in this domain; in addition to uncertainty as an inherent aspect of the Web, one must also deal with forms of uncertainty due to inconsistency and incompleteness, uncertainty resulting from automatically processing Web data, as well as uncertainty stemming from the integration of multiple heterogeneous data sources. In this paper, we present two algorithms for answering conjunctive queries over a probabilistic extension of guarded Datalog+/- that uses Markov logic networks as the underlying probabilistic semantics. Conjunctive queries ask: “what is the probability that a given set of atoms hold?”. These queries are especially relevant to Web information extraction, since extractors often work with uncertain rules and facts, and decisions must be made based on the likelihood that certain facts are inferred. The first algorithm for answering conjunctive queries is a basic one using classical forward chaining (known as the chase procedure), while the second one is a backward chaining algorithm and works on a specific subset of guarded Datalog+/-; it can be executed as an anytime algorithm for greater scalability.