3.3 Algèbre relationnelle - Irif

Correction : 1. Les clefs primaires : Auteur : CODE_AUTEUR.

Part of the document

CPGEINFORMATIQUECOMMUNEIntroduction aux
Bases de Données
RelationnellesSerge Abiteboul
Inria, ENS Cachan, Conseil national du numérique
serge.abiteboul@inria.fr
Benjamin Nguyen
Université de Versailles St-Quentin-en-Yvelines, Inria
benjamin.nguyen@uvsq.fr
Yannick Le Bras
Mathématiques MPSI, Lycée Montesquieu, Le Mans
yannick.le-bras@prepas.org
2
Logic is the beginning of wisdom, not the end.
Mr. Spock, Star Trek
3
4
Table des matières
1 Introduction7
1.1 Les principes et l"architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.2 Le calcul et l"algèbre relationnels . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.3 L"optimisation de requête†. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11
1.4 Les transactions‡. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13
1.5 Conception d"une Base de Données‡. . . . . . . . . . . . . . . . . . . . . . . . .14
1.6 Notions du programme officiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2 Le Calcul Relationnel 17
2.1 Objectif du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.2 Concepts des Bases de Données . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.2.1 Définitions et Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.3 Calcul conjonctif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.3.1 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.3.2 Formules bien-formées du calcul conjonctif . . . . . . . . . . . . . . . . . .
20
2.3.3 Exercices corrigé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
2.4 Calcul relationnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
2.4.1 Formules bien-formées du calcul relationnel . . . . . . . . . . . . . . . . .
23
2.4.2 Exercices corrigés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.4.3 Pour aller plus loin‡. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24
3 L"Algèbre Relationnelle 27
3.1 Objectif du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.2 Algèbre conjonctive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.3 Algèbre relationnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.4 Théorème d"Equivalence de Codd . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
4 SQL et Requêtes Agrégat 33
4.0.1 Objectif du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.1 Le langage de définition de données . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.2 Le langage de manipulation de données . . . . . . . . . . . . . . . . . . . . . . .
35
4.3 L"interrogation des données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
4.3.1 La syntaxe SQL duSELECT, FROM, WHERE. . . . . . . . . . . . . . .36
4.3.2 Traduction en calcul relationnel . . . . . . . . . . . . . . . . . . . . . . . .
37
4.3.3 Traduction en algèbre relationnelle . . . . . . . . . . . . . . . . . . . . . .
37
4.3.4 Exemple de requêtes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
4.4 Requêtes agrégats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
4.5 Requêtes ensemblistes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
4.6 Tri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
5
TABLE DES MATIÈRES
5 Exercices41
5.1 Objectif du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
5.2 Activités du Programme Officiel . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
5.2.1 Installation du SGBDMySQL, du serveur webApache, de l"application
PHPMyAdminet de la BDbanque-simple. . . . . . . . . . . . . . . . . .42
5.2.2 De la présentation des exercices . . . . . . . . . . . . . . . . . . . . . . . .
47
5.2.3 Méthodologie pour répondre à une question . . . . . . . . . . . . . . . . .
48
5.2.4 Requêtes sur une base de données existante . . . . . . . . . . . . . . . . .
49
5.3 Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
5.4 Exercices hors programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
6
1Introduction
Nous allons parler de systèmes informatiques qui nous aident à gérer des données. Nous avons
donc, d"un côté, un serveur de données quelque part sur la Toile, avec des disques magnétiques
1et
leurs pistes qui gardent précieusement des séquences de bits, des structures d"accès compliquées
comme des index ou des arbres-B, des hiérarchies de mémoires avec leurs caches et, de l"autre,
un utilisateur. Supposons que le serveur soit celui d"IMDb qui gère une base de données sur le
cinéma. Supposons que l"utilisateur, disons Alice, veuille savoir quels films ont été réalisés par
Alfred Hitchcock. Pour ce faire, elle spécifie des mots-clés ou remplit les champs d"un formulaire
proposé par IMDb. Sa question voyage depuis son navigateur jusqu"au serveur de données. Là,
cette question est transformée en un programme peut-être complexe qui s"exécute pour obtenir
la réponse. Ce qui est important : ce programme, Alice n"a pas envie de l"écrire; elle n"a pas à
l"écrire.
Le système élémentaire qui permet de gérer des données est un système de fichiers. Un fichier
est une séquence de bits qui peut représenter une chanson, une photo, une vidéo, un courriel, une
lettre, un roman, etc. Votre ordinateur personnel et votre téléphone stockent leurs données dans
des systèmes de fichiers. Et parfois quand vous ne savez plus où vous avez mis quelque chose, vous
faites desrecherchesdans ces système de fichiers. C"est rudimentaire. Un moteur de recherche
de la Toile ne fait pas autre chose, seulement il le fait sur un système de fichiers à l"échelle de la
planète. Dans ce chapitre, nous parlerons de systèmes qui gèrent aussi des données mais qui sont
bien plus sophistiqués que les systèmes de fichiers : les systèmes de gestion de bases de données.
Ce sont des logiciels complexes, résultats de dizaines d"années de recherche et de développement.
Ils permettent à des individus ou des programmes d"exprimer des requêtes pour interroger des
bases de données ou pour les modifier. Nous nous focaliserons ici sur les plus répandus d"entre
ces systèmes, les systèmes relationnels, parmi lesquels nous trouvons des logiciels commerciaux
très répandus comme celui d"Oracle et des logiciels libres très utilisés comme MySQL.
Dans ce livre, nous couvrons le programme des classes préparatoires scientifiques, toutefois
il nous est paru indispensable d"aller au delà d"une interprétation stricte du programme, pour
permettre au lecteur de comprendre les fondements de la théorie des bases de données, sans
laquelle il ne serait qu"un simple utilisateur de SGBD. Nous indiquons les éléments qui sont à
la limite du programme par la notation†, et ceux qui sont au delà par la notation‡.
1.1
Les princip eset l"arc hitecture
Au fil des ans, trois grands principes ont émergé qui ont façonné le domaine de la gestion de
données :
-
Abstraction : Un système de gestion de bases de données sert de médiateur en tredes 1. À l"heure actuelle, un nombre croissant de serveurs utilisent désormais des disques basés sur de la mémoire
Flash, appelés Solid State Drive (SSD). Les travaux historiques sur les systèmes de gestion des bases de donnés font
l"hypothèse de l"utilisation de disques magnétiques. L"optimisation des SGBD aux disques SSD est du domaine
de la recherche actuel (voir [?]).
7
1CHAPITRE 1. INTRODUCTION
SalSe Titr="iHyiPHooS0lo»HFTmo»TiHmoooSslo,amiohiohFttuimooooooooooooohatmo imotPa8imooFigure1.1-Arc hitecturesprincipales
individus et des machines. Pour mieux s"adapter aux individus, il doit organiser et présenter
les données de façon intuitive et permettre de les manipuler en restant à un niveau abstrait
sans avoir à considérer des détails d"implémentation.
-
Indép endance: nous distinguons trois niv eaux,ph ysique,logique et externe, que l"on es-
saie de rendre le plus indépendants possible. Au niveau externe, nous trouvons les vues
d"utilisateurs particuliers qui partagent la base de données. Chaque vue est adaptée aux
besoins de l"utilisateur. Au niveau logique, nous trouvons une organisation unique des don-
nées typiquement dans le modèle relationnel que nous détaillons plus loin. Et au niveau
physique, les détails de l"organisation sur disque et de structures comme des index dont
le rôle est d"accélérer les calculs. Le but est de pouvoir modifier un niveau (par exemple,
ajouter un nouvel utilisateur avec de nouveaux besoins) sans modifier les autres niveaux.
-
Univ ersalité: Ces systèmes visen tà capturer toutes les données d"un een treprise,d"un
groupe, d"une organisation quelconque, pour tout type d"applications. Il leur faut donc
offrir des langages de développement d"applications puissants et une gamme de fonction-
nalités très riche. Des limites de cette universalité existent aujourd"hui pour les systèmes
relationnels : énormément de données moins structurées sont par exemple gérées dans des
systèmes de fichiers.
Mentionnons brièvement les architectures les plus répandues de systèmes de gestion de don-
nées. Voir Figure??. Une première architecture est celle des systèmes client/serveur. La base de
données est gérée sur un serveur. L"application tourne sur une autre machine, le client. De plus
en plus, cette architecture se complique avec l"introduction d"un troisième "tiers" (ce qui signifie
en réalité "niveau" en anglais), une machine qui gère l"interface, typiquement un navigateur Web
sur une tablette ou un laptop.
Nous pouvons noter différentes évolutions générées par des améliorations dans les matériels
disponibles :
-
l"accroissemen tdes p erformancesnotammen tfondées sur les mémoires viv esde plus en
plus massives, et des mémoires flash encore plus massives;