Leonid Libkin (Université d'Edimbourg), lauréat 2019 de la chaire d'excellence de la FSMP, a effectué un séjour de trois mois à Paris à compter de septembre 2019, durant lequel il a collaboré avec les équipes de l'IRIF, du DI ENS et d'Inria.
Dans ce cadre, il a doné un cours intitulé A modern theory of database query languages.
Cliquez ici pour télécharger l'affiche.
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