🤖 AI

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

This paper analyzes the data complexity of query entailment and repair enumeration for inconsistent prioritized knowledge bases using three optimal repair notions, while establishing precise correspondences between these repairs and argumentation framework extensions to propose a novel, computationally efficient semantics inspired by grounded extensions.

Original authors: Meghyn Bienvenu, Camille Bourgaux

Published 2026-05-27

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Meghyn Bienvenu, Camille Bourgaux

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: A Messy Library with a Rulebook

Imagine you have a massive library (a Knowledge Base) that contains two things:

The Rulebook (Ontology): A set of strict laws about how things work (e.g., "All snakes are reptiles," "No animal can be both a mammal and a reptile").
The Stack of Notes (Facts/ABox): A pile of sticky notes left by different people describing specific animals (e.g., "Rex is a snake," "Rex is a mammal").

Sometimes, the notes contradict the rulebook or each other. If you have a note saying "Rex is a snake" and another saying "Rex is a mammal," and your rulebook says "Snakes and mammals are mutually exclusive," the whole library becomes inconsistent. In a normal computer system, this mess would cause it to crash or say "Everything is true" (which is useless).

This paper asks: How do we fix the mess without throwing away too much information, especially when we know some notes are more reliable than others?

The "Priority" Twist: Who Gets to Decide?

In the real world, we often know which sources are better. Maybe the note "Rex is a mammal" was written by a famous zoologist, while "Rex is a snake" was scribbled by a confused tourist. We need a way to say, "Trust the zoologist."

The paper introduces a Priority Relation. Think of this as a hierarchy of trust. If two notes conflict, the one with higher priority "wins" and stays; the lower-priority one gets tossed out.

The Three Ways to Clean the Mess (Optimal Repairs)

When you have conflicting notes, there isn't just one way to fix the library. The paper explores three different strategies for deciding which notes to keep, based on the priority rules:

The "Pareto" Approach (The Fair Trade):
- Analogy: Imagine you are trading cards. You only swap a card you have for a new one if the new one is strictly better than the one you are giving up, and you don't have to give up anything else to get it.
- In the paper: You keep a set of notes if you can't swap any of them for a "better" note without losing something else you already have. This is the most flexible approach.
The "Global" Approach (The Total Overhaul):
- Analogy: Imagine you are looking at the whole pile of notes. You ask, "Is there any way to swap a bunch of my current notes for a different bunch of notes that are collectively better?" If the answer is yes, you switch to the new bunch.
- In the paper: This is a stricter check. You look for a "global improvement" where the new set is better in every possible way compared to the old one.
The "Completion" Approach (The Greedy Line):
- Analogy: Imagine a line of people waiting to enter a club. The bouncer (the computer) checks them one by one, starting with the VIPs (highest priority). If a VIP fits in the club without breaking the rules, they get in. Then the next VIP. If a VIP causes a conflict with someone already inside, they are turned away. The bouncer never goes back to check the VIPs they skipped earlier.
- In the paper: This is a "greedy" method. It processes facts in a specific order (a total order) and adds them if they fit.

The Complexity: How Hard is the Math?

The authors ran a "difficulty test" on these three methods to see how much computing power they need.

The Bad News: Fixing the library using the "Pareto" or "Global" methods is very hard for computers. It's like trying to solve a massive Sudoku puzzle where the rules keep changing. For the "Global" method, it's so hard that even powerful computers might take a very long time to find the answer if the library is huge.
The Good News: The "Completion" method (the greedy line) is much easier and faster.
The Surprise: Even though the "Pareto" method is hard to compute, it turns out to be the most "natural" way to think about the problem (more on that below).

The Secret Connection: Argumentation (The Courtroom)

This is the paper's most creative insight. The authors realized that fixing the library is exactly the same as running a courtroom debate.

The Arguments: Each sticky note is an "argument."
The Attacks: If two notes contradict each other, they "attack" each other.
The Preferences: If one note is more reliable, it "defeats" the other note in the debate.

The paper proves a stunning mathematical link:

