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

Overview

• The paper explores the issue of handling inconsistencies in prioritized knowledge bases (KBs), which consist of an ontology, a set of facts, and a priority relation between conflicting facts.
• It examines different notions of optimal repairs (global, Pareto, and completion) for prioritized inconsistent KBs, and studies the computational complexity of key reasoning tasks related to these repairs.
• The paper also clarifies the relationship between optimal repairs and different notions of extensions in argumentation frameworks.

Plain English Explanation

In the world of knowledge management, it's common to encounter conflicting information. This paper focuses on how to handle these inconsistencies when working with prioritized knowledge bases. A prioritized knowledge base is a collection of facts, rules (an ontology), and a system for determining the relative importance of different pieces of information.

The researchers explore three different ways to "fix" or "repair" these inconsistent knowledge bases: global, Pareto, and completion-optimal repairs. Global repairs aim to resolve all conflicts by keeping the most important information. Pareto repairs find a compromise where no single piece of information can be improved without making another worse. Completion repairs fill in any remaining gaps to create a consistent knowledge base.

The paper then looks at the computational complexity of working with these different repair strategies. How difficult is it to determine which repair is best, or to list all possible repairs? The researchers provide a detailed analysis of the time and resources required for these key reasoning tasks, covering common types of ontologies.

Additionally, the paper examines the connection between these repair strategies and the field of argumentation frameworks. It shows that certain repair approaches correspond to well-known concepts in argumentation, like "stable" and "grounded" extensions. This helps bridge the gap between knowledge representation and reasoning about conflicting information.

Technical Explanation

The paper begins by transferring the notions of globally-, Pareto-, and completion-optimal repairs from the database setting to the context of prioritized knowledge bases. These repairs aim to resolve conflicts by keeping the most important information, finding a compromise, or filling in any remaining gaps, respectively.

The researchers then analyze the computational complexity of key reasoning tasks related to these optimal repairs. This includes determining query entailment under different inconsistency-tolerant semantics, checking if a unique optimal repair exists, and enumerating all optimal repairs. They provide a thorough analysis of the data complexity (i.e., the complexity in terms of the size of the input data) for common Description Logic (DL-Lite) ontologies.

The second main contribution of the paper is to clarify the relationship between optimal repairs and different notions of extensions in argumentation frameworks. The researchers show that Pareto-optimal repairs correspond precisely to stable extensions (and often also to preferred extensions) in argumentation. They also propose a novel semantics for prioritized KBs inspired by the concept of grounded extensions, which has favorable computational properties.

Finally, the paper includes some results of independent interest regarding preference-based argumentation frameworks.

Critical Analysis

The paper provides a comprehensive analysis of inconsistency handling in prioritized knowledge bases, covering both theoretical and practical aspects. One strength of the research is the level of detail in the complexity analysis, which gives a clear picture of the computational feasibility of the different repair strategies.

However, the paper does not address how these repair strategies would perform in real-world applications with large, complex knowledge bases. The theoretical complexity results may not always translate directly to practical implementation challenges. Additionally, the paper does not explore how the different repair approaches might impact the quality or usefulness of the resulting knowledge base for tasks like question answering or reasoning about concepts.

Further research could investigate the empirical performance of these repair strategies on realistic datasets, as well as their integration with knowledge linking and other knowledge management tasks. Exploring the tradeoffs between repair quality, computational efficiency, and downstream application performance would be a valuable next step.

Conclusion

This paper makes significant contributions to the understanding of inconsistency handling in prioritized knowledge bases. By defining and analyzing different notions of optimal repairs, the researchers provide a solid theoretical foundation for dealing with conflicting information in knowledge representation and reasoning systems.

The connections drawn between optimal repairs and argumentation frameworks also help bridge the gap between these related fields, potentially leading to fruitful cross-pollination of ideas. The detailed complexity analysis offers guidance on the practical feasibility of implementing these repair strategies, which is crucial for their real-world application.

Overall, this work advances the state of the art in knowledge representation and reasoning, laying the groundwork for more robust and reliable knowledge management systems that can handle the inherent inconsistencies present in large-scale, diverse knowledge bases.