Les Bases de Données 13.00 / 20

Plan :

Table des matières
0.1 Données, Bases de données et SGBD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
0.2 Que doit-on savoir pour utiliser un SGBD ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
0.2.1 Définition du schéma de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
0.2.2 Les opérations sur les données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
0.2.3 Optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
0.2.4 Concurrence d’accès . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
0.3 Le plan du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
I Modèles et langages 13
1 Le modèle Entité/Association 15
1.1 Principes généraux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.1 Bons et mauvais schémas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.1.2 La bonne méthode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.2 Le modèle E/A : Présentation informelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3 Le modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.3.1 Entités, attributs et identifiants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.3.2 Associations binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.3 Entités faibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.3.4 Associations généralisées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.4 Avantage et inconvénients du modèle E/A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2 Le modèle relationnel 33
2.1 Définition d’un schéma relationnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2 Passage d’un schéma E/A à un schéma relationnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.2.1 Règles générales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.2.2 Retour sur le choix des identifiants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.2.3 Dénormalisation du modèle logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.3 Le langage de définition de données SQL2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.3.1 Types SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.3.2 Création des tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3.3 Contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.3.4 Modification du schéma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3 L’algèbre relationnelle 51
3.1 Les opérateurs de l’algèbre relationnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.1.1 La sélection, �� . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.1.2 La projection,


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.1.3 Le produit cartésien,

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.1.4 L’union,

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Philippe Rigaux (rigaux@lri.fr), Cours de bases de données, 2004
TABLE DES MATIÈRES 4
3.1.5 La différence,
��
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.1.6 Jointure,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2 Expression de requêtes avec l’algèbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2.1 Sélection généralisée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2.2 Requêtes conjonctives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2.3 Requêtes avec

et
��
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4 Le langage SQL 63
4.1 Requêtes simples SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.1.1 Sélections simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.1.2 La clause WHERE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.1.3 Valeurs nulles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2 Requêtes sur plusieurs tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2.1 Jointures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2.2 Union, intersection et différence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.3 Requêtes imbriquées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.3.1 Conditions portant sur des relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.3.2 Sous-requêtes correllées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.4 Agrégration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.4.1 Fonctions d’agrégation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.4.2 La clause GROUP BY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.4.3 La clause HAVING . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.5 Mises à jour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.5.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.5.2 Destruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.5.3 Modification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5 Schémas relationnels 77
5.1 Schémas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.1.1 Définition d‘un schéma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.1.2 Utilisateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.2 Contraintes et assertions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.3 Vues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.3.1 Création et interrogation d’une vue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.3.2 Mise à jour d’une vue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.4 Triggers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.4.1 Principes des triggers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.4.2 Syntaxe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6 Programmation avec SQL 87
6.1 Interfaçage avec le langage C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.1.1 Un exemple complet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.1.2 Développement en C/SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
6.1.3 Autres commandes SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
6.2 L’interface Java/JDBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
6.2.1 Principes de JDBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
6.2.2 Le plus simple des programmes JDBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.2.3 Exemple d’une applet avec JDBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
TABLE DES MATIÈRES 5
II Aspects systèmes 101
7 Techniques de stockage 103
7.1 Stockage de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.1.1 Supports . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.1.2 Fonctionnement d’un disque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
7.1.3 Optimisations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
7.1.4 Technologie RAID . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.2 Fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
7.2.1 Enregistrements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
7.2.2 Blocs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.2.3 Organisation d’un fichier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
7.3 Oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
7.3.1 Fichiers et blocs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.3.2 Les tablespaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
7.3.3 Création des tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
7.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
8 Indexation 129
8.1 Indexation de fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
8.1.1 Index non-dense . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
8.1.2 Index dense . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
8.1.3 Index multi-niveaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
8.2 L’arbre-B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
8.2.1 Présentation intuitive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
8.2.2 Recherches avec un arbre-B+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
8.3 Hachage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
8.3.1 Principes de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
8.3.2 Hachage extensible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
8.4 Les index bitmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
8.5 Indexation dans Oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
8.5.1 Arbres B+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
8.5.2 Arbres B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
8.5.3 Indexation de documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
8.5.4 Tables de hachage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
8.5.5 Index bitmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
9 Évaluation de requêtes 151
9.1 Introduction à l’optimisation des performances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
9.1.1 Opérations exprimées par SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
9.1.2 Traitement d’une requête . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
9.1.3 Mesure de l’efficacité des opérations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
9.1.4 Organisation du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
9.2 Algorithmes de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
9.2.1 Recherche dans un fichier (sélection) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
9.2.2 Quand doit-on utiliser un index ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
9.2.3 Le tri externe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
9.3 Algorithmes de jointure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
9.3.1 Jointure par boucles imbriquées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
9.3.2 Jointure par tri-fusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
9.3.3 Jointure par hachage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
9.3.4 Jointure avec un index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
9.3.5 Jointure avec deux index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
9.4 Compilation d’une requête et optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
Philippe Rigaux (rigaux@lri.fr), Cours de bases de données, 2004
TABLE DES MATIÈRES 6
9.4.1 Décomposition en bloc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
9.4.2 Traduction et réécriture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
9.4.3 Plans d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
9.4.4 Modèles de coût . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
9.4.5 Pipelinage ou matérialisation des résultats intermédiaires . . . . . . . . . . . . . . . . . . . . 181
9.5 Oracle, optimisation et évaluation des requêtes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
9.5.1 L’optimiseur d’ORACLE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
9.5.2 Plans d’exécution ORACLE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
9.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
9.6.1 Opérateurs d’accès aux données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
9.6.2 Algorithmes de jointure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
9.6.3 Plans d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
9.6.4 Plans d’exécution ORACLE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
9.6.5 Utilisation de EXPLAIN et de TKPROF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
9.6.6 Exercices d’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
10 Introduction à la concurrence d’accès 199
10.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
10.1.1 Exécutions concurrentes : sérialisabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
10.1.2 Transaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
10.1.3 Exécutions concurrentes : recouvrabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
10.2 Contrôle de concurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
10.2.1 Verrouillage à deux phases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
10.2.2 Contrôle par estampillage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
10.3 Gestion des transactions en SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
10.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
A Travaux pratiques 211
A.1 Interrogation avec SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
A.1.1 Sélections simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
A.1.2 Jointures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
A.1.3 Requêtes imbriquées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
A.1.4 Négation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
A.1.5 Fonctions de groupe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
A.2 Création d’un schéma relationnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
A.2.1 Création des tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
A.2.2 Insertion de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
A.2.3 Vues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
A.3 Programmation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
A.3.1 Procédures stockées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
A.3.2 Triggers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
A.3.3 Applications externes : PHP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
A.4 Concurrence d’accès . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218