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 defeasible 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 extensions of less conservative forms of defeasible entailment: Relevant and Lexicographic Closure.
2.1
Propositional logic [
An interpretation is a function I : P ! fT; F g which assigns a single truth value to each atom. A formula 2 L is satis ed by an interpretation I, denoted I , if it can be evaluated to true by I in the usual recursive truth-functional way. We de ne the models of a nite set of formulas X to be JXK = fI : I ; 2 Xg. We say that a set of formulas X entails a formula , denoted by X j= , if JXK Jf gK. 2.2
The KLM approach [
Let a knowledge base K be a nite set of defeasible implications. The KLM framework answers the question: \What does it mean for a defeasible implication j to be entailed by a knowledge base K?". This is referred to as defeasible entailment, and denoted by K j j .
Unlike classical entailment, it is well-accepted that defeasible entailment is
not unique. There are multiple formalizations of defeasible entailment, such
as Rational Closure [
Rational closure is the most conservative form of defeasible entailment. We use
the algorithmic de nition [
Input: A knowledge base K
Output: An ordered tuple (R0; : : : ; Rn 1; R1; n) 1 i := 0; 2 E0 := !K := f ! 3 repeat 4 Ei+1 := f ! 5 Ri := Ei n Ei+1; 6 i := i + 1; 7 until Ei 1 = Ei; 8 R1 := Ei 1; 9 if Ei 1 = ; then 10 n := i 1; 11 else 12 n := i; j j
2 Kg; 2 Ei j Ei j= : g; 13 return (R0; : : : ; Rn 1; R1; n)
The RationalClosure algorithm is used to compute whether a defeasible implication is entailed by the knowledge base and uses the BaseRank algorithm.
Input: A knowledge base K and a defeasible implication j
Output: true, if K j j , and false, otherwise 1 (R0; : : : ; Rn 1; R1; n) := BaseRank(K); 2 i := 0; 3 R := Sij=<0n Rj; 4 while R1 [ R j= : and R 6= ; do 5 R := R n Ri; 6 i := i + 1; 7 return R1 [ R j=
! ;
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 : j ? [
A Herbrand Base BP is the set of all ground facts constructible from the symbols 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 constant symbols, and is identi ed with a subset BP . For any Herbrand interpretation , we de ne 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 2 ; l1 2 ; : : : ; lm 2 then at least one of lm+1 2 ; lm+2 2 ; : : : ; ln 2 holds. A fact l0 ^ l1 ^ ^ lm is true for Herbrand interpretation if and only if, for each substitution which replaces variables by constants, l0 2 ; l1 2 ; : : : ; lm 2 all hold. A Herbrand interpretation 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 de nes
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 de nition of entailment under Herbrand semantics for rst-order
logic [
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 3.1
We represent plausible inference in Disjunctive Datalog using defeasible rules of the form: b1 ^ ^bm j 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 de nition of defeasible rules. We will instead de ne defeasible rules by adapting rational defeasible entailment algorithms for Disjunctive Datalog.
Let knowledge base K be a nite set of defeasible rules. The main question of
this paper is to algorithmically analyse defeasible entailment K j j . That
is, how do we answer the question: \Can we conclude j from a defeasible
knowledge base K? ". When analysing di erent defeasible entailment algorithms,
Lehmann and Magidor [
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) j s(X) ^ e(X) from ft(X) j s(X); t(X) j e(X)g.
Datalog+ Our proposed extension to Datalog, Datalog+, introduces the idea of compounds. Compounds, denoted by A; B; : : :, are recursively de ned from base literals l as follows: A ::= l j :A j A ^ A j 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 2 , if and only if one of the following conditions holds, where B; are compounds and l is a literal:
A = l and l 2 A = :B and B 62 A = B ^ , B 2 A = B _ and B and 2 or 2
2
Herbrand interpretation is a model of fact A if and only if A 2 for every possible . Herbrand interpretation is a model of rule A ! B if and only if, whenever A 2 for some , then B 2 for the same . A knowledge base K entails Datalog+ Horn clause (rule or fact) , denoted by K j= , if and only if each Herbrand model of K is also a model of .
erties (in Datalog+) for Datalog below, where molecules ; ; are used as a shorthand.
(LLE) j= In the propositional case, we can rewrite a classical statement as the defeasible statement : j ? 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 de nite, it adds them to the the most typical level (the in nite level).
In the propositional case, a statement is exceptional with respect to a set of statements X if X j= : . Datalog_'s syntax does not include the negation connective :, so we use the ? literal to de ne a notion of falsehood, and hence exceptionality.
Proposition 1. Let be a Herbrand interpretation. Then, is a model of : under Datalog+ semantics i is a model of ! ? under Datalog_ semantics.
The exceptionality of molecule is now assessed using the entailment check Ei [ C j= ! ? on line 4. Finally, when all the defeasible rules are ranked, BaseRank adds the classical clauses to the in nite level by setting R1 := Ei 1[C on line 8. 4.2
As with the BaseRank algorithm, we choose to represent falsehood using the ? literal. The RationalClosure algorithm now uses the entailment check R1[R j= ! ? 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 j is defeasibly entailed by the knowledge base K = D [ C. 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
It seems unnecessary for the Rational Closure algorithm to throw away an entire
level of statements when there is a con ict. While it is true that a statement
within the level is causing the con ict, there are other statements in the level that
may have no e ect on the con ict occurring. Lexicographic closure [
We adapt the de nition of Lexicographic Closure for propositional logic
provided by Casini et al.[
The SubsetRank algorithm, Algorithm 3, constructs a new ranking of statements by using the base ranks R0; : : : ; Rn 1; R1 computed by the BaseRank algorithm. It adds new rank levels Di;ni 1, Di;ni 2,..., Di;1 in between each existing rank level Ri and Ri+1. Each level Di;j represents all the di erent ways of removing jRij j statements from Ri. The Subsets(X; k) function nds all possible subsets of size k < n of a set X of size n.
Input: A knowledge base K
Output: An ordered tuple (R0; : : : ; Rk; R1; k + 1) 1 (B0; : : : ; Bm 1; B1; m) := BaseRank(K); 2 i := 0; k := 0; 3 repeat 4 for j := jBij to 1 do 5 Si;j := Subsets(Ri; j); 6 Di;j := WX2Si;j Vx2X x; 7 Rk := Di;j; 8 k := k + 1; 9 i := i + 1; 10 until i := m; 11 R1 := B1; 12 return (R0; : : : ; Rk; R1; k + 1)
The LexicographicClosure algorithm ranks the statements in the input knowledge base K using the SubsetRank algorithm. It then checks whether the defeasible implication j 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
In section 5.2 we extend the Lexicographic Closure algorithm for the propositional case to the Datalog case. We conclude the section by showing that our extended algorithm is LM-rational.
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 entailment 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 f 1^ ! 1_; 2^ ! 2_; : : : ; k^ ! k_g. 4. Returns the set of clauses.
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 Appendix C and D. 6.1
Here, we give the de nition for Relevant Closure as provided by Casini et al. [
The algorithm for Relevant Closure, provided by Casini et al. [
Input: A knowledge base K, a defeasible implication
< R; R > of K
Output: true, if K j j , and false, otherwise 1 (R0; : : : ; Rn 1; R1; n) := BaseRank(K); 2 i := 0; 3 R0 := R; 4 while R1 [ R [ R0 j= : and R0 6= ; do 5 R0 := R0 n fRi \ Rg; 6 i := i + 1; 7 return R1 [ R [ R0 j= ! ; j , and a partition
In the partition < R; R > of K, R represents all statements relevant to the query j . When throwing away statements from a level, the algorithm only considers these statements in R as eligible for removal. We say that a statement j is in the Relevant Closure of K if and only if the RelevantClosure algorithm returns true when given j and K. 6.3
Now that the algorithm has been de ned, the only work remaining is to de ne
how to calculate the partition < R; R > for a given query j . Based on
the ideas explored by Casini et al. [
is said to be exceptional for K if K j= : .
De nition 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 -justi cation w.r.t.K if is exceptional for J and for any J 0 J , is not exceptional for J 0.
De nition 3. For a sentence and knowledge base K, let J K( ) = fJ j J is an -justi cation w.r.t. Kg. Then j is said to be in the Basic Relevant Closure of K if it is in the Relevant Closure of K w.r.t. S J K( ). 6.4
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 -justi cations as relevant to proving that is exceptional. However, we could instead consider only the statements of minimal rank from each -justi cation as relevant, and still x the exceptionality of . De nition 4. For some set of justi cations J K, let JmKin = f j j rK( ) rK( ) for every j 2 J g.
For a sentence , let JmKin( ) = SJ 2J K( ) JmKin.
Then j is said to be in the Minimal Relevant Closure of K if it is in the Relevant Closure of K w.r.t. S JmKin( ). 6.5
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 de ne 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 de nitions for both Basic and Minimal Relevant Closure only entail manipulating sets and checking the rankings of statements. 6.6
For this, we will use Minimal Relevant Closure as the de nition for Relevant
Closure. As shown by Casini et al. [
Let us consider the proofs that show that Rational Closure ful lls the KLM properties of Ref, RW, and And. The only di erence 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 j ), as can be seen in the de nition 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 ful lls 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 [
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 on this topic would most likely include nding a semantic de nition 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 satis es the KLM properties, while still maintaining the basic ideas of Relevant Closure.
As another option, Casini et al. [
This full paper, with appendices, can be accessed online here.