Base de données relationnelles 1

Chapitre 4: La Normalisation d’une Relation

Plan

 Normalisation d’une relation

 But et principe
 Dépendance Fonctionnelle
 Les Formes Normales : 1ère, 2ème, 3ème FN, et BCNF
 TD1:DF
 TD2:Normalisation
Gestion de la cohérence
 Un schéma conceptuel relationnel est l’ensemble des
relations qui permettent la meilleur représentation des
entités et des liens connus.
 Cette représentation doit être suffisante pour répondre
aux demandes des utilisateurs dans des délais
raisonnables.
 L’ensemble des relations issues du schéma conceptuel
doivent vérifier des critères de cohérence tel que les
dépendances entre les données et les formes
normales.
Les dépendances de données

 Les dépendances représentent des liens sémantiques

entre des données élémentaires. Elles sont toujours
définies par rapport à une relation.
 Il existe plusieurs types de dépendances: fonctionnelles,
multivaluées, hiérarchiques,…
 Nous nous limiterons aux dépendances fonctionnelles
puisqu’elles sont les plus intéressantes.
 Les dépendances fonctionnelles

 Définition (dépendance fonctionnelle) :

Soit R(A1,A2,...An) un schéma de relation, et X et Y des

sous ensembles de {A1,A2,...An}. On dit que X détermine
Y ou que Y dépend fonctionnellement de X si, et
seulement si, des valeurs identiques de X impliquent
des valeurs identiques de Y. On le note : X -> Y
Les dépendances fonctionnelles

 On symbolise la dépendance fonctionnelle par A -> B

où:
 A est appelé source de la DF (on dit aussi déterminant ou partie
gauche)
 et B la cible (on dit aussi but, déterminé ou partie droite) de la DF.
Exemples :
 NumClient -> NomClient
 NumCLient -> AdresseClient
 RefProduit -> LibProduit
Les dépendances fonctionnelles
Exemple :
 Soit le schéma de relation PERSONNE (No_SS,
Nom, Adresse, Age, Profession).
 Les dépendances fonctionnelles qui s'appliquent sur
ce schéma de relation sont les suivantes :
 No_SS -> Nom,
 No_SS -> Adresse,
 No_SS -> Age,
 No_SS -> Profession.
 On pourra aussi écrire : No_SS -> Nom Adresse Age
Profession.
 Les dépendances fonctionnelles
DF forte:
 La DF associe à chaque valeur de A une et une seule de B : il y a
unicité au départ
 la DF est vérifiée pour toutes les valeurs de A : il y a totalité au
départ (toutes les valeurs de A ont une image dans l’ensemble
d’arrivée B)
Exemple :
 la dépendance fonctionnelle NumCommande -> NumClient
est une DF forte car il n’y a pas de commande sans client.
Les dépendances fonctionnelles
DF faible:
 Il y a dépendance fonctionnelle entre A et B lorsque,
connaissant une valeur de A, quelque soit cette valeur, on
détermine au plus une valeur de B.

 Cette définition supprime la contrainte de totalité au

départ. On parle de DF faible. Certaines valeurs de A
n'ont pas de valeurs de B.
Les dépendances fonctionnelles
DF à partie gauche composée:
 Une dépendance fonctionnelle peut comporter dans sa
partie gauche plusieurs attributs. On parle dans ce cas de
dépendance fonctionnelle à partie gauche
composée.
 Pour connaître une valeur de l’ensemble d’arrivée C,
il faut connaître un couple (ou plus) de valeurs provenant
de A et de B.
 Ce type de DF est noté : (d1, d2) -> d3
Les dépendances fonctionnelles
DF à partie gauche composée:
Exemples :
 (NoFacture, CodeProduit) ->QtéFacturée,
 (NoElève, Matière, Date) -> Note

 Je ne peux connaître la note d’un étudiant en Français

pour le devoir du 10 mai que si je connais ces trois
éléments : Le code de l'élève , la matière concernée et la
date. S'il manque l'un quelconque de ces éléments, je ne
peux pas déterminer avec exactitude la note
correspondante.
Les dépendances fonctionnelles
DF élémentaire:
 Une dépendance fonctionnelle est élémentaire s’il
n’existe aucune donnée ou sous-ensemble de
données de la partie gauche assurant une
dépendance fonctionnelle vers le même but.
 Par définition les dépendances fonctionnelles à deux
rubriques (A-> B) sont toujours élémentaires.
Les dépendances fonctionnelles
DF élémentaire:
Exemples :
 RefProduit -> LibProduit est élémentaire (deux
rubriques).

(NumFacture, RefProduit) -> QtéFacturée est
élémentaire (ni la référence produit seule, ni le numéro
de facture seul permettent de déterminer la quantité).

