Cours complet de Bases de données en pdf


Télécharger Cours complet de Bases de données en pdf

★★★★★★★★★★4 étoiles sur 5 basé sur 1 votes.
Votez ce document:

Télécharger aussi :


Cours de Bases de Données

Jean-Claude Marti

1997

Correction 2007

UNIVERSITE DES SCIENCES

ET TECHNOLOGIES DE LILLE

Cours de Bases de Données

Jean-Claude Marti

1997

Correction 2007

UNIVERSITE DES SCIENCES

ET TECHNOLOGIES DE LILLE

Introduction

1         Qu’est-ce qu’un SGBD

Un SGBD est un système au sein du système, et dans certains cas, ses fonctionnalités (gestion des disques) se substituent à celles du système gérant la machine sur laquelle il est implanté.

C’est un progiciel de stockage et d’exploitation de l’information qui en assure la recherche et la maintenance. Les données sont persistantes (gestion de disques), partagées entre de nombreux utilisateurs ayant des besoins différents, qui les manipulent à l’aide de langages appropriés (graphiques ou “proches” du langages naturel). Le système assure également la gestion de la sécurité et des conflits d’accès (gestion des transactions). Son administration est centralisée (action d’un Administrateur, le DBA). Les SGBD sont munis d’un langage de requêtes et leur conception est établie à partir de trois couches indépendantes : la couche conceptuelle, la couche logique et la couche physique (implémentation).

Il faut remarquer que les données sont accessibles directement, alors que les systèmes de banques de données antérieurs ne fournissaient qu’un accès à un ensemble plus ou moins vaste au sein duquel il fallait encore faire une recherche séquentielle. On retrouve ce dernier mode de fonctionnement quand on utilise sur Internet des moteurs de recherche dont la conception a reposé au départ sur des moteurs de bases de données.

2      Historique

Le mot Data Base est apparu en 1964 lors d’une conférence sur ce thème aux USA, organisée dans le cadre du programme spatial américain.

Auparavant, on ne connaissait que des systèmes de gestion de fichiers (SGF), basés sur la gestion de bandes magnétiques, destinés à optimiser les accès séquentiels. Les disques étaient alors chers et réservés à de petits fichiers.

La figure suivante montre comment, au sein d’une même entreprise, on pouvait concevoir deux fichiers COBOL permettant la gestion du personnel. De tels fichiers ne pouvaient s’échanger de données sans des programmes d’extraction et de conversion appropriés. Les informations sont en compte d’octet. Le concept de type de donnée au sens actuel du terme n’est pas encore apparu : tout est caractère (octet), même les chiffres des nombres!

0 5                            17                     27                                    43 52                60

0 7 22                                               42                  50

n° emp  

     prénom                     

nom                                         

 salaite

Fichier "personnel"

La course à la lune change la donne. Il faut impérativement définir de nouveaux outils, plus efficaces et mieux normalisés. Vers la fin de la décennie 60 apparaissent les premiers SGBD, con¸cus selon les modèles hiérarchiques, puis réseaux dans la décennie suivante. On voit apparaˆ?tre des langages navigationnels, inspirés du cobol, et la description des données est indépendante des programmes d’application. Cette première génération suit les recommandations du DTBG CODASYL (Data Base Task Group - Conference On Data System Language), influencé par le système IMS d’IBM.

Le modèle relationnel voit le jour en 70 et met 20 ans pour s’imposer sur le marché. Ce modèle permet la naissance de langages assertionnels, basés sur la logique du premier ordre et les traitements ensemblistes. Dans le même temps, l’emploi des disques se généralise, les accès directs deviennent la règle, le développement des techniques d’optimisation assurent aux SGBD des performances largement équivalentes à celles des anciens modèles de données.

Au cours des années 80, de nouveaux besoins se font jour. Les systèmes mis jusque là sur le marché


privilégiaient des données de gestion. On cherche de plus en plus à manipuler des données techniques, des images, du son. De nombreux travaux de recherche tentent de faire le lien avec le monde OrientéObjet ainsi qu’avec les systèmes d’inférence utilisés en Intelligence Artificielle. Compte tenu de l’inertie du marché, il faudra attendre encore une dizaine d’années pour qu’un modèle vraiment nouveau et performant commence à l’envahir. C’est à la fin des années 90 qu’on voit une évolution vers le modèle relationnel-Objet. Aujourd’hui, tous les SGBD qui sortent suivent ce dernier modèle, bien que la majorité des utilisateurs continue de n’en utiliser que la couche relationnelle.

La figure suivante trace l’historique et la filiation des principaux produits.

      3         Objectifs des SGBD

      3.1    Indépendance des données

Un aspect important des SGBD vient du principe de découpage en couches, lequel est inspiré du dévelopement d’Arpanet apparu à la fin des années 50, qui assure l’indépendance des données par rapport au système et à l’architecture, mais aussi par rapport aux problèmes du monde réel qu’il s’agit de modéliser.

Le schéma conceptuel est issu des travaux des analystes, dirigés par un chef de projet et correspond à une modélisation purement intellectuelle de l’univers à gérer et des paramètres qui doivent être pris en compte. C’est à ce niveau qu’opère le chef de projet chargé de la conception de la base.

