Logique, complexité descriptive et théorie des bases de données

Code APOGÉE : IFJCE350 | 6 ECTS | Coordinateur : Leonid Libkin | Validation : examen
Horaires hebdomadaires : 4h CM | Mutualisé avec : M2 MPRI

Titre en anglais : Querying Data: Foundations and Practice

Contexte

La théorie des bases de données a subi plusieurs transformations importantes qui sont rarement reflétées dans les cours, alors qu’elles ont déjà trouvé des applications dans la pratique des bases de données. Dans les années 1980 et 90, l’épine dorsale de la théorie des bases de données était la théorie des modèles finis, qui a maintenant été développée au point d’être une collection d’outils prêts à l’emploi qui peuvent être appliqués pour analyser la complexité et l’expressivité des langages de requête.

Les dernières décennies ont apporté trois nouvelles directions :

1. Au niveau purement théorique, un traitement uniforme de plusieurs domaines différents tels que les jointures relationnelles et les requêtes conjonctives et les données incomplètes via une riche théorie des homomorphismes de graphes.
2. Au niveau plus pratique, la théorie des algorithmes de jointure optimaux dans le pire des cas, qui sont passés des articles théoriques aux systèmes grand public en moins d’une décennie, et ont conduit à repenser certains principes sur lesquels les bases de données SQL sont construites.
3. Au niveau encore plus pratique, l’émergence des bases de données de graphes comme une nouvelle industrie clé, à la fois natives et représentées via relationnelles, toutes nécessitant une approche différente de la conception de langages.

Programme des cours

8 cours magistraux de 3 heures chacun. Le premier jour de cours est le 20 décembre. Le cours du 31 janvier sera en ligne car l’enseignant sera absent à une conférence.

1. Fondements des bases de données relationnelles : Logique du premier ordre, Algèbre relationnelle, théorème de Codd, Analyse statique (théorème de Trakhtenbrot).
2. Jointures et requêtes conjonctives ; homomorphismes de graphes ; évaluation, analyse statique, minimisation et cœurs de graphes.
3. Évaluation rapide de requêtes conjonctives : borne AGM et jointures optimales dans le pire des cas.
4. Expressivité et complexité des langages de requête : localité, loi zéro-un, bases de la complexité descriptive.
5. Programmation SQL (EN ZOOM)
6. Information incomplète : théorie et vie réelle.
7. Requêtage de graphes : théorie (RPQ et similaires), pratique (Cypher/GQL et SQL/PGQ).
8. Langages de requête relationnelle de nouvelle génération (Rel).

Documents

La source principale est Database Theory: Querying Data par Marcelo Arenas, Pablo Barceló, Leonid Libkin, Wim Martens, et Andreas Pieris. Le livre est quasi-terminé et librement disponible sur https://github.com/pdm-book/community.

Évaluation

Examens à emporter orientés recherche.

Prérequis

Techniquement parlant, juste une bonne formation générale en informatique, bien que ceci étant un cours de base de données de niveau Master couvrant de nouveaux sujets, il serait utile d’avoir une compréhension de base des classiques, par exemple la logique du premier ordre, l’algèbre relationnelle, quelques connaissances en SQL.

Bibliographie complémentaire

• Libkin, L. Elements of Finite Model Theory (librement disponible aux étudiants en classe)
• Hell, P. & Nešetril, J. Graphs and Homomorphisms
• Documentation SQL/Cypher/Rel librement disponible et guides