(NumFacture, RefProduit) -> LibProduit n’est pas
élémentaire puisque la référence du produit suffit à
déterminer le libellé.
Les dépendances fonctionnelles
DF directe:
Une dépendance fonctionnelle d1 -> d2 est directe s’il
n’existe aucune donnée d3 qui engendrerait une
dépendance fonctionnelle transitive telle que d1 -> d2
-> d3.
Exemple, soient les dépendances fonctionnelles :
 NumFacture -> NumReprésentant et
 NumReprésentant -> NomReprésentant

- NumFacture -> NomReprésentant n’est pas une
dépendance fonctionnelle directe puisqu’elle est
obtenue par transitivité.
Les dépendances fonctionnelles
Exercice:
 Nous définissons les propriétés vérifiées par une base
baignades. Deux personnes distinctes peuvent, par
exemple, porter le même nom, le même prénom, et avoir
le même qualité de nage. Deux numéro de nageur
différent les distinguent l’une de l’autre.
 Nous pouvons également supposer que deux plages
distinctes ont toujours deux numéro différents. Une plage
se trouve dans une région. La pollution et le type sont
propre à une plage, et que deux plages de la même région
ne peuvent pas porter le même nom.
Les dépendances fonctionnelles
Graphe des DF:
 C’est une représentation graphique permettant de
visualiser aisément toutes les dépendances fonctionnelles.

Exemple: toutes les DF citées précédemment peuvent être
représentées de la façon suivantes:
Les règles d’inférences(Axiomes d’Armstrong)
 A partir d'un ensemble F de dépendances fonctionnelles
entre les attributs d'un schéma de relation R, on peut en
déduire d'autres à partir des trois propriétés suivantes :
 Transitivité : si X -> Y, et Y -> Z, alors X -> Z,
 Augmentation : si X -> Y, alors XZ -> YZ pour tout
groupe Z d'attributs appartenant au schéma de relation,
 Réflexivité : si X contient Y, alors X -> Y.
 Les règles d’inférences(Axiomes
d’Armstrong)
 Règles additionnelles:

1- Si X-> YZ alors X-> Y * Projection

2- Si X->Y, X->Z alors X->YZ * Union
3- Si X->Y et WY->Z alors WX-> Z * Pseudo-transitivité
4- Si X->YZ alors X->Y, X->Z * Décomposition
5- X->X * Réflexivité
6- Si X->Y et V->Z alors XV-> YZ * Composition
7- SI X->Y alors XW->Y * Augmentation à
 gauche.
La fermeture d’un attribut
 La fermeture d'un ensemble d'attributs X, notée (X)+,
