Datalog and its extensions (such as existential rules) are widely studied querying formalism. A natural question is to characterise which queries can be expressed within such query languages, in the style of Immerman-Vardi theorem. In this talk, I will present some results regarding the expressivity of Datalog-based query languages. The last such result if that, perhaps surprisingly, any query that is decidable and closed under homomorphism is expressible by a set of existential rules for which the standard chase is universally terminating. This talk is based on joint work with Camille Bourgaux, David Carral, Markus Kroetzsch and Sebastian Rudolph.
Bio: Michaël Thomazo is an Inria researcher (chargé de recherche) within the Valda team of DI ENS, Paris. He got his PhD in 2013 from the University of Montpellier, working on conjunctive query answering under existential rules with Jean-François Baget and Marie-Laure Mugnier. He then joined TU Dresden as an Alexander von Humboldt fellow to work with Sebastian Rudolph.
