Fuzzy Datalog∃ over Arbitrary t-Norms

Matthias Lanzinger, Stefano Sferrazza, Przemyslaw Andrzej Walega, Georg Gottlob

Abstract

This paper introduces $t$-Datalog$^\exists$, a novel fuzzy logic framework that extends Datalog with existential rules to manage uncertain data using arbitrary t-norms. By employing a "truth-greedy" chase strategy, the authors demonstrate that reasoning within this framework for weakly acyclic programs maintains a data complexity of P-complete, matching its classical counterpart. This work provides a robust bridge for Neuro-Symbolic AI, allowing for efficient reasoning over probabilistic neural network outputs and structured symbolic knowledge.

Introduction

A persistent challenge in Neuro-Symbolic AI is the representational gap between neural networks and symbolic logic. Neural models typically output probabilistic scores (e.g., an image is 80% likely to contain a "tiger shark"), whereas classical symbolic logic operates on binary truth values. Existing attempts to unify these paradigms often face high computational complexity or impose rigid constraints on how uncertainty is handled.

The authors propose $t$-Datalog$^\exists$ to address these issues. This formalism is designed to be flexible enough to incorporate various fuzzy logic operators (t-norms) and powerful enough to include existential rules, which are essential for reasoning about unknown entities in web data and ontologies, all while ensuring computational tractability.

Methodology: t-Norms and Fuzzy Chases

The core of the framework is the use of t-norms—mathematical functions that generalize the logical "AND" to the interval [0, 1]. Common examples include the product t-norm and the Łukasiewicz t-norm.

To perform reasoning, the authors adapt the classical "chase" algorithm into a fuzzy chase. In this version, derived facts are associated with specific truth degrees. A key innovation is the truth-greedy strategy: the algorithm prioritizes applying rules that yield the highest possible truth degree first. This prevents infinite loops or excessive updates to truth values, allowing the fuzzy chase to be mapped back to a finite sequence of classical chase steps.

An overview of the $t$-Datalog$^\exists$ reasoning process, combining neural predictions from EfficientNet with lexical knowledge from WordNet.

The framework also supports stratified negation and unary operators (like thresholds), ensuring that the logic remains consistent and efficient even when filtering facts based on confidence levels.

Complexity and Key Results

The most significant finding is that adding fuzzy uncertainty does not necessarily impose a "complexity tax." For programs that are weakly acyclic—a standard condition to ensure chase termination—the data complexity of entailment in $t$-Datalog$^\exists$ remains P-complete.

Key results include:

  • Proper Extension: $t$-Datalog$^\exists$ behaves identically to classical Datalog when truth values are restricted to {0, 1}.
  • Flexibility: Support for arbitrary t-norms allows the framework to be tailored to specific domains, such as medical diagnosis or image classification, where different uncertainty models may be appropriate.
  • Efficiency: The P-complete complexity is the "gold standard" for database reasoning, suggesting that the framework can scale to large-scale datasets.

Conceptual Application

While primarily a theoretical contribution, the paper illustrates the framework's utility through a conceptual example. It combines fuzzy labels from a convolutional neural network (EfficientNet) with hierarchical, "crisp" knowledge from WordNet. As shown in the system overview, the reasoner can take image classification probabilities and apply lexical rules to derive common classes and higher-level categories with calculated confidence scores.

Conclusion and Future Work

$t$-Datalog$^\exists$ provides a theoretical foundation for integrating neural uncertainty with symbolic reasoning without sacrificing efficiency. Future work aims to extend these results to fragments where the chase may be infinite but reasoning remains decidable, such as "guarded" or "warded" Datalog$^\exists$. Additionally, the authors envision implementing these techniques within industrial-strength reasoners like Vadalog to test their performance in real-world large-scale applications.

Summary updated

Abstract

One of the main challenges in the area of Neuro-Symbolic AI is to perform logical reasoning in the presence of both neural and symbolic data. This requires combining heterogeneous data sources such as knowledge graphs, neural model predictions, structured databases, crowd-sourced data, and many more. To allow for such reasoning, we generalise the standard rule-based language Datalog with existential rules (commonly referred to as tuple-generating dependencies) to the fuzzy setting, by allowing for arbitrary t-norms in the place of classical conjunctions in rule bodies. The resulting formalism allows us to perform reasoning about data associated with degrees of uncertainty while preserving computational complexity results and the applicability of reasoning techniques established for the standard Datalog setting. In particular, we provide fuzzy extensions of Datalog chases which produce fuzzy universal models and we exploit them to show that in important fragments of the language, reasoning has the same complexity as in the classical setting.
BibTeX
@inproceedings{lanzinger2024fuzzy,
  author = {Matthias Lanzinger and Stefano Sferrazza and Przemyslaw Andrzej Walega and Georg Gottlob},
  title = {{Fuzzy Datalog∃ over Arbitrary t-Norms}},
  booktitle = {LPAR},
  year = {2024},
  doi = {10.29007/cngw},
}
Figure