Real-world knowledge bases (KBs) are rarely perfect. They often contain noise, conflicting entries, or data that deviates from a strict schema. In classical logic, even a single contradiction can cause a system to "explode," allowing any conclusion to be technically derived. This paper, presented at AAAI-21, addresses this challenge by moving beyond binary consistency checks. Instead, the authors propose a quantitative framework to measure the "degree of inconsistency" by counting "anti-witnesses"—models of the knowledge base that fail to satisfy a specific Datalog query.
Quantifying Inconsistency via Non-Entailment
Standard reasoning in Description Logics (DLs) typically asks if a query is entailed (true in all possible models). This research focuses on the inverse: non-entailment (NE). By counting the number of models that cannot satisfy a query, researchers can obtain a granular measure of how "broken" a knowledge base is relative to that query. This quantitative approach is particularly valuable for data cleaning and assessing the reliability of AI-driven conclusions in imperfect environments.
To illustrate this, the authors use a medical setting example involving diseases, symptoms, and "superspreaders." This example demonstrates how structural relationships in the data can be analyzed even when inconsistencies are present.
Methodological Framework
The authors employ several sophisticated theoretical tools to analyze the complexity of counting anti-witnesses:
- Fixed-Domain Semantics: The analysis focuses on scenarios with a finite and fixed set of individuals, a common constraint in practical database applications.
- Structural Analysis via Treewidth: To manage computational complexity, the authors represent the relationship between a KB and a query as a graph. They utilize treewidth—a measure of how "tree-like" a graph is—to develop efficient dynamic programming algorithms.
- Complexity Mapping: The problem is analyzed across various Datalog query types (stratified to disjunctive) and Description Logics (such as $SROIQ$ and $DL_{min}$).
- Optimality: Using the Exponential Time Hypothesis (ETH), the authors demonstrate that their algorithms are near-optimal; significant runtime improvements would require fundamental breakthroughs in complexity theory.
Key Results and Complexity Map
The core contribution of the paper is a comprehensive "complexity map" for the Non-Entailment problem. The difficulty of deciding if an anti-witness exists or counting them varies significantly based on the query type and whether "projection" (counting distinct answers for a subset of variables) is involved.
The results show that while these problems are generally high in the polynomial hierarchy (ranging from $\Sigma^P_2$ to $\Sigma^P_4$ for decision problems), they become Fixed-Parameter Tractable (FPT) when the treewidth and domain size are fixed. This means that for large knowledge bases with a "thin" or sparse logical structure, the counting problem can be solved in time linear to the size of the KB.
Insights and Future Directions
A key insight from this work is that the structural complexity of the knowledge—rather than just its raw size—is the primary driver of performance. However, a practical limitation remains: the "constant" factor in these linear-time algorithms involves a "tower" of exponentials based on the treewidth, necessitating very low treewidths for real-world feasibility.
Future work includes extending these methods to "open-world" reasoning with infinite domains and implementing these algorithms in practical solvers to evaluate their performance on large-scale ontologies like those found in the Semantic Web. By providing a rigorous foundation for measuring inconsistency, this research paves the way for more robust AI systems capable of navigating the messy reality of modern data.
Summary updated