On the Real Expressive Power of Datalog Extensions

by Bruno Marnette

Abstract
Numerous extensions of the Datalog language have been introduced to address the lack of expressive power of traditional Datalog. In particular, equality constraints and value invention have proven convenient in the context Data Exchange and DL-like reasoning. Adding such constraints to the Datalog language however leads to intractability, and a great amount of work has aimed at identifying tractable islands, typically relying on syntactic properties (such as acyclicity or guardedness). In this talk we'll investigate whether the theoretic expressive power of these tractable extensions truly differ from standard Datalog (Spoiler alert: they don't).

Bio
Dr. Marnette is currently finishing my PhD in Oxford,  and he will soon be starting a post-doc at the INRIA Saclay, with Serge Abiteboul,  in the Webdam project.  He did his undergrad at the ENS Cachan, where he completed the MSc. in Computer Science MPRI in 2006.  He also studied at the EHESS where he completed the MSc. in Cognitive Science CogMaster in 2007.

More information