LA NORMALISATION DES RELATIONS

Idée: Comment choisir une structure logique de données.

Quelles Relations avec quels Attributs?

I. Exemple Introductif:

Soit la relation concernant des dons de bienfaiteurs pour une association.

DONS
NOM VILLE RUE MONTAN DATE
T
Ali Tanger Du Detroit 4000 DH Janvier 2006
Ali Tanger Du Detroit 5000 DH Juin 2004
Ali Tanger Du Detroit 5000 DH Janvier 2003
Karim Casa Du Port 10000 DH Janvier 2001

• On note une redondance : 3 premiers tuples même adresse.

• Supposer Ali change d'adresse (VILLE = Marrakech, RUE =

Atlas). Risque de ne pas corriger toutes les lignes concernées. D'où
BD incohérente

• Suppression donations antérieures à 2003. Alors perte des références

d'un excellent bienfaiteur ( Karim)

Najib TOUNSI Normalisation-1

 Problème : dit : «Anomalies de Mise à Jour»

Cause : Les Redondances d'informations sont sources

d'Incohérences

Solution : On aimerait la structure suivante:

PERSONNE
NOM VILLE RUE
Ali Marrakech Atlas
Karim Casa Du Port

DONS
NOM MONTANT DATE
Ali 4000 DH Janvier 2006
Ali 5000 DH Juin 2004
Ali 5000 DH Janvier 2003
Karim 10000 DH

• L'adresse de Ali figure une seule fois.

• On a séparé des informations distinctes

(sur la personne, sur les dons).

Najib TOUNSI Normalisation-2

 Définition : Le processus de Normalisation est celui qui permet, par
étapes, d'aboutir à des relations ayant des propriétés de plus en plus
désirables.

1FN → 2FN→ 3FN→ 4FN→ 5FN

FN=Forme Normale.
• 5 formes normales possibles.
• De plus en plus désirables.

Toute relation en nième Forme Normale est aussi

en (n-1)ième Forme Normale.

NORMALISATION ⇒
• Programmation plus facile des applications
• Relations plus simples à gérer

Najib TOUNSI Normalisation-3

 1ERE FORME NORMALE

Définition : Une relation est en Première Forme Normale (1FN) si et

seulement si elle ne contient que des valeurs simples et élémentaires (non
structurées ni répétitives).

Relations Normalisées

Non en 1FN

PERE ENFANT

Aziz {Ali, Samia,

Sara}
Amine {Brahim}
PERE ENFANT
Aziz Ali
Aziz Samia
Aziz Sara
Amine Brahim

En 1FN

Non 1FN

NOM ADRESSE
Ali < 2, Rue Mali, Casa >

NOM NO RUE VILLE

Ali 2 Mali Casa

En 1FN

Najib TOUNSI Normalisation-4

Exercice : Normaliser la relation

COMMANDE

NUMCOMMANDE PRODUITS
C1 {Table 20DH, Chaise 14DH,
Micro 120DH}
C2 {Micro 120DH, Souris 15DH}

Solution :

NUMCOMMANDE PRODUIT PRIX

C1 Table 20DH
C1 Chaise 14DH
C1 Micro 120DH
C2 Micro 120DH
C2 Souris 15DH

Najib TOUNSI Normalisation-5

 2e ET 3e FORME NORMALE

Soit la relation :

FOUR1
NOM_FOUR CAT_FOUR VILLE NB_HAB PIECE QTE_EXP
Ali 40 Rabat 2 Table 300
Ali 40 Rabat 2 Chaise 400
Ali 40 Rabat 2 Armoire 500
Karim 55 Casa 3 Table 400
Karim 55 Casa 3 Chaise 300
Amine 45 Fes 1,5 Chaise 200

Quelques anomalies :

• Redondances.

• Difficulté maintenance intégrité.

• Mémoriser adresse fournisseur impossible si pas de pièce fournie. e.g.

<Aziz, 40, Rabat, 2>

• Suppression de toutes les pièces fournies par Karim fait perdre aussi son
adresse.

Il faudrait séparer dans deux tables distinctes les informations

concernant un fournisseur (propriétés immédiates) et celles
concernant les pièces fournies.

Fait_à_propos_de quelque chose bien déterminée

Najib TOUNSI Normalisation-6

 On décompose donc (PROJECTION)

