MV-Datalog+/-: Effective Rule-based Reasoning with Uncertain Observations (Extended Abstract)

1 Introduction

Datalog and its extensions are important languages for databases access and lie at the foundation of many rule-based reasoning formalisms. Continuous theoretical and technical improvements have led to the development of highly efficient Datalog systems for widespread practical use in a variety of applications (see e.g., [Maier et al., 2018]).

However, in many such real-world applications the observations and facts that serve as the input are not actually certain but rather associated with some (possibly unknown) level of uncertainty. Particularly important in this context are settings where observations are made by Machine Learning (ML) systems. Consider a database that contains a relation which labels images of animals with the class of animal observed in the image. In modern settings, such labels are commonly derived from the output of ML systems that attempt to classify the image contents. Generally, such systems output possible labels for an image, together with a score that can be interpreted as the level of confidence in the correctness of the label (cf., [Mishkin et al., 2017; Lee et al., 2017]). When such labelling is used in further logical inference, the level of confidence in the individual labels would ideally also be reflected in any knowledge inferred from these uncertain observations. However, classical logical reasoning provides no way to consider such information and requires the projection of uncertainty levels to be either true or false, usually via some simple numerical threshold. Beyond the overall loss of information, this can also lead to problematic outcomes where logical conclusions are true despite their derivation being based on observations made with only moderate confidence. With observations from ML systems becoming a commonplace feature of many modern reasoning settings, the projection to binary truth values severely limits the immense potential of integrating ML observations with logic programming.

∗This is an extended abstract of paper [Lanzinger et al., 2022a] that received the Best Paper Award at the International Conference for Logic Programming (ICLP) 2022

There are two natural ways to interpret uncertain observations as described in the example above. One can consider them as the likelihood of the fact being true, i.e., the level of confidence in a fact is interpreted as a probability of the fact holding true. Such an interpretation has been widely studied in the context of Problog [Raedt et al., 2007], Markov Logic Networks [Richardson and Domingos, 2006], and probabilistic databases [Suciu et al., 2011; Cavallo and Pittarelli, 1987]. However, generally, such formalisms make strong assumptions on the pairwise probabilistic independence of all tuples which can be difficult to satisfy. An approach to probabilistic reasoning in Datalog± based on the chase procedure was proposed recently by [Bellomarini et al., 2020].

Alternatively, one can express levels of confidence in a fact in terms of degrees of truth as in fuzzy logics (cf. [H´ajek, 1998]). That is, a fact that is considered to be true to a certain degree, in accordance with the level of confidence in the observation. A variety of approaches to combining logic programming with fuzzy logic have been studied in the past. Pioneering work in this area by [Achs and Kiss, 1995], [Ebrahim, 2001], and [Vojt´as, 2001] introduced an early foundational idea for fuzzy logic programming. Similar ideas have also been proposed in fuzzy description logics, see e.g., [Bobillo and Straccia, 2016; Borgwardt and Pe˜naloza, 2017; Stoilos et al., 2007], or [Lukasiewicz and Straccia, 2008] for an overview of fuzzy DLs.

One limiting factor of the existing logic programming approaches in our intended setting is the reliance on the G¨odel t-norm (see, [Preining, 2010]) as the basis for many-valued semantics. The G¨odel t-norm of two formulas φ, ψ is the minimum of the respective truth degrees of φ and ψ. While this simplifies the resulting logics in certain technical respects, the resulting semantics are not ideal for our envisioned applications in which we want to combine uncertain observations from AI systems with large certain knowledge bases.

Finally, Probabilistic Soft Logic (PSL) was introduced by [Bach et al., 2017] as a framework for fuzzy reasoning with semantics based on Łukasiewicz logic. PSL is a significantly different language with different use cases than our proposed languages. It allows for negation in rule bodies as well as disjunction in the head, in addition to certain forms of aggregation. Semantically it treats all rules as soft constraints (i.e., they might not hold true) and aims to find interpretations that satisfy rules as much as possible. In the context of learning such behaviour is desirable but in terms of reasoning the resulting formalism deviates from many typical characteristics of the Datalog formalisms that we aim to generalise here.

In the following, we provide a high-level overview of our proposed formalisms. Full details and further discussion are available in the full version of this paper [Lanzinger et al., 2022a].

2 Łukasiewicz Logic and K-fuzzyModels

In this paper, we will study the generalisations of Datalog and Datalog± to infinite-valued Łukasiewicz logic Ł (see, [H´ajek, 1998]). Some of our techniques are particular to Łukasiewicz logic and do not readily apply to other many-valued semantics. For some relational signature σ, we consider the following logical language, where R is a relational atom (in σ) and a formula ϕ is defined via the grammar

