Skip to Main content Skip to Navigation
New interface
Conference papers

Querying and Repairing Inconsistent Prioritized Knowledge Bases: Complexity Analysis and Links with Abstract Argumentation

Meghyn Bienvenu 1 Camille Bourgaux 2 
2 VALDA - Value from Data
DI-ENS - Département d'informatique - ENS Paris, Inria de Paris
Abstract : In this paper, we explore the issue of inconsistency handling over prioritized knowledge bases (KBs), which consist of an ontology, a set of facts, and a priority relation between conflicting facts. In the database setting, a closely related scenario has been studied and led to the definition of three different notions of optimal repairs (global, Pareto, and completion) of a prioritized inconsistent database. After transferring the notions of globally-, Pareto- and completion-optimal repairs to our setting, we study the data complexity of the core reasoning tasks: query entailment under inconsistency-tolerant semantics based upon optimal repairs, existence of a unique optimal repair, and enumeration of all optimal repairs. Our results provide a nearly complete picture of the data complexity of these tasks for ontologies formulated in common DL-Lite dialects. The second contribution of our work is to clarify the relationship between optimal repairs and different notions of extensions for (set-based) argumentation frameworks. Among our results, we show that Pareto-optimal repairs correspond precisely to stable extensions (and often also to preferred extensions), and we propose a novel semantics for prioritized KBs which is inspired by grounded extensions and enjoys favourable computational properties. Our study also yields some results of independent interest concerning preference-based argumentation frameworks.
Document type :
Conference papers
Complete list of metadata

Cited literature [46 references]  Display  Hide  Download
Contributor : Camille Bourgaux Connect in order to contact the contributor
Submitted on : Thursday, September 24, 2020 - 12:34:55 PM
Last modification on : Wednesday, June 15, 2022 - 3:25:23 AM
Long-term archiving on: : Thursday, December 3, 2020 - 5:07:08 PM


BieBou-KR20 (1).pdf
Files produced by the author(s)


  • HAL Id : hal-02947251, version 1



Meghyn Bienvenu, Camille Bourgaux. Querying and Repairing Inconsistent Prioritized Knowledge Bases: Complexity Analysis and Links with Abstract Argumentation. KR 2020 - 17th International Conference on Principles of Knowledge Representation and Reasoning, Sep 2020, Rhodes, Greece. pp.141-151. ⟨hal-02947251⟩



Record views


Files downloads