Normalisation
Inventée et théorisée par Ted Codd (1923-2003)
• Objectifs
• Dépendance fonctionnelle
• 1FN, 2FN,3FN etc.
Normalisation
Permet de définir une méthode de conception de
"bonnes" tables, c'est-à-dire sans redondances et sans
perte d'information
Redondances et erreurs
Normalisation : pourquoi ?
Pour éliminer les redondances
Pour mieux comprendre les relations
sémantiques entre les données
Pour éviter les incohérences de mise à jour
Pour éviter, autant que possible, les valeurs
nulles
Normalisation : comment ?
Approche par décomposition
A partir d’une table contenant tous les attributs ,
Décomposer jusqu’à ce qu’il n’y ait plus de redondances
Approche par synthèse
A partir de l’ensemble des attributs et des
dépendances fonctionnelles constituer les tables
Processus itératif (1FN, puis 2FN, puis 3FN etc.)
Première forme normale 1FN
Définitions (T. Codd) : une relation est en première
forme normale si aucun de ses domaines ne peut
contenir des éléments qui soient eux-mêmes des
ensembles.
Une relation qui n’est pas en première forme normale
est dite non normalisée.
Contre-exemples :
PERSONNE (NOM, PRENOMS)
o En 1FN : PERSONNE (NOM, PRENOM1, PRENOM2)
PERSONNE (NOM, PRENOM, ADRESSE)
o En 1FN : PERSONNE (NOM, PRENOM, N°RUE,
RUE, CODEPOSTAL, VILLE)
Deuxième forme normale 2FN
Définition : une relation est en 2ème Forme Normale
(2FN) si :
o Elle est en 1FN
o Tout attribut non clé dépend de la clé entière et
non d’une partie seulement
Exemple
COURS (NOMPROF, VILLE, DEPARTEMENT, NOMETUD,
AGE, NOMCOURS, NOTE)
1 seule clé (NOMETUD, NOMCOURS)
Les DF
• NOMPROF → VILLE
• NOMETUD, NOMCOURS → NOTE
• VILLE → DEPARTEMENT
• NOMCOURS → NOMPROF
• NOMETUD → AGE
Problème pour les attributs NOMPROF, VILLE,
DEPARTEMENT et AGE
COURS(NOMETUD,NOMCOURS,NOTE)
R1 ( NOMCOURS,NOMPROF,VILLE,DEPARTEMENT) 2 FN
R2(NOMETUD,AGE)
Troisième forme normale 3FN
Une relation est en troisième forme normale (3FN) si :
Elle est en 2 FN
Aucune DF entre deux attributs non clé
Exemple :
COURS (NOMETUD NOMCOURS NOTE)
R1 (NOMCOURS NOMPROF VILLE DEPARTEMENT)
R2 (NOMETUD AGE)
R1 n'est pas en 3 FN car NOMPROF →VILLE et
VILLE → DEPARTEMENT
R1 (NOMCOURS NOMPROF)
• R3 (NOMPROF VILLE DEPARTEMENT)
R3 n'est pas en 3 FN car VILLE →DEPARTEMENT
R3 (NOMPROF VILLE)
R4 (VILLE DEPARTEMENT)
Algorithme de mise sous 3 FN
0FN → 1FN : mise sous forme atomique des attributs
1FN → 2FN : pour chaque partie X de clé déterminant
des attributs non clés Y1, …, Yn
Création d’une relation supplémentaire avec X
pour clé et Y1, …, Yn comme attributs non clés
Retrait de Y1, …, Yn de la relation initiale
2FN → 3FN : pour chaque attribut non clé Y
déterminant des attributs non clés Z1, …, Zn
Création d’une relation R' supplémentaire
avec Y comme clé et Z1, …, Zn comme attributs
non clés
Retrait de Z1, …, Zn de la relation initiale
Si R' n'est pas en 3 FN, réitérer le processus sur R'
Dans une décomposition d'une relation en plusieurs
autres, on dit que la décomposition préserve une
dépendance fonctionnelle s'il reste, après
décomposition, une relation contenant tous les
attributs de la DF
Propriété : toute relation a au moins une
décomposition en 3 FN qui
préserve une couverture minimale de DF
est sans perte
Une relation en 3FN peut encore rencontrer des
redondances
Exemple : R(VILLE, DEPARTEMENT, CODE POSTAL)
avec les DF :
VILLE, DEPARTEMENT → CODE
CODE → DEPARTEMENT
et la clé : VILLE, DEPARTEMENT
les redondances : pour toutes les villes ayant le
Même code postal, répétition du département.
Problème : une DF d'un attribut non clé vers une
partie de la clé
Forme Normale de BOYCE-CODD
Définition : les seules DF autorisées sont celles dans
lesquelles une clé détermine un attribut
Exemple :
R (VILLE, DEPARTEMENT, CODE POSTAL) n'est pas en BCNF
R peut être décomposée en
R1 (VILLE, CODE POSTAL)
R2 (CODE POSTAL, DEPARTEMENT)
Ne garde pas la DF : VILLE, DEPARTEMENT → CODE.
R1 et R2 sont en BCNF.
Problème résolu ? Non, encore des redondances…
Exemple
« L'étudiant de numéro NUMETUD pratique le sport
SPORT et suit le COURS »
Pas de DF
CLE = {NUMETUD, SPORT, COURS}
R est en 3FN et en BCNF
Cependant R contient des redondances :
Dépendance multivaluée
La notion de dépendance fonctionnelle ne suffit pas
à définir toutes les dépendances entre les données
Dépendance multivaluée (DM)
R (A1, A2, …, An)
X et Y sous-ensembles de {A1, A2, …, An}
X ->> Y : « X multidétermine Y » si, soit Z = R - X - Y,
{(xyz) et (xy'z') ∈ R => (xy'z) et (xyz') ∈ R }
"A chaque valeur de X, il y a un ensemble de
valeurs de Y associées et cet ensemble est
indépendant des autres attributs »
•Propriété : s'il y a la DM X-->>Y alors il y a aussi X-->>Z
On note : X-->>Y|Z
• Exemple : R (NUMETUD, SPORT, COURS)
NUMETUD->>SPORT et NUMETUD->>COURS
Pas de lien entre les cours suivis et les sports pratiqués
• Contre-exemple : R (NUMEMP, LANGUE, PRODUIT)
"L'employé NUMEMP parle LANGUE et vend PRODUIT"
Si pour vendre un produit, il faut parler la langue du
pays où il est distribué, il n'y a pas de DM (dépend.
multiv.)
Quatrième forme normale : 4FN
• Une relation est en 4FN si les seules DM sont celles
dans lesquelles une clé multidétermine un attribut
•Autrement dit, la 4FN permet de séparer des faits
multivalués indépendants qui auraient été réunis
dans une même relation
• 4FN => 3FN et BCNF
• En fait, on ne considère que les DM élémentaires
(parties gauche et droite minimale)
Exemple : PSL (PERSONNE, SPECIALITE, LANGUE)
PSL est en 3 FN
Cette relation pose quelques problèmes !!
•Adjonction nouvelle spécialité (ou langue) pour Ali
Quel(s) tuple(s)s insérer?
• Problème inverse pour la suppression.
• Croissance multiplicative
• Redondances
Solution:
Pas de redondance. Croissance additive.
On dit qu'on est passé à la 4e Forme Normale (4FN)
on a : PERSONNE −>> SPECIALITE
et aussi PERSONNE −>> LANGUE
i.e.
PERSONNE −>> SPECIALITE | LANGUE
Cette DMV exprime que la relation entre une
personne et la langue parlée n'a rien à voir avec sa
spécialité.
Si
<Ali, Cinéma, Arabe> et <Ali, Peinture, Anglais>
sont vrais,
Alors
<Ali, Peinture, Arabe> et <Ali, Cinéma, Anglais>
sont vrais aussi.
Remarque Importante:
Soit R (X, Y, Z) un schéma de relation
Si X −> Y Alors X −>> Y
Autrement dit une DF est un cas particulier de DM
Proposition: Une relation R (X, Y, Z) est décomposable
en R1 (X, Y) et R2(X, Z), si et seulement si:
X −>> Y | Z
Dans notre exemple on a:
PERSONNE −>> SPECIALITE | LANGUE
donc (et inversement),
PSL = PS * PL
Autrement dit, une relation 3FN qui n'est pas 4FN peut
toujours être remplacée par des relations 4FN.
Dépendance de jointure
Un agent représente une compagnie pour vendre
des produits.
Soit la contrainte:
«Si un agent vend un produit, et s'il représente une
compagnie faisant ce produit, alors il vend ce
produit pour cette compagnie».
Ce n'est pas le cas de Ali par exemple sans la ligne 1.
Problèmes:
• Si on n'avait que la 2e et la 3e ligne, le fait de
rajouter la ligne 4 oblige, d'après la contrainte, de
rajouter la ligne 1.
•Redondances.
•La suppression de la ligne 1, oblige à supprimer une
autre ligne pour maintenir la contrainte. (Laquelle?)
•Croissance multiplicative.
etc…
La relation ACP est en 4FN mais non en 5FN.
Solution:
On dit qu'on est passé à la 5e Forme Normale (5FN)
La contrainte précédente signifie:
Si < a, c > figure dans AC (a travaille pour c)
et < a, p > figure dans AP (a vend p)
Et < c, p > figure dans CP (c fabrique p)
ALORS < a, c, p > figure dans ACP
(a travaille pour c pour vendre p)
Autrement dit :
ACP = AC * AP * CP
On dit que ACP contient une dépendance de jointure
Exercice: Vérifier que ACP n'est égale à aucune jointure
de deux projections quelconques parmi AC, AP, CP
Définition: Une relation R (X1, X2, ..., Xn) satisfait la
Dépendance Jointure (DJ)
R1 * R2 * ... * Rn
Si et seulement si
R = R1 * R2 * ... * Rn
où Ri est la projection de R sur les attributs Xi, i dans [1..n]
Autrement dit : R est décomposable en R1, R2, ... , Rn
Exemple: ACP = AC * AP * CP
Remarque Importante: Soit R (X, A1, A2, ..., An)
Si ∀ i dans [1..n] X −> Ai {X est clé dans R}
Alors R = R [X, A1] * R [X, A2] * ... * R [X, An]
Définition: Une relation R est en 5FN si et seulement si :
Toute Dépendance Jointure de R est la conséquence
d'une clé (candidate).
Exemple:
AC, AP, CP sont en 5FN (absence de DJ)
ACP n'est pas 5FN (ACP = AC*AP*CP)
Une relation 4FN qui n'est pas 5FN peut toujours
être remplacée par des relations 5FN.
Processus de Normalisation:
Réduire par décompositions une relation R à d'autres
relations «plus simples», équivalentes à R et ayant de
meilleures propriétés.
En bref: (meilleures propriétés)
Toute sorte de contrainte (ou dépendance) figurant
dans R, doit être la conséquence de la clé.
Dans un schéma de BD, seules les clés traduisent
les dépendances entre données.
• Pour la 3FN Il s'agit des DFs
• Pour la 4FN Il s'agit des DMVs
• Pour la 5FN Il s'agit des DJs
Le processus revient formellement à :
1. Projeter 1FN:
«éliminer DFs non totales/clé» pour avoir 2FN
2. Projeter 2FN:
«éliminer DFs non directe/clé» pour avoir 3FN
2'. Projeter 3FN:
«éliminer DFs où le déterminant ne contient pas
une clé» pour avoir FNBC
3. Projeter 3FN:
«éliminer DMVs qui ne sont pas des DFs
(conséquences d'une clé)» pour avoir 4FN
4. Projeter 4FN:
«éliminer DJs qui ne sont pas conséquences
d'une clé» pour avoir 5FN
