Leonid Libkin - 2019

Recevez la lettre d'information

Télécharger la lettre d'information


Leonid Libkin
(Université d'Edimbourg), lauréat 2019 de la chaire d'excellence de la FSMP, effectue un séjour de six mois à Paris à dater de septembre 2019, durant lequel il collabore avec les équipes de l'IRIF, du DI ENS et d'Inria.

Dans ce cadre, il donnera un cours de 7 séances d'1h30 intitulé A modern theory of database query languages.
Les séances se tiendront en salle 3052 du Bâtiment Sophie Germain, Université Paris-Diderot (1, place Auréie Nemours, 75013 Paris).

Cliquez ici pour télécharger l'affiche.






Calendrier du cours

Le cours aura lieu les :
- 30 septembre 2019 de 10h30 à 12h
- 4 octobre 2019 de 10h30 à 12h
- 7 octobre 2019 de 10h30 à 12h
- 11 octobre 2019 de 10h30 à 12h
- 14 octobre 2019 de 10h30 à 12h
- 18 octobre 2019 de 10h30 à 12h
- 21 octobre 2019 de 10h30 à 12h

Résumé du cours

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.

Thèmes abordés

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