Defeasible Datalog

Joshua Abraham and Thomas Pownall



Defeasible Datalog is an extension to the expressivity of classical datalog, which will allow it to reason with knowledge bases of a defeasible nature. It is written as a Python wrapper for the RDFox system.

Description

Datalog is the declarative programming language we have chosen for our project. It is a syntactical subset of Prolog. However unlike Prolog, statements may be evaluated in any order, finite statement sets are guaranteed to terminate and Datalog does not contain Prolog's cut operator. These differences make Datalog a fully declarative programming language. Furthermore, there are other restrictions that limit the expressivity of Datalog. Datalog is often used as a querying language for deductive databases as a result of allowing for efficient query resolution algorithms. This gives it wider application in security, program analysis, networking, cloud computing, information extraction and data integration. Despite this, the restrictions placed on Datalog limit its application in other areas. There exist several extensions of Datalog to address these limitations and our project plans to construct another extension that will allow it to handle defeasible reasoning.

Defeasible reasoning falls under non-monotonic logic, which is a form of logic that allows for the retraction of previously stated claims. Specifically, defeasible reasoning allows for contingent claims. That is, defeasible reasoning allows one to make a claim that may be incomplete and may be retracted given new claims. In this way, it awknowledges fallibility and corrigibility of claims. Defeasible reasoning is important in the field of artificial intelligence (AI) and finds its fullest expression in knowledge representation and planning.

Datalog does not possess the expressivity to handle refeasible reasoning. Our project aim to construct an extension of Datalog with defeasible reasoning called Defeasible Datalog. Our project is split into two main parts:

  1. the theoretical construction of Defeasible Datalog as well as the proof for theoretical correctness.
  2. the implementation of Defeasible Datalog as a proof of concept.
Both parts will be discussed in more detail below and in full detail in the linked papers. We hope that our project will encourage more systems to handle defeasible reasoning, such as is its importance in AI.

Objectives

We briefly mention above the premise of our project. Here we outline our main objectives in achieving this premise. Again, as mentioned above, our project is split into two main parts and as a result the objectives fall into one of these two parts.

Theory

  • Introduce extended syntax that will be required to construct Defeasible Datalog.
  • Describe the semantics related to the this syntax.
  • Describe and adapt the rational closure algorithm for Defeasible Datalog.
  • Show that our adapted rational closure algorithm satisfies the KLM postulates that are required for a reasonable non-monotonic reasoning procedure.

Implementation

  • Extend datalog with negation, to allow for defeasible reasoning.
  • Allow for the input of defeasible statements in RDFox.
  • Adapt the description logic version of the Rational Closure algorithm to a declarative programming language logic.
  • Implement the Defeasible Datalog reasoner, using RDFox as the classical reasoner.
  • Provide test cases to verify the correctness of the reasoner.
  • Run tests on the Defeasible Datalog reasoner, using the provided test cases.

Theory

In order to construct Defeasible Datalog we first decided upon the procedure for which defeasible reasoning will be done. The algorithm we aim to use is known as the Rational Closure algorithm. However, in order to use this algorithm we need to enhance the expressivity of Datalog. In particular, we require Datalog to handle rules that may use negation and disjunction.

Syntax and Semantics

With these requirements in mind, we analysed the current syntax and semantics of Datalog using a bottom-up approach. Using this analysis we constructing the syntax and semantics of Defeasible Datalog, again using a bottom-up approach. This allowed us to incorporate negation and disjunction into Datalog rules.

Rational Closure

Once the syntax and semantics of Defeasible Datalog were constructed we needed to address the Rational Closure algorithm. There are many descriptions of the Rational Closure algorithm, however, we needed to adapt it for Defeasible Datalog. Furthermore, the Rational Closure algorithm requires a procedure for ranking the defeasible statements in order to work. Once we have defined our Rational Closure algorithm we are able to handle reasoning with both classical and defeasible Datalog rules. We are able to do this by making the defeasible rules into classical rules and ranking them according to exceptionality. Then when presented with a query we are able to reason using a number of classical entailment checks.

KLM Postulates

It was stated in the literature that in order for a procedure to be a reasonable non-monotonic reasoner it must satisfy a number of properties. These properties define what is known as a rational relation.



To truly call our construction of Defeasible Datalog sound and complete, we had to show that our definition of Rational Closure reflected a rational relation. That is, it possessed each of the properties shown above. Fortunately, we were able to show that our Rational Closure algorithm does in fact satisfy these properties. Thus, our construction of Defeasible Datalog is sound and complete.

Implementation