EXPEDITION
NOM_FOUR PIECE QTE
Ali Table 300
Ali Chaise 400
Ali Armoire 500
Karim Table 400
Karim Chaise 300
Amine Chaise 200
FOUR2
NOM_FOUR CAT_FOUR VILLE NB_HAB
Ali 40 Rabat 2
Karim 55 Casa 3
Amine 45 Fes 1,5
Aziz 40 Rabat 2

On dit qu'on est passé à la 2e Forme Normale

• Dans la relation FOUR1, des attributs non clé (e.g. VILLE), d'une partie de
la clé (NOM_FOUR).

• Les anomalies précédentes ont ainsi été éliminées, renforçant l'intégrité de la

base.
(on a pu insérer aziz... par exemple).

Najib TOUNSI Normalisation-7

 En fait, les redondances ont juste été minimisées. Car la relation FOUR2
souffre encore de quelques anomalies.
(Exercice: Lesquelles? Considérer toujours le tuple supplémentaire
<Aziz, ..., Rabat, 2> )

• On décompose encore la relation FOUR2

FOUR3
NOM_FOUR CAT_FOUR VILLE
Ali 40 Rabat
Karim 55 Casa
Amine 45 Fes
Aziz 40 Rabat
METROPOLE
VILLE NB_HAB
Rabat 2
Casa 3
Fes 1,5

On dit qu'on est passé à la 3e Forme Normale

• Dans la relation FOUR2, des attributs non clé (e.g. NB_HAB), d'un autre
attribut non clé ( ici VILLE) .

• Il n'y a plus de redondances

Najib TOUNSI Normalisation-8

RÉSULTAT FINAL:

FOUR3
NOM_FOUR CAT_FOUR VILLE
Ali 40 Rabat
Karim 55 Casa
Amine 45 Fes
Aziz 40 Rabat

METROPOLE
VILLE NB_HAB
Rabat 2
Casa 3
Fes 1,5

EXPEDITION
NOM_FOUR PIECE QTE
Ali Table 300
Ali Chaise 400
Ali Armoire 500
Karim Table 400
Karim Chaise 300
Amine Chaise 200

Najib TOUNSI Normalisation-9

II. Généralisation et Définitions:

Définition : Dans une relation, un attribut B est dit fonctionnellement

dépendant d'un attribut A, ssi:

Deux tuples qui ont une même valeur pour A doivent avoir une même valeur
pour B.

• On dit que
A détermine B,

• et qu'il y a une
Dépendance fonctionnelle entre A et B.

• et on note : A→B

Exemple :

A … B …
a 1
b 2
a 1
c 1
b 2
A→B
A … B …
a 1
b 2
a 3
c 1
b 2
A ⎯/→ B

Najib TOUNSI Normalisation-10

Extension : On étend la définition à une collection d’attributs.

A B C D …
a a 1 2
b c 2 4
a b 1 5
c d 1 4
b c 2 4

A, B → C, D

Notée aussi : AB → CD
S’il n’y a pas d’ambiguïté.

Najib TOUNSI Normalisation-11

 Exemples de DFs :

NOM_FOUR → CAT_FOUR
NOM_FOUR → VILLE

en notation plus concise: NOM_FOUR → CAT_FOUR,VILLE

VILLE → NB_HAB
NOM_FOUR, PIECE → QTE

Lire : NOM_FOUR détermine CAT_FOUR

Comprendre : Pour un fournisseur donné, la catégorie est unique, ou bien un

fournisseur n'a qu'une seule catégorie, etc…

Najib TOUNSI Normalisation-12

Propriétés des DFs:

...X, Y, Z représentent des attributs (éventuellement composés).

(a) X → W pour tout W⊂X (réflexivité)

(b) si X → Y alors X → YZ (décomposition)

et X → Z

(c) si X → Y alors X → Z (transitivité)

et Y → Z

(d) si X → Y alors XZ → YZ (augmentation)

(e) si X → Y alors XZ → W
et YZ → W (pseudo-transitivité)

Remarques : (d) et (e) découlent de (a), (b) et (c).

L'inverse de (b) est vrai, (d'où la notation concise)

(Exercice : le montrer)

Montrer aussi que

(f) si X → Z alors XY → Z
et Y → Z
et que l'inverse est faux

Najib TOUNSI Normalisation-13

 _____________________________
Proposition : Dans une relation, une clé détermine fonctionnellement tout autre
attribut.
____________________________________

