Search

Ontology-mediated query answering is a paradigm that seeks to exploit the semantic knowledge expressed in terms of ontologies to improve query answers over incomplete data sources. In this paper, we focus on description logic ontologies, and study the problem of explaining why an ontology-mediated query is entailed from a given data source. Specifically, we view explanations as minimal sets of assertions from an ABox, which satisfy the ontologymediated query. Based on such explanations, we study a variety of problems taken from the recent literature on explanations (studied for existential rules), such as recognizing all minimal explanations. Our results establish tight connections between intractable explanation problems and variants of propositional satisfiability problems. We provide insights on the inherent computational difficulty of deriving explanations for ontology-mediated queries.

Ontologies and rules play a central role in the development of the Semantic Web. Recent research in this context focuses especially on highly scalable formalisms for the Web of Data, which may highly benefit from exploiting database technologies. In this paper, as a first step towards closing the gap between the Semantic Web and databases, we introduce a family of expressive extensions of Datalog, called Datalog^+/-, as a new paradigm for query answering over ontologies. The Datalog^+/- family admits existentially quantified variables in rule heads, and has suitable restrictions to ensure highly efficient ontology querying. We show in particular that Datalog^+/- encompasses and generalizes the tractable description logic EL and the DL-Lite family of tractable description logics, which are the most common tractable ontology languages in the context of the Semantic Web and databases. We also show how stratified negation can be added to Datalog^+/- while keeping ontology querying tractable. Furthermore, the Datalog^+/- family is of interest in its own right, and can, moreover, be used in various contexts such as data integration and data exchange. It paves the way for applying results from databases to the context of the Semantic Web.

We report on a recently introduced family of expressive extensions of Datalog, called Datalog±, which is a new framework for representing ontological axioms in form of integrity constraints, and for query answering under such constraints. Datalog± is derived from Datalog by allowing existentially quantified variables in rule heads, and by enforcing suitable properties in rule bodies, to ensure decidable and efficient query answering. We first present different languages in the Datalog ± family, providing tight complexity bounds for all cases but one (where we have a low complexity AC0 upper bound). We then show that such languages are general enough to capture the most common tractable ontology languages. In particular, we show that the DL-Lite family of description logics and F-Logic Lite are expressible in Datalog ±. We finally show how stratified negation can be added to Datalog± while keeping ontology querying tractable in the data complexity. Datalog± is a natural and very general framework that can be successfully employed in different contexts such as data integration and exchange. This survey mainly summarizes two recent papers. Copyright 2009 ACM.

We present an ontological framework, based on preference rankings, that allows users to express their preferences between the knowledge explicitly available in the ontology. Using this formalism, the answers for a given query to an ontology can be ranked by preference, allowing users to retrieve the most preferred answers only. We provide a host of complexity results for the main computational tasks in this framework, for the general case, and for EL and DL-Lite_core as underlying ontology languages.

For practical ontology-based applications representing and reasoning with probabilities is an essential task. For Description Logics with subjective probabilities reasoning procedures for testing instance relations based on the completion method have been developed. In this paper we extend this technique to devise algorithms for solving non-standard inferences for EL and its probabilistic extension Prob- EL01c: computing the most specific concept of an individual and finding explanations for instance relations.

Translations to (first-order) datalog have been used in a number of inferencing techniques for description logics (DLs), yet the relationship between the semantic expressivities of function-free Horn logic and DL is understood only poorly. Although Description Logic Programs (DLP) have been described as DLs in the "expressive intersection" of DL and datalog, it is unclear what an intersection of two syntactically incomparable logics is, even if both have a first-order logic semantics. In this work, we offer a characterisation for DL fragments that can be expressed, in a concrete sense, in datalog. We then determine the largest such fragment for the DL , and provide an outlook on the extension of our methods to more expressive DLs. © 2010 Springer-Verlag Berlin Heidelberg.

Using mappings between ontologies is a common way of approaching the semantic heterogeneity problem on the Semantic Web. To fit into the landscape of Semantic Web languages, a suitable logic-based representation formalism for mappings is needed, which allows to reason with ontologies and mappings in an integrated manner, and to deal with uncertainty and inconsistencies in automatically created mappings. We analyze the requirements for such a formalism, and propose to use frameworks that integrate description logic ontologies with probabilistic rules. We compare two such frameworks and show the advantages of using the probabilistic extensions of their deterministic counterparts. The two frameworks that we compare are tightly coupled probabilistic dl-programs, which tightly combine the description logics behind OWL DL resp. OWL Lite, disjunctive logic programs under the answer set semantics, and Bayesian probabilities, on the one hand, and generalized Bayesian dl-programs, which tightly combine the DLP-fragment of OWL Lite with Datalog (without negation and equality) based on the semantics of Bayesian networks, on the other hand. © 2008 Springer Berlin Heidelberg.