Cours complet pour apprendre les différents types de bases de données et le langage SQL


précédentsommairesuivant

VIII. Normalisation

VIII-A. Le problème

Mélanger dans une même relation des informations relatives à plusieurs entités entraîne, en général des redondances d'information qui provoquent les anomalies suivantes :

  • anomalies d'insertion ;
  • anomalies de mise à jour ;
  • anomalies de suppression.

VIII-B. Exemple

isbn

titre

éditeur

pays

2-212-09283-0

Bases de données - objet et relationnel

Eyrolles

France

2-7117-8645-5

Fondements des bases de données

Vuibert

USA

0-201-70872-8

Databases and Transaction Processing

Addison Wesley

USA

2-212-09069-2

Internet/Intranet et bases de données

Eyrolles

France

Cette relation qui décrit des livres et leurs éditeurs, contient des redondances provoquant les anomalies suivantes :

  • Insertion : il n'est pas possible d'insérer un livre sans connaître son éditeur. Attribuer une valeur nulle aux attributs éditeur et pays violerait l'intégrité d'entité : un attribut appartenant à la clé, ne doit pas avoir de valeur nulle.
  • Mise à jour : si un éditeur change de pays, il faut modifier ce pays pour chacun des livres qu'il a édités.
  • Suppression : si l'unique livre publié par un éditeur est supprimé, l'information sur cet éditeur est perdue. Attribuer une valeur nulle aux attributs isbn et titre violerait l'intégrité d'entité.

VIII-C. Solution

La solution à ces problèmes consiste à normaliser la relation en cause en la décomposant en plusieurs relations.

Cette décomposition s'appuie sur les dépendances qui existent entre les attributs de la relation initiale :

  • dépendances fonctionnelles ;
  • dépendances multivaluées.

Par exemple, la dépendance entre l'ISBN d'un livre et son titre ou bien entre le nom d'un éditeur et son pays.

VIII-D. Dépendances fonctionnelles

Il y a une dépendance fonctionnelle entre un constituant X et un constituant Y d'une relation R si pour toute extension de R, à chaque valeur de X il correspond toujours la même valeur de Y.

On dit que X détermine fonctionnellement Y et l'on note :

  • X → Y

Un constituant {A1, …, An} apparaissant à gauche ou à droite du signe → sera noté A1 … An.

VIII-D-1. Dépendances fonctionnelles triviales

Une dépendance fonctionnelle X → Y est dite triviale si Y est un sous-ensemble de X ou bien si Y est vide.

Par exemple, les dépendances :

  • isbn titre → pitre
  • éditeur pays → Ø

sont triviales.

VIII-D-2. Propriétés des dépendances fonctionnelles

À partir d'un ensemble de dépendances fonctionnelles, on peut en déduire d'autres.

Par exemple, à partir des dépendances :

  • éditeur → ville
  • ville → pays

on peut déduire, par transitivité, la dépendance :

  • éditeur → pays

Étant donné un ensemble de dépendances fonctionnelles F construit sur l'ensemble R des attributs d'une relation, l'ensemble F+ (fermeture de F) de toutes les dépendances fonctionnelles logiquement impliquées par F peut être calculé à partir des trois règles suivantes (axiomes d'Armstrong) :

  • (réflexivité) si Y ⊆ X ⊆ R alors X → Y
  • (augmentation) si X → Y et Z ⊆ R alors X ∪ Z → Y ∪ Z
  • (transitivité) si X → Y et Y → Z alors X → Z

Des axiomes d'Armstrong, on peut déduire deux règles plus pratiques pour calculer F+ :

  • (union) si X → Y et X → Z alors X → Y ∪ Z.
  • (décomposition) si X → Y ∪ Z alors X → Y et X → Z.

VIII-D-3. Dépendances fonctionnelles et clés

On peut définir une clé d'une relation comme un sous-ensemble de ses attributs qui détermine tous les autres.

