Normalisation

Cours pour licence générale informatique deuxième année

Mr HAMMOUDA Mohamed, USDB, Faculté des sciences,

Dept. informatique

Normalisation

Définition: La normalisation est une approche de conception de base de données relationnelles qui s'appuie sur les
formes normales

But: Eliminer les anomalies de redondance et de maj

Principe: Décomposer une relation en un ensemble de relations afin de passer à un degré plus élevé de forme
normale :

Relativement aux dépendances fonctionnelles, les formes normales suivantes les plus utilisées et qui permettent
d'éliminer la majorité des anomalies de redondance :

 la 1ère forme normale,

 la 2e forme normale,
 la 3e forme normale,
 la forme normale de Boyce-Codd (BCNF).

1ère forme normale: (Elémentarités des données)

Une relation est en première forme normale si tous ses attributs sont atomiques.
Un attribut est atomique si il ne contient qu'une seule valeur pour tout tuple donné.

Exemple 1

PERSONNE NoSS Nom Prénom NoTel adresse PrénomEnfant

001 ABBAD TAREK ABEDLWAHAB RANIA

002 AISSAT HAMZA MOHAMED
003 BENAMEUR MOHAMED SEDDIK SARRA YOUNES

La relation PERSONNE est en 0 forme normale car l'attribut PrénomEnfant est non atomique.

Décomposition :

PERSONNE(NoSS, Nom, Prénom, NoTel, adresse)

PERSONNE NoSS Nom Prénom NoTel adresse

001 ABBAD TAREK
002 AISSAT HAMZA
003 BENAMEUR MOHAMED

