Explaining Inconsistency-Tolerant Query Answering over Description Logic Knowledge Bases

Meghyn Bienvenu 1, 2 Camille Bourgaux 3 François Goasdoué 4
1 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
4 SHAMAN - Symbolic and Human-centric view of dAta MANagement
IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : 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-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 propositional satisfiabil-ity (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.
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-01277086
Contributor : François Goasdoué <>
Submitted on : Monday, February 22, 2016 - 9:41:42 AM
Last modification on : Saturday, June 29, 2019 - 5:27:26 PM
Long-term archiving on : Sunday, November 13, 2016 - 12:12:24 AM

File

bienvenu-bourgaux.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01277086, version 1

Citation

Meghyn Bienvenu, Camille Bourgaux, François Goasdoué. Explaining Inconsistency-Tolerant Query Answering over Description Logic Knowledge Bases. AAAI Conference on Artificial Intelligence, Feb 2016, Phoenix, United States. ⟨hal-01277086⟩

Share

Metrics

Record views

970

Files downloads

237