Dans FOUR1 on a :

NOM_FOUR , PIECE → QTE , VILLE , CAT_FOUR , NB_HAB

(Exercice: Pourquoi?)

Définition : Une relation est en 2FN ssi:

i) Elle est en 1FN
ii) Tout attribut non clé, dépend fonctionnellement de la
totalité de la clé.

• non clé = ne faisant partie d'aucune clé candidate.

• Une DF X → Y est dite totale s'il n'existe pas W

tel que: W⊂X

et W → Y.

Aucune partie de X ne détermine Y.

(e.g. si A B → C, ni A ni B, ne détermine C)

Najib TOUNSI Normalisation-14

Ainsi

• EXPEDITION et FOUR2 sont en 2FN.

• FOUR1 n'était pas en 2FN, car d'après la proposition précédente, nous avons:

NOM_FOUR , PIECE → QTE , VILLE , CAT_FOUR , NB_HAB

Or

VILLE (ainsi que CAT_FOUR et NB_HAB), ne dépendent que de

NOM_FOUR, partie de la clé.

NOM_FOUR → VILLE , CAT_FOUR , NB_HAB

• On peut noter qu'une relation en 1FN est aussi en 2FN si sa clé n'est pas
composée.

Najib TOUNSI Normalisation-15

 Une relation en 1FN qui n'est pas en 2FN peut toujours être réduite
à (décomposée en) une collection équivalente de relations en 2FN.
Le processus consiste à remplacer la 1ère relation par les
projections appropriées.
La relation initiale pouvant être retrouvée par jointures de ces
projections.

• Collection équivalente signifie même contenu informatif (on ne

perd pas au change).

• Formellement, cela veut dire que la jointure des

projections est sans perte d'informations
(Voir plus loin).

(Exercice : vérifier ce résultat sur l'exemple)

Najib TOUNSI Normalisation-16

 Définition : Une relation est en 3FN ssi:
i) Elle est en 2FN
ii) Les attributs non clé, sont mutuellement indépendants (ou ne
dépendent pas transitivement de la clé*).

Ainsi

• FOUR3 et METROPOLE sont en 3FN.

• FOUR2 n'était pas en 3FN, car on y a:

VILLE → NB_HAB

Deux attributs non clé ne sont pas mutuellement indépendants.

(*) ou bien, la DF
NOM_FOUR → NB_HAB (due à la clé)
est aussi transitive, puisque :
NOM_FOUR → VILLE (due aussi à la clé)
et que
VILLE → NB_HAB (donnée)

• Comme précédemment, on peut noter qu'une relation en 2FN qui n'a qu'un
seul attribut non clé est aussi en 3FN. C'est le cas de la relation EXPEDITION.

Najib TOUNSI Normalisation-17

 Les mêmes remarques que précédemment s'appliquent :

Le processus de passage d'une relation 2FN vers des relations 3FN

est réversible. Aucune information n'est perdue.

• Une relation en 2FN qui n'est pas ne 3FN peut toujours être décomposée (par
projections) en une collection équivalente de relations en 3FN.

• Cependant, la 3FN rend certaines informations plus explicites, e.g. le

nombres d'habitants d'une ville pour la relation METROPOLE.

Najib TOUNSI Normalisation-18

Bonnes et Mauvaises Décompositions :

R [X, Y] dénote la projection de R sur X et Y.

Définition Une relation R(X, Y, Z) est dite décomposable en deux :

R1 = R [X, Y] et
R2 = R [Y, Z]
si on a:
R = R1 * R2

(i.e. R est la jointure naturelle de R1 et R2)

• C'est cela une décomposition équivalente: On remplace R par

R1 et R2

• Aucune information n'est perdue: On peut retrouver R par jointure

(naturelle) de R1 et R2

Najib TOUNSI Normalisation-19

Exemple:

R
NOM NO_TEL ADRESSE
Ali 10 01 00 Casa
Sara 30 03 00 Casa

R1
NOM ADRESSE
Ali Casa
Sara Casa
R2
NO_TEL ADRESSE
10 01 00 Casa
30 03 00 Casa

R1 * R2
NOM NO_CARTE ADRESSE
Ali 10 01 00 Casa
Sara 10 01 00 Casa ✗
Ali 30 03 00 Casa ✗
Sara 30 03 30 Casa

✗ Superflus.

