Algorithmes des Bases de Données
Responsables
Iovka Boneva, Pierre BouhrisVolume horaire
Cet enseignement est une option qui a lieu au second semestre du Master 1. Il est organisé sur 12 semaines, avec 1h30 de Cours TD et 2h de TP machine par semaine.
Cette option remplace l'option Administration des Bases de Données.
Crédits
5 ECTSdernière modification : 10/11/2015 à 13:48:46
Objectifs
À l'issue de ce cours, les étudiants devraient:- comprendre les difficultés pour assurer un accès efficace et fiable aux données dans une application;
- être capables d'apporter des solutions de gestion efficace des données, grâce à la connaissance des algorithmes fondamentaux mis en oeuvre dans les systèmes de gestion de bases de données.
Motivations
La gestion des données est un problème récurrent et majeur de l'informatique. Les bases de données relationnelles sont un succès retentissant pour faire face à ce problème et maintenant apparaissent très simples à utiliser, par exemple grâce aux systèmes comme MySQL. Toutefois, leur simplicitè apparente cache une technologie et des algorithmes avancés, sans lesquels cette efficacité serait impossible à atteindre.
Aujourd'hui, les données sont stockées de plus en plus dans des formats différents et les bases de données relationnelles n'apportent plus une solution universelle. Toutefois, les mêmes problématiques se posent : comment interroger efficacement des données, comment garder les données propres et correctes, et comment permettre la mise à jour des données simultanément par plusieurs utilisateurs dans un cadre asynchrone.
Les techniques développées pour les bases données relationnelles proposent des solutions efficaces à ces problèmes, et leur connaissance permet d'apporter des solutions efficaces au problème de gestion de données dans un cadre général.
Contenu
Nous allons nous intéresser plus particulièrement à ces aspects de la gestion données:Techniques pour l'évaluation et l'optimisation de requêtes
- Utilisation d'index: gains et coûts de l'utilisation d'un index, comment faire un index, algorithmes et structures de données pour l'indexation.
- Optimisation statique des requêtes: comment transformer une requête en une requête équivalente, mais dont l'évaluation est plus rapide.
Intégrité des données
- Transactions, ou comment garantir la correction des données lorsque plusieurs requêtes peuvent modifier ces données en parallèle.
- Contraintes: garantir les contraintes de manière efficace.
Organisation des enseignements
Pour chacun des sujets abordés, en Cours-TD nous allons introduire le problème, ainsi que quelques algorithmes et techniques classiques permettant d'attaquer ce problème. En TP, les étudiants devront implémenter leur propre solution dans le cadre d'un projet de semestre, en se basant sur les concepts vus en cours.
A l'issue des enseignements, les étudiants auront implémenté un mini système de gestion de bases de données. Il est à noter que nous fournirons des bibliothèques de manière à ce que les étudiants aient à implémenter uniquement les parties intéressantes d'un point de vue algorithmique, et qui sont en relation avec les concepts enseignés.
Les différentes implémentation pourront se comparer entre elles, en mesurant leur performance et efficacité dans un environnement contrôlé par les enseignants, et sur des benchmarks classiques de bases de données.
Le projet est à faire par groupe de 3-4 étudiants.
dernière modification : 10/11/2015 à 13:48:00
| Gpe | Nature | Horaire | Salle | Enseignant | |
|---|---|---|---|---|---|
| Cours | jeudi 13:30--15:00 | I. Boneva, P. Bourhis | iovka.boneva@univ-lille1.fr pierre.bourhis@univ-lille1.fr | ||
| 1 | TP | jeudi 15:15--17:15 | M5 A12 | P. Bourhis | pierre.bourhis@univ-lille1.fr |
| 2 | TP | jeudi 15:15--17:15 | M5 A13 | I. Boneva | iovka.boneva@univ-lille1.fr |
dernière modification : 09/11/2015 à 12:25:03
L'évaluation s'effectue suivant une procédure de contrôle continu. Quatre notes seront attribuées à chaque étudiant durant le semestre :
- Proj : note sur 20 qui évalue l'implémentation du projet. La même note sera attribuée à tous les étudiants dans un groupe de projet.
- CTP : note sur 20 de contrôle TP, qui s'effectuera en fin de semestre
- DS : note sur 20 d'un devoir surveillé en fin de semestre.
La note finale sur 20 (N) est calculée comme une moyenne pondérée de ces notes :
N = (2 * Proj + CTP + DS) /4
La session de rattrappage remplacera les notes CTP et DS.
L'unité acquise apporte 5 ECTS.
dernière modification : 10/11/2015 à 13:45:40
Les documents de cours seront disponibles sur la plateforme Moodle.
dernière modification :