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.
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