Defeasible Reasoning for Datalog

Datalog is an expressive database query language based on the logic programming paradigm, meaning that its queries can be interpreted in terms of mathematical formulas in classical first-order logic. Recently, extensions of Datalog have been proposed for use as an ontology language, to represent the relationships between concepts and objects in various application domains.

Our goal in this project is to provide a mathematical framework for working with defeasible relationships in Datalog. Defeasibility has to do with assertions like “birds usually fly”, in which a relationship is expressed that usually holds, but which may have exceptions.

Our approach is to combine classical Datalog semantics with the KLM framework, an existing mathematical theory of defeasible reasoning for propositional logic. Currently we have a basic framework that can deal with a number of the edge-cases in the literature, and an implementation of a prototype reasoner for Defeasible Datalog programs.

In future work we plan to fix some of the conceptual issues with our current framework, and deal with topics we have left untouched so far, such as the complexity of basic reasoning tasks like entailment and satisfaction.