Un constituant X d'une relation R(A1, …, An) est une clé de cette relation si et seulement si :

  • X → A1, …, An,
  • il n'existe pas de constituant Y inclus dans X tel que Y → A1, …, An.

Étant données une relation et l'une de ses clés, on appelle :

  • attribut clé un attribut qui appartient à cette clé ;
  • attribut non clé un attribut qui ne lui appartient pas.

On appelle super-clé un constituant qui inclut une clé.

Par exemple dans la relation :

  • personne(nom, prénom, age)

de clé {nom, prénom} :

  • nom et prénom sont des attributs clés ;
  • age est un attribut non clé ;
  • {nom, prénom, age} est une super-clé.

VIII-D-4. Normalisation d'une relation

La normalisation d'une relation consiste à la décomposer en un ensemble de relations telles qu'aucune des relations obtenues ne possède les anomalies de redondance, de mise à jour et de suppression.

Relativement aux dépendances fonctionnelles, on distingue quatre formes normales :

  • la 1re forme normale ;
  • la 2e forme normale ;
  • la 3e forme normale ;
  • la forme normale de Boyce-Codd qui est la plus aboutie.

Ce sont les deux dernières que l'on cherche à atteindre :

  • la 1re est impliquée par l'atomicité des valeurs ;
  • la 2e n'est qu'une étape vers la 3e.

VIII-D-4-a. Propriétés d'une décomposition

Soit R une relation et R1, …, Rn les relations issues d'une décomposition D de R :

  • D est sans perte si la relation R peut être recomposée par jointures des relations R1, …, Rn.
  • D préserve les dépendances fonctionnelles si les dépendances fonctionnelles de R sont impliquées par les dépendances fonctionnelles de R1, …, Rn.

VIII-D-4-b. 1re forme normale

Une relation est en 1re forme normale si tous ses attributs ont une valeur atomique.

Le fait que, dans le modèle relationnel, les domaines soient atomiques implique que toutes les relations sont en 1re forme normale.

Image non disponible

VIII-D-4-c. 2e forme normale

Une relation est en 2e forme normale si elle est en 1re forme normale et si chaque attribut non-clé dépend totalement et non partiellement de la clé primaire.

Image non disponible

Cette décomposition est sans perte et préserve les dépendances fonctionnelles.

VIII-D-4-c-i. Insuffisance de la 2e forme normale
Image non disponible

Il reste des redondances : (…, Eyrolles, France).

VIII-D-4-d. 3e forme normale

Une relation est en 3e forme normale si pour chaque dépendance fonctionnelle non triviale X → Y, on a :

  • soit, X est une super-clé de R ;
  • soit, Y appartient à une clé candidate de R.

La 2e partie de la règle est importante, car elle dit qu'un constituant d'une clé candidate peut dépendre :

  • soit d'un constituant d'une clé candidate ;
  • soit d'un constituant non-clé ;

ce qui peut être source de redondances.

Image non disponible

Cette décomposition est sans perte et préserve les dépendances fonctionnelles.

Image non disponible

Cette décomposition est sans perte et préserve les dépendances fonctionnelles.

VIII-D-4-d-i. Insuffisance de la 3e forme normale
Image non disponible

Il reste des redondances : (…, 83100, Toulon).

VIII-D-4-e. Forme normale de Boyce-Codd

Une relation R est en forme normale de Boyce-Codd (FNBC) si, pour chaque dépendance fonctionnelle non triviale X → Y, X est une super-clé de R.

La forme normale de Boyce-Codd implique la 3e forme normale.

La forme normale de Boyce-Codd est la forme idéale relativement aux dépendances fonctionnelles, mais malheureusement elle peut ne pas préserver les dépendances fonctionnelles.

Image non disponible

Cette décomposition est sans perte, mais ne préserve pas les dépendances fonctionnelles.

VIII-D-4-f. Décomposition en 3e forme normale et en FNBC

