Today, new trends in data management introduce complex datasets and knowledge graphs where data is obtained via crowd-sourcing or from observations made by artificial intelligence systems. Moreover, existing knowledge graphs (KGs) are now commonly enriched using link prediction and KG-completion techniques [1]. Such data points are often associated with a degree of certainty, expressing the level of confidence of the human or AI source in the truth of the datum. These developments raise new challenges for data management and the need for formalisms that can take into account degrees of certainty in data1. Fuzzy logic has a long history as a tool for combining logical reasoning with the diferent types of uncertainty that are encountered in real-world settings by interpreting degrees of certainty as degrees of truth. This naturally motivates the study of Datalog with fuzzy logic semantics as a reasoning formalism for large databases and KGs with uncertainty. Many variants of fuzzy logic programming have been proposed in the literature [2, 3, 4, 5, 6, 7], with the most active research focusing on complex multi-adjoint settings [8, 7], or Prologderived semantics based on fuzzy similarity of constants and fuzzy unification procedures [ 5]. Alternative frameworks for reasoning with uncertainty like Markov Logic Networks [9] and Probabilistic Soft Logic [10] require extensive grounding before inference that can quickly become prohibitive when reasoning over large amounts of data. Our proposed language Datalog aims to be a simpler alternative focused on efective reasoning in large databases and KGs with uncertainty and aims to be the fuzzy analogue of standard Datalog. In this paper, we present the -Datalog formalism and report on ongoing research. In particular, we present a simple and eficient fixpoint procedure for computing minimal fuzzy models for -Datalog. Furthermore, we show how Datalog with fuzzy semantics relates to
the recently proposed Datalog∘ formalism [
A t-norm is a commutative, monotone, and associative function ⊙ : [
The following presentation extends recent work on a restricted version of -Datalog that
allows only the Łukasiewicz t-norm [
To simplify presentation, we assume some fixed global signature and domain Dom
throughout this paper. We write GAtoms for the set of all ground atoms with respect to and Dom. A
truth assignment is a function : GAtoms → [
( ⊙ ′) = ⊙ ( ( ), ( ′)) ( → ′) = min{1, 1 − ( ) + ( ′)} With truth degrees for atoms, it also becomes interesting to consider degrees of satisfaction. For rational ∈ (0, 1] we say that a rule is -satisfied by if for every grounding of over Dom it holds that ( ) ≥ . In particular, a rule → ′ is 1-satisfied by truth assignment exactly when ( ) ≤ ( ′). For a program Π , we say that a truth assignment is a − fuzzy model if all formulas in Π are -satisfied by .
In place of the database in the classical setting, we have (finite) partial truth assignments , that is, partial functions : GAtoms → (0, 1] that are defined for a finite number of ground atoms. Let (Π , ) be a pair where Π is a set of formulas and is a partial truth assignment, a 2By slight abuse of notation we use the same symbol for the t-norm and the corresponding connective in a Datalog rule 3Note that for technical reasons there is only a single → connective and it can not vary by rule. Note also that all standard implications in fuzzy logic behave the same when considering 1-satisfiability. -fuzzy model of (Π , ) is a -fuzzy model of Π where () = () for every ground atom for which is defined. For a partial truth assignment , we write * for the induced truth assignment where * () = () if is defined for , and * () = 0 otherwise.
The natural query task, given Π , and , ∈ (0, 1] is whether a fact is at least true to a target degree in all -fuzzy models of (Π , ). For truth assignments , ′, we say ≤ ′ if for every fact , () ≤ ′(). As in Datalog, if (Π , ) is consistent, then it has a unique minimal -fuzzy model that can be used to evaluate the query task described above.
A step-wise evaluation of -Datalog programs that follows standard procedures for Datalog directly may have to revise the truth of a fact multiple times, as diferent paths of inference may imply diferent degrees of truth. In this section, we show that with the right kind of procedure this is not necessary and evaluation of -Datalog requires at most as many steps of inference as classical Datalog.
For program Π , we first define
Π( ) = max{ (body( )) | ∈ GRulesΠ, (head( )) < (body( )) + − 1} where GRulesΠ is the set of all groundings of rules in Π . The immediate maximal -consequence operator Π, is then defined as Π, ( ) = ′, where is a truth assignment and ′ is the truth assignment determined by the following: 1. if is the head of ground rule with (body( )) = Π( ) > 0 that is not -satisfied by , then set ′() = (body( )) + − 1, 2. otherwise set ′() = ().
Clearly the operator is monotone, i.e., if 1 ≤ 2, then also Π, ( 1) ≤ Π, ( 2). Let Π( ,) denote the -fold application of Π, . It is known that Π, always reaches a fixpoint in a ifnite number of steps, we write Π(∞,) for the application of the operator until a fixpoint is reached. We call the smallest where Π( ,) ( ) = Π( ,+ 1)( ) the fixpoint index of Π , (for ). Observe that when maps only to {0, 1} (i.e., a classical database), Π,1 is precisely the standard immediate consequence operator for Datalog. It is not dificult to see that the procedure can be used for the evaluation of -Datalog.
Theorem 1. Let Π be a -Datalog program and let be a finite partial truth assignment. Then Π(∞,)( * ) is the minimal -fuzzy model of (Π , ).
Simpler immediate consequence operators have been studied in similar settings [
Theorem 2. Let Π be a -Datalog program and let be a finite partial truth assignment. The ifxpoint index of Π , * for is less or equal to the fixpoint index of Π , Δ* for .
Theorem 2 also holds when we adapt the operator Π, to only change one atom at a time.
That is, -Datalog reasoning requires the materialisation of at most as many atoms as reasoning
in Datalog over the corresponding crisp database. This is a significant improvement over the
previously mentioned Markov Logic Networks [
We see that the semantics of -Datalog closely follow classical Datalog semantics, both in terms of minimal models as well as fixpoint semantics. This provides a tight link to existing Datalog literature and thus opens up clear directions for extensions analogous to work for classical Datalog. Among them, we are particularly interested in fuzzy extensions of the Datalog± family of languages, -Datalog with stratified negation, as well as integration with existing Datalog reasoning systems where implementations are based on the immediate consequence operator.
Very recently, Abo Khamis, et al. [
This raises the question of whether the Datalog∘ framework and in particular its convergence conditions, can be extended to consider individual semirings per rule (even with a shared addition monoid). This would allow full expression of -Datalog in Datalog∘ , while also opening up the possibility of combining complex fuzzy reasoning with various forms of aggregation. 4Note that a practical implementation of Π, does not actually require the materialisation of the full set GRulesΠ to compute Π. 5It remains unclear if the same is also possible for -fuzzy models where < 1
We reported on new motivations and ongoing research in the intersection between fuzzy logic
and Datalog. The procedure introduced in Section 3 provides an important foundation for future
work. We are in the process of extending the Vadalog system [
Stefano Sferrazza was supported by the Austrian Science Fund (FWF):P30930. Georg Gottlob is a Royal Society Research Professor and acknowledges support by the Royal Society in this role through the “RAISON DATA” project (Reference No. RP\R1\201074). Matthias Lanzinger acknowledges support by the Royal Society “RAISON DATA” project (Reference No. RP\R1\201074).