Abstract
Inconsistency-tolerant semantics have been proposed to provide meaningful query answers even in the presence of inconsistent knowledge. Recently, explainability has also become a prominent problem in different areas of AI. While the complexity of inconsistency-tolerant semantics is rather well-understood, not much attention has been paid yet to the problem of explaining query answers when inconsistencies may exist. Recent work on existential rules in the inconsistent setting has focused only on understanding why a query is entailed. In this paper, we address another important problem, which is explaining why a query is not entailed under an inconsistency-tolerant semantics. In particular, we consider three popular semantics, namely, the ABox repair, the intersection of repairs, and the intersection of closed repairs. We provide a thorough complexity analysis for a wide range of existential rule languages and for several complexity measures.
Introduction
In the field of automated reasoning, systems are frequently tasked with deriving truths from a set of rules and facts. However, real-world databases are often characterized by inconsistencies—contradictory information arising from the integration of multiple data sources. For instance, one source might identify an individual as a "Professor" while another identifies them as a "Student," violating a rule that these roles are mutually exclusive.
To manage such scenarios, researchers employ inconsistency-tolerant semantics. Rather than failing upon encountering a contradiction, these systems analyze "repairs"—maximal consistent subsets of the data. While significant progress has been made in explaining positive entailments (why a query is true), explaining negative entailments (why a query is not true) has remained a critical gap. Understanding why a system returns a "No" is essential for user trust and debugging in complex knowledge bases.
Formalizing Negative Explanations
The core challenge addressed by Lukasiewicz, Malizia, and Molinaro (IJCAI-22) is providing a formal framework for explaining why a query is not entailed under three primary semantics:
- AR (ABox Repair): The query must hold in every possible repair.
- IAR (Intersection of Repairs): The query must hold using only facts present in every repair.
- ICR (Intersection of Closed Repairs): The query must hold in the intersection of the logical closures of all repairs.
The authors define minimal explanations for negative answers by identifying the "lost" facts. In an inconsistent database, a query typically fails because the repair process deleted the specific facts required to prove it. An explanation is thus a set of facts that, if they had not been removed (or if conflicts were resolved differently), would have allowed the query to be entailed.
Complexity Analysis
A central contribution of this work is a rigorous complexity analysis across various Datalog± (existential rule) languages. The authors evaluate the computational difficulty of checking if a set of facts constitutes a valid minimal explanation, considering both data complexity (scaling with database size) and combined complexity (scaling with both data and rules).
AR and IAR Semantics
For the AR and IAR semantics, the complexity of explaining a negative answer generally mirrors the complexity of the underlying reasoning task. For simpler rule languages like Linear (L) or Acyclic (A) TGDs, checking a minimal explanation is often tractable in terms of data complexity.
ICR Semantics: The "Final Boss"
Explaining non-entailment under ICR semantics is significantly more demanding. This is because ICR requires reasoning about the logical closure of every possible repair, which can be exponentially large. As shown in the complexity map, for more expressive languages like Guarded (G) or Full (F) TGDs, the problem often jumps to $D^P$-complete for data complexity and can reach 2EXP-complete in combined complexity for classes like Weakly Sticky (WS) rules.
Key Insights and Future Directions
The research establishes several foundational principles for explainable AI in inconsistent settings:
- Symmetry of Explanation: Explaining a negative answer is conceptually complementary to explaining missing answers in clean databases; it focuses on identifying which facts were "broken" by the repair process.
- Complexity Parity: A major takeaway is that explaining a negative answer is generally as computationally difficult as the reasoning task itself. If finding an answer is hard, explaining its absence is equally so.
- Minimalism: The framework prioritizes minimal explanations, ensuring users are not overwhelmed by a list of every deleted fact, but rather the smallest set of deletions that invalidated the query.
Future work aims to move beyond fact-centric explanations to include Negative Constraints (the rules themselves) to provide better context (e.g., "Fact X was deleted because of Rule Y"). Additionally, distinguishing between "necessary" facts (present in every explanation) and "relevant" facts (present in at least one) will be crucial for prioritizing information presented to the end-user.
Summary updated