Defeasible disjunctive datalog

    Matthew Morris1[0000−0003−3337−7229] , Tala Ross1[0000−0002−4856−9410] , and
                     Thomas Meyer1,2[0000−0003−2204−6969]
                 1
                     University of Cape Town, Cape Town, South Africa
                                   2
                                     CAIR, South Africa


        Abstract. Datalog is a declarative logic programming language that
        uses classical logical reasoning as its basic form of reasoning. Defeasible
        reasoning is a form of non-classical reasoning that is able to deal with
        exceptions to general assertions in a formal manner. The KLM approach
        to defeasible reasoning is an axiomatic approach based on the concept of
        plausible inference. Since Datalog uses classical reasoning, it is currently
        not able to handle defeasible implications and exceptions. We aim to
        extend the expressivity of Datalog by incorporating KLM-style defeasi-
        ble reasoning into classical Datalog. We present a systematic approach
        to extending the KLM properties and a well-known form of defeasible
        entailment: Rational Closure. We conclude by exploring Datalog exten-
        sions of less conservative forms of defeasible entailment: Relevant and
        Lexicographic Closure.


1     Introduction
The KLM approach, proposed by Kraus, Lehmann and Magidor [8], is a well-
known framework for defeasible reasoning. The KLM properties can be used to
determine the rationality of different forms of defeasible entailment. The frame-
work has been discussed at length in the literature for propositional logic [8,9,10]
and description logics [2,3,11,14]. We present what we believe to be the first the-
oretical approach for extending the KLM framework to Datalog. We consider
an extended form of Datalog, Disjunctive Datalog, which allows for disjunction
in the head of Datalog clauses. We do not consider a semantic characterisation,
in terms of a class of ranked interpretations, for the Datalog case. We instead
provide an algorithmic definition.
    There are two well-known forms of defeasible entailment satisfying the KLM
properties: Rational Closure (RC) [10] and Lexicographic Closure (LC) [9]. Both
are rational [4], with RC being the most conservative form of rational defeasible
entailment, and LC a more permissive form. Another form of defeasible entail-
ment, Relevant Closure (RelC) [2], has been proposed for description logics. It
intuitively seems rational but does not satisfy all of the KLM properties. We
provide algorithmic definitions of RC, LC and RelC, showing that RC and LC
are still rational when converted to Datalog and that RelC is not.
    In the next section we provide the relevant background material, after which
we present our work on KLM-style defeasible entailment for the Datalog case.
We conclude with a discussion of related work and suggestions for future work.


Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0)
2      M. Morris et al.

2     Background

2.1   Propositional Logic

Propositional logic [1] is a simple logic which is built up from a finite set P
of propositional atoms, denoted by meta-variables p, q, . . .. The language L of
propositional logic is the set of all formulas, denoted by α, β, . . ., which are
recursively defined as usual: α ::= > | ⊥ | p | ¬α | α ∧ α | α ∨ α | α → α | α ↔ α.
    An interpretation is a function I : P → {T, F } which assigns a single truth
value to each atom. A formula α ∈ L is satisfied by an interpretation I, denoted
I α, if it can be evaluated to true by I in the usual recursive truth-functional
way. We define the models of a finite set of formulas X to be JXK = {I : I
α, α ∈ X}. We say that a set of formulas X entails a formula α, denoted by
X |= α, if JXK ⊆ J{α}K.


2.2   KLM-style Defeasible Entailment

The KLM approach [8] is based on the concept of plausible inference, which is
represented by defeasible implication operators of the form α |∼ β. This is read
as “typically, if α, then β”.
    Let a knowledge base K be a finite set of defeasible implications. The KLM
framework answers the question: “What does it mean for a defeasible implication
α |∼ β to be entailed by a knowledge base K?”. This is referred to as defeasible
entailment, and denoted by K |≈ α |∼ β.
    Unlike classical entailment, it is well-accepted that defeasible entailment is