1
ENFANT(#NoSS, PrénomEnfant)

ENFANT NoSS PrénomEnfant

001 ABEDLWAHAB
001 RANIA
002 MOHAMED
003 SEDDIK
003 SARRA
003 YOUNES

2ème forme normale

Une relation est en 2ème forme normale si et seulement si:

- elle est en 1ère forme normale,
- tout attribut n'appartenant à une clé ne dépend pas d'une partie d'une clé.

A B A B A

C
C D D

R (A,B,C,D)  R1(#A,B,D) et R2(A,C)

Exemple 2

VEHICULE (Marque,Type, Pays, NbrPlaces, NbrVitesses, NomPDG)

F= { Marque, Type  NbrPlaces, NbrVitesses; Marque  Pays, NomPDG }
CC={ (Marque, Type) }

VEHICULE Marque Type Pays NbrPlaces NbrVitesses NomPDG

Toyota Touristique Japon 5 6
Chevrolet Utilitaire USA 3 5
Toyota Utilitaire Japon 2 5
Toyota Minibus Japon 2 6
Toyota Camion Japon 3 6

VEHICULE en 1ère FN car Marque  Pays, NomPDG et Marque fait partie de la CC (Marque, Type).
2
Décomposition :
VEHICULE (#Marque, Type, NbrPlaces, NbrVitesses)
PRODUCTEUR (Marque, Pays, NomPDG)

VEHICULE Marque Type NbrPlaces NbrVitesses

Toyota Touristique 5 6
Chevrolet Utilitaire 3 5
Toyota Utilitaire 2 5
Toyota Minibus 2 6
Toyota Camion 3 6

PRODUCTEUR Marque Pays NomPDG

Toyota Japon
Chevrolet USA
Toyota Japon
Toyota Japon
Toyota Japon

3ème forme normale: (absence de DF transitives)

Une relation est en 3ème FN si et seulement si:

- elle est en 2ème FN
- aucun attribut non clé ne doit déterminer un autre attribut non clé.

A A
C

D
B C D B C

R (A,B,C,D)  R1(A,B,C) et R2(C,D)

3
Exemple 3

ETUDIANT ( NoInsc, Nom, Prénom, DateNaissance, VilleNaissance, PaysNaissance)

Avec Matricule  Nom, Prénom, DateNaissance, VilleNaissance, PaysNaissance
VilleNaissance  PaysNaissance
CC={ NoInsc }

ETUDIANT NoInsc Nom Prénom DateNaissance VilleNaissance PaysNaissance

100 ABBAD TAREK 05/06/2000 Blida Algérie
200 AISSAT HAMZA 12/01/2000 Sousse Tunisie
300 BENAMEUR MOHAMED 23/12/1999 Alger Algérie

Décomposition:
ETUDIANT (NoInsc, Nom, Prénom, DateNaissance, #VilleNaissance)
LOCALISATION( VilleNaissance, PaysNaissance)

ETUDIANT NoInsc Nom Prénom DateNaissance VilleNaissance

100 ABBAD TAREK 05/06/2000 Blida
200 AISSAT HAMZA 12/01/2000 Sousse
300 BENAMEUR MOHAMED 23/12/1999 Alger

LOCALISATION NoInsc VilleNaissance PaysNaissance

100 Blida Algérie
200 Sousse Tunisie
300 Alger Algérie

Forme Normale de Boyce et Codd (BCNF)

Une relation est en BCNF si et seulement si:

- Elle est en 3NF

- Aucune partie de la clé ne doit dépendre d'un attribut d'un autre attribut non clé

A B A E
E

B
C D E C D

R (A,B,C,D)  R1(A,E,C,D) et R2(E,B)

4
Exemple 4

RESULTAT (Etudiant,Matière, Enseignant, Note)

Avec Etudiant Matière

Etudiant,matière  Enseignant, Note

Enseignant  Matière

Décomposition

ENSEIGNANT (Enseignant, Matière)

RESULTAT (Etudiant, Enseignant#, Note)

Note Enseignant

Les proriétés SPI et SPD d'une décomposition

Soit F un ensemble de DF.

- Une décomposition d'une relation R en R1, R2, …, Rn est sans perte de d'information (SPI) par rapport à F si et
seulement si 1 ⋈ 2 ⋈ ⋯ n =

- Selon le théorème de Heath une décomposition de R en R1 et R2 est SPI si et seulement si:

(1) R=R1R2
(2) F implique R1∩R2  R1-R2 ou R2-R1

- Une décomposition d'une relation R en R1, R2, …, Rn est sans perte de dépendances (SPD) par rapport à F si et
seulement si (FR1FR2 … FRn)+ = F+.

Remarques :
- On peut tolérer une décomposition non SPD mais pas non SPI
- La décomposition BCNF est sans perte d'information mais elle ne préserve généralement pas les
dépendances fonctionnelles

5
Exemple 5

R Nom Adresse Poste Age

Ahmed Alger Agent 27
Fatima Blida Agent 32
Farid Tipaza Vendeur 40

R1 Nom Adresse Poste

Ahmed Alger Agent
Fatima Blida Agent
Farid Tipaza Vendeur

R2 Poste Age
Agent 27
Agent 32
Vendeur 40

⋈ Nom Adresse Poste Age

Ahmed Alger Agent 27
Ahmed Alger Agent 32
Fatima Blida Agent 27
Fatima Blida Agent 32
Farid Tipaza Vendeur 40

Nous avons  ⋈  décomposition avec perte d'information (non SPI)

Exemple 6
Soit la relation R(I, J, K, L), l'ensemble F={JI, IKL} et la décompositon de R en R1(J,K, L) et R2(J,I).

Vérification de la propriété SPI

- R=R1R2 = { I, J, K, L}
- R1∩R2  R1-R2 | R2-R1 on retrouve JL

 décomposition SPI

Vérification de la propriété SPD

(FR1  FR2)+ = ({}  { JI} )+= { JI} et F+=F

(FR1  FR2)+  F+  décomposition non SPD

Exemple 7

La décomposition de l'exemple 4 permettra d'éviter la redondance de matière dans RESULTAT mais il y a perte de la
DF Etudiant,matière  Enseignant

6
Algorithme de synthèse
C'est un algorithme qui permet de construire un schéma de BD en 3ème forme normale. Dont voici le principe:

(1) construire une couverture minimale CM

(2) Editer l'ensemble des attributs isolés dans une même relation (tous sont des clés)
(3) Chercher le plus grand ensemble d'attribut X qui détermine d'autres attributs A1,A2, …, An
(4) Construire la relation Ri(X, A1,A2, …, An). Cette relation est en 3ème FN
(5) Eliminer les DF XA1, XA2, …, XAn de la couverture minimale
(6) Supprimer les attributs isolés de CM (c'est-à-dire les attributs non sources ou cibles de dépendances
fonctionnelles)
(7) Reprendre à l'étape 3 jusqu'à ce que CM soit vide
(8) Si aucune des clés candidates ne figure dans une des relations Ri alors il est nécessaire de rajouter une
relation dont les attributs constituent une clé candidate

Résultat: un schéma relationnel en 3ème FN

Remarque: C'est un algorithme simplifié qui est efficace lorsqu'il n y a pas d'attributs isolés dans une couverture
minimale. Si la CM contient des attributs isolés il faut les réunir tous dans une relation constituée de tous ses
attributs.
A

Exemple 6
C
Soit une relation R(A, B, C, D, E) et un ensemble F = {AB, AC , CD  E, BD }

Nous avons F ≡ CM B

Trois groupes de DF avec la même partie gauche: {A  BC}, {CD  E} et {B  D}

D

 une décomposition en trois relations: R1 (A, B#, C#), R2(C,D, E) et R3(B, D#)

A est une clé candidate de R et elle est dans R1

Algorithme de décomposition BCNF

Un schéma relationnel R(A1, . . . , An) avec un ensemble F de DF est en forme normale de Boyce-Codd (BCNF) si pour
chaque DF X  A dans F+, la partie gauche X est une clé candidate.

Toute relation admet une décomposition en BCNF sans perte d’information mais parfois au prix de perte de
dépendances fonctionnelles.

Algorithme de décomposition en BCNF.

Tant qu’il existe une relation R(Z) qui n’est pas en BCNF

• chercher une dépendance non triviale X  Y dans R telle que X ne soit pas une clé candidate et

• décomposer R en R1(XY ) = πXY(R) et R2(Z \ Y) = πZ\Y (R).

On répète cette procédure tant qu’il existent des relations qui ne sont pas BCNF.

A la fin, s’il existe des relations Ri(Xi) et Rj(Xj ) dans la décomposition telle que Xi ⊂Xj alors on supprime Ri.