Leonid Libkin - 2019

Leonid Libkin (University of Edinburgh), 2019 laureate of the FSMP Research Chair, is spending six months in Paris from September 2019, during which he is collaborating with the IRIF, DI ENS and Inria teams.

In this context, he will give a course of 7 sessions of 1h30 entitled A modern theory of database query languages.
The sessions will take place in room 3052 of the Sophie Germain Building, Université Paris-Diderot (1, place Auréie Nemours, 75013 Paris).

Click here to download the poster.






Schedule of the course

- September 30th 2019 from 10:30 to 12:00
- Octobre 4th 2019 from 10:30 to 12:00
- Octobre 7th 2019 from 10:30 to 12:00
- Octobre 11th 2019 from 10:30 to 12:00
- Octobre 14th 2019 from 10:30 to 12:00
- Octobre 18th 2019 from 10:30 to 12:00
- Octobre 21st 2019 from 10:30 to 12:00

Abstract of the course

A modern theory of database query languages
This short course presents a modern perspective on database query languages over complete and incomplete data. From the mathematical point of view, queries are mappings between finite relational structures (e.g., graphs), usually defined in logical languages such as first-order predicate logic. While this is the standard presentation, these days the theory of graph homomorphisms plays a prominent role in understanding query languages. In this short course, we mix and blend the logical and graph homomorphism views of query languages, showing how it leads to new and often simpler ways of proving classical results and deriving new ones.

Topics

1. Finite structures, logical and procedural query languages

2. Basics of graph and relational structures homomorphisms

3. Conjunctive queries:

  • 3a: evaluation, containment, preservation
  • 3b: complexity and approximation

4. Building up expressive power:

  • 4a: unions of conjunctive queries, preservation theorem
  • 4b: adding negation: inexpressibility of counting via 0/1 laws
  • 4b: adding counting: inexpressibility of recursion via locality

5. Handling incomplete information:

  • 5a: exact evaluation and homomorphism preservation
  • 5b: certain answers and the lattice of cores
  • 5c: approximations and 0/1 laws