Skip to Main content Skip to Navigation
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 de l'École normale supérieure, 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.
Complete list of metadatas

Cited literature [46 references]  Display  Hide  Download

https://hal.inria.fr/hal-02947251
Contributor : Camille Bourgaux <>
Submitted on : Thursday, September 24, 2020 - 12:34:55 PM
Last modification on : Friday, September 25, 2020 - 11:20:15 AM

File

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

Identifiers

Collections

Citation

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 / Virtual, Greece. pp.141-151, ⟨10.24963/kr.2020/15⟩. ⟨hal-02947251⟩

Share

Metrics

Record views

23

Files downloads

93