Le schéma logique en est la traduction informatique abstraite (au sens ou` on parle de type abstrait de données en algorithmique). Selon le modèle utilisé, les données sont organisées selon un schéma arborescent (modèle hiérarchique), un graphe (modèle réseau), des tables (modèle relationnel), des objets (modèle objet). A ce niveau travaillent des analystes programmeurs et le DBA (Data Base Administrator) ou administrateur de la base de données. C’est lui qui est responsable de la modification du schéma d’analyse dans le but d’optimiser l’exploitation de la base.

Le schéma physique correspond à l’implémentation des données sous forme de fichiers sur disques et gère les mécanismes d’accès. C’est le domaine des programmeurs système, mais aussi celui du DBA qui peut, lorsque le SGBD le permet, décider des modalités d’implantation de la base (position médiane sur le disque, nature des fichiers - séquentiels, ordonnés, hachés, ... ).

Ces 3 niveaux doivent être indépendants, de fa¸con à permettre la modification de l’un sans pour autant remettre en cause la totalité des autres couches, du moins tant que les règles d’interface restent respectées. Les logiciels d’aide à l’analyse permettent tous une transformation automatique et normalisée du schéma d’analyse en un script de création de la base.

      3.2     Administration centralisée

Elle prend tout son sens dans le contexte historique de développement de l’informatique, par rapport à une époque ou`, l’anarchie étant la règle, on nageait, au sein d’une même entreprise, dans la plus totale incohérence. Avec un SGBD, personne ne peut modifier de données, encore moins leur mode d’organisation, sans y avoir été duˆment autorisé par l’administrateur. Ce dernier a tous les droits sur la base, la crée, l’optimise, suit son évolution, gère les sauvegardes, ajuste les paramètres, distribue les droits d’accès. Il joue le rôle du responsable système vis à vis de ce système spécifique qu’est le SGBD.

Il utilise un langage de définitions des données ou DDL en anglais (Data Definition Language), un langage de manipulation de données ou DML (Data Manipulation Language), ainsi qu’un langage de sécurité des données ou DSL (Data Security Language).

      3.3     Normalisation

C’est un aspect fondamental qui permet l’échange et la recherche de données à travers des systèmes différents. Malgré les développements particuliers de chaque éditeur de logiciel, la normalisation s’est imposée très tôt, que ce soit au niveau des modèles (ANSI/SPARC, CODASYL) ou des langages (SQL). Aujourd’hui, la communication à travers des SGBD différents est largement utilisée.

Le Modèle Conceptuel des Données

Il existe plusieurs systèmes de modélisation. Le plus répandu demeure le modèle Entité-Association qui est l’aboutissement de méthodes d’analyse dont la plus utilisée en France est la méthode MERISE.

      1      Concepts

      1.1     Type d’entité

Une entité ou individu est un objet discernable des autres objets du monde à modéliser, par exemple une personne, un véhicule. Ce peut être aussi un concept ou une grandeur abstraite. Une entité ne peut exister par elle-même sans être déterminée par la liste de ses propriétés ou attributs. Une propriété constitue le plus petit élément d’information ayant un sens intrinsèque : un nom, une date de naissance, un numéro de téléphone, ...

Nom de l’Entité

propriété 1 propriété 2 propriété 3

..............

Un type d’entité est représentée par l’ensemble des entités de même nature que l’on pourra déterminer au cours du temps : l’ensemble des individus, des véhicules, des comptes en banque, ...

Chaque entité devra pouvoir être distinguée de fa¸con unique par un identifiant ou clé. Ce dernier est en général représenté par une propriété particulière. L’usage veut qu’elle soit soulignée dans la représentation graphique du type d’entité.

      1.2     Association

C’est un lien logique entre 2 ou plusieurs types d’entité. Elle est le plus souvent per¸cue comme une action entre des catégories d’objets et se traduit presque toujours par un verbe. On dira ainsi qu’un auteur publie (cf. fig) des ouvrages

Une association peut aussi posséder des propriétés qui dans ce cas n’appartiennent en propre à aucun des types d’entités qu’elle relie.

On distingue :

–   Les associations binaires qui relient entre elles les différentes instances de deux types d’entité.

–   Les associations n-aires (n > 2) qui relient les instances de n types d’entité.

–   Les associations réflexives qui relient des instances d’un type d’entité avec d’autres instances dumême type. On en trouve un exemple dans l’association Composant-Composé qui traduit le fait qu’une pièce de machine peut être un assemblage de plusieurs autres composants, et réciproquement.

      1.2.1      Cardinalités

Les cardinalités d’une association sont un élément clé de la traduction du MCD vers un modèle logique. Elles permettent de préciser les nombres minimum, et surtout maximum d’occurrences d’une entité pouvant être impliquée dans les occurrences de l’association.

Il faut faire très attention au fait que les normes US et européennes sont inverses l’une de l’autre dans la représentation des cardinalités. En Europe, et en France plus particulièrement, les cardinalités sont placées vis à vis du type d’entité qu’elles renseignent. Ainsi, dans l’exemple ci-dessous, un client passe de 0 à plusieurs commandes, et une commande est passée par un client et un seul. L’interprétation de ces cardinalités seraient inversées si le schéma figurait dans un livre publié aux USA.

Les cardinalités doivent toujours être analysées du point de vue de l’entité à laquelle elles sont accolées.

Les valeurs possibles sont : 0,1 0,n 1,1 et 1,n

Les cardinalités permettent de préciser la nature de l’association et du lien qu’elle constitue entre les entités. On parle de liens hiérarchiques, fonctionnels et maillés. Un lien fonctionnel est l’inverse d’un lien hiérarchique et relie des feuilles à la racine d’un arbre. Le lien maillé est le lien qui permet de relier entre-eux des nœuds au sein d’un graphe.

Les cardinalités minimales peremettent de préciser des éléments de l’annalyse, mais ne jouent aucun rôle sur la traduction du MCD en un schéma logique. Lorsque les cardinalités maximales valent 1 et N de part et d’autre d’une association, il y a présence d’un lien hiérarchique (du côté du N) et d’un lien fonctionnel (du côté du 1). Le lien hiérarchique exprime le point de vue du sommet d’un arbre, le lien fonctionnel le point de vue des feuilles. Dans l’exemple de la figure, un client passe plusieurs commandes. Il est placé à la racine d’un arbre dont les commandes sont en feuilles. Chaque commande “voit” le client qui l’a émise.

Le lien maillé correspond à des cardinalités maximales valant N de part et d’autre de l’association. L’association publie figurant à la page précédente est construite sur un lien maillé : un auteur peut publier plusieurs ouvrages, mais il se peut qu’un ouvrage soit publié par plusieurs auteurs. Le lien maillé peut être implémenté par la réunion de deux liens fonctionnels opposés l’un à l’autre.

      2        Règles d’écriture du MCD

–   Les propriétés doivent être mono valuées. On ne peut rencontrer une propriété sous la forme d’uneliste de valeurs; elle est toujours représentée par une valeur unique. Dans le cas contraire, elle doit être décomposée sous la forme d’au moins deux entités associées.

–   Les différentes valeurs des propriétés d’une entité doivent dépendre entièrement de l’identifiant (clé)de cette entité.

–   Dans le cadre d’une association, deux entités de types différents sont reliées par une seule instancede l’association.

–   Si la propriété d’une entité dépend d’une propriété autre que la clé, c’est le signe que l’analyse aété mal faite et qu’il existe un type d’entité imbriqué dans le type initial. Les propriétés ne peuvent dépendre que de la clé, sauf s’il existe plusieurs clés candidates dans l’entité. Ainsi, si l’on est certain de ne jamais avoir d’homonymes, un employé peut indistinctement être repéré par un numéro ou par son nom. Ces deux propriétés sont des clés candidates, et une seule (probablement le numéro) sera choisie comme clé primaire. La clé primaire est une clé d’implémentation. Au niveau du modèle (sur le plan théorique), les autres propriétés ne dépendent que de cette clé, mais au niveau logique (sur le plan pratique), elles continuent toutes de dépendre à la fois du numéro et du nom.

Anciens modèles de données

      1      Le modèle hiérarchique

      1.1   Généralités

Développé pour les besoins de la NASA, il a donné naissance entre autre à IMS (IBM) qui utilise, pour manipuler les données, un COBOL navigationnel.



Les entités du MCD sont représentées par des segments de données. Il n’y a pas de concept d’enregistrement. Les propriétés sont des champs, et le type de lien pris en compte est le lien hiérarchique. Le SGBD est une forêt composée d’arbres de segm ents et de pointeurs.

      1.2       Traduction du MCD

1,n                           1,1

                  1,1                         1,1                                                                                   X                  Y

                              X                  Y

Y11 Y12    Y1n

1,1 1,1

                              X                  Y

p

X

Y1 Y2 ...    Yn

Le mécanisme de traduction s’appuit sur l’arité et la cardinalité des associations. On distingue les cas suivants :

–   Les associations binaires bi-univoques X ? Y sont traduites par des arbres dont soit X soit Y est la racine, selon la sémantique des entités (fig. 1-a). Si l’association est porteuse de propriétés, celle-ci est représentée p ar un nœud constituant un niveau intermédiaire entre X et Y (fig. 1-b).

–   Les associations binaires hiérarchiques X ? Y sont traduites par des arbres dont X est obligatoirement la racine (fig. 1-c).

–   les associations n-aires ou construites sur des liens maillés sont traduites par une série d’arbres(forêt). L’un d’eux est constitué des données (segments), les autres étant des arbres de pointeurs, fournissant un accès hiérarchisé à une informati on qui n’est pas dupliquée. Le SGBD est la racine (symbolique) qui permet de relier tous ces arbres en un arbre unique. (fig 1-d).

      1.3     Anomalies

le modèle donne lieu à un certain nombre d’anomalies de fonctionnement.

–   il est impossible d’insérer des données sans avoir au préalable créé la chaˆ?ne des nœuds supérieursqui la relient à la racine.

–   la suppression d’un nœud conduit nécéssairement à la destruction du sous arbre associé.

–   la mise à jour conduit à balayer la totalité de la forêt dont le SGBD est la racine.

      1.4     Avantages-inconvénients

–   Le modèle conduit naturellement à une bonne représentation des systèmes hiérarchiques et fonc-tionne remarquablement avec des applications de cartographie et de CAO.

–   il est simple et facile à implémenter.

–   il est cependant mal adapté à la représentation des liens maillés et des réalités complexes.

–   ses bonnes performances sont limitées par les anomalies de fonctionnement exposées ci-dessus.

–   les bases hiérarchiques doivent être manipulées à l’aide de langages navigationnels lourds et couˆteuxà mettre en œuvre.

–   l’indépendance entre les niveaux logiques et physiques est pratiquement inexistante.

      2     Le modèle réseau

      2.1   généralités

Ce modèle correspond à la deuxième génération de SGBD. Il a été normalisé par le DBTG CODASYL, et a donné lieu à de nombreux produits commerciaux (IDS (CII-HB), DBMS (DEC), IDMS). Les recommandations du CODASYL ont conduit à fixer la syntaxe et la sémanti que des opérations des langages de manipulation.

Au concept d’entité du MCD correspond la notion d’enregistrement. Les propriétés sont des items de données. Le type du lien pris en compte est le lien hiérarchique.

Le concept de base, sur lequel repose tout le modèle, est le concept de COSET, qui relie un type d’enregistrement maˆ?tre avec un type d’enregistrement membre, et fait disparaˆ?tre le besoin d’une clé pour accéder à un enregistrement parti culier.

      2.2       traduction du MCD

                 1,1                       1,1                        Coset XY : Maître :   X          (ou l’inverse)

XY membre : Y

Si A contient une propriété p, celle-ci est transférée au niveau de l’entité membre.

                   1,n                       1,1                       Coset XY : Maître :   X

XY

membre   Y

                   1,n                     1,n                        Coset XA : Maître :   X                   Coset YA : Maître   Y             A est une entité artificielle

XY

                                                                                      membre : A                                   membre : A

Y

                              X                                     Coset XA                 Coset YA                       Coset ZA                    A est une entité artificielle

Z

Le mécanisme de traduction est schématisé ci-dessus. Il fait intervenir, pour la traduction des liens maillés ou des associations n-aires (avec n > 2), une entité “bidon”, éventuellement vide, qui n’est là que pour permettre la décomposition du lien ma illé en une série de liens hiérarchiques.

      2.3      propriétés du COSET

–   une occurence donnée d’un COSET possède un propriétaire et plusieurs membres. Les types d’entitésdu propriétaire et des membres sont nécessairement différents.

–   un type d’enregistrement peut être propriétaire dans plusieurs instances de COSETS différents,mais pas dans des instances différentes du même COSET.

–   un type d’enregistrement peut être membre dans plusieurs instances de COSETS différents, maispas dans des instances différentes du même COSET.

      2.4     Avantages - inconvénients

–   Le modèle assure une bonne représentation des liens maillés.

–   Il permet de ce fait une meilleure représentation des réalités plus complexes que les organisationshiérarchiques.

–   il est dépourvu d’anomalies de fonctionnement.

–   Il a donné lieu à une offre commerciale assez étoffée.

–   Les moteurs de bases de données réseaux ont été largement utilisés dans la conception de produitshyper-textes, en association avec des index arborescents.

–   il conduit malheureusement à une indépendance faible entre les niveaux logiques et physiques.

–   Les données ne peuvent être manipulées qu’avec des outils de navigation lourds et couˆteux.

                 2.5     Langage navigationnel

Le système dispose d’une multitude de pointeur :

–   un par type d’enregistrement.

–   un par type de COSET.

–   un pour l’enregistrement courant.

les échanges de données se font à l’aide de gabarits d’enregistrements.

De nombreux éléments syntaxiques des langages permettent de positionner ces pointeurs sur telle ou telle partie de l’information.

–   recherche par nom ou critère : La recherche du premier enregistrement de nom donné se fait par :

FIND enregistrement RECORD USING valeur;

La recherche des autres enregistrements de même nom utilise :

FIND NEXT DUPLICATE enregistrement RECORD [USING condition]

En cas d’erreur, une condition (STATUS CHECK) est levée et permet d’interrompre le traitement.

–   Recherche d’un membre d’un COSET :

FIND PRIOR | NEXT | FIRST | LAST | n enregistrement RECORD WITHIN coset SET – Recherche du propriétaire : FIND OWNER RECORD OF coset SET – Recherche au sein d’un COSET :

FIND enregistrement RECORD VIA coset SET [WHERE condition] Le LMD dispose aussi d’instructions de boucles de la forme :

loop until condition ... end loop

La condition de boucle pouvant être : no more records ou encore end of set

La programmation consiste à naviguer à travers le graphe de la base et conduit à des programmes rapidement assez complexes, qui rendent difficiles la réalisation d’applications à la carte.

Exemple d’utilisation pour les type d’entités définis ci-dessous avec leurs propriétés :

Stations(ns,nom,nr)

Region(nr,nom) Activités(na,libelle) propose(ns,na)

Les Cosets correspondants sont :

AP : Maitre = Activites, membre = propose

RS : Maitre = Region, membre = Station

SP : Maitre = Station, membre = Propose

Procédure : Activités des stations des alpes d’altitude > 1200m

find region record using nom=’ALPES’; exit if status_check;

find station record via RS set where altitude > 1200;

exit if status_check; loop until no more records find first propose record within SP set;

exit if status_check; find owner record of AP set; output libelle of activite; loop until end of set find next propose record within SP set;

exit if status_check; find owner record of AP set; output nom of activite;

end loop; find next duplicate station record using altitude > 1200; end loop;

Le modèle relationnel

      1    Généralités

      1.1     Historique

Il est né de la thèse de Codd (IBM San José - 1970) et il est basé sur des concepts très simples. De 72 à 75, les laboratoires IBM ont con¸cu un premier prototype : SYSTEM R, d’ou` sont directement issus les logiciels : INGRES (RTI - 1976), ORACLE (1979), SQL/DS (IBM-1981) et DB2 (IBM - 1983). Pour manipuler System R, des prototypes de langages ont été créés qui ont rapidement abouti à SQL. Normalisé par l’ANSI en 86, ce langage a continué son développement pour donner lieu en 92 à la norme SQL-2. Une nouvelle et dernière normalisation a eu lieu en 1999 (SQL-3).

      1.2    Définitions

Au type d’entité du MCD correspond la notion de Relation, à ne pas confondre avec une association. Une relation, dans le cadre du modèle, est assimilée à une table. Les propriétés sont appelées des attributs. Le seul type de lien reconnu par le modèle est le lien fonctionnel entre N instances d’un type d’entité et une et une seule instance du type d’entité associé.

Un Domaine est un ensemble de valeurs : ensemble des entiers, ensemble des couleurs (bleu, blanc, rouge), intervalle 0..1, etc ...

Le produit cartésien de plusieurs domaines D1, D2, ..., Dn est constitué d’un ensemble de n-uplets encore appelés tuples : (v1, v2,..., vn), ou` chaque vi est une valeur d’un Di.

D1

D2

Bleu

0

Bleu

1

Blanc

0

Blanc

1

Rouge

0

Rouge

1

Produit cartésien de l’ensemble D1 des couleurs par celui D2 des valeurs binaires

Une relation est un sous ensemble du produit cartésien des domaines sur lesquels sont définis ses attributs. Elle peut donc être représentée par une table à 2 dimensions dont les colonnes correspondent aux différents domaines et dont les lignes représentent les tuples.

Le schéma relationnel est constitué de l’ensemble des relations définies par leur nom suivi de la liste de leurs attributs. Exemple de schéma relationnel :

EMPLOYE(numero, nom, adresse, salaire, emploi, departement)

Il n’y a pas d’identificateur de tuple. C’est un attribut particulier, la clé primaire (numero dans l’exemple précédent), qui permet d’identifier une rangée de la table parmi toutes les autres. Il arrive que plusieurs attributs soient capables de jouer le rôle de clé pour une relation. L’un d’eux est alors choisi pour constituer la clé primaire, les autres clés candidates deviennent alors des clés secondaires.

Le schéma de chaque relation représente son intention, alors que les données du tableau constituent une extension particulière, c.à.d un instantané des valeurs qu’il contient à un instant donné. La figure précédente représente une extention du schéma (couleur, nombre binaire), alors que le schéma relationnel de la table employe représente l’intention de cette même table.

      1.3     Traduction

La traduction du MCD en un schéma relationnel est un processus extrêmement simple : – Chaque relation est traduite par une table.

–   Les associations construites sur des liens maillés sont représentées par des tables, et elles clé primaire est au minimum obtenue par la réunion des clés des relations associées. Il peut arriver que ce regroupement ne soit pas suffisant pour garantir l’unicité des valeurs sur chaque ligne et qu’il faille y rajouter des propriétés supplémentaires de l’association.

–   Les associations construites sur des liens fonctionnels sont implémentées de la manière suivante :Dans la table qui représente le type d’entité situé du côté du lien fonctionnel, on ajoute un attribut représentant un pointeur par valeur vers la clé de la table qui implémente l’autre type d’entité. Dans l’exemple Clients-Commandes du chapitre sur le MCD, on place dans la table commandes un attribut permettant de faire référence à la clé du client ayant passé la commande. Si l’association est porteuse de propriétés, celles-ci suivent la représentation de l’association. Une propriété éventuelle de l’association passe serait représentée par l’ajout de l’attribut correspondant dans la table commandes.

      1.4    Règles d’intégrité

Ces règles garantissent le bon fonctionnement du modèle et l’accès aux donnéesélémentaires représentées par les lignes des tables qui traduisent les relations.

      1.4.1      L’intégrité d’unicité

L’accès à une ligne particulière d’une table ne peut être réalisé directement que par l’intermédiaire de la valeur d’une clé qui joue le rôle d’un identifiant. Le modèle relationnel est un “modèle valeur” parce que ce sont des valeurs qui servent à l’identification; le corollaire, c’est qu’une telle valeur doit obligatoirement être unique et définie. Lorsqu’aucune valeur ne peut convenir pour repérer la rangée d’une table, il faudra en créer une, même artificiellement, en lui attribuant par exemple un numéro qui n’aura qu’une signification interne au sein du système.

      1.4.2     L’intégrité de référence

Cette contrainte traduit l’existence d’un lien fonctionnel entre deux relations. La relation qui est du côté de la cardinalité 1,1 dans l’association est la relation référen¸cante, celle qui est racine de la hiérarchie (cardinalité 1,n) est la relation référencée. On doit trouver dans la relation référenc¸ante un attribut construit sur le même domaine que la clé de la relation référencée. Une ou plusieurs valeurs de cet attribut doivent correspondre à une valeur unique de la clé. Ce procédé permet d’associer par valeur plusieurs rangées de la relation référen¸cante à une et une seule ligne de la relation référencée.



      1.4.3      L’intégrité de domaine

Les valeurs d’un attribut doivent obligatoirement correspondre aux valeurs du domaine sur lequel il est défini. Un domaine est souvent associé à des critères logiques qui permettent de restreindre le type sur lequel il est construit (entiers positifs, caractères limités aux voyelles, etc). Le respect de l’intégrité de domaine permet donc de contrôler lors de l’insertion ou de la mise à jour d’une valeur que celle-ci est conforme au cahier des charges (un salaire ne peut être négatif, un mois doit être compris entre 1 et 12, un nom sera transformé indépendemment de sa saisie avec une initiale en capitale, etc ...) Un schéma totalement relationnel est un schéma satisfaisant tous ces types d’intégrité.

      1.5     Avantages et inconvénients du modèle

–   Le modèle relationnel est un modèle simple pour l’utilisateur qui ne manipule que des tables.

–   L’indépendance entre les niveaux peut être parfaitement respectée.

–   Le représentation est uniforme. Elle possède une certaine puissance que lui confert la théoriealgébrique qui la fonde.

–   Le concept de table permet de garantir des accès sécurisés aux données, en ligne comme en colonne.

–   Il existe de nombreux interfaces non procéduraux, un grand nombre de langages conviviaux demanipulation et un standard (SQL).

–   L’offre commerciale est énorme et concerne tous les systèmes, toutes les plates-formes.

–   Néanmoins, le processus de normalisation pose certaines difficultés (anomalies de fonctionnement, baisses de performances) et fait perdre un peu de l’indépendance entre le niveau conceptuel et le niveau logique.

–   Le modèle est inadapté au traitement de données multimédia.

      2      L’algèbre relationnelle

Elaborée par Codd dans sa thèse, elle repose sur un petit nombre d’opérateurs de type ensemblistes.

Les exemples qui vont suivrent manipulent les relations suivantes, R, S et T respectivement :

A

B

C

a

1

a

b

1

b

a

1

d

b

2

f

A

B

C

a

3

f

RS

B

C

D

1

a

1

3

b

1

3

c

2

1

d

4

2

a

3

T

      2.1     Opérateurs monadiques

Ces opérateurs sont des réducteurs de données.

      2.1.1       Projection

Symbole graphique de l’opérateur de projection

La projection est un opérateur d’accès par les colonnes. La projection U d’une relation R sur une liste d’attributs est la relation dont le schéma se réduit aux attributs de la liste. Ses tuples sont ceux de R, avec élimination des tuples en double.

A

B

a

1

b

1

b

2

Y U = R

A,B

      2.1.2       Restriction

Symbole graphique de l’opérateur          de restriction

La restiction est un opérateur d’accès par les lignes. Une formule de restriction ou qualification q est une expression logique reliant des attributs de la relation opérande avec des constantes par l’intermédiaire d’opérateurs de comparaison; par exemple :

A = a AND B < 2

La restriction U de la relation R par la qualification q est une relation de même schéma que R dont les tuples sont ceux de R qui vérifient la qualification.

A

B

C

a

1

a

a

1

d

U = ?A=a (R)

      2.2     Opérateurs dyadiques

      2.2.1      Union

Symbole graphique de l’opérateur d’union

L’union de deux relations R et S de même schéma est la relation de même schéma dont les tuples sont à la fois ceux de R et de S. L’union est un opérateur expanseur de données.

A

B

C

a

1

a

b

1

b

a

1

d

b

2

f

a

3

f

S U= R      S

      2.2.2     Différence

Symbole graphique de l’opérateur de différence

La différence de deux relations de même schéma R et S est une relation de même schéma dont les tuples sont ceux de R n’appartenant pas à S. La différence n’est pas un opérateur commutatif. 2.2.3        Intersection

Symbole graphique de l’opérateur d’intersection

L’intersection de deux relations R et S de meme schéma est une relation de même schéma constituée des tuples qui appartiennent à la fois R et à S. L’intersection, obtenue par composition de différences, n’est pas un opérateur de base.

      2.2.4      Division

Symbole graphique de l’opérateur de division

La division d’une relation R par une relation S est la relation formée des tuples qui, concaténés à chaque tuplede S, redonnent un tuple de R. La division n’est pas un opérateur de base et peut être réalisée par l’expression algébrique :

ou` X est l’ensemble des attributs de R qui ne sont pas dans S. Soit la relation Z :

B

C

1

a

1

d

A

a

La division R ÷ Z est :

      2.2.5      Produit cartésien

Le produit cartésien de deux relations R et S est une relation dont le schéma est la concaténation de ceux des relations composantes et dont les tuples sont obtenus en combinant chaque tuple de R avec tous ceux de S.

Le produit cartésien (ainsi que tous les opérateurs dérivés) est un expanseur de données.

      2.2.6      Jointures

l’opérateur de jointure

On distingue plusieurs opérateurs de jointures. Ils sont associés à des formules de qualification reliant entre eux certains attributs des relations composantes. On distingue :

– l’équijointure : La clause de qualification est une égalité entre deux attributs des relations opérandes. La relation résultante est le sous-ensemble du produit cartésien réduit aux tuples vérifiant la qualification, sans répétition, dans le schéma, de l’attribut commun.

U = R             ./          T

R.A = T.C

A

R.B

R.C

T.B

T.D

a

1

a

1

1

a

1

a

2

3

b

1

b

3

1

a

1

d

1

1

a

1

d

2

3

b

2

f

3

1

– la ?-jointure : dans la clause de qualification, l’opérateur d’égalité est remplacé par un des cinq autres opérateurs de comparaison.

U = R             ./          S

R.B < T.D

– l’autojointure : c’est la jointure d’une relation avec elle-même. SI algébriquement parlant, il est possible d’écrire :

U = R         ./       R

B < B

dans la pratique, il conviendra de donner des noms ou alias différents aux deux opérandes, puisque les traitements vont concerner des lignes différentes.

–   la jointure naturelle : C’est l’équijointure de deux relations sur tous les attributs ayant même nomet construits sur le même domaine.

–   les semi-jointures : on distingue la semi–équijointure, la semi-? jointure, la semi-jointure semi jointure entre R et S : R .<A = AS, est la projection sur l’opérande gauche de la jointure correspondante. On a la relation :

La semi-jointure de deux relations R et S est la relation de même schéma que R dont les tuples sont ceux de R qui participent à la jointure de R et de S.

La semi-jointure est un opérateur réducteur de données et n’est pas commutative.

      2.3     Composition d’opérations

La composition des divers opérateurs permet d’envisager des traitements algébriques complexes autorisant des manipulations formelles des données.

Soient les relations :

EMP(numemp, nomemp, salaire, emploi, departement)

DEPT(numdept, nomdept, adresse, ville)

La détermination des informaticiens basés à Lille et gagnant plus de 20000 F se fera par :

Cette expresion peut être représentée graphiquement par l’arbre statique d’exécution suivant :

      3      Normalisation

3.1      Quel est le bon schéma?

Il n’y a pas une solution unique à un problème de gestion de données. En général, des équipes d’analystes indépendantes permettraient d’aboutir à des dizaines de MCD différents pour un même problème complexe. Une fois que l’on applique les règles automatiques de traduction présentées au début de ce chapitre, on obtient des schémas relationnels aux propriétés bien différentes. Au début du développement des bases de données relationnelles, ces schémas pouvaient aboutir à des requêtes d’interrogation qui s’exécutaient en des temps variant de moins dune seconde à plusieurs dizaines de minutes. Très tôt s’est donc posé un problème d’évaluation des schémas et de classification de leurs propriétées.

C’est par l’introduction du concept de dépendance fonctionnelle qu’on a pu construire des outils d’évaluation et de manipulation des schémas relationnels. On a pu ainsi répondre aux questions : “qu’estce qu’un bon schéma”, “quel est le meilleur schéma”, “comment améliorer un schéma ”.

      3.2     Dépendance fonctionnelle

      3.2.1    généralités

Les dépendances fonctionnelles (D.F.) permettre d’introduire des dépendances de valeurs entre les données. C’est une notion intuitive : un salaire dépend (en général) de la qualification d’un employé, la vitesse maximale d’un véhicule dépend de sa puissance. Si la date de naissance dépend d’un individu, elle dépend donc de la clé (éventuellement un numéro) qui, dans la base, sert à le repérer.

On aura dans ce cas : numero ? date naissande.

Dans toute relation R(X,Y) munie de la DF X ? Y, X est clé candidate. Si elle est la seule possible, ou si elle choisie parmi d’autres possibles, elle devient la clé primaire de la relation R.

On appelle dépendance élémentaire X ? Y, toute dépendance telle que Y ne dépend pas d’un sousensemble de X.



C’est un modèle de dépendance de valeur. La valeur d’une donnée dépend de celle d’une autre donnée. (Attention : l’inverse n’est pas forcément vrai! La détection d’une conséquence n’implique pas qu’elle soit due à une cause spécifique, sauf lorsque le mécanisme causal, auquel s’apparente le mécanisme des DF ne dépend que d’une cause unique). Ceci veut dire que si on fait dépendre un âge d’un nom, le même nom devra toujours être associé à la même valeur de l’âge. La dépendance impose ainsi au nom d’être associé au même âge qui doit rester fixe, et tous les homonymes devront avoir cet âge. Il convient donc, lors de la modélisation, d’examiner cette notion de dépendance en faisant preuve de beaucoup de sens critique.

      3.2.2        Axiomes d’Armstrong

Le formalisme des dépendances fonctionnelles est celui d’Armstrong (1974).

X,Y,Z désignant des ensembles d’attributs, on dit que Y dépend fonctionnellement de X, et on note X ? Y , s’il existe une DF de X vers Y.

1.    Réflexivité : si Y               ? X alors X ? Y

2.    Augmentation : Si X ? Y et si W est un ensemble quelconque d’attributs, alors XW ? Y W

3.    Transitivité : Si X ? Y et Y ? Z, alors X ? Z

4.    Pseudo-transitivité : si X ? Y et Y W ? Z, alors XW ? Z

5.    Union : si X ? Y et X ? Z, alors X ? Y Z

6.    décomposition : Si X ? Y Z, alors X ? Y et X ? Z

l’axiome d’augmentation permet d’intégrer des attributs isolés, non liés à une dépendance fonctionnelle particulière. Les trois dernières règles ne sont pas indispensables; ce sont des règles opératoires permettant, plus directement, la manipulation des graphes de dépendances.

Ces différentes DF génèrent un graphe F. On appelle fermeture transitive d’un graphe le graphe obtenu en ajoutant à F l’ensemble de tous les arcs qui se déduisent de ceux de F par les 3 premiers axiomes. Ce graphe F+ définit la couverture maximale des DF.

Soit R(A,B,C,D) une relation munie des DF suivantes :

A ? BC

C ? D D ? B la fermeture transitive sera obtenue par l’ajout de :

A ? D

au graphe initial.

La couverture minimale est obtenue par l’ensemble des arcs de F+ qui ne sont pas redondants. C’est ce graphe qui permet d’obtenir une décomposition de F sans perte d’information (cf. plus loin).

Deux graphes F et G obtenus à partir de la même liste de DF correspondent à une solution correcte (mais dont les propriétés ne sont pas équivalentes) si F+ = G+

En pratique, le graphe des dépendances fonctionnelles permet d’obtenir, de fa¸con algorithmique, le schéma conceptuel ( ou une version de ce schéma), et la réciproque est vraie aussi.

      3.3     Décomposition

Puisqu’on peut toujours transformer un graphe de DF en sa fermeture transitive, on peut imaginer de placer tous les attributs du problème dans une seule et même relation universelle U. On constate que la gestion d’une base relationnelle organisée selon ce principe conduit à une série de disfonctionnements qui la rendent rapidement incohérente et inefficace. On s’aper¸coit qu’une décomposition de U en plusieurs relations regroupant les DF autours de leur source améliore le fonctionnement de la base. Cette décomposition, appliquant l’axiome 6, doit être réversible (axiome 5) et sans perte d’information. Elle utilise pour ce faire les opérations de projection et de jointure qui réalisent respectivement ces deux opérations de décomposition et d’union.

On dit qu’une décomposition (par projection) est sans perte d’information s’il existe des jointures qui permettent de reconstituer les données sous leur forme initiale. En d’autres termes, si on décompose U en :

, on doit obligatoirement avoir :

Soit par exemple :

A

B

C

D

a

5

x

2

B

5

y

2

C

5

x

2

On voit bien que, dans cette relation R, les DF énoncées au paragraphe précédent sont vérifiées.

La décomposition R1(A,B) et R2(B, C, D) n’est pas conservative puisque R1 ./ R2 =6        R. Par contre R1(A, B, C) et R2(A,D) constitue bien une décomposition sans perte.

      3.4     Formes normales

Ce processus de décomposition permet de mettre en évidence des situations caractérisées par la présence ou non d’anomalies de fonctionnement. Ces situations fournissent des critères d’évaluation du comportement d’une base relationnelle.

      3.4.1       Première forme normale

Une relation est en première forme normale si tous ses attributs contiennent des valeurs atomiques.

Sont exclus les attributs construits sous formes complexes (vecteurs, listes, arbres, objets ...) Dans la relation (numemp, nom, enfant(prenom,dateNaissance)) l’attribut enfant est un groupe composé qui ne peut être pris en compte dans le modèle relationnel. Une telle “relation” appartient au monde orienté-objet (OO) et ne peut être manipulée par les opérateurs relationnels. Le modèle relationnel est un modèle ensembliste, et tous les éléments d’un ensemble doivent avoir la même cardinalité, faute de quoi on ne peut plus parler d’ensemble au sens mathématique du terme.

Il est nécessaire de décomposer la relation précédante en deux relations qui seront alors en première forme normale :

Emp(numemp, nom) et Enfants(numemp,prenom, dateNaissance)

      3.4.2       Deuxième forme normale

Cette forme normale ne s’applique qu’aux relations possedant une clé multiple.

Une relation est 2NF ssi :

–   elle est 1NF

–   tous ses attributs non-clé dépendent de la totalité de la clé.

La relation Stock(piece, entrepot, qté, adresse) n’est pas 2NF car l’adresse ne dépend que de l’entrepôt. Elle subit de ce fait des anomalies de fonctionnement qui sont :

–   une redondance d’informations susceptible d’induire des incohérences;

–   en cas de mise à jour de l’adresse d’un entrepôt, l’obligation de balayer toute la table pour modifiercette dernière partout ou` elle peut être présente;

–   lors de la suppression de la dernière pièce de l’entrepôt, on perd toute trace de celui-ci.

Si on désire mettre la relation en 2NF, on doit la décomposer en :

Stock(piece, entrepot, qté)

Local(entrepot, adresse)

      3.4.3      Troisième forme normale

Une relation est 3NF ssi :

–  elle est 2NF

–  Aucun attribut non-clé ne dépend fonctionnellement d’un autre attribut non-clé.Soit : Emp(numemp, nom, service, batiment)

Le service implique le bâtiment dans lequel il se situe. De ce fait, Emp n’est pas 3NF. Elle dissimule la présence d’une relation cachée qui a échappé à l’analyse, et doit être décomposée en :

Emp(numemp, nom, service)

Localisation(service, batiment)

La décomposition est bien 3NF. En pratique, cette forme normale est importante car dotée de propriétés correctes. Il existe souvent plusieurs fa¸cons d’opérer des décompositions 3NF, mais toute relation en possède au moins une qui soit sans perte et qui préserve les DF. Un algorithme duˆ à Bernstein permet de la générer automatiquement.

Le principe de la normalisation des relations s’appuie sur la notion de clé. On distingue la clé primaire parmi toutes les clés candidates possibles (les clés candidates non retenues sont appelées clés secondaires). La normalisation en 3NF prend en compte la notion générale de clé, qu’elle soit primaire ou secondaire. La seule différence qui intervient entre différentes clés correspond à un choix d’implémentation, mais toute clé candidate joue le même rôle que la clé primaire vis à vis des autres attributs de la relation.

      3.4.4         Forme normale de Boyce-Codd

Dans la définition des formes normales qui précèdent, on ne s’est pas préoccupé des dépendances transitives (cachées) qui peuvent causer des anomalies de mise à jour. Celles-ci peuvent se manifester de fa¸con insidieuse par l’intermédiaire de clés candidates qui pourraient demeurer dans une relation. La forme normale de Boyce Codd doit donc prendre en compte toute clé (au sens large) dans la relation.

Une relation est BCNF si et seulement si les seules DF élémentaires sont celles dans lesquelles il n’y a pas d’autre déterminant que la clé primaire. Une relation BCNF est aussi 3NF et constitue le degré ultime de décomposition sur la base des dépendances fonctionnelles.

En général, une décomposition BCNF aboutit à une perte de dépendance. Soit la relation : Entretiens(candidat,datexam, heure, jury, salle) avec les dépendances :

candidat, datexam ? heure, jury, salle jury, datexam, heure ? candidat jury, datexam ? salle

La relation ci-dessus contient des dépendances transitives partielles et nécessite, pour éviter des anomalies de mise à jour, la transformation en deux relations BCNF :

Entretiens(candidat,datexam,heure,jury) Planning(jury,datexam, salle) La seconde DF est perdue.

      3.4.5      Dépendances multivaluées

La décomposition BCNF est insuffisante pour éliminer totalement toutes les anomalies de fonctionnement et les redondances.

La relation Etudiants(numetud, cours, sport) indique quels cours suit et quels sports pratique un

étudiant. Elle n’est pas 3NF et il n’y a même pas de dépendance fonctionnelles entre les données, ainsi qu’on peut le constater sur l’extension suivante ou` aucune clé ne peut être trouvée :

Numetud

Cours

Sport

100

BD

Tennis

100

BD

Football

200

BD

Vélo

200

CL

Footing

En fait, on trouve des dépendances multivaluées, les valeurs des attributs cours et sport étant intercorrellées par l’attribut numetud.

On dit qu’il y a multi-détermination entre des ensembles d’attributs X et Y ou encore que X multidétermine Y (X ³ Y ) lorsqu’il existe un ensemble Z tel que, si z ? Z, x1 ? X, x2 ? X, y1 ? Y , et y2 ? Y , si x1zy1 et x2zy2 sont présents dans la relation R, alors x1zy2 et x2zy1 y sont aussi représentés (ou susceptibles de l’être).

X Z                                                            Y

Ces dépendances multivaluées (DM) sont régies par les axiomes suivants :

–   Complémentation : X ³ Y ?            X ³ R ? X ? Y

–   Multi-augmantation : Si X ³ Y , et si W est un ensemble d’attributs de R, alors XW ³ Y W

–   Pseudo-transitivité : si X ³ Y et Y ³ Z            ?            X ³ Z ? Y



813