Curriculum LDD Informatique-Mathématiques

Projet : Bases de Données (S2)

Objectifs : Le but de ce projet est de réaliser un système de gestion de bases de données (SGBD dans la suite), capable d’exécuter des requêtes SQL, y compris des requêtes de création/modification de données, sur des données stockées sur disque. Le projet sera fait par groupe, chaque groupe réalisant une partie du système et devant s’interfacer avec les autres groupes.

Plan détaillé : Il sera demandé à chaque groupe d'implémenter un module. On décompose ici l'architecture d'un SGBD en quatre modules.

  • Un compilateur de SQL, qui fournit en sortie un arbre algébrique abstrait.
  • Un générateur de plan d'exécution prenant un arbre algébrique abstrait en entrée et construisant un plan d'exécution physique optimisé pour le modèle de coût des algorithmes de gestion de données.
  • Des algorithmes de gestion de données, utilisant le modèle physique de données et les indexes éventuels pour l'optimisation, et proposant un modèle de coût dépendant des statistiques des tables et de la présence d'indices.
  • Un module de stockage de données maintenant le modèle de données physique des tables, et des indexes, et exposant des méthodes d'accès aux données, ainsi que des statistiques sur les différentes tables.

Le projet est divisé en trois volets pour organiser la production de code et s'assurer d'une certaine synchronisation entre les groupes. On attend pour l'ensemble des rendus un bonne documentation du code, idéalement avec Ocamldoc.

  1. D'abord on construira des interfaces entre le code des différents groupes, avec un attention particulière au fait que ces interfaces permettent un certaine indépendance entre les groupes.
  2. Ensuite on proposera une implémentation naïve mais fonctionnelle, le but ici est que tous les groupes puissent se reposer sur une implémentation minimale des autres groupes dans la partie finale. On développera dans la séance suivante un jeu de tests des différentes parties et de l'architecture entière et on mettra en place de l'intégration continue sur git.
  3. La partie finale consiste en l'implémentation de primitives plus complexes et d'optimisations.

Références :

  • Abraham Silberschatz, Henry F Korth, Shashank Sudarshan et al. Database system concepts. T. 5. McGraw-Hill New York, 2002.
  • Georges Gardarin. Bases de données. Editions Eyrolles, 2003.