Datalog is a powerful language that can be used to represent explicit knowledge and compute inferences in knowledge bases. Datalog cannot represent or reason about contradictory rules, though. This is a limitation as contradictions are often present in domains that contain exceptions. In this paper, we extend datalog to represent contradictory and defeasible information. We define an approach to efficiently reason about contradictory information in datalog and show that it satisfies the KLM requirements for a rational consequence relation. Finally, we introduce an implementation of this approach in the form of a defeasible datalog reasoning tool and evaluate the performance of this tool.
Datalog [
Datalog has been around since the eighties, but interest in it waned as there
did not seem to be many compelling uses for it. Datalog has experienced some
renewed interest in the past decade as the world moves towards greater levels
of automation in most industries. Some of the areas where datalog is currently
being used include data integration, declarative networking, program analysis,
information extraction, network monitoring, security, and cloud computing [
Most of these reasoning systems have limited applicability to real-world
problems, though, as they can usually not reason about inconsistent or contradictory
information. Contradictions often occur in domains that contain exceptions.
Many systems cannot handle these contradictions due to the systems being
monotonic [
We present a simple example of a case where we would want to be able to represent and reason about exceptional information:
– All mammals don’t lay eggs. – All platypusses are mammals. – All platypusses lay eggs.
If we wanted to query the knowledge base in Example 1 to find out if platypusses lay eggs, traditional datalog reasoning systems (including DLV) would conclude that platypusses lay eggs and platypusses don’t lay eggs, thereby returning an empty model (essentially saying that there can be no platypusses). This is obviously not a desirable result. We would like to extend datalog to represent defeasible knowledge. A defeasible rule is a non-strict rule that typically holds. A defeasible version of Example 1 would be:
– All mammals typically don’t lay eggs. – All platypusses are mammals. – All platypusses typically lay eggs.
Defeasible rules, unlike strict rules, would not have to hold if they are contradicted by strict information.
A seminal approach to reasoning about defeasible knowledge is the
preferential approach, as defined by Kraus, Lehmann, and Magidor [
The KLM approach’s abstract framework and impressive computational tractability make it an appealing candidate for application to the datalog setting. In this paper, we define a defeasible extension to datalog. We define an algorithm that performs a defeasible entailment check for our extended defeasible datalog language, as well as defining the supporting algorithms required to perform this kind of reasoning. We show that our approach meets the KLM requirements for a rational consequence relation. We then introduce an implemented system that can create, edit, and, critically, query a defeasible datalog program. 2
We will first define vanilla datalog before we propose our extensions to it. A datalog program consists of a set of datalog rules. Datalog rules are expressions of the form
b1; :::; bn ! h1 where b1; :::; bn and h1 are literals. The left-hand side of the rule is the body and the right-hand side of the rule is the head 1. Traditionally, the head of a datalog rule contains only one literal but the body is made up of a conjunction of any finite number of literals. If all the literals in the body are true in a model of a datalog program, then the literal in the head is implied and added to the model.
In vanilla datalog, a literal is just an atom p. An atom is an expression p(t1; :::; tm), where p is a predicate with arity m and t1; :::; tm are terms. A term can either be a constant or a variable.
Datalog follows a model-theoretic semantics where the datalog program is
viewed as a set of first-order sentences that describes the desired answer [
We define two language extensions to datalog: 1. A practical defeasible datalog language that is used in our implemented defeasible datalog reasoning. 2. A theoretical defeasible datalog language enriched with additional operators that is used purely to prove how our approach meets the KLM requirements for a rational consequence relation (defined in Section 4). 2.1
We need to define an extension to datalog that is capable of expressing defeasible knowledge. 1 Datalog is often written with the head on the left and the body on the right, with a fullstop at the end of each rule. :– is also often used to represent the implication operator instead of !. This more traditional representation is used for the syntax of our implementation.
The first essential extension to the language is negation, :2. Any literal in the head or body can now be an atom p or a negated atom :p. Negation is necessary in order to be able to express any contradictory information.
Our next extension is disjunction _. We include disjunction as a nice-to-have, purely because our system is built on top of DLV, which uses disjunctive datalog as its underlying language. We, therefore, also only allow disjunction in the head between literals.
Our final extension is an essential one — we add a defeasible implication operator ;3. This operator can be used in place of the traditional strict implication operator ! when we want to express a defeasible rule. 2.2
We define further extensions to our defeasible datalog language, purely to express the postulates that characterise the language and in proving that the postulates hold for our approach.
We introduce disjunction in the body between literals and conjunction in the head between literals.
The defeasible datalog rule corresponds to the logical sentence
b1 _ ::: _ bn ! h1 8x1; :::; xm(b1 _ ::: _ bn ! h1) where x1; :::; xm are all the terms occurring in the all the literals of the rule.
Similarly, the defeasible datalog rule
b1 ! h1 ^ ::: ^ hn corresponds to the logical sentence
8x1; :::; xm(b1 ! h1 ^ ::: ^ hn) where x1; :::; xm are all the terms occurring in all the literals of the rule.
Furthermore, we introduce bottom ?, which can be seen as shorthand for p ^ :p.
Bodies of rules are seen as equivalent if they are modelled by the same interpretations.
A defeasible datalog fact ; is defeasibly entailed (j ) by a defeasible datalog program if, knowing is true and based on the information contained in the defeasible datalog program, it would be sensible to (defeasibly) conclude that is true.
If we have a set of defeasible rules DR, then DR is a set of strict versions ! of all defeasible rules ; in DR. 2 is used to represent negation in our implementation. 3 : is used to represent defeasible implication in our implementation.
Kraus, Lehmann, and Magidor studied preferential consequence relations as an
approach to nonmonotonic reasoning [
A nonmonotonic inference procedure needs to meet properties known as the KLM postulates to be considered a rational consequence relation. The original KLM postulates were defined in propositional logic. We define defeasible datalog versions of the KLM postulates that characterise a rational consequence relation for ranked defeasible datalog models:
; ; K j ; Kj
Kj ; Kj ; ; j= ! Kj ; Kj Kj Kj Kj ; ; Kj Kj ; ^ ; ; ; Kj ; Kj _ ; ; ; Kj Kj ^ ; ; ; K6j Kj ^ ; ; ;: 4
In this section, we attempt to emulate rational closure (a specific construction
given by KLM [
Our rational closure will rely on a ranking of the defeasible datalog rules in a defeasible datalog program. We need to construct a ranking of our defeasible datalog rules based on the exceptionality of each rule. If a rule is assigned a lower ranking, then that rule is more normal or general. If a rule is assigned a higher ranking, then that rule is more exceptional or specific. Only once we have this ranking can we perform rational closure to determine if a rule is defeasibly entailed by our knowledge base. 4 https://github.com/MindfulMichaelJames/proofs/blob/master/Proofs.pdf
Firstly, we define an algorithm to determine which defeasible rules in a set of defeasible rules are exceptional with regards to that set of defeasible rules and an optional set of strict rules. A defeasible rule is exceptional with regards to a set of defeasible and strict rules if the body of the rule is not satifisfiable with regards to the set of defeasible and strict rules.
Platypusses would not be satisfiable in Example 2, meaning that the defeasible rule with platypusses as the body (“All platypusses typically lay eggs”) will be exceptional with regards to the strict rule and the other defeasible rule in Example 2.
1 DRE0 := ;;
Input : A set of strict datalog rules SR and a set of defeasible datalog rules DRE Output: DRE0 DRE such that DRE0 is exceptional w.r.t. SR and DRE Next, we define an algorithm that computes the ranking of a set of defeasible rules. This algorithm starts by putting all the defeasible rules in rank 0. It then utilises Algorithm 1 to determine which rules are exceptional to rank 0 and a set of strict rules. The exceptional rules are moved from rank 0 to rank 1. The same process is then performed to determine which rules in rank 1 are exceptional relative to rank 1 and the strict rules. Those exceptional rules will be moved to rank 2. This process is continued until either there are no more exceptional rules in a rank or all the rules in a rank are exceptional. If all the defeasible rules in a rank are exceptional, then the defeasible rules are strict rules represented as defeasible rules. These rules will be moved to the set of strict rules and represented as strict rules.
Going back to Example 2, the two defeasible rules (“All platypusses typically lay eggs” and “All mammals typically don’t lay eggs”) would start on rank 0. “All platypusses typically lay eggs” would be found to be exceptional with regards to the other defeasible rules in its current rank (“All mammals typically don’t lay eggs”) and the strict rules (“All platypusses are mammals”). “All platypusses typically lay eggs” would, therefore, be moved to rank 1.
Input : A knowledge base consisting of the set of strict datalog rules
SR and the set of defeasible datalog rules DR
Output: The ranking of defeasible rules R and set of strict rules SR 1 DR0 := DR; DR1 := exceptional(SR; DR0); n := 1; R := ;; 2 while DRn 1 6= DRn and DRn 6= ; do 3 n := n + 1; DRn := exceptional(SR; DRn 1); 4 if DRn 6= ; then 5 SR := SR [ DRn; 6 for i = 1 to n 1 do 7
Ri 1 = DRi 1 n DRi; 8 Ri := DRi; 9 return R = Sjj=0i Rj and SR;
Once we have computed the ranking for a defeasible datalog knowledge base, we can go about checking if a defeasible rule is defeasibly entailed by the knowledge base. We do this by checking if the rule is in the rational closure of the knowledge base. Essentially, the rational closure algorithm looks at the portion of the knowledge base for which the queried rule is not exceptional (using Algorithm 1). The algorithm then checks if the rule classically follows from this portion of the knowledge base.
Going back to Example 2 again, if we wanted to query that knowledge base to see if it defeasibly entailed the query “All platypusses typically lay eggs”, we would first look at the portion of the knowledge base where the body of the query is satisfiable. Platypusses are not satisfiable when considering rank 0 (“All mammals typically don’t lay eggs”), rank 1 (“All platypusses typically lay eggs”) and the strict rules (“All platypusses are mammals”). When considering just rank 1 and the strict rules, though, platypusses are satisfiable. We will then look at the strict version of the remaining defeasible rules and the strict rules and see if a strict version of our query is classically entailed, which it is in this case.
Our approach can also check for defeasible entailment of strict rules. To do this, we check if the strict query is classically entailed by the strict portion of the knowledge base. This is worth mentioning, but it is not our focus so it shall not be discussed further here.
; ) Input : A knowledge base K that consists of the ranking R of the set of defeasible rules DR and the set of strict rules SR, and a defeasible query ; Output: True iff ; is in the rational closure of the knowledge base consisting of defeasible rules DR and strict rules SR, False otherwise 1 i := 0; n := number of ranks in R + 1; 2 while Sj n !
j=i Rj [ SR j= 3 i := i + 1; 4 return Sj n ! j=i Rj [ SR j= ! ? and i
n do ! ; 5
We now introduce DDLV. DDLV is a system that performs prefential reasoning for defeasible datalog programs. The defeasible datalog language for defeasible datalog programs is defined in Section 3.1 of this paper.
Defeasible datalog programs can be edited in DDLV for convenience, but its main feature is the capability to query if a defeasible datalog rule is entailed by a defeasible datalog program. DDLV achieves this by implementing the algortithms defined in Section 4.1 of this paper.
DDLV creates a ranking of a defeasible datalog program using implementations of Algorithm 1 and Algorithm 2. This ranking is computed when a defeasible datalog program is loaded into DDLV or edited in DDLV.
To check if a defeasible datalog rule is defeasibly entailed by a defeasible datalog program, DDLV utilises an implementation of Algorithm 3.
Algorithm 1 performs a classical datalog entailment check on line 3.
Algorithm 3 performs two classical datalog entailment checks — one on line 2
and one on line 4. DDLV uses DLV [
DDLV is built in Java and uses the DLV Wrapper [
This section evaluates the performance of DDLV. Seeing as though there are no
other preferential reasoning systems for defeasible datalog, we compare DDLV
5 https://github.com/MindfulMichaelJames/DDLV
with DIP, the Defeasible-Infererence Platform for Description Logics [
We evaluate 10 groups of defeasible datalog programs. Each group has a different percentage of defeasible rules in the program, starting from 10% and going up to 100% in intervals of 10%. Each group contains 35 programs, with the smallest program containing 150 rules and the largest program containing 3500 rules. The program sizes are uniformly distributed between the smallest and largest programs.
Computing the ranking is the greatest bottleneck with this approach. Once the ranking has been computed, defeasible entailment checks can be performed very quickly. We will first compare DDLV’s ranking compilation time with DIP’s.
Moodley used percentile plots because they give a good general picture of
the performance and reveal outliers quickly [
As with DIP, the time that DDLV takes to compute rankings increases with the level of defeasibility present in the program. DDLV seems to perform favourably against DIP, though. DIP already takes about 100 seconds on average to compute a ranking for an ontology with 60% defeasibility. DIP, in the worst case of datalog programs with 100% defeasibility, only takes just over 40 seconds on average to compute a ranking. The longest DIP takes to compute a ranking is nearly 1000 seconds. The longest DDLV takes to compute a ranking is less than 130 seconds.
Next, we will compare the time DDLV takes to perform a defeasible entailment check with the time DIP takes to perform a defeasible entailment check.
DDLV does not outperform DIP on average when it comes to defeasible entailment checks. DIP’s average query time is less than 50 milliseconds, even for ontologies with 100% defeasibility. DDLV’s average query time is about 120 milliseconds in the worst categories. In the worst cases, however, DDLV outperforms DIP. The longest DIP takes to perform a defeasible entailment check is just over 300 millisconds whereas the longest DDLV takes to perform a defeasible entailment check is about 220 milliseconds.
Even though DDLV’s average query time is slower than DIP, the difference is very small in terms of real units of time and almost negligible when single queries are performed in isolation.
DDLV’s impressive ranking time is to be celebrated, because getting the bottleneck of the ranking time to be as short as possible will greatly increase the usability of the system.
To test how well DDLV will scale up, we also present stress tests.
For the size stress test, we recorded the ranking compilation time for 20 defeasible datalog programs varying uniformly in size from 5000 rules to 10000 rules, with all 20 programs having a 20% level of defeasibility. For the ranking depth stress test, we recorded the ranking compilation time for 20 defeasible datalog programs of 5000 rules and a 20% level of defeasibility, while the number of ranks in each program varied from 2 to 21. These two tests were performed because the number of rules in a program and the number or defeasible ranks have shown to have the greatest impact on ranking time. The two stress tests were performed on an Intel Xeon processor with 96 cores. DDLV performs the exceptionality checks for each rule in a rank asynchronously. This allows DDLV to perform as many exceptionality checks in parallel as the number of cores available. We believe this approach is the reason for the impressive results shown in Figure 5 and Figure 6. The longest DDLV took to compute a ranking in the size stress test is just under 7 seconds for 8750 rules. The longest DDLV took to compute a ranking in the ranking depth stress test is just under 6.5 seconds for 19 ranks. 7
The KLM preferential reasoning approach has been lifted to the Description
Logic setting a couple of times in a couple of different flavours [
There does not seem to be much work on handling inconsistent datalog
programs. There is research into handling incomplete knowledge in datalog programs
[
Morris et al., in a submission to this conference, consider the extension of a version of defeasible datalog to relevant closure and lexicographic closure. Their considerations are purely theoretical. 8
We have identified the need for an extension to datalog that can handle inconsistent information in order to deal with exceptions. We introduced the defeasible datalog language that is able to express defeasible datalog rules and contradictory datalog rules.
We lifted the KLM preferential reasoning framework to our defeasible datalog setting. We defined versions of the rational closure algorithm and its supporting ranking and exceptionality algorithms for defeasible datalog. We defined defeasible datalog versions of the KLM postulates and proved that our rational closure algorithm meets these KLM requirements to be considered a rational consequence relation.
Finally, we introduced an implementation of our defeasible datalog reasoning approach that can perform efficient defeasible entailment checks for defeasible datalog programs.
In this paper, our preferential reasoning approach was very syntactic. Future work would involve clearly defining a semantics for this work and demonstrating the correspondence between the syntactic and semantic approaches.