For a signature σ and countably infinite domain Dom, let GAtoms be the set of all ground atoms with respect to σ and Dom. A truth assignment is a function ν : GAtoms → [0, 1], intuitively assigning a degree of truth in the real interval [0, 1] to every ground atom. By slight abuse of notation, we also apply ν to formulas to express the truth of ground formulas γ, γ ′ according to the following inductive definitions.

That is, ⊙ is the usual Łukasiewicz t-norm and ⊕ is the corresponding t-conorm, which take the place of conjunction and disjunction, respectively. Note that implication γ → γ ′ is equivalent to ¬γ ⊕γ ′ .

For rational K ∈ (0, 1] we say that a formula ϕ is Ksatisfied by ν if for every grounding γ of ϕ over Dom it holds that ν(γ) ≥ K. Whenever we make use of K in this context we assume it to be rational. In the context of rulebased reasoning, it may be of particular interest to observe that an implication is 1-satisfied exactly when the head is at least as true as the body. For a set of formulas Π, we say that a truth assignment ν is a K-fuzzy model if all formulas in Π are K-satisfied by ν.

In place of the database in the classical setting, we instead consider (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 K-fuzzy model of (Π, τ) is a K-fuzzy model ν of Π where ν(G) = τ(G) for every ground atom G for which τ is defined. Whenever we talk about formulas Π and partial truth assignments τ we use ADom to refer to their active domain, i.e., the subset of the domain that is mentioned in either Π or {G ∈ GAtoms | τ(G) is defined.}. We write GAtoms[Adom] to indicate GAtoms restricted to groundings over Adom. K-fuzzy models and their theory were introduced and studied in the context of logic programming by [Ebrahim, 2001] but under different many-valued semantics based on the G¨odel t-norm. For further discussion of the difference in semantics see the full paper [Lanzinger et al., 2022a].

3 MV-Datalog

Definition 1 (MV-Datalog Program). An MV-Datalog program Π is a set of Ł formulas of the form

where all Bi, for 1 ≤ i ≤ n, and H are relational atoms.

As partial truth assignments τ : GAtoms → (0, 1] take the place of the database in a classical Datalog setting. we also refer to such τ as databases in the context of MV-Datalog. We call a pair Π, τ of an MV-Datalog program and database an MV-instance. We can map a MV-Datalog program Π naturally to a Datalog program by substituting ⊙ with ∧. We refer to the resulting Datalog program as Πcrisp . For the respective crisp version of τ, we write Dτ for the (classical) database containing all facts G for which τ(G) is defined.

Analogous to fact entailment in classical Datalog, we consider the following decision problem K-TRUTH, deciding whether a fact is true to at least a degree c in all models.

K-TRUTH

MV-Datalog is a proper extension of Datalog in the sense that for K = 1 and when all ground atoms in the database are assigned truth 1, its models coincide exactly with those of Datalog programs.

Fact entailment in Datalog is typically decided by deriving a minimal model of program and database and checking whether the fact holds true in the (unique) minimal model. The ability to use minimal models as a representative to decide entailment is the key to efficient reasoning in Datalog. In the rest of this Section, we will discuss how the same is also possible for MV-Datalog. For two truth assignment ν, µ we write ν ≤ µ when for all G ∈ GAtoms, it holds that ν(G) ≤ µ(G). We similarly write ν < µ if ν ≤ µ and ν(G) < µ(G) for at least one G ∈ GAtoms .

Definition 2. Let Π, τ be an MV-instance. We say that a Kfuzzy model µ of (Π, τ ) is minimal if for every K-fuzzy model ν of (Π, τ) it holds that µ ≤ ν.

In contrast to Datalog, MV-instances do not always have models. Consider a program consisting only of rule R(x) → S(x). For any K > 0, there is a database τ that assigns truth 1

to R(a) and some truth less than K to S(a) such that the rule is not K-satisfied. This is a consequence of the definition of a K-fuzzy model ν of (Π, τ), which requires the truth values in ν to agree exactly with τ, for every fact for which τ is defined. In some settings, it may be desirable to relax this slightly and consider K-fuzzy models ν where ν(G) ≥ τ (G) where τ(G) is defined. Our semantics cover such a relaxation since it can be simulated by straightforward rewriting of the program: for every relation symbol R that occurs in τ add rule R(x) → R′ (x), and replace all other occurrences of R in the program by R′ . Nonetheless, for satisfiable instances, a suitable minimal model indeed always exists.

Proposition 1. Let Π, τ be an MV-instance. For every rational K ∈ (0, 1], if (Π, τ ) is K-satisfiable, then there exists a unique minimal K-fuzzy model for (Π, τ).

It is not difficult to see that deciding K-TRUTH is straightforward once we have such a unique minimal K-fuzzy model µ. From the definition of the minimality of such models, it directly follows that for every ground fact G we have µ(G) ≥ c if and only if ν(G) ≥ c for all K-fuzzy models of (Π, τ). The remaining question thus is how to find such models. To this end, we provide a characterisation of the minimal K-fuzzy model for some (Π, τ) in terms of a linear program Opt KΠ,τ . The constraints in the program are induced by the oblivious chase procedure (see, [Cal`ı et al., 2013]) 1 for Πcrisp ,Dτ .

Let (Π, τ) be an MV-instance. Let Γ = {γ1, . . . , γm} be the ground rules that occur 2 in an execution of the oblivious chase on Πcrisp ,Dτ . Let G = {G1, . . . ,Gn} be all of the ground atoms occurring in rules in Γ. For every Gi ∈ G we associate Gi with a variable xi in our linear program that intuitively will represent the truth degree of Gi. For γj of the formGj1 ⊙ · · · ⊙Gjℓ →Gjhead define

which directly expresses the satisfaction of rule γj , with variable xjk representing the truth of Gjk . The linear program Opt KΠ,τ is then defined as follows

By construction, any feasible solutions x of Opt KΠ,τ induces a K-fuzzy model νx that assigns νx(Gi) = xi and 0 to all other ground atoms not in G and vice versa. In the full paper, we additionally prove that optimality in the program corresponds exactly to the minimality of the induced K-fuzzy model. This then gives us a concrete and practical procedure for finding K-fuzzy minimal models and thus deciding KTRUTH.

1 While the use of the oblivious chase without existential quantification is untypical we explicitly require all rules induced by oblivious applications for our characterisation. Furthermore, this allows for a simpler transition to the semantics for existential rules in the following section.

2 For a formal definition of this step see [Lanzinger et al., 2022a].

Theorem 2. Let Π, τ be an MV-instance. Then x is an optimal solution of Opt KΠ,τ if and only if νx is a minimal K-fuzzy model of (Π, τ)

Corollary 3. Fix a rational K ∈ (0, 1]. K-TRUTH is in P with respect to data complexity. Moreover, 1-TRUTH is P-complete in data complexity.

4 MV-Datalog±

Existential quantification in the head of rules provides a natural way of dealing with the common problem of incomplete or missing data by declaratively stating that certain facts must exist. Such usage is especially powerful in applications where rule-based reasoning is used for complex data analysis (see e.g., [Bellomarini et al., 2017]). In the following, we introduce MV-Datalog± as an extension of MV-Datalog with a focus on providing a fuzzy reasoning language that is useful for such applications.

To obtain semantics matching our intuition for such a system, we propose an alternative to the commonly studied semantics for existential quantification for Łukasiewicz logic. We then identify certain preferred models that exhibit desired conceptual and computational behaviour as the basis for reasoning in MV-Datalog±.

4.1 Strong Existential Quantification in Łukasiewicz Semantics

The semantics of existential quantification in Łukasiewicz logic is traditionally defined as ν(∃xϕ(x)) = sup{ν(ϕ[x/c]) | c ∈ Dom|x| } where ϕ[x/c] is the substitution of variables x in ϕ by constants c (cf. [H´ajek, 1998]). However, with our focus set on practical applications, we propose alternative semantics for existential quantification that match the semantics of ⊕. To contrast between the aforementioned semantics of ∃ we refer to our semantics as strong existential quantification.

We refer to Ł extended with strong existential quantification as Ł∃ (following standard syntax of first-order existential quantification). Such semantics for quantification in Łukasiewicz logic have also recently been studied more generally in a purely logical context by [Fjellstad and Olsen, 2021].

Definition 3. AMV-Datalog± program is a set of Ł∃ formulas that are either MV-Datalog rules or of the form

where Bi are relational atoms, y are the variables in the body, and ϕ is a formula that contains only a relational atom that uses all variables of x. We refer to a pair of a MV-Datalog± program and a database as an MV±-instance.

As in Datalog±, our truth assignments are not constrained to the active domain of Π and τ but allow for the introduction of "new" constants (i.e., fromDom\Adom). As noted above, the introduction of new constants provides a natural mechanism to deductively handle missing and incomplete data. We propose the use of strong existential quantification to obtain specific desirable behaviour in case of incomplete information, as illustrated by the following example.

Example 1. We consider the following example rule, expressing that every company has a key person, to illustrate the difference between the two semantics for ∃.

Suppose we have the following database, we know for certain that Acme is a company and we are 0.8 degrees confident that Amy is the key person of Acme.

We discuss the case in a 1-fuzzy model in the following. With existential semantics via the supremum of matching ground atoms, the first rule implies the existence of some new KeyPerson(N1, Acme) with truth degree 1. With strong existential quantification, the first rule implies only truth degree 0.2 for some KeyPerson(N1,Acme) since the known observation KeyPerson(Amy,Acme) already contributes 0.8 degrees of truth to the head.

Intuitively, the new constant N1 assumes the role of the unknown other object that possibly is the key person. In traditional semantics for ∃ we have to infer (in a 1-fuzzy model) that N1 is certain to control Acme. In contrast, under strong existential semantics, the confidence in N1 being the key person is determined by the known observation that Amy might be the key person.

4.2 PreferredModels for MV-Datalog±

When considered in full generality, our proposed strong existential quantification semantics create a number of complex theoretical challenges. In particular, it can be necessary for a model to introduce multiple new constants per ground rule to satisfy an existential quantification in certain situations as illustrated by the following example.

Example 2. Consider database τ with τ(S(a)) = 0.8, τ (T (a)) = 0.2 and program Π

Then there is no 1-fuzzy model with only one new constant. However, there is a solution where the facts P(a, n1), P(a, n2), P(a, n3), P(a, n4), with new constants n1, . . . , n4, are all assigned truth degree 0.2.

We focus our development on desired behaviour for practical applications that avoids some of the theoretical corner cases. We formalise this motivation via the notion of preferred models, which are intended to capture the desired output of an MV-Datalog± system in a way that is practically meaningful while also admitting good computational properties. Intuitively, a preferred model of Π, τ has two vital properties. First, the model must relate to some execution of the oblivious chase procedure on Πcrisp , Dτ (we say the model has an oblivious base). This restricts the scope of the unusual behaviour illustrated in Example 2. Second, a preferred model is minimal with respect to some partial ordering of all models with an oblivious base. Looking back at Example 2 again, it is easy to see that plain minimality of models is no longer a useful concept as we can arbitrarily "shift" truth between any of the four facts P(a, ni), e.g., have three of them be true to degree 0.1 and the fourth with truth 0.5. The partial order used in the definition instead orders the models by truth assignments in some "core" part of the model.

Naturally then, an MV±-instance does not necessarily have a unique preferred model. However, analogous to minimal models in MV-Datalog we are still able to characterise them via linear programs. That is, for MV±-instance Π, τ we show how to construct a linear program ∃-Opt KΠ,τ , extending the ideas from the previous construction of Opt KΠ,τ . Note that any of the preferred models is a sensible representative solution that can be used to fact entailment for instances that are satisfiable by a model with an oblivious base.

Theorem 4. Let Π, τ be a MV-Datalog program and database where OLim(Πcrisp ,Dτ) is finite. The following two statements hold.

1. If (Π, τ) has a preferred K-fuzzy model, then ∃-Opt KΠ,τ is feasible.
2. For any optimal solution x of ∃-Opt KΠ,τ , we have that νx is a preferred K-fuzzy model for (Π, τ).

5 Conclusion &FutureWork

We introduced MV-Datalog and MV-Datalog± as generalisations of classical Datalog and Datalog± to the semantics of infinite-valued Łukasiewicz logic. We propose semantics for logic programming for both of these formalisms that are motivated by applications for interfacing classical data with data from ML systems and crowd-sourcing. Reconsidering many-valued generalisations of Datalog± with traditional semantics for existential quantification is an interesting next step for future work. Such semantics would align with the most prominent fuzzy DLs and it is of natural interest whether a corresponding decidable fuzzy Datalog± language can capture such fuzzy DLs, analogous to how DL-Lite and EL are captured by guarded Datalog±. Initial work in this direction has been outlined in recent follow-up work [Lanzinger et al., 2022b].

Acknowledgements

Stefano Sferrazza was supported by the Vienna Science and Technology Fund (WWTF) [10.47379/VRG18013]. 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 and Stefano Sferrazza acknowledge support by the Royal Society "RAISON DATA" project (Reference No. RP\R1\201074). For the purpose of Open Access, the authors have applied a CC BY public copyright licence to any Author Accepted Manuscript (AAM) version arising from this submission.