Researchers Map Complexity of Repairing Inconsistent Knowledge Bases Using Argumentation Theory

Computer scientists have tackled the thorny problem of how to query and repair inconsistent knowledge bases—systems that combine facts, rules, and priorities that may contradict one another.

The Core Problem#

Knowledge bases typically combine three layers: an ontology (the structural rules), a set of facts, and priorities that indicate which conflicting pieces of information should take precedence. When contradictions arise, the question becomes how to repair the system while preserving as much information as possible. The challenge is understanding which repair strategy—and the computational effort required—best fits different scenarios.

Three Approaches to Repair#

The researchers, building on database research, identified three distinct ways to repair an inconsistent prioritized knowledge base:

• Global repairs focus on maximizing the total amount of preserved information
• Pareto repairs aim to avoid situations where one fact is unnecessarily discarded in favor of another
• Completion repairs balance preservation with structural coherence

Links to Argumentation Frameworks#

A key insight of the work involves connecting these repair strategies to abstract argumentation—a formal framework for modeling disagreement and resolution. The researchers demonstrated that Pareto-optimal repairs correspond directly to stable extensions in argumentation theory, revealing a deep structural relationship between database repair and how arguments are evaluated.

Complexity and Practical Implications#

The team completed a comprehensive analysis of the computational difficulty of core tasks: determining whether a query logically follows from a repaired base, checking if repairs are unique, and listing all possible repairs. They provided this complexity mapping for knowledge bases expressed in DL-Lite, a common and widely-used description logic. The work also introduces a novel semantics inspired by grounded extensions from argumentation, offering favorable computational properties for practitioners seeking to handle inconsistency-tolerant reasoning.