Ici, R1 et R2 sont une décomposition avec perte d'information. On ne peut

reconstituer la relation initiale.

Najib TOUNSI Normalisation-20

 Proposition Soit R (X, Y, Z)
Pour que R soit décomposable en R1 (X, Y) et R2 (Y, Z),
il suffit que dans R, on ait
Y → X ou Y → Z

i.e. Si Y → X alors R = R1 * R2
ou Y → Z

Il suffit que l'attribut commun soit clé dans l'une des relations (ou les deux).

Najib TOUNSI Normalisation-21

Exemple (décomposition sans Perte) :

On a NOM → ADRESSE

R
NOM NO_TEL ADRESSE
Ali 10 01 00 Casa
Sara 30 03 00 Casa
Sara 20 02 00 Casa

R1
NOM ADRESSE
Ali Casa
Sara Casa
R2
NOM NO_TEL
Ali 10 01 00
Sara 30 03 00
Sara 20 02 00

(Exercice : Montrer que l'inverse du théorème n'est pas toujours vrai.)

Najib TOUNSI Normalisation-22

 Le passage de la 1FN vers la 2FN ainsi que
le passage de la 2FN vers la 3FN
sont des décompositions sans perte.

1FN ➨ 2FN

• R (A, B, C, D) avec { AB → CD, B → C }

➥ R1 ( A, B, D) R2 ( B, C)

2FN ➨ 3FN

• R (A, B, C) avec { A → BC, B → C }

➥ R1 ( A, B) R2 ( B, C)

R = R1 * R2

Remarque : Les dépendances aussi sont sauvegardées.

Najib TOUNSI Normalisation-23

Cas particuliers : Relations en 3FN avec problèmes

EMP
ETUDIANT MATIERE PROF
Ali Math White
Ali Physique Green
Rim Math White
Rim Physique Brown
3FN

EM → P P→M

Supprimer l'information que Rim apprend Physique, fait perdre le fait que
«Brown enseigne Physique»..

EP
ETUDIANT PROF
Ali White
Ali Green
Rim White
Rim Brown
PM
PROF MATIERE
White Math
Green Physique
Brown Physique

Ces deux relations sont en FNBC, une forme améliorée de la 3FN.

Najib TOUNSI Normalisation-24

 Définition : Forme normale de BOYCE-CODD
Une relation R est en FNBC ssi :
A chaque fois que X → Y dans R, X est (ou contient) une clé.

i.e. Les seules DFs qu'une relation contient, sont dues à une clé (candidate)

Dans la relation EMP, on avait P → M , mais P n'est pas clé.

Remarques :

• On utilise en générale cette définition pour la 3FN, et on considère que c'est

la bonne structure pour une base de donnée. (3FN est en générale FNBC sauf cas
particuliers)

• Remarque que EPM = EP * PM

• La DF EM → P n'est cependant pas sauvegardée, et par conséquent

on ne peut mettre à jour une relation indépendamment de l'autre. Considérer
l'insertion de <rim, Green> dans EP. La DF EM → P est contredite.

• Si clé non composée, 3FN = BCFN.

Le pb est dû à : attribut-non-clé → attribut-partie-de-clé

(Ne pas confondre avec 2FN)

Najib TOUNSI Normalisation-25

III. 4e et 5e Forme Normale :

Exemple :
PSL
PERSONNE SPECIALITE LANGUE
Ali Cinéma Français
Ali Cinéma Anglais
Ali Cinéma Arabe
Ali Peinture Français
Ali Peinture Anglais
Ali Peinture Arabe
3FN

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

Najib TOUNSI Normalisation-26

Solution:

PS
PERSONNE SPECIALITE
Ali Cinéma
Ali Peinture
PL
PERSONNE LANGUE
Ali Français
Ali Anglais
Ali Arabe

• Problèmes précédents résolus.

Pas de redondance. Croissance additive.

On dit qu'on est passé à la 4e Forme Normale (4FN)

Najib TOUNSI Normalisation-27

Dépendances Multivaluées (DMV) et 4FN

Définition : Soit R (X, Y, Z) un schéma de relation.

On dit qu'il y a une dépendance Multivaluée entre X et Y (notée X −>> Y)
ssi :
quand les tuples <x, y, z> et <x, y', z'> apparaissent dans R, alors les tuples
<x, y, z'> et <x, y', z> aussi.

