Laboratoire d'informatique de l'École polytechnique

Talk by Louis Jachiet: «On the Optimization of Recursive Relational Queries»

Speaker: Louis Jachiet
Location: Room Flowers, Alan Turing building
Date: Fri, 11 Jan 2019, 14:00-15:00

Louis Jachiet will give a talk on Friday 11th January, at 2pm. The talk will take place in the Turing building, Inria Saclay, in the room Flowers.


The relational model has benefited from a huge body of research in the last half century. Since its introduction, the relational model has seen various attempts to extend it with recursion and it is now possible to use recursion in several SQL or Datalog database systems. The optimization of recursive queries remains, however, a challenge.

In this talk, we introduce μ-RA, a variation of the Relational Algebra that allows for the expression of relational queries with recursion. μ-RA can express unions of conjunctive regular path queries as well as certain non-regular properties. We present its syntax, semantics and the rewriting rules we specifically devised to tackle the optimization of recursive queries. We will also present our experiment to compare our prototype implementation of these rewriting rules with respect to state-of-the-art systems.