Querying and Repairing Inconsistent Prioritized Knowledge Bases: Complexity Analysis and Links with Abstract Argumentation
This academic paper addresses inconsistency handling in prioritized knowledge bases by analyzing the computational complexity of query entailment and repair enumeration under three optimal repair notions (global, Pareto, completion). The work establishes formal connections between optimal repairs and argumentation theory extensions, offering theoretical foundations for knowledge base consistency management.
This paper tackles a fundamental computer science problem: how to handle conflicting information in knowledge bases when facts are assigned different priority levels. The research bridges two traditionally separate fields—database repair theory and formal argumentation—to provide a comprehensive complexity analysis of reasoning tasks over inconsistent prioritized knowledge bases. The authors transfer database repair concepts to description logic settings, specifically focusing on DL-Lite dialects commonly used in semantic web applications.
The work builds on decades of database theory addressing inconsistency, but extends these ideas to ontology-based systems where formal reasoning requirements are stricter. This context matters because modern AI systems increasingly rely on knowledge graphs and ontologies that may contain conflicting information from multiple sources. By establishing that Pareto-optimal repairs correspond to stable extensions in argumentation frameworks, the paper reveals deep structural relationships between these domains.
For the knowledge representation and reasoning community, these results provide actionable guidance on computational trade-offs. The complexity analysis clarifies which reasoning tasks remain tractable under different repair semantics, enabling system designers to choose appropriate consistency-handling strategies based on their computational constraints. The novel grounded-extension-inspired semantics offers favorable properties, suggesting practical alternatives to existing approaches.
The work's significance lies in its theoretical rigor rather than immediate commercial impact. However, it advances the foundations upon which deployed knowledge base systems depend. Future research will likely apply these insights to real-world knowledge graphs managed by major technology companies, where inconsistency handling directly affects AI system reliability and trustworthiness.
- →Three optimal repair notions (global, Pareto, completion) from database theory are successfully adapted to prioritized knowledge bases with complexity analysis.
- →Pareto-optimal repairs precisely correspond to stable extensions in argumentation frameworks, revealing fundamental connections between two research areas.
- →A novel grounded-extension-inspired semantics is proposed with favorable computational properties for inconsistency-tolerant reasoning.
- →Data complexity results for DL-Lite ontologies provide nearly complete picture of core reasoning task tractability.
- →Findings enable knowledge base system designers to make informed choices about consistency-handling strategies based on computational constraints.