Cours SGBD : introduction aux differents types

Cours SGBD pdf : introduction aux différents types
...
Table des matie`res
- Concepts fondamentaux 1
- Introduction ... 2
- Un vieux problème : la bibliothèque de Leibniz........ 2
- Données, bases de données et SGBD....... 2
- Un exemple : BD sur l’INA-PG... 3
- Quelles compétences pour utiliser un SGBD ?... 3
- Définition du schéma de données...... 4
- Les opérations sur les données... 4
- Optimisation........ 5
- Concurrence d’accès......... 5
- Caractéristiques de l’approche base de données....... 5
- Architecture des SGBD et indépendance des données... 5
- Persistance des données......... 6
- Langage de requête.... 6
- Partage des données......... 6
- Fiabilité des données........ 6
- Sécurité des données......... 6
- Le contexte..... 6
- Pourquoi une Base de Données ?........ 6
- Où trouve-ton des BD....... 6
- Applications récentes et à venir......... 6
- Avantages liés à l’utilisation d’un SGBD.... 6
- Les acteurs en jeu dans l’usage de SGBD..... 6
- Historique des SGBD et types de SGBD....... 6
- Objectifs du cours....... 8
- Introduction ... 2
- Modèle abstrait des bases de données 9
- Introduction : modélisation des données...... 9
- Généralités sur la conception d’une Base de Données... 9
- Problèmes d’une conception sans précautions....... 10
- Introduction à une bonne méthode........ 11
- Le modèle entité-association (E/A)....... 11
- Présentation informelle........ 12
- Le modèle 13
- Avantages et inconvénients du modèle E/A..... 13
- Langages de bases de données 15
- Le modèle relationnel et ses règles......... 15
- Un peu d’histoire..... 16
- Les notions de base......... 16
- Bases théoriques des langages relationnels : l’algèbre relationnelle..... 18
- Une manipulation ensembliste des données..... 18
- Les opérateurs de l’algèbre relationnelle..... 19
- Expressions de requêtes avec l’algèbre......... 23
- Conclusions 23
- Bien concevoir une base de données..... 23
- Les dépendances fonctionnelles...... 25
- Décomposition en formes normales...... 29
- Les contraintes d’intégrité structurelles...... 31
- Passage d’un schéma E/A à un schéma relationnel.... 31
- Le langage relationnel SQL........ 31
- Les langages relationnels complets........ 31
- Le langage SQL : historique....... 32
- Le DML : Data Manipulation Language en SQL... 33
- Le DDL (Data Description Language) en SQL........ 48
4 Pratique des SGBD 53
- Exemples de SGBD........ 54
- Perspectives historiques....... 54
- ORACLE 54
- Microsoft Access....... 54
- Techniques d’optimisation........ 54
- Techniques d’accès partagés : le contrôle de concurrence........ 54
- Problèmes potentiels et notions de base...... 54
- Techniques de contrôle de concurrence....... 62
- La gestion des transactions en SQL...... 65
- Le contrôle de concurrence sous Oracle....... 67
- Techniques de récupération d’erreur.... 69
- Les mécanismes utilisés....... 69
- Les bancs de mesure des performances ("benchmarks")... 71
- Sécurité et autorisations....... 73
- L’interface C/SQL... 73
- Un exemple complet...... 74
- Autres commandes SQL...... 78
- Les environnements de programmation d’applications sur les bases de données...... 79
- La "programmation visuelle".... 79
- Langages de quatrième génération......... 80
- Les interfaces au standard SQL et la portabilité.... 80
- Les ateliers de génie logiciel (AGL / CASE)..... 81
5 Réalisation physique des bases de données 83
- Introduction........ 84
- Techniques de stockage....... 84
- Stockage de données....... 84
- Organisation des fichiers..... 85
- Organisation primaire des fichiers......... 86
- L’exemple du SGBD Oracle....... 87
- Structures de données pour optimiser les accès..... 87
- Indexation de fichiers.... 87
- Hachage........ 93
- L’arbre-B....... 97
- Autres méthodes d’indexation....... 100
- Bilan...... 101
- Comparaison... 101
- Quelques règles....... 101
- Indexation dans Oracle...... 101
- Index en SQL... 101
- Structures de données multidimensionnelles........ 105
- Évaluation des requêtes..... 105
- Introduction à l’optimisation des performances......... 105
- Algorithmes de base.... 105
- Algorithmes de jointure..... 105
- Compilation d’une requête et optimisation.... 106
- Oracle : optimisation et évaluation des requêtes......... 106
- Vision globale sur l’exécution d’une requête SQL....... 106
- Optimisation de l’accès à une table.... 106
6 Perspectives des SGBD 107
- Nouveaux modèles de données pour nouvelles applications......... 107
- Bases de données réparties...... 107
- Motivations 108
- Fragmentation d’une BD... 108
- Les problèmes spécifiques........ 108
- Transaction répartie..... 109
- Bases de données déductives... 109
- Entrepôts de données et fouille de données..... 109
- Perspectives historiques..... 109
Bibliographie 111
Index 113
Concepts fondamentaux
Sommaire
-
Introduction........ 2
- Un vieux problème : la bibliothèque de Leibniz..... 2
- Données, bases de données et SGBD...... 2
- Un exemple : BD sur l’INA-PG......... 3
-
Quelles compétences pour utiliser un SGBD ?..... 3
- Définition du schéma de données... 4
- Les opérations sur les données........ 4
- Optimisation...... 5
- Concurrence d’accès....... 5
-
Caractéristiques de l’approche base de données... 5
- Architecture des SGBD et indépendance des données.... 5
- Persistance des données....... 6
- Langage de requête........ 6
- Partage des données...... 6
- Fiabilité des données..... 6
- Sécurité des données...... 6
-
Le contexte... 6
- Pourquoi une Base de Données ?..... 6
- Où trouve-ton des BD.... 6
- Applications récentes et à venir....... 6
- Avantages liés à l’utilisation d’un SGBD..... 6
- Les acteurs en jeu dans l’usage de SGBD..... 6
- Historique des SGBD et types de SGBD....... 6
- Objectifs du cours...... 8
1. Introduction
1.1 Un vieux problème : la bibliothèque de Leibniz
- Données, bases de données et SGBD
Une donnée est une information quelconque, comme, par exemple, « voici une personne, elle s’appelle Antoine ». C’est aussi une relation entre des informations. Par exemple : « Antoine enseigne les bases
de données ». Des relations de ce genre définissent des structures.
Une base de données est un ensemble, en général volumineux, de telles informations, avec la caractéristique essentielle que l’on cherche à les mémoriser de manière permanente.
Déftnition 1.1 (Base de données)
Une base de données est un gros ensemble d’informations structurées mémorisées sur un support per- manent qui peut être partagée par plusieurs applications et qui est interrrogeable par le contenu.
L’utilisation de fichiers classiques pourrait sembler pouvoir apporter une solution à ce problème. Mais l’utilisation directe de gros fichiers soulève de gros problèmes :
- Lourdeur d’accès aux données. En pratique, pour chaque accès aux données, même le plus simple, il faudrait écrire un programme.
- Manque de sécurité. Si tout programmeur peut accéder directement aux fichiers, il est impossible de garantir la sécurité et l’intégrité des données.
- Pas de contrôle de concurrence. Dans un environnement dans lequel plusieurs utilisateurs accèdent aux mêmes données, des problèmes de concurrence d’accès se posent.
Il est donc nécessaire d’avoir recours à un logiciel chargé de gérer les fichiers constituant une base de données, de prendre en charge les fonctionnalités de protection et de sécurité et de fournir les différents types d’interfaces nécessaires à l’accès aux données. Ce logiciel (le SGDB) est très complexe.
Déftnition 1.2 (Système de Gestion de Bases de Données (SGBD))
Un Système de Gestion de Bases de Données (SGBD) est un logiciel de haut niveau permettant aux utilisateurs de structurer, d’insérer, de modifier, de rechercher de manière efficace des données spécifiques, au sein d’une grande quantité d’informations, stockées sur mémoires secondaires partagée de manière transparente par plusieurs utilisateurs.
Plus précisément, les systèmes de gestion de bases de données (SGBD) sont des programmes permettant à l’utilsateur de créer et de gérer des bases de données. les SGBD sont des logiciels à usage général qui assurent les processus de définition, de construction, de manipulation et de partage des bases de données par et entre les différents utilisateurs et applications.
La déftnition d’une base de données implique une spécification des types de données, des structures et des contraintes. La construction d’une base de données consiste à enregistrer les données proprement dites sur un support de stockage contrôlé par le SGBD. La manipulation de la base consiste notamment à l’interroger afin d’en extraire des informations, à l’actualiser en fonction des modifications du microcosme considéré et à générer des rapports. Le partage d’une base de données permet à différents utilsateurs et applications d’y accéder simultanément.
Les SGBD assurent d’autres fonctions importantes, notamment la protection de la base de données et son
/em entretien à long terme. La protection implique à la fois la protection du système contre les pannes logicielles et matérielles et la protection sécuritaire conre les accès illicites ou malveillants. Une grande base de données peut être utilisées de nombreuses années. Le SGBD doit donc être capable d’entretenir et de faire évoluer ses propres structures dans la durée.
La complexité d’un SGBD tient essentiellement à la diversité des techniques mises en œuvre, à la multi- plicité des composants intervenant dans son architecture, et aux différents types d’utilisateurs (adminis-
Chapitre 1 3
trateurs, programmeurs, utilisateurs non informaticiens, ...) qui sont confrontés, à différents niveaux, au système.
Ainsi, dans ce cours, seront abordés :

- Les modèles de données : entité-relation (mais pas les modèles en réseaux, hiérarchiques, relationnels, orientés objets, sémantiques).
- Les langage de requête, incluant leurs fondements théoriques et les langages comme SQL.
- Les techniques de stockage.
- L’organisation des fichiers : index, arbre-B, hachage, ...
- L’architecture : centralisée, distribuée, sur d’autres bases accessibles par réseau.
- Les techniques d’évaluation et d’optimisation de requêtes.
- La concurrence d’accès et les techniques de reprise sur panne.
Ces fonctions sont remplies par trois niveaux, théoriquement distincts, d’un SGBD :
- Le niveau physique : gestion sur mémoire secondaire (fichiers) des données, du schéma, des index ; Partage de données et gestion de la concurrence d’accès ; reprise sur pannes (fiabilité) ; Distribution des données et interopérabilité (accès aux réseaux).
- Le niveau logique : Définition de la structure des données : Langage de Description des Don- nées (LDD) ; Consultation et Mise à Jour des données : Langage de Requête (LR) et Langage de Manipulation de Données (LMD) ; Gestion de la confidentialité (sécurité) ; Maintien de l’intégrité.
- Le niveau externe : Vues ; Environnement de programmation (intégration avec un langage de programmation) ; Interfaces conviviales et Langage de 4ème Génération (L4G) ; Outils d’aides (e.g. conception de schémas) ; Outils de saisie, d’impression d’états.
En résumé, un SGBD est destiné à gérer un gros volume d’informations, persistantes, fiables (protection sur pannes), partageables entre plusieurs utilisateurs et/ou programmes manipulés indépendamment de leur représentation physique.
Nous avons introduit un certain nombre de termes et de sigles. Nous allons progressivement en apprendre le sens.
1.3 Un exemple : BD sur l’INA-PG
- Qu’est-ce qu’on veut faire ?
- Quelles données sont utiles ?
- Quels types de requêtes ?
- Quelles mises à jour ?
- Quels acteurs ?
- Concurrence
- Redondance et incohérence
- Quelle sécurité ?
1.3.1 Questions essentielles
- Comment concevoir une BD ?
- Comment optimiser sa conception ?
- Comment optimiser son fonctionnement ?
- Comment assurer la concurrence ?
- Comment assurer la sécurité ?
2. Quelles compétences pour utiliser un SGBD ?
L’utilisation d’un SGBD suppose de comprendre et de savoir utiliser les fonctionnalités suivantes :
- Définition du schéma de données en utilisant les modèles de données du
4 2 Quelles compétences pour utiliser un SGBD ?
- Opérations sur les données : recherches, mises-à-jour,
- Partager les données entre plusieurs utilisateurs (mécanismes de transaction).
- Optimiser les performances par le réglage de l’organisation physique des données. cet aspect relève plutôt de l’administrateur de données.
En reprenant ces différents points.
2.1 Déftnition du schéma de données
Un schéma est simplement la description des données contenues dans la base. Cette description est conforme à un modèle de données qui propose des outils de description (structures, contraintes et opé- rations). Dans un SGBD, il existe plusieurs modèles plus ou moins abstraits des mêmes objets. Par exemple :
- Le modèle conceptuel : la description du système d’information
- Le modèle logique : réglant l’interface avec le SGBD
- Le modèle physique : les fichiers.
Ces différents modèles correspondent aux niveaux de l’architecture d’un SGBD. Prenons l’exemple du modèle conceptuel le plus courant : le modèle Entité/Association. C’est essentiellement une description très abstraite décrivant :
- l’analyse du monde réel telle que pertinente pour l’utilisation
- la conception du système d’information
- la communication entre différents acteurs de l’entreprise.
En revanche, il ne propose pas d’opérations. Or définir des structures sans disposer d’opérations pour agir sur les données stockées dans ces structures ne présente pas d’intérêt pratique pour un SGBD. D’où, à un niveau inférieur, des modèles dits « logiques » qui proposent :
- Un langage de définition de données (LDD) pour décrire la structure, incluant les
- Un langage de manipulation de données (LMD) pour appliquer des opérations aux données.
Ces langages sont abstraits. le LDD est indépendant de la représentation physique des données, et le LMD est indépendant de l’implantation des opérations. On peut citer une troisième caractéristique : outre les structures et les opérations, un modèle logique doit permetre d’exprimer des contraintes d’intégrité sur les données.
Exemple
nom character 15, not null ; âge integer between 0 and 120 ; débit = crédit ;
...
Bien entendu, le SGBD doit être capable de garantir le respect de ces contraintes.
Quand on conçoit une application pour une BD, on tient compte de cette architecture en plusieurs niveaux. Typiquement : (1) on décide la structure logique, (2) on décide la structure physique, (3) on écrit les programmes d’application en utilisant la structure logique, enfin (4à le SGBD se charge de transcrire les commandes du LMD en instructions appliquées à la représentation physique.
Cette approche offre de très grands avantages. Tout d’abord elle ouvre l’utilisation des SGBD à des utilisateurs non-experts : les langages proposés par les modèles logiques sont plus simples, et donc plus accessibles, que les outils de gestion de fichiers. Ensuite, on obtient une caractéristique essentielle : l’indé- pendance physique. On peut modifier l’implantation physique sans modifier les programmes d’application. Un concept voisin est celui d’indépendance logique : on peut modifier les programmes d’application sans toucher à l’implantation.
Enfin le SGBD décharge l’utilisateur, et en grande partie l’administrateur, de la lourde tâche de contrôler la sécurité et l’intégrité des données.
2.2 Les opérations sur les données
Il existe 4 opérations classiques (ou requêtes :

Chapitre 1 Concepts fondamentaux 5
- La création (ou insertion)
- La modification (ou mise-à-jour)
- La destruction
- La recherche
Ces opérations correspondent à des commandes du LMD. La plus complexe est la recherche en raison de la variété des critères.
Pour l’utilisateur, une bonne requête a les caractéristiques suivantes. Tout d’abord, elle s’exprime fa- cilement : l’idéal serait de pouvoir utiliser le langage naturel, mais celui-ci présente trop d’ambiguïtés. Ensuite, le langage ne devrait pas demander d’expertise technique (syntaxe compliquée, structure de données, implantation particulière ...). Il est également souhaitable de ne pas attendre trop longtemps (à charge pour le SGBD de fournir des performances acceptables). Enfin, et peut-être surtout, la réponse doit être fiable.
Une bonne partie du travail sur les SGBD consiste à satisfaire ces besoins. le résultat est ce que l’on appelle un langage de requêtes, et constitue à la fois un sujet majeur d’étude et une caractéristique essentielle de chaque SGBD. le langage le plus répandu à l’heure actuelle est SQL.
2.3 Optimisation
L’optimisation (d’une requête) s’appuie sur l’organisation physique des données. les principaux types d’organisation sont les fichiers séquentiels, les index (denses, secondaires, arbres B) et le regroupement des données par hachage.
Un module particulier du SGBD, l’optimiseur, tient compte de cette organisation et des caractéristiques de la requête pour choisir le meilleur séquencement des opérations.
2.4 Concurrence d’accès
Plusieurs utilisateurs doivent pouvoir accéder en même temps aux mêmes données. Le SGBD doit savoir :
- Gérer les conflits si ces utilisateurs font simultanément des mises-à-jour.
- Offrir un mécanisme de retour arrière si on décide d’annuler des modifications en cours.
- Donner une image cohérente des données sur l’un fait des requêtes et un autre des mises-à-jour. Le but est d’éviter des blocages tout en empêchant des modifications anarchiques.
3. Caractéristiques de l’approche base de données
- Abstraction des données : requêtes en termes presque en langage naturel
- Notion de vues
3.1 Architecture des SGBD et indépendance des données
Architecture en trois schémas
6 4 Le contexte
3.2 Persistance des données
- Langage de requête
- Partage des données
- Fiabilité des données
- Sécurité des données
4. Le contexte
- Pourquoi une Base de Données ?
- Intégration de données
- Moins de duplications
- Partage de données
- Fiabilité de données
- Transactions, Reprises sur pannes, Tolérance de pannes
- Sécurité de données
- Langages assertionnels de requêtes
- SQL, QBE
- Interfaces conviviales
- 4-GL & Web
4.2 Où trouve-ton des BD
4.2.1 Types de BDs
- BDs personnelles
- MsAccess etc.
– 10 KO – 100 KO
- BDs professionnelles typiques 100 KO – 100 GO
- BDs professionnelles très grandes
- Very Large Databases (VLDB)
– > 100 GO
4.3 Applications récentes et à venir
4.4 Avantages liés à l’utilisation d’un SGBD
4.5 Les acteurs en jeu dans l’usage de SGBD
4.6 Historique des SGBD et types de SGBD
4.6.1 Historique
Moteur : évolution des modèles de données, elle-même motivée par l’évolution des besoins.
- 1ère génération 1950 – 65
- SGF, SGF généralisés avec les langages booléens de manip.
- 2ème génération 1965 - 70
- SGBD navigationnel
- Hierarchique (IMS), Réseau (Codasyl), Pseudo-relationnel
- 3ème génération 1969 - . . .
Chapitre 1 Concepts fondamentaux 7
- SGBD relationnel (DB2, Oracle, Informix, MsAcess. . .
- SGBD OO 1990 - 1999
- En pratique : une impasse (O2, Objectstore, Objectivity..)
- SGBD relationnel – objet (RO) 1993 - . . .
- Évolution probable de tout SGBD relationnel
Il faut donc distinguer entre modèles conceptuels, /em a priori indépendants des SGBD, et /em modèles logiques, caractéristiques d’une génération de SGBD. Ces modèles logiques sont eux-mêmes dépendants d’organisations physiques (placement et méthodes d’accès) comme, par exemple, les graphes en arbres ou en réseaux, seules structures offertes par la première génération de SGBD, celle des modèles naviga- tionnels, hiérarchique et réseau.
Ces SGBD obligeaient à "voir" - c’est à dire à traduire - une base de données comme un ensemble d’enregistrements, reliés les uns aux autres par des ensembles de pointeurs. Cette organisation fige les relations existant entre les différents enregistrements de la base et impose un type de manipulation, la navigation, qui consiste à suivre, d’enregistrement en enregistrement, les chaînes de pointeurs. En fait, il serait préférable de parler de modèles d’accès (physiques) plutôt que de modèles de données (logiques) pour ces anciens SGBD. En effet leur organisation physique des données imposait la méthode d’accès et, au delà, la nature des langages de manipulation.
4.6.2 Le modèle hiérarchique
Longtemps considéré comme le seul modèle permettant aux SGBD d’atteindre les performances exigées en production, le modèle hiérarchique possède effectivement la capacité de traiter rapidement des in- formations organisées sous la forme d’une hiérarchie stricte mais, par contre, interdit tout autre type de représentation, limitant ainsi considérablement la puissance d’expression du modèle. Le SGBD le plus connu dans cette catégorie est IMS, produit ancien de IBM, très répandu dans les applications de production.
4.6.3 Le modèle réseau
Ce modèle a été introduit en 1961 par BACHMAN. Il propose une utilisation de structures de listes afin de relier sémantiquement des entités. Il permet ainsi une meilleure représentation de la réalité que le modèle hierarchique. Un des intérêts du modèle fut l’existence d’une proposition de normalisation émise par le groupe DBTG (Data Base Task Group) du Comité CODASYL (COnference on DAta SYstem Language). On parle ainsi souvent de modèle CODASYL pour les systèmes réseaux qui suivent ces recommandations. Deux niveaux de recommandations ont été émis : l’un, en 1971, conseillait la séparation d’un niveau de schéma externe et d’un niveau de schéma interne/conceptuel ; le second, en 1978, préconisait les trois niveaux de schéma -interne, conceptuel, externe-. Seul le premier niveau de recommandations a été réellement suivi par les produits. En 1978, il était déjà tard pour voir les produits prendre en compte ces recommandations : l’heure du relationnel avait déjà sonné pour les investissements à long terme ; quasiment aucun SGBD réseau réellement nouveau n’a été conçu depuis cette date. Mais à l’heure où les SGBD relationnels sont à leur tour défiés par les nouveaux SGBD orientés objets, il est encore intéressant de comprendre ce que les SGBD réseau avaient apporté de plus novateur : l’expression des requêtes sur les données dans une logique de chemin (c.à.d. de navigation ). Parmi les SGBD construits selon ce modèle, encore largement utilisés, on peut citer IDS2 chez BULL, IDMS de CULLINET, TOTAL de CINCOM, SOCRATE.
8 5 Objectifs du cours

5. Objectifs du cours
5.0.4 Que doit-on savoir pour utiliser un SGBD
- Déftnition du schéma de données
- Opérations sur les données
- Optimisation
- Concurrence d’accès
- Fonctionnement d’un SGBD
- Plan du cours
Mode`le abstrait des bases de donne´es
Sommaire
-
Introduction : modélisation des données....... 9
- Généralités sur la conception d’une Base de Données... 9
- Problèmes d’une conception sans précautions........ 10
- Introduction à une bonne méthode...... 11
-
Le modèle entité-association (E/A)........ 11
- Présentation informelle..... 12
- Le modèle........ 13
- Avantages et inconvénients du modèle E/A... 13
1. Introduction : modélisation des données
Ce chapitre présente le modèle Entité/Association (E/A) qui est utilisé à peu près universellement pour la conception de bases de données (relationnelles principalement). La conception d’un schéma correct est essentielle pour le développement d’une application viable. Dans la mesure où la base de données est le fondement de tout le système, une erreur pendant sa conception est difficilement récupérable par la suite. Le modèle E/A a pour caractéristiques d’être simple et suffisamment puissant pour représenter des structures relationnelles. Surtout, il repose sur une représentation graphique qui facilite considérablement sa compréhension. En revanche, il admet certaines ambiguïtés.
La présentation qui suit est délibérement axée sur l’utilité du modèle E/A dans le cadre de la conception d’une base de données. Ajoutons qu’il ne s’agit pas de concevoir un schéma E/A (voir un cours sur les systèmes d’information), mais d’être capable de le comprendre et de l’interpréter.
- Généralités sur la conception d’une Base de Données
La réalisation d’une Base de Données implique trois grandes étapes (voir figure ??) :
- La définition d’un cahier des charges
- La modélisation
- L’implantation physique dans un système
10 1 Introduction : modélisation des données
Cahier des charges
Modélisation {
Implantation {
Fig. 2.1: Grandes étapes de la conception d’une base de données.
Nous allons nous intéresser ici à la deuxième étape.
Déftnition 2.1 (Modèle des données)
Un modèle des données (« data model ») est une description formelle et structurée des données et de leurs relations dans un système d’information.
Pour obtenir un modèle des données, il faut trois grandes phases :
- Modélisation / analyse des données
- Construction d’un modèle entité-association
- Conversion en un schéma de base de données
Nous nous concentrons dans la suite sur la deuxième phases.
La méthode de conception permet de distinguer les entités qui constituent la base de données, et les associations entre ces entités. Ces concepts permettent de donner une structure à la base, ce qui s’avère indispensable. Nous commençons par montrer les problèmes qui surviennent si on traite une base rela- tionnelle comme un simple fichier texte, sans se soucier de lui donner une structure correcte.
1.2 Problèmes d’une conception sans précautions
Les redondances (duplications) présentes dans la table faite sans précaution peut conduire à plusieurs types de problèmes :
- Erreurs possibles lors de l’insertion
- Erreurs possibles lors de la mise-à-jour