On the Complexity of Querying Inconsistent Weighted Knowledge Bases (Short paper)

Thomas Lukasiewicz, Enrico Malizia, Cristian MolinaroDP@AI*IA 2024 · OpenReview

Introduction

In modern data management, particularly within neuro-symbolic AI and large-scale data integration, information is frequently messy and contradictory. Traditional knowledge representation systems struggle when data from multiple sources conflicts. To address this, researchers employ inconsistency-tolerant semantics, which allow for meaningful query answering even when the underlying knowledge base (KB) is logically inconsistent.

Standard approaches typically rely on "repairs"—maximal consistent subsets of the data. However, these methods often treat all facts as equally reliable. This paper investigates the theoretical implications of adding weights to facts, representing confidence scores or importance, and analyzes how this affects the computational complexity of querying these weighted knowledge bases using the Datalog± family of languages.

Weighted Inconsistency-Tolerant Semantics

The authors extend three established inconsistency-tolerant semantics to accommodate weighted facts:

  1. $\le_w$-AR (ABox Repair): A query is considered true if it is entailed by every weight-maximal consistent subset (repair) of the data.
  2. $\le_w$-IAR (Intersection of Repairs): A query is true if it holds in the intersection of all weight-maximal repairs.
  3. $\le_w$-ICR (Intersection of Closed Repairs): This considers the logical consequences (closure) of each weight-maximal repair before taking their intersection.

By assigning weights, these semantics can prioritize "most reliable" answers. For instance, if every fact is given a weight of 1, these semantics naturally generalize to standard cardinality-maximal repairs.

Complexity Results

The core contribution of this work is a rigorous complexity analysis across various Datalog± fragments, including Linear ($L_\perp$), Guarded ($G_\perp$), and Sticky ($S_\perp$) rules. The analysis considers data complexity (scaling with the number of facts) and combined complexity (scaling with facts, rules, and the query).

Complexity of query answering under $\le_w$-AR semantics.

As shown in the results for the $\le_w$-AR semantics, the data complexity for most fragments is $\Delta^p_2$-complete. This indicates that the problem is significantly harder than standard querying, requiring polynomial time with access to an NP oracle. Combined complexity reaches even higher levels, such as 2EXP-complete for weakly sticky rules.

Complexity of query answering under $\le_w$-IAR and $\le_w$-ICR semantics.

Interestingly, the $\le_w$-IAR and $\le_w$-ICR semantics exhibit identical complexity profiles in the weighted setting. While they are generally more tractable than AR semantics in some measures, the introduction of weights still pushes them into higher complexity classes compared to their unweighted, subset-maximal counterparts.

Key Insights: The Price of Importance

The research highlights a "price of importance": incorporating weights consistently increases the mathematical complexity of the query-answering process.

  • Generalization: Weighted repairs generalize cardinality-maximal repairs, making them a powerful but computationally expensive tool.
  • Semantic Convergence: The convergence of IAR and ICR complexity mirrors the behavior of cardinality-maximal repairs, a departure from the divergence often seen in standard subset-maximal semantics.
  • Computational Bottlenecks: The AR semantics remains the most expensive, particularly under fixed-program combined complexity.

Conclusion and Future Directions

While providing a robust theoretical foundation, the high complexity classes identified (often exponential) suggest that exact methods may be impractical for massive datasets. Future research should focus on:

  • Approximation Algorithms: Developing methods that provide near-optimal answers with better performance.
  • Weighting Rules: Extending the model to include weights for logical rules, not just facts.
  • Explainability: Investigating how to explain derivations from weighted, inconsistent KBs to support "Explainable AI" (XAI) initiatives.

This work clarifies the theoretical landscape of weighted inconsistency-tolerant querying, setting the stage for more practical implementations in complex AI systems.

Summary updated

BibTeX
@inproceedings{lukasiewicz2024complexity,
  author = {Thomas Lukasiewicz and Enrico Malizia and Cristian Molinaro},
  title = {{On the Complexity of Querying Inconsistent Weighted Knowledge Bases (Short paper)}},
  booktitle = {DP@AI*IA},
  year = {2024},
  url = {https://openreview.net/forum?id=aaqfxvlzv7},
}
Figure