Defeasible Datalog was implemented as a wrapper for the RDFox system. RDFox is an RDF triple store that allows for classical datalog reasoning. It was chosen for its efficiency and its incredible materialisation capabilities. It was possible to use RDFox in this project due to the way that the Rational Closure algorithm elegantly turns a defeasible inference check into a series of classical inference checks, by means of ranking the knowledge base according to exceptionality.

Extending Datalog

In order to represent defeasible statements/rules classical datalog had to be extended to allow for negation. This was done by adding a standard negation atom to the datalog language. Using this, a datalog rule to represent that penguins don't fly would be written as:
<http://defeasibledatalog.org/hons/negation#False> :- <http://animal#Penguin>(?X), <http://ability#Fly>(?X)

Ranking Statements

The defeasible statements in the knowledge base are ranked according to exceptionality. A statement is said to be exceptional if its antecedent doesn't produce a clash or contradiction in the current knowledge base. Defeasible statements are ranked from lowest exceptionality, to highest. The last rank consists of all the classical statements (i.e. unexceptional statements), as well as those defeasible statements that are found to be implicitly unexceptional. Below is the adapted version of the Exceptional and Ranking algorithms that were used:

Algorithm 1: Exceptional
											
INPUT: T, the TBox (i.e. the classical datalog rules); D', the defeasible TBox (i.e. the defeasible datalog rules) OUTPUT: E, the list of exceptional rules with respect to the given knowledge base 1 let K' = T + D' 2 let E = [] 3 4 for A ∽⊳ B in D' do 5 if K' ⊧ ¬A then 6 extend E by [A ∽⊳ B] 7 return E
Algorithm 2: Ranking
											
INPUT: T, the TBox (i.e. the classical datalog rules); D, the defeasible TBox (i.e. the defeasible datalog rules) OUTPUT: R, the ranking of the given knowledge base 1 let R = [] 2 let E0 = D 3 let E1 = Exceptional(T, E0) 4 5 while E1 = [] or E0 ≠ E1 do 6 extend R by E1 7 let E0 = E1 8 let E1 = Exceptional(T, E0) 9 10 if E0 = E1 then 11 extend R by [E1 + T] 12 else 13 extend R by E0 14 extend R by T 15 16 return R

Performing Queries

Once all the defeasible statments are ranked, queries are performed by checking whether or not they are in the Rational Closure of the knowledge base. A query is said to be in the Rational Closure if it can be found in the materialisation of any of the subsets of the knowledge base. Subsets are created by, starting with the entire knowledge base, iteratively removing the current lowest rank until the query can be satisfied or only the last rank (i.e. the infinite rank) remains. The syntax of queries should conform to the syntax of our extended datalog. The adapted version of the RationalClosure algorithm is shown below:

Algorithm 3: RationalClosure
											
INPUT: R, the ranked knowledge base; A ∽⊳ B, the query to the knowledge base (typically typical) OUTPUT: True, if R ⊧ A ∽⊳ B and False if not 1 let i = 0 2 while R ⊧ ¬A or length of R > 1 do 3 remove R[i] from R 4 let i = i + 1 5 if R ⊧ A ∽⊳ B then 6 return True 7 else 8 return False


Our implementation of Defeasible Datalog only serves as a prototype to practically show that Datalog can be correctly extended to express and reason with defeasible statements. There are still a lot of improvements that can be made to the system, such as optimisations and the inclusion of various other RDF syntaxes, other than the rdf:type operator that has already been included.

Results

A few examples of the output of our Defeasible Datalog reasoner are given here. The format of the outputs are:

  1. The imported knowledge base, with a seperation between the classical and defeasible statements.
  2. The amount of time it took to rank the knowledge base, along with the final result of ranking the knowledge base.
  3. A few queries to the ranked knowledge base, in datalog syntax, along with the answer to those queries.
These outputs can be obtained by testing the Defeasible Datalog reasoner against the provided test cases (all of which can be found in the GitHub repo) and are numbered accordingly. They are as follows:

(1.1)

(1.2)

(1.3)

(1.4)

(2.1)

(2.2)

Conclusion

We set out to construct Defeasible Datalog, a declarative programming language for reasoning with defeasible statements. We achieved this. Our achievement can be split up in two parts:

  1. We showed that we could theoretically construct such a language. This was done by enhancing the syntax and semantics of Datalog. Adapting the Rational Closure algorithm to be used as our reasoning procedure. Showing that our Rational Closure algorithm represents a rational relation, making it a reasonable procedure for non-monotonic reasoning.
  2. We were able to construct a proof of concept. This was done by extending RDFox with our syntax as well as implementing our Rational Closure algorithm as part of the reasoning procedure.