Knowledge-Base Degrees of Inconsistency: Complexity and Counting

Johannes Klaus Fichte, Markus Hecher, Arne MeierAAAI 2021 · DOI

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.

Figure 1: A medical domain example represented as a graph and its corresponding tree decomposition.

Methodological Framework

The authors employ several sophisticated theoretical tools to analyze the complexity of counting anti-witnesses:

  1. Fixed-Domain Semantics: The analysis focuses on scenarios with a finite and fixed set of individuals, a common constraint in practical database applications.
  2. 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.
  3. Complexity Mapping: The problem is analyzed across various Datalog query types (stratified to disjunctive) and Description Logics (such as $SROIQ$ and $DL_{min}$).
  4. 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.

Figure 5: Complexity results for various classes of Datalog programs and counting problems.

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

BibTeX
@inproceedings{fichte2021knowledge,
  author = {Johannes Klaus Fichte and Markus Hecher and Arne Meier},
  title = {{Knowledge-Base Degrees of Inconsistency: Complexity and Counting}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i7.16788},
}
Figure