The "Pareto" way of fixing the library is mathematically identical to finding the "Stable Extensions" in a courtroom debate. A "Stable Extension" is a group of arguments that can all stand together without attacking each other, and they defeat every argument outside the group.
This means that if you can solve the debate problem, you automatically solve the library repair problem.

The New Solution: The "Grounded" Repair

Because the "Pareto" method is so hard to compute, the authors proposed a new, simpler method inspired by the concept of a "Grounded Extension" in argumentation.

Analogy: Imagine a game of "Rock, Paper, Scissors" played in rounds.
1. First, we identify the notes that are so strong they can't be attacked by anything (the "Rock" that no one beats). We keep those.
2. Then, we look at the notes that are only attacked by the ones we just kept. Since their attackers are gone, these notes are now safe. We keep those too.
3. We repeat this process until no new notes can be saved.

This "Grounded" method is:

Fast: Computers can do it very quickly (in polynomial time).
Safe: It never includes a note that is definitely wrong. It is a "conservative" guess.
Better than the competition: The authors compared it to another recent method called "Elect" and showed that the "Grounded" method saves more correct information than "Elect" does.

Summary of Results

Pareto Repairs are the "Gold Standard" (mathematically perfect and natural) but are computationally expensive (hard to calculate).
Global and Completion Repairs are subsets of the Pareto repairs but have different properties.
Grounded Semantics is the authors' new proposal. It is a fast, safe, and efficient way to get a "good enough" answer that is guaranteed to be part of the best possible solution.

Why This Matters (According to the Paper)

The paper doesn't claim to fix real-world medical records or self-driving cars yet. Instead, it provides the theoretical foundation. It tells us:

Which methods are mathematically equivalent (so we can use tools from one field to solve problems in another).
Which methods are too slow for big data and which are fast enough.
That the "Grounded" method is a practical, fast alternative that is better than previous attempts.

In short, the paper builds the bridge between database repair (fixing messy data) and argumentation theory (debating ideas), showing us how to use the logic of debates to clean up messy information efficiently.

Technical Summary: Querying and Repairing Inconsistent Prioritized Knowledge Bases

1. Problem Statement

The paper addresses the challenge of handling inconsistency in Ontology-Mediated Query Answering (OMQA) when the underlying knowledge base (KB) contains prioritized facts. While standard inconsistency-tolerant semantics (such as AR, IAR, and brave) rely on the concept of repairs (inclusion-maximal consistent subsets of the data), they often fail to distinguish between repairs based on the reliability or preference of specific facts.

In database settings, Staworko, Chomicki, and Marcinkowski (2012) introduced three notions of optimal repairs (Pareto, global, and completion) based on a priority relation between conflicting facts. This paper investigates the transfer of these notions to the OMQA setting, specifically for lightweight Description Logics (DL-Lite). The core problems analyzed are:

Query Entailment: Determining if a query holds under inconsistency-tolerant semantics based on optimal repairs (AR, IAR, and brave variants).
Uniqueness: Deciding if a unique optimal repair exists.
Enumeration: Enumerating all optimal repairs.
Argumentation Link: Establishing a formal correspondence between these repairs and extensions in abstract argumentation frameworks.

2. Methodology

The authors employ a two-pronged methodology combining complexity analysis with abstract argumentation theory.

2.1 Complexity Analysis

The study focuses on data complexity, where the ontology ( $T$ ) and query ( $q$ ) are fixed, and complexity is measured against the size of the ABox ( $A$ ). The analysis covers:

DL-Lite Dialects: Primarily $DL\text{-}Lite_{core}$ and $DL\text{-}Lite_{H_{horn}}$ .
Repair Types: Standard repairs ($SRep$), Pareto-optimal ($PRep$), Globally-optimal ($GRep$), and Completion-optimal ($CRep$).
Semantics: Variants of AR (entailment from all repairs), IAR (entailment from the intersection), and brave (entailment from at least one).
Priority Relations: General acyclic relations, transitive relations, and score-structured relations (where priorities are derived from priority levels).

2.2 Argumentation Framework Mapping

The paper introduces a novel translation from prioritized KBs to Preference-based Set-based Argumentation Frameworks (PSETAFs).