Il est démontré que :

  • toute relation a au moins une décomposition en 3e forme normale qui préserve les dépendances fonctionnelles et qui est sans perte ;
  • toute relation a au moins une décomposition en forme normale de Boyce-Codd qui est sans perte, mais qui peut ne pas préserver les dépendances fonctionnelles.

VIII-E. Dépendances multivaluées

Il y a une dépendance multivaluée entre un constituant X et un constituant Y d'une relation R(X, Y, Z) si, pour toute extension de R, à chaque valeur de X il correspond toujours le même ensemble de valeurs de Y et que cet ensemble de valeurs ne dépend pas des valeurs de Z.

On dit que X multidétermine Y et l'on note :

  • X →→ Y

Soit par exemple la relation :

  • livre(isbn, titre, auteur)

Si un livre peut avoir plusieurs auteurs, la relation livre possède la dépendance multivaluée :

  • isbn →→ auteur

Soit un livre d'isbn i et d'auteurs a1, a2 et a3. Si le triplet (i, t, a1) apparaît dans une extension de la relation livre, alors les triplets (i, t, a2) et (i, t, a3) doivent y apparaître aussi.

VIII-E-1. 4e forme normale

Une dépendance multivaluée X →→ Y d'une relation R est dite non triviale si :

  • Y n'est pas un sous-ensemble de X ;
  • X ∪ Y n'inclut pas tous les attributs de R.

Une relation R est en 4e forme normale, si pour chaque dépendance multivaluée X →→ Y non triviale, X est une super-clé de R.

La 4e forme normale implique la forme normale de Boyce-Codd puisqu'une dépendance fonctionnelle est un cas particulier de dépendance multivaluée.

Image non disponible

Cette décomposition est sans perte et préserve les dépendances fonctionnelles.

VIII-E-2. Décomposition en 4e forme normale

Il est démontré que toute relation a au moins une décomposition en 4e forme normale qui est sans perte, mais qui peut ne pas préserver les dépendances fonctionnelles.

Soit U la relation à décomposer et D l'ensemble des dépendances existantes entre les attributs de U :

  • S := {U}
  • Tant qu'il existe dans S une relation R qui n'est pas en 4e forme normale :

    • on cherche dans D une dépendance X →→ Y telle que R(X, Y, Z) et X n'est pas une clé de R,
    • on ajoute à Y l'ensemble Z' des attributs de Z fonctionnellement déterminés par X, produisant la dépendance X →→ Y Z',
    • on remplace R dans S par les deux relations R1(X, Y ∪ Z') et R2(X, Z - Z').

S = {U(isbn, titre, auteur, mot_clé, éditeur, pays, bib, nb_ex)}

D = {isbn → titre,

     isbn → éditeur,

     éditeur → pays,

     isbn →→ auteur, isbn →→ mot_clé,

     isbn bib → nb_ex}

S = {U1(isbn, titre, éditeur, pays),

     U2(isbn, auteur, mot_clé, bib, nb_ex)}

S = {U1(isbn, titre, éditeur, pays),

     U21(isbn, auteur),

     U22(isbn, mot_clé, bib, nb_ex)}

S = {U1(isbn, titre, éditeur, pays),

     U21(isbn, auteur),

     U221(isbn, mot_clé),

     U222(isbn, bib, nb_ex)}

S = {U11(éditeur, pays),

     U12(isbn, titre, éditeur),

     U21(isbn, auteur),

     U221(isbn, mot_clé),

     U222(isbn, bib, nb_ex)}

Les relations de S sont en 4e forme normale (et donc en forme normale de Boyce-Codd) et les dépendances sont préservées.

VIII-F. Bilan

 

3FN

FNBC

4FN

Élimination de la redondance due aux dépendances fonctionnelles

Pas toutes

Oui

Oui

Élimination de la redondance due aux dépendances multivaluées

Non

Non

Oui

Préservation des dépendances fonctionnelles

Oui

Pas toujours

Pas toujours

Préservation des dépendances multivaluées

Pas toujours

Pas toujours

Pas toujours


précédentsommairesuivant

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+