Datalog emerged in the 1970s as a prominent logic-based query language from Logic Programming and has found numerous applications over the years. It essentially extends the language of unions of conjunctive queries, which corresponds to the select-project-join-union fragment of Relational Algebra, with the important feature of recursion much needed to express some natural queries. As for every other query language, explaining why a result to a Datalog query is obtained is an essential task towards explainable and transparent query evaluation. Several natural explainability notions for Datalog queries have been proposed in the literature that can be captured via the unifying framework of semiring provenance. The goal of this talk is to give an overview of those explainability notions and present very recent results concerning their computational complexity, as well as discussing interesting open problems. We will also discuss the possibility of devising algorithms for explaining answers to Datalog queries based on sophisticated SAT solvers.

This is joint work with Marco Calautti, Ester Livshits and Markus Schneider.

DatalogMTL is a powerful extension of Datalog, designed to handle complex temporal reasoning. In this framework, a temporal dataset consists of facts that hold over intervals along a rational timeline. A DatalogMTL program enables recursive reasoning over these facts, by incorporating metric temporal operators—a metric extension of linear temporal logic (LTL) operators. This results in an expressive language that enhances Datalog's capabilities and opens the door to a range of potential applications.

While the temporal aspect introduces significant computational challenges, several reasoning approaches for DatalogMTL have been proposed, with some already seeing implementation. DatalogMTL has also been further extended with features such as non-monotonic negation, existential rules, and temporal aggregation, introducing even more complex behaviour.

During the talk, I will introduce the line of research on DatalogMTL. I will discuss properties of DatalogMTL, focussing on the reasoning algorithms and analysis of computational complexity.