représente l'ensemble des attributs de R qui peuvent être
déduits de X à partir d'une famille de dépendances
fonctionnelles en appliquant les axiomes d'Armstrong. Ainsi, Y
sera inclus dans (X)+ ssi X -> Y.
La fermeture d’un attribut: Algorithme
La fermeture d’un attribut
Exemple: les employés et leurs projets

 EP={SS#, Enom, P#, Loc, Temps}

 F={SS# ->Enom; P#->{Pnom,Loc}; {SS#,P#}->Temps}

 SS#+ ={SS#, ENom}

 P#+ ={P#, Pnom, Loc}
 {SS#,P#}+ = {S#, P#, Enom, Pnom, Loc,Temps}
Notions de clé:clé candidate, clé
primaire,super-clé, clé étrangère
 Soit R une relation, une clé candidate C pour R, est un sous
ensemble d’attributs de R tq:
 Il n’existe pas deux n-uplets distincts dans R ayant la même
valeur C(propriété d’unicité)
 Aucun sous ensemble strict de C ne possède la propriété
d’unicité(propriété d’irréductibilité)

 Soit la relation Produit(NumP, Désignation,PrixU), sachant

qu’il n’existe pas deux produits différents ayant le même
numéro ni la même désignation
La relation Produit a 2 clés candidates: NumP et
Désignation
Notions de clé:clé candidate, clé
primaire,super-clé, clé étrangère
Clé primaire
 Si la relation a plusieurs clés candidates, le modèle
relationnel exige que seule une de ces clés candidates
soit choisie comme clé pour cette relation qu’on
appellera clé primaire; les autres clés sont appelées clés
alternatives.
 La relation Produit a 2 clés candidates NumP et
Désignation. On choisit une des deux comme clé
primaire, soit NumP.
 Définition d’une Superclé
 Une super-clé pour une relation R est un ensemble de R
inclut au moins une clé candidate de R.
Notions de clé:clé candidate, clé
primaire,super-clé, clé étrangère
Remarque
 Une super-clé a la propriété d’unicité , mais pas la
propriété d’irréductibilité
 Une clé candidate est une super-clé, l’inverse n’est pas
vrai
Fermeture des dépendances fonctionnelles
Fermeture de DFs:
 Soit R une relation et F un ensemble de DFs satisfaites
par R. On appelle fermeture de F(noté F+), l’ensemble de
toutes les DFs qui sont impliquées(dérivées) par les DFs
de F.
Couverture:
 Soit R une relation et F1, F2 deux ensembles de DFs
définies dans R, F1 est une couverture de F2 Ssi F2+ est
inclus dans F1+
 Remarque: Pour montrer que F1 est une couverture de
F2, il suffit de montrer que toute DF de F2 appartient à
F1+(est dérivable à partir des DFs de F1)
Fermeture des dépendances fonctionnelles
Ensembles de DFs équivalents:
 Soit R une relation, F1 et F2 ensembles de DFs définies
dans R, F1 et F2 sont équivalents ssi F1+=F2+
 Ou encore, Ssi F1 est une couverture de F2 et F2 est une
couverture de F1.
Théorie de la normalisation

La normalisation permet de garantir que le schéma

Relationnel est un bon schéma.
Normalisation
Exemple de mauvais schéma:
 Considérons la relation enseignant suivante:


On a la contrainte suivante: tous les enseignants de la

même classe et de la même catégorie gagnent le même
salaire:
 CATEGORIE, CLASSE -> SALAIRE
Normalisation
 Exemple de mauvais schéma:
 Il y a dans cette relation des
redondances de données. Ceci
conduit à des anomalies
de stockage(anomalies lors des
opérations de mise à jour)

 Anomalie de modification: S’il y a

une modification du salaire pour le
MC 1er classe, on fait autant
d’opération de modification qu’il y a
d’enseignants de cette catégorie et
de cette classe.
Normalisation
Exemple de mauvais schéma:
 Anomalie d’insertion: Pour
pouvoir stocker le salaire MC
2eme classe, il faut qu’il y ait au
moins un enseignant dans cette
catégorie et dans cette classe.
 Anomalie de suppression: Si
l’unique professeur de la classe 2
part, on perd l’information sur le
salaire des professeurs de la
classe 2.
Normalisation
 L’objectif de la normalisation est d’éliminer les anomalies de
stockage et éliminer les redondances.

 La normalisation consiste à éclater une relation en plusieurs:

Décomposition.

 Elle comprend plusieurs étapes: 1FN, 2FN, 3FN, BCNF

Décomposition d'un schéma relationnel
 La décomposition consiste à remplacer un schéma R (A1,
A2, …, An) par un ensemble de schémas T = {R1, R2, …,
Rk} tels que R = R1 U R2 U … U Rk.
Exemple : Soit le schéma de relation
 FOURNISSEUR (Nom_F, Adresse_F, Produit, Prix).

 Les dépendances fonctionnelles s'appliquant sur ce

schéma sont les suivantes :
 F = {Nom_F -> Adresse_F ; Nom_F, Produit ->
Prix}.
Décomposition d'un schéma relationnel
Exemple (suite) :
 Une décomposition possible de ce schéma aboutit aux
schémas:
 R1 = (Nom_F, Adresse_F),
 R2 = (Nom_F, Produit, Prix).
 Il est alors possible avec cette décomposition d'ajouter
ou de modifier un fournisseur dans la relation R1 sans
incidence sur la relation R2.
 Avant de supprimer un fournisseur dans R1, il faudra
quand même s'assurer qu'il n'y a plus de produits
correspondant à ce fournisseur dans R2.
Décomposition d'un schéma relationnel
Exemple (suite) :
 Si fournisseur est la relation (table contenant des
données) correspondant au schéma FOURNISSEUR,
alors en décomposant on aura :
 r1 = Π Nom_F Adresse (fournisseur) et
 r2 = Π Nom_F Produit Prix (fournisseur)

 La jointure des relations r1 et r2 redonnera la relation

fournisseur.
Décomposition d'un schéma relationnel
 Décomposition sans perte d’information:

On remplace une relation R par ses projections Ri, i=1,2…

telle que la jointure R’ des Ri est égale à R, c-à-d. pour
toute extension de R:
 Il n’y a pas de tuples de R qui manquent dans R’.
 Il n’y a pas de tuples en plus dans R’ par rapport à R.
Décomposition d'un schéma relationnel
 Décomposition sans perte de dépendances:

Soit un schéma de décomposition T = {R1, R2, …, Rk}, et
un ensemble F de dépendances fonctionnelles.

On dit que T préserve les dépendances fonctionnelles
si Π R1 (F) U Π R2 (F) … U Π Rk (F) permet de
retrouver l'ensemble F d'origine.
Décomposition d'un schéma relationnel

 Exemple :
 Soit le schéma de relation R (Nom_F, Adresse_F, Produit,
Prix), avec comme ensemble de dépendances
fonctionnelles F = { Nom_F ->
Adresse_F ; Nom_F Produit -> Prix }.
 Considérons la décomposition de ce schéma en :
 R1 = (Nom_F, Adresse_F),
 R2 = (Nom_F, Produit, Prix).
 On a alors :
 Π R1 (F) = {Nom_F -> Adresse_F},
 Π R2 (F) = {Nom_F Produit -> Prix},
 Π R1 (F) U Π R2 (F) = F.
 et la décomposition préserve donc les dépendances.
Première forme normale
 Définition (Première forme normale) : Une relation
est en première forme normale si et seulement si tout
attribut contient une valeur atomique (non
décomposable)
Contre-exemple
ELEVE (no_elv, nom, prenom, liste_notes)
Un attribut ne peut pas être un ensemble de valeurs
Décomposition
ELEVE (no_elv, nom, prenom)
NOTE (no_elv, no_matiere, note)
.
Deuxième forme normale
Définition (Deuxième forme normale) :
 La deuxième forme normale concerne les tables
dont la clé est constituée de plusieurs attributs.
 Une relation est en deuxième forme normale si et
seulement si :
· elle est en première forme normale ;
· tout attribut n'appartenant pas à une clé ne dépend
pas que d'une partie de cette clé.
 Autrement dit, il faut éviter la configuration suivante:

Deuxième forme normale
Exemple de relation non en 2FN:
 Enseignant(Num, CodeMatiére, Nom, VolumeHoraire)
avec Num-> Nom.

Graphiquement:
Deuxième forme normale
Comment normaliser en 2FN:
 Isoler la DF partielle dans une nouvelle relation.
 Eliminer l’attribut cible de la DF de la relation initiale.

Exemple:
 Enseignement(Num, CodeMatiére,VolumeHoraire)
 Enseignant(Num, Nom)
Deuxième forme normale
 Remarque: un couple clé primaire, clé étrangère est
apparu.

Une relation en 1FN, dont la clé est mono-attribut
est forcément en 2FN
Troisième forme normale

Une relation est dite en 3FN si:

 Elle est en 2FN.
 Elle ne contient pas de DF transitive entre des attributs
non clé.

Exemple:
 Enseignant(Num, Nom, Catégorie, Classe, Salaire) avec
Catégorie, Classe ->Salaire
Troisième forme normale
 Comment normaliser en 3FN:
 Isoler la DF transitive dans une nouvelle relation.
 Eliminer l’attribut cible de la DF de la relation initiale.

Exemple:
 Enseignant(Num, Nom, Catégorie, Classe)
 Salaire(Catégorie, Classe, Salaire)
Troisième forme normale
 Exemple (suite):

 Opérations de mise à jour:

 Modification: si le salaire de MC 1er classe change, une
seule modification.
 Insertion: On peut stocker le salaire des MC 2ème classe,
sans avoir d’enseignant dans cette catégorie.
 Suppression: si le professeur en 2ème classe part, on
conserve le salaire des professeur de la classe 2.
Forme normale de Boyce/Codd
Définition de la forme normale de Boyce/Codd(BCNF)
 Une relation est en BCNF Ssi les seuls déterminants sont
des clés candidates
 Le BCNF impose qu’il ne peut pas exister dans une
relation, d’autres DFs que celles qui partent des clés
candidates
Exemple de relation en BCNF
 La décomposition de la relation Enseignant en
Enseignant2 et locaux est en BCNF
 Enseignant2(Nom, Bureau, Batiment): BCNF
 Locaux(Batiment,Discipline) : BCNF
Forme normale de Boyce/Codd
 Considérons la relation Cours(Matiere,Classe,professeur),
avec les règles de gestion suivantes:
 Un prof n’enseigne qu’une seule matière
 Une classe n’a qu’un seul enseignant par matière
 Desquelles on déduit les DFs{Matière,Classe->Professeur,
Professeur->Matière)
 Cette relation est en 3 FN, mais pas en BCNF.
 Il est impossible d’insérer un professeur dans classe
affectée(puisque classe est une partie de la clé primaire
de la table Cours), et la disparition d’une classe peut
entrainer la disparition de professeur.
Forme normale de Boyce/Codd
 La relation Cours peu être décomposée en 2 relations
BCNF:
 Spécialité(Professeur, Matière)
 Enseignant(Classe, professeur)
 La première DF serait alors perdue
Modèle normalisé
Résumé
Modèle normalisé = relations avec
 une clé, qui permet de distinguer chaque
occurrence
 des attributs élémentaires (1FN)
 en dépendance de TOUTE la clé (2FN),
 et RIEN QUE de la clé (3FN)