Bienvenu, Meghyn (CNRS, Université Montpellier, Inria) | Bourgaux, Camille (Université Paris-Sud, CNRS ) | Goasdoué, François (Université Rennes 1, CNRS)

Several inconsistency-tolerant semantics have been introduced for querying inconsistent description logic knowledge bases. This paper addresses the problem of explaining why a tuple is a (non-)answer to a query under such semantics. We define explanations for positive and negative answers under the brave, AR and IAR semantics. We then study the computational properties of explanations in the lightweight description logic DL-Lite_R. For each type of explanation, we analyze the data complexity of recognizing (preferred) explanations and deciding if a given assertion is relevant or necessary. We establish tight connections between intractable explanation problems and variants of propositional satisfiability (SAT), enabling us to generate explanations by exploiting solvers for Boolean satisfaction and optimization problems. Finally, we empirically study the efficiency of our explanation framework using the well-established LUBM benchmark.

Bienvenu, Meghyn, Bourgaux, Camille, Goasdoué, François

Several inconsistency-tolerant semantics have been introduced for querying inconsistent description logic knowledge bases. The first contribution of this paper is a practical approach for computing the query answers under three well-known such semantics, namely the AR, IAR and brave semantics, in the lightweight description logic DL-LiteR. We show that query answering under the intractable AR semantics can be performed efficiently by using IAR and brave semantics as tractable approximations and encoding the AR entailment problem as a propositional satisfiability (SAT) problem. The second issue tackled in this work is explaining why a tuple is a (non-)answer to a query under these semantics. We define explanations for positive and negative answers under the brave, AR and IAR semantics. We then study the computational properties of explanations in DL-LiteR. For each type of explanation, we analyze the data complexity of recognizing (preferred) explanations and deciding if a given assertion is relevant or necessary. We establish tight connections between intractable explanation problems and variants of SAT, enabling us to generate explanations by exploiting solvers for Boolean satisfaction and optimization problems. Finally, we empirically study the efficiency of our query answering and explanation framework using a benchmark we built upon the well-established LUBM benchmark.

Riguzzi, Fabrizio (University of Ferrara) | Bellodi, Elena (University of Ferrara) | Lamma, Evelina (University of Ferrara) | Zese, Riccardo (University of Ferrara)

Modeling real world domains requires ever more frequently to represent uncertain information. The DISPONTE semantics for probabilistic description logics allows to annotate axioms of a knowledge base with a value that represents their probability. In this paper we discuss approaches for performing inference from probabilistic ontologies following the DISPONTE semantics. We present the algorithm BUNDLE for computing the probability of queries. BUNDLE exploits an underlying Description Logic reasoner, such as Pellet, in order to find explanations for a query. These are then encoded in a Binary Decision Diagram that is used for computing the probability of the query.

Pound, Jeffrey (University of Waterloo) | Toman, David (University of Waterloo) | Weddell, Grant (University of Waterloo) | Wu, Jiewen (University of Waterloo)

We consider a generalization of instance retrieval over knowledge bases that provides users with assertions in which descriptions of qualifying objects are given in addition to their identifiers. Notably, this involves a transfer of basic database paradigms involving caching and query rewriting in the context of an assertion retrieval algebra. We present an optimization framework for this algebra, with a focus on finding plans that avoid any need for general knowledge base reasoning at query execution time when sufficient cached results of earlier requests exist.

The idea of using ontologies as a conceptual view over data repositories is becoming more and more popular. For example, in Enterprise Application Integration(Lee, Siau, & Hong 2003), Data Integration (Lenzerini 2002), and the Semantic Web (Heflin & Hendler 2001), the intensional level of the application domain can be profitably represented by an ontology, so that clients can rely on a shared conceptualization when accessing the services provided by the system. In these contexts, the set of instances of the concepts in the ontology is to be managed in the data layer of the system architecture (e.g., in the lowest of the three tiers of the Enterprise Software Architecture), and, since instances correspond to the data items of the underlying information system, such a layer constitutes a very large (much larger than the intensional level of the ontology) repository, to be stored in secondary storage (see (Borgida et al. 1989)).