Autrement dit, pour une valeur donnée x de X, les valeurs de Y associées sont
indépendantes de celles de Z. x est associée d'une part à y et y' et d'autre part à z et
z', et toutes les combinaisons sont possibles.

X et Y jouant un rôle symétrique, si on a X −>> Y alors on a aussi X −>> Z.

On note

X −>> Y | Z

Najib TOUNSI Normalisation-28

 Dans PSL 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 est
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.

Najib TOUNSI Normalisation-29

 ________________________________________
Remarque Importante : Soit R (X, Y, Z) un schéma de relation
Si X→Y Alors X −>> Y
____________________________________________

Une DF est un cas particulier d'une DMV.

Démonstration : X → Y veut dire que dans la définition précédente, y et y' sont

égaux. C'est dire que : (y' étant remplacé par y)

quand les tuples <x, y, z> et <x, y, z'> apparaissent dans R, alors les
tuples <x, y, z'> et <x, y, z> aussi.
Ce qui est la même chose.

Najib TOUNSI Normalisation-30

 Définition : Une relation R est en 4FN ssi:

Toute Dépendance Multivaluée de R est la conséquence d'une clé

(candidate).

Chaque fois qu'on a X −>>Y dans R, X est (ou contient) une clé.

i.e. les DMVs que R contient sont en réalité des DFs. (Voir remarque précédente).
En l'occurrence, les DFs que la clé détermine tout autre attribut.

Exemple : PL et PS sont en 4FN.

PSL n'est pas en 4FN.

PL et PS sont des projections de PSL.

C'est une décomposition sans perte, car on a le résultat suivant :

Najib TOUNSI Normalisation-31

 Proposition : Une relation R (X, Y, Z) est décomposable en
R1 (X, Y) et R2 (X, Z),
ssi:

X −>> Y | Z

Noter le si et seulement si :

R = R1 * R2 ⇒ X −>> Y | Z et
R = R1 * R2 ⇐ X −>> Y | Z

Dans notre cas 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.

Najib TOUNSI Normalisation-32

Dépendances Jointures et 5FN

ACP
AGENT COMPAGNIE PRODUIT
Ali Ford Voiture
Ali Ford Camion
Rim Ford Voiture
Ali Toyota Voiture
4FN

Un agent représente une compagnie pour vendre des produits.

Soit la contrainte supplémentaire :

« 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.

Najib TOUNSI Normalisation-33

Problèmes :

• Redondances.

• 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.

• La suppression de la ligne 1, oblige à supprimer une autre

ligne pour maintenir la contrainte. (Laquelle?)

• Croissance multiplicative.

etc…

ACP est en 4FN mais non en 5FN.

Najib TOUNSI Normalisation-34

Solution :

AC
AGENT COMPAGNIE
Ali Ford
Rim Ford
Ali Toyota
AP
AGENT PRODUIT
Ali Voiture
Ali Camion
Rim Voiture
CP
COMPAGNIE PRODUIT
Ford Voiture
Ford Camion
Toyota Voiture

En 3 relations !

On dit qu'on est passé à la 5e Forme Normale (5FN)

Najib TOUNSI Normalisation-35

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 jointure

Exercice : Montrer que ACP n'est égale à aucune jointure de deux projections
quelconques parmi AC, AP, CP

Najib TOUNSI Normalisation-36

De façon générale :

Définition: Une relation R (X1, X2, ..., Xn) satisfait la Dépendance

Jointure (DJ)
R1 * R2 * ... * Rn
ssi
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]
_____________________________________________________

Résultat immédiat

Najib TOUNSI Normalisation-37

 Définition : Une relation R est en 5FN ssi:

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)

Résultat :

Une relation 4FN qui n'est pas 5FN peut toujours être remplacée par des relations
5FN. Remplacement sans perte (pourquoi?)

Najib TOUNSI Normalisation-38

 RECAPITULATIF

Processus de Normalisation :

Réduire par décompositions une relation R à d'autres relations,

équivalentes à R et ayant de meilleures propriétés.

En bref : (meilleures propriétés)

Toute sorte de contrainte structurelle (ou dépendance) figurant

dans R, doit être la conséquence de la clé.
(D'où l'importance des clés!)

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

Najib TOUNSI Normalisation-39

Le processus est : (informellement)

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 (i.e. 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

Najib TOUNSI Normalisation-40