not unique. There are multiple formalizations of defeasible entailment, such
as Rational Closure [10], Lexicographic Closure [9], and Relevant Closure [2].
Lehmann and Magidor [10] proposed a set of rationality properties known as the
KLM properties. They argue that if a defeasible entailment algorithm satisfies
all the properties it is believed to be an acceptable form of defeasible entail-
ment. We adopt this approach and refer to these forms of defeasible entailment
as LM-rational. The KLM properties for propositional logic are stated below:

                                                       α ≡ β, K |≈ α |∼ γ
          (Ref) K |≈ α |∼ α                    (LLE)
                                                          K |≈ β |∼ γ

                  K |≈ α |∼ β, β |= γ                  K |≈ α |∼ β, K |≈ α |∼ γ
          (RW)                                 (And)
                      K |≈ α |∼ γ                          K |≈ α |∼ β ∧ γ

                 K |≈ α |∼ γ, K |≈ β |∼ γ              K |≈ α |∼ β, K |≈ α |∼ γ
          (Or)                                 (CM)
                     K |≈ α ∨ β |∼ γ                       K |≈ α ∧ β |∼ γ

                  K |≈ α |∼ γ, K |6≈ α |∼ ¬β
          (RM)
                       K |≈ α ∧ β |∼ γ
                                                 Defeasible disjunctive datalog   3

2.3      Rational Closure
Rational closure is the most conservative form of defeasible entailment. We use
the algorithmic definition [6], which we refer to as the Rational Closure Algo-
rithm, as the sole definition of Rational Closure. The algorithm is split into two
distinct sub-algorithms, proposed by Casini et al. [4]. The BaseRank algorithm
                                                          →
                                                          −
is used to construct a ranking of the classical versions ( K ) of the statements in
the defeasible knowledge base (K), according to typicality of the statements.

 Algorithm 1: BaseRank
   Input: A knowledge base K
   Output: An ordered tuple (R0 , . . . , Rn−1 , R∞ , n)
 1 i := 0;
           −
           →
 2 E0 := K := {α → β | α |∼ β ∈ K};
 3 repeat
 4     Ei+1 := {α → β ∈ Ei | Ei |= ¬α};
 5     Ri := Ei \ Ei+1 ;
 6     i := i + 1;
 7 until Ei−1 = Ei ;
 8 R∞ := Ei−1 ;
 9 if Ei−1 = ∅ then
10     n := i − 1;
11    else
12        n := i;
13    return (R0 , . . . , Rn−1 , R∞ , n)


   The RationalClosure algorithm is used to compute whether a defeasible
implication is entailed by the knowledge base and uses the BaseRank algorithm.

 Algorithm 2: RationalClosure
   Input: A knowledge base K and a defeasible implication α |∼ β
   Output: true, if K |≈ α |∼ β, and false, otherwise
 1 (R0 , . . . , Rn−1 , R∞ , n) := BaseRank(K);
 2 i := 0;
          Sj<n
 3 R := i=0 Rj ;
 4 while R∞ ∪ R |= ¬α and R 6= ∅ do
 5     R := R \ Ri ;
 6     i := i + 1;
 7    return R∞ ∪ R |= α → β;


    Note that while the query passed to RationalClosure must be expressed in
terms of the defeasible implication operator, we can express any classical sentence
α as a defeasible implication ¬α |∼ ⊥ [4]. Thus, the algorithm can be used to
check classical queries as well. Also note that the RationalClosure algorithm
just reduces to a sequence of classical entailment checks.
4        M. Morris et al.

2.4    Disjunctive Datalog
Datalog [5] is a more expressive logic than propositional logic and a popular
query language for deductive databases [12,13]. Datalog is a simplified version
of general logic programming. The language of Disjunctive Datalog is made
up of function-free Horn clauses with the general form: l0 ∧ l1 ∧ · · · ∧ lm →
lm+1 ∨ lm+2 ∨ · · · ∨ ln . Each literal li is either ⊥ or is a positive atom of the form
pi (t0 , . . . , tki ), where pi is a predicate symbol and t0 , . . . , tki are terms. A term is
either a constant or a variable. In our version of Datalog, the left-hand side of
the clause is referred to as the body and the right-hand side as the head. Horn
clauses with a body are called rules and those without a body are called facts.
     A Herbrand Base B P is the set of all ground facts constructible from the sym-
