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

arXiv: https://arxiv.org/abs/2003.05746 · HTML: https://mlsanity.com/paper/2003.05746/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Mar 2020.

## Built on by (most cited first, 7 of 7)

- [Querying Inconsistent Prioritized Data with ORBITS: Algorithms, Implementation, and Experiments](https://mlsanity.com/paper/2202.07980/) (2022)
- [Inconsistency Handling in Prioritized Databases with Universal Constraints: Complexity Analysis and Links with Active Integrity Constraints](https://mlsanity.com/paper/2306.03523/) (2023)
- [Dialogue-based Explanations for Logical Reasoning using Structured Argumentation](https://mlsanity.com/paper/2502.11291/) (2025)
- [A Rule-Based Approach to Specifying Preferences over Conflicting Facts and Querying Inconsistent Knowledge Bases](https://mlsanity.com/paper/2508.07742/) (2025)
- [Cleaning Inconsistent Data in Temporal DL-Lite Under Best Repair Semantics](https://mlsanity.com/paper/2108.12149/) (2021)
- [Using ASP(Q) to Handle Inconsistent Prioritized Data](https://mlsanity.com/paper/2604.21603/) (2026)
- [Inconsistent Databases and Argumentation Frameworks with Collective Attacks](https://mlsanity.com/paper/2605.03954/) (2026)

## Abstract (arXiv)

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.