Computing and Explaining Query Answers over Inconsistent DL-Lite Knowledge Bases

Meghyn Bienvenu 1 Camille Bourgaux 2 François Goasdoué 3
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
2 DIG - Data, Intelligence and Graphs
LTCI - Laboratoire Traitement et Communication de l'Information
3 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. 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-Lite R. 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 entail-ment 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-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 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.
Type de document :
Article dans une revue
Journal of Artificial Intelligence Research, Association for the Advancement of Artificial Intelligence, 2019, 64, pp.563-644. 〈10.1613/jair.1.11395〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-02066288
Contributeur : François Goasdoué <>
Soumis le : mercredi 13 mars 2019 - 17:17:38
Dernière modification le : vendredi 15 mars 2019 - 08:20:31

Fichier

11395-Article (PDF)-21164-1-10...
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Citation

Meghyn Bienvenu, Camille Bourgaux, François Goasdoué. Computing and Explaining Query Answers over Inconsistent DL-Lite Knowledge Bases. Journal of Artificial Intelligence Research, Association for the Advancement of Artificial Intelligence, 2019, 64, pp.563-644. 〈10.1613/jair.1.11395〉. 〈hal-02066288〉

Partager

Métriques

Consultations de la notice

38

Téléchargements de fichiers

84