bols in a Datalog program P . A Herbrand interpretation assigns each constant
symbol to itself and each predicate symbol to a set of predicates ranging over con-
stant symbols, and is identified with a subset τ ⊆ B P . For any Herbrand interpre-
tation τ , we define that ⊥ is not in τ . A rule l0 ∧l1 ∧· · ·∧lm → lm+1 ∨lm+2 ∨· · ·∨ln
is true for Herbrand interpretation τ if and only if, for each substitution θ which
replaces variables by constants, if l0 θ ∈ τ, l1 θ ∈ τ, . . . , lm θ ∈ τ then at least one
of lm+1 θ ∈ τ, lm+2 θ ∈ τ, . . . , ln θ ∈ τ holds. A fact l0 ∧ l1 ∧ · · · ∧ lm is true for
Herbrand interpretation τ if and only if, for each substitution θ which replaces
variables by constants, l0 θ ∈ τ, l1 θ ∈ τ, . . . , lm θ ∈ τ all hold. A Herbrand inter-
pretation τ is a Herbrand model of a set of Horn clauses X if and only if every
clause in X is true for τ .

Entailment of Horn Clauses The semantics of standard Datalog only defines
entailment of ground facts. However, for the purposes of this paper, we extend
the semantics of Datalog to allow for classical entailment of non-ground clauses.
We use the definition of entailment under Herbrand semantics for first-order
logic [7]. A set of Horn clauses X entails Horn clause α, denoted by X |= α, if
and only if each Herbrand model of X is also a model of α.

Molecules as Combinations of Literals We introduce the idea of molecules
as a shorthand for a combination of literals. A disjunctive molecule, denoted
α∨ , is a combination of literals of the form: l1 ∨ l2 ∨ · · · ∨ ln . A conjunctive
molecule, denoted α∧ , is a combination of literals of the form: l1 ∧ l2 ∧ · · · ∧ ln . A
molecule, denoted α, is either a disjunctive molecule or a conjunctive molecule.
Now a Disjunctive Datalog rule can be written as α∧ → β ∨ .

3     Defeasible Disjunctive Datalog
3.1    KLM-style Defeasible Rules
We represent plausible inference in Disjunctive Datalog using defeasible rules of
the form: b1 ∧· · ·∧bm |∼ h1 ∨· · ·∨hn . This is read as “typically, if all of b1 , . . . , bm
are true, then at least one of h1 , . . . , hn is true”. We do not consider a semantic
definition of defeasible rules. We will instead define defeasible rules by adapting
rational defeasible entailment algorithms for Disjunctive Datalog.
                                            Defeasible disjunctive datalog     5

3.2   Defeasible Entailment
Let knowledge base K be a finite set of defeasible rules. The main question of
this paper is to algorithmically analyse defeasible entailment K |≈ α |∼ β. That
is, how do we answer the question: “Can we conclude α |∼ β from a defeasible
knowledge base K? ”. When analysing different defeasible entailment algorithms,
Lehmann and Magidor [10] advocate that the KLM properties be used to assess
the rationality of these algorithms. We adopt this approach for Datalog and
provide an extension of the KLM properties for Disjunctive Datalog.

A Motivation for Extending Disjunctive Datalog We find that, due to
the restrictive nature of Datalog’s syntax, none of the KLM properties can be
expressed using Disjunctive Datalog without violating the syntax. However, we
need to ensure that LM-rational forms of defeasible entailment satisfy all of
the KLM properties. We argue that this is necessary, even though the reason-
ing described by some of these properties will never be computed by defeasible
entailment algorithms for Disjunctive Datalog.
   Let us consider an example where we can come to a conclusion that cannot be