Arguments: ABox assertions.
Attacks: Derived from conflicts (minimal inconsistent subsets). An attack $S \to \alpha$ occurs if $S \cup \{\alpha\}$ is inconsistent.
Preferences: The priority relation $\succ$ over facts is mapped to a preference relation over arguments.
Reduction: The authors define a reduction from PSETAFs to standard SETAFs, allowing the application of established argumentation semantics (stable, preferred, grounded) to define repairs.

3. Key Contributions and Results

3.1 Complexity of Reasoning Tasks

The paper provides a nearly complete picture of the data complexity for reasoning with optimal repairs in DL-Lite.

Repair Checking:
- Pareto and Completion: In P (polynomial time).
- Global: coNP-complete.
Query Entailment:
- Pareto/Completion (AR/IAR): coNP-complete.
- Pareto/Completion (Brave): NP-complete.
- Global (AR/IAR): $\Pi^p_2$ -complete.
- Global (Brave): $\Sigma^p_2$ -complete.
- Note: Unlike standard repairs where IAR and brave semantics are tractable (in $AC^0$ ), the introduction of optimality criteria generally increases complexity to the second level of the polynomial hierarchy for global repairs.
Uniqueness and Enumeration:
- Pareto Uniqueness: coNP-complete.
- Global Uniqueness: $\Pi^p_2$ -complete.
- Enumeration: Enumeration of Pareto and Global repairs is not in TOTALP (cannot be done with polynomial total time) for $DL\text{-}Lite_{core}$ . However, for Completion-optimal repairs, enumeration is in DELAYP (polynomial delay) for binary conflicts.
Transitivity: If the priority relation is transitive, uniqueness for Global repairs becomes tractable (P), though other lower bounds remain unchanged.

3.2 Connection to Argumentation

A central theoretical contribution is the precise mapping between optimal repairs and argumentation extensions:

Pareto-Optimal Repairs: Correspond exactly to stable extensions of the associated PSETAF.
Preferred Extensions: Under reasonable assumptions (specifically, if the priority relation is transitive or conflicts are binary), Pareto-optimal repairs also coincide with preferred extensions.
Global and Completion Repairs: These correspond to proper subsets of stable extensions but currently lack a direct analog in standard argumentation literature.

3.3 Grounded Semantics

Inspired by the grounded extension in argumentation, the authors propose a new semantics for prioritized KBs:

Definition: A query is entailed under grounded semantics if it holds in the grounded extension of the associated PSETAF.
Properties:
- The grounded extension is a subset of every Pareto-optimal repair (an under-approximation of P-IAR).
- It is strictly more productive (contains more assertions) than the recently proposed Elect semantics.
- Complexity: Query entailment under grounded semantics is P-complete in data complexity for $DL\text{-}Lite_{H_{horn}}$ .
Implementation: The grounded extension can be computed via the well-founded semantics of a normal logic program, or approximated by a first-order query (SQL) for fixed iteration depths.

4. Significance and Claims

The paper claims significance in three main areas:

Complexity Landscape: It clarifies that while optimal repairs offer more nuanced inconsistency handling, they come at a significant computational cost compared to standard repairs, often pushing problems to the second level of the polynomial hierarchy. However, it identifies specific tractable cases (Pareto/Completion entailment, Grounded semantics).
Argumentation Bridge: It establishes a rigorous link between prioritized database repairs and abstract argumentation. By showing that Pareto-optimal repairs are stable extensions, the paper situates OMQA within a broader theoretical context, allowing for the import of results from argumentation (e.g., coherence properties of symmetric frameworks).
Practical Semantics: The proposal of the grounded semantics offers a tractable alternative for inconsistency handling. It provides a polynomial-time computable approximation of the Pareto-IAR semantics that is more informative than existing alternatives like Elect. The paper demonstrates that this semantics can be implemented using standard logic programming or relational database systems.

The authors note that while they do not definitively answer which of the three optimal repair notions (Pareto, Global, Completion) is "most natural," the correspondence of Pareto repairs with stable and preferred extensions suggests a strong theoretical justification for their adoption. The work also contributes new technical results to the argumentation community, such as the coherence of strongly symmetric PSETAFs with transitive preferences.