expressed in Datalog’s syntax. Even though we cannot express that conclusion,
we still want the algorithm to be able to compute it, otherwise the algorithm
would not be rational. For example, we would want to be able to conclude
t(X) |∼ s(X) ∧ e(X) from {t(X) |∼ s(X), t(X) |∼ e(X)}.

Datalog+ Our proposed extension to Datalog, Datalog+, introduces the idea
of compounds. Compounds, denoted by A, B, . . ., are recursively defined from
base literals l as follows: A ::= l | ¬A | A ∧ A | A ∨ A. In Datalog+ a fact is a
compound A and rules have the form A → B.
    Let τ be a Herbrand interpretation and consider some substitution θ which
replaces variables by constants. We say that compound A is in τ under θ, denoted
Aθ ∈ τ , if and only if one of the following conditions holds, where B, Γ are
compounds and l is a literal:
 • A = l and lθ ∈ τ
 • A = ¬B and Bθ 6∈ τ
 • A = B ∧ Γ , Bθ ∈ τ and Γ θ ∈ τ
 • A = B ∨ Γ and Bθ ∈ τ or Γ θ ∈ τ
   Herbrand interpretation τ is a model of fact A if and only if Aθ ∈ τ for every
possible θ. Herbrand interpretation τ is a model of rule A → B if and only if,
whenever Aθ ∈ τ for some θ, then Bθ ∈ τ for the same θ. A knowledge base K
entails Datalog+ Horn clause (rule or fact) α, denoted by K |= α, if and only if
each Herbrand model of K is also a model of α.

The KLM Properties Expressed in Datalog+ We state the KLM prop-
erties (in Datalog+) for Datalog below, where molecules α, β, γ are used as a
shorthand.
6       M. Morris et al.


                   |= α → β, |= β → α, K |≈ α |∼ γ
            (LLE)
                              K |≈ β |∼ γ
                                                K |≈ α |∼ β, |= β → γ
          (Ref) K |≈ α |∼ α               (RW)
                                                     K |≈ α |∼ γ
                  K |≈ α |∼ β, K |≈ α |∼ γ      K |≈ α |∼ γ, K |≈ β |∼ γ
          (And)                            (Or)
                      K |≈ α |∼ β ∧ γ               K |≈ α ∨ β |∼ γ
                  K |≈ α |∼ β, K |≈ α |∼ γ      K |≈ α |∼ γ, K |6≈ α |∼ ¬β
          (CM)                             (RM)
                      K |≈ α ∧ β |∼ γ                K |≈ α ∧ β |∼ γ


4     Rational Closure for Datalog
In this section we propose a simple adaptation to the Rational Closure algorithms
for the Disjunctive Datalog case.

4.1   Base Rank Algorithm
In the propositional case, we can rewrite a classical statement α as the defeasible
statement ¬α |∼ ⊥ and, hence, we can assume that all of the statements in
our knowledge base are defeasible. It is not possible to rewrite classical clauses
as defeasible rules for the Datalog case. Instead, the adapted version of the
BaseRank algorithm, Algorithm 1, ranks the statements in a knowledge base
K = D∪C, where D is the set of defeasible rules and C the set of classical clauses.
                                                                             →
                                                                             −
It forms a ranking using only the defeasible statements by setting E0 := D on
line 2. Then, since the classical statements are all definite, it adds them to the
the most typical level (the infinite level).
    In the propositional case, a statement α is exceptional with respect to a set
of statements X if X |= ¬α. Datalog∨ ’s syntax does not include the negation
connective ¬, so we use the ⊥ literal to define a notion of falsehood, and hence
exceptionality.
Proposition 1. Let τ be a Herbrand interpretation. Then, τ is a model of ¬α
under Datalog+ semantics iff τ is a model of α → ⊥ under Datalog∨ semantics.
   The exceptionality of molecule α is now assessed using the entailment check
Ei ∪ C |= α → ⊥ on line 4. Finally, when all the defeasible rules are ranked,
BaseRank adds the classical clauses to the infinite level by setting R∞ := Ei−1 ∪C
on line 8.

4.2   Rational Closure Algorithm
As with the BaseRank algorithm, we choose to represent falsehood using the ⊥
literal. The RationalClosure algorithm now uses the entailment check R∞ ∪R |=
α → ⊥ on line 4. Under the assumption that we can compute classical entailment
for Datalog∨ , this adapted version of the RationalClosure algorithm can be
used to check whether a rule α |∼ β is defeasibly entailed by the knowledge base
K = D ∪ C.
                                               Defeasible disjunctive datalog       7

Proposition 2. The adapted RationalClosure algorithm is LM-rational.
    The adapted algorithms and proof of LM-rationality (proofs for satisfaction
of each KLM property) are provided in Appendix A and B.

5     Lexicographic Closure
It seems unnecessary for the Rational Closure algorithm to throw away an entire
level of statements when there is a conflict. While it is true that a statement
within the level is causing the conflict, there are other statements in the level that
may have no effect on the conflict occurring. Lexicographic closure [9] takes a
finer-grained approach to removing statements. It considers all possible subsets of
worst-ranked statements and removes the smallest possible subset such that there
is no longer a conflict. The semantic and algorithmic definitions of Lexicographic
Closure for propositional logic are known and have been shown to be LM-rational
[9]. In this section we provide an extension of Lexicographic Closure to the
Datalog∨ case.

5.1   Lexicographic Closure for Propositional Logic
We adapt the definition of Lexicographic Closure for propositional logic pro-
vided by Casini et al.[4]. The new definition, in terms of the sub-algorithms
SubsetRank and LexicographicClosure, can easily be adapted for Datalog∨ .
    The SubsetRank algorithm, Algorithm 3, constructs a new ranking of state-
ments by using the base ranks R0 , . . . , Rn−1 , R∞ computed by the BaseRank
algorithm. It adds new rank levels Di,ni −1 , Di,ni −2 ,..., Di,1 in between each ex-
isting rank level Ri and Ri+1 . Each level Di,j represents all the different ways
of removing |Ri | − j statements from Ri . The Subsets(X, k) function finds all
possible subsets of size k < n of a set X of size n.

 Algorithm 3: SubsetRank
   Input: A knowledge base K
   Output: An ordered tuple (R0 , . . . , Rk , R∞ , k + 1)
 1 (B0 , . . . , Bm−1 , B∞ , m) := BaseRank(K);
 2 i := 0; k := 0;
 3 repeat
 4     for j := |Bi | to 1 do
 5            Si,j := Subsets(R
                      W        V i , j);
 6            Di,j := X∈Si,j x∈X x;
 7            Rk := Di,j ;
 8            k := k + 1;
 9    i := i + 1;
10 until i := m;
11 R∞ := B∞ ;
12 return (R0 , . . . , Rk , R∞ , k + 1)
8       M. Morris et al.

    The LexicographicClosure algorithm ranks the statements in the input
knowledge base K using the SubsetRank algorithm. It then checks whether the
defeasible implication α |∼ β is defeasibly entailed by K in a manner equivalent
to that used by the RationalClosure algorithm (LexicographicClosure is the
same as RationalClosure, barring the use of SubsetRank instead of BaseRank.)

5.2   Lexicographic Closure for Datalog
In section 5.2 we extend the Lexicographic Closure algorithm for the proposi-
tional case to the Datalog case. We conclude the section by showing that our
extended algorithm is LM-rational.

Rephrasing SubsetRank for Datalog The definition of Lexicographic Clo-
sure for the propositional case cannot directly be applied to the Datalog case.
The statement Di,j is formed by combining statements from subset Si,j using ∧
and ∨ connectives. It will violate Datalog∨ ’s syntax if Si,j contains multiple rules
or multiple subsets of facts. However, the statement Di,j can be transformed into
Conjunctive Normal Form (CNF) Di,j := D1 ∧ D2 ∧ . . . ∧ Dn , where:
                  Di := ¬ai,1 ∨ . . . ∨ ¬ai,ri ∨ bi,1 ∨ . . . ∨ bi,si
                      := ¬(ai,1 ∧ . . . ∧ ai,ri ) ∨ (bi,1 ∨ . . . ∨ bi,si )
                      := ai,1 ∧ . . . ∧ ai,ri → bi,1 ∨ . . . ∨ ∨bi,si
                      := αi∧ → βi∨
    Thus, Di,j can be rewritten as a conjunction of Disjunctive Datalog rules.
Checking entailment from a conjunction of rules is equivalent to checking entail-
ment from a set of the same rules. Hence, we can replace each statement Di,j
with a set of Datalog∨ rules. On line 7 of the SubsetRank algorithm, Algorithm
3, we now set Rk := RNF(Di,j ). The Rule Normal Form function RNF(Γ ) takes an
“extended” Disjunctive Datalog statement Γ as input and does the following:
 1. Computes the Conjunctive Normal Form CNF(Γ ).
 2. Converts CNF(Γ ) into a conjunction of clauses of the form (α1∧ → β1∨ )∧(α2∧ →
    β2∨ ) ∧ . . . ∧ (αk∧ → βk∨ ).
 3. Converts the conjunction of clauses into a set of clauses {α1∧ → β1∨ , α2∧ →
    β2∨ , . . . , αk∧ → βk∨ }.
 4. Returns the set of clauses.

Rephrasing LexicographicClosure for Datalog LexicographicClosure is
the same as RationalClosure for the Datalog∨ case, with the exception that
the adapted SubsetRank algorithm is used to rank statements on line 1 instead
of the BaseRank algorithm.
Proposition 3. The adapted LexicographicClosure algorithm is LM-rational.
   The adapted algorithms and proof of LM-rationality are provided in Ap-
pendix C and D.
                                             Defeasible disjunctive datalog      9

6      Relevant Closure for Datalog
6.1     Motivation for Relevant Closure
Here, we give the definition for Relevant Closure as provided by Casini et al. [2].
The algorithm is based on RationalClosure, with some slight changes. The
main idea behind it is that not all statements in a level are responsible for being
able to prove R∞ ∪ R |= ¬α, given the query α |∼ β. This is the motivation for
only throwing away the “relevant” statements in a level.

6.2     Algorithmic Definition
The algorithm for Relevant Closure, provided by Casini et al. [2], is defined in
terms of ALC, a description logic. To make the algorithm easier to understand
and convert to Datalog, we will first express it in terms of propositional logic.

    Algorithm 4: RelevantClosure
   Input: A knowledge base K, a defeasible implication α |∼ β, and a partition
               < R, R− > of K
   Output: true, if K |≈ α |∼ β, and false, otherwise
 1 (R0 , . . . , Rn−1 , R∞ , n) := BaseRank(K);
 2 i := 0;
     0
 3 R := R;
                       −      0            0
 4 while R∞ ∪ R ∪ R |= ¬α and R 6= ∅ do
           0       0
 5     R := R \ {Ri ∩ R};
 6     i := i + 1;
 7    return R∞ ∪ R− ∪ R0 |= α → β;


   In the partition < R, R− > of K, R represents all statements relevant to the
query α |∼ β. When throwing away statements from a level, the algorithm only
considers these statements in R as eligible for removal. We say that a statement
α |∼ β is in the Relevant Closure of K if and only if the RelevantClosure
algorithm returns true when given α |∼ β and K.

6.3     Defining Relevance
Now that the algorithm has been defined, the only work remaining is to define
how to calculate the partition < R, R− > for a given query α |∼ β. Based on
the ideas explored by Casini et al. [2], we would want R to contain exactly all
the statements used to prove ¬α. To formalize this, we present a sequence of
definitions to gradually build up the idea of relevance.
Definition 1. α is said to be exceptional for K if K |= ¬α.
Definition 2. Let K be a knowledge base, J ⊆ K such that J only contains
defeasible implications, and α a propositional sentence. Then J is said to be an
α-justification w.r.t.K if α is exceptional for J and for any J 0 ⊂ J , α is not
exceptional for J 0 .
10     M. Morris et al.

Definition 3. For a sentence α and knowledge base K, let
J K (α) = {J | J is an α-justification w.r.t. K}. Then α |∼ β is said toSbe in the
Basic Relevant Closure of K if it is in the Relevant Closure of K w.r.t. J K (α).

6.4   Minimal Relevant Closure
It could be argued that for Basic Relevant Closure, we are still considering too
many statements as relevant to the query. This is because we consider all the
statements in all α-justifications as relevant to proving that α is exceptional.
However, we could instead consider only the statements of minimal rank from
each α-justification as relevant, and still fix the exceptionality of α.
                                                            K
Definition 4. For some set of justifications J ⊆ K, let Jmin     = {α |∼ β |
rK (α) ≤ rK (γ) for every γ |∼ λ ∈ J }.S
                            K                    K
    For a sentence α, let Jmin (α) = J ∈J K (α) Jmin .
    Then α |∼ β is said to be in Sthe Minimal Relevant Closure of K if it is in
                                       K
the Relevant Closure of K w.r.t. Jmin    (α).

6.5   Relevant Closure for Datalog
In terms of adapting the RelevantClosure algorithm for Datalog, no further
work needs to be done beyond what has already been said for Rational Closure.
To define a molecule α being exceptional, we simply need to be able to check
entailment of negated molecules, which is something we already know how to do.
The remainder of the definitions for both Basic and Minimal Relevant Closure
only entail manipulating sets and checking the rankings of statements.

6.6   LM-Rationality
For this, we will use Minimal Relevant Closure as the definition for Relevant
Closure. As shown by Casini et al. [2], Relevant Closure for propositional logic
satisfies the properties Ref, LLE, And, and RW, and does not satisfy Or, CM,
or RM. We will show that the same holds true for Relevant Closure for Datalog.
    Let us consider the proofs that show that Rational Closure fulfills the KLM
properties of Ref, RW, and And. The only difference RelevantClosure has from
RationalClosure is the inclusion of the “relevance partition”. Thus, the proofs
can be re-used without editing, provided that the relevance partition is the same
throughout the various queries.
    The relevance partition is fully determined by the antecedent of the query
(e.g. α in α |∼ β), as can be seen in the definition of Minimal Relevant Closure.
In the aforementioned properties, the antecedent is the same in all queries made
to the algorithm. Hence, the proofs can be directly re-used to show that Relevant
Closure fulfills the KLM properties of Ref, RW, and And.
    The proof for satisfaction of the property LLE and the counter-examples for
satisfaction of the properties Or, CM, and RM can be found in Appendix F.
The counter-examples were adapted from the ALC case [2].
                                             Defeasible disjunctive datalog    11

7   Conclusions

The main focus of this paper was to provide versions of defeasible reasoning
for Disjunctive Datalog. To be able to express the KLM properties and the
algorithm in Datalog, we motivated for extensions that would have to be made
to the syntax and semantics of Datalog. We proved that Rational Closure for
Datalog was LM-rational (i.e. it conforms to the KLM properties).
    We introduced Relevant Closure and Lexicographic Closure as alternatives
for computing defeasible entailment and adapted both of the algorithms for
Datalog. We found that Lexicographic Closure is still LM-rational, but that
Relevant Closure does not satisfy some of the KLM properties.


8   Future Work

Future work on this topic would most likely include finding a semantic defini-
tion of Rational Closure for Datalog, based on minimal models. Other future
work could include an attempted adaptation of the Relevant Closure method for
computing defeasible entailment, done in such a way that it satisfies the KLM
properties, while still maintaining the basic ideas of Relevant Closure.
    As another option, Casini et al. [4] showed that LM-rationality is necessary
but not sufficient. The additional properties for Basic Defeasible Entailment pro-
posed by Casini et al. [4] can be extended to Datalog. Furthermore, other prop-
erties that are specific to defeasible entailment for Datalog should be explored.
Finally, there is also potential for an implementation of defeasible reasoning in
Datalog. In a paper submitted to this conference, Harrison and Meyer present
an implementation of a defeasible Datalog reasoner for Rational Closure.


9   Appendices
This full paper, with appendices, can be accessed online here.
12      M. Morris et al.

References
 1. Ben-Ari, M.: Mathematical Logic for Computer Science. Springer Science & Busi-
    ness Media, Rehovot, Israel (2012)
 2. Casini, G., Meyer, T., Moodley, K., Nortje, R.: Relevant closure: A new form
    of defeasible reasoning for description logics. In: JELIA 2014: Logics in Artificial
    Intelligence. pp. 92–106. Springer, Funchal, Madeira, Portugal (2014)
 3. Casini, G., Meyer, T., Moodley, K., Varzinczak, I.: Towards practical defeasible
    reasoning for description logics. In: Proceedings of the 26th International Workshop
    on Description Logics. pp. 587–599. CEUR Workshop Proceedings, Ulm, Germany
    (2013)
 4. Casini, G., Meyer, T., Varzinczak, I.: Taking defeasible entailment beyond rational
    closure. In: JELIA 2019: Logics in Artificial Intelligence. pp. 182–197. Springer,
    Rende, Italy (2019)
 5. Ceri, S., Gottlob, G., Tanca, L.: What you always wanted to know about datalog
    (and never dared to ask). IEEE Transactions on Knowledge and Data Engineering
    1, 146–166 (1989)
 6. Freund, M.: Preferential reasoning in the perspective of Poole default logic. Arti-
    ficial Intelligence 98, 209–235 (1998)
 7. Genesereth, M., Eric, K.: Introduction to Logic. Morgan & Claypool, Stanford,
    California (2013)
 8. Kraus, S., Lehmann, D., Magidor, M.: Nonmonotonic reasoning, preferential mod-
    els and cumulative logics. Artificial Intelligence 44, 167–207 (1990)
 9. Lehmann, D.: Another perspective on default reasoning. Annals of Mathematics
    and Artificial Intelligence 15(1), 61–82 (1995)
10. Lehmann, D., Magidor, M.: What does a conditional knowledge base entail? Arti-
    ficial Intelligence 55, 1–60 (1992)
11. Moodley, K.: Practical Reasoning for Defeasible Description Logics. Ph.D. thesis,
    University of KwaZulu-Natal (2015). https://doi.org/10.31237/OSF.IO/DW5P2,
    https://thesiscommons.org/dw5p2/
12. Pasarella, E., Lobo, J.: A Datalog Framework for Modeling Relationship-
    based Access Control Policies. In: Proceedings of the 22nd ACM on Sym-
    posium on Access Control Models and Technologies - SACMAT ’17 Ab-
    stracts. pp. 91–102. ACM Press, New York, New York, USA (2017).
    https://doi.org/10.1145/3078861.3078871
13. Shkapsky, A., Yang, M., Interlandi, M., Chiu, H., Condie, T., Zaniolo, C.: Big Data
    Analytics with Datalog Queries on Spark. In: Proceedings of the 2016 International
    Conference on Management of Data - SIGMOD ’16. pp. 1135–1149. ACM Press,
    New York, New York, USA (2016). https://doi.org/10.1145/2882903.2915229,
    http://dl.acm.org/citation.cfm?doid=2882903.2915229
14. Straccia, U., Casini, G.: Defeasible inheritance-based description logics. Journal of
    Artificial Intelligence Research 48, 415–473 (2013)