Introduction à la
normalisation relationnelle
Abdelkrim LAHLOU
[email protected]
Plan
I. Introduction
II. Dépendance fonctionnelle
III. Formes normales (1FN – 2FN – 3FN)
IV. Algorithmes de normalisation
V. Conclusion
2
I – Introduction
• La théorie de la normalisation permet de définir une méthode de
conception de « bonnes » tables, c'est-à-dire sans redondance
et sans perte d'information
• Exemple :
• Redondance : on dit 2 fois que le propriétaire N°1500 a pour
nom BBBBB et habite à Nantes
3
Pourquoi la normalisation ?
• 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
Insertion d’une personne sans voiture introduction de valeurs nulles
• Pour éviter la perte d’information
Suppression de la dernière voiture possédée par une personne perte
d’information
4
Exemple
• Relation COURS
• des données redondantes : Dupont à Lille (59)
• des risques d'incohérence : déménagement de Dupont à
Marseille
• des valeurs nulles : représenter un prof qui n'a pas d'étudiant
entraînent des anomalies à l'interrogation
– Problème du choix des relations
5
Comment normaliser un schéma
relationnel ?
• Approche par décomposition :
– on part d’une table contenant tous les attributs
– et on décompose jusqu’à ce qu’il n’y ait plus de
redondances
• Approche par synthèse :
– à partir de l’ensemble des attributs
– et des dépendances fonctionnelles
– on constitue les tables
6
Exemple de table non normalisée
7
Exemple de normalisation par décomposition
en utilisant les Dépendances Fonctionnelles
8
Décomposition sans perte
Jointure
Exemple
Définition
9
II – Dépendance fonctionnelle
• Soient
– R1(A1, …, An) un schéma relationnel
– X et Y sont deux sous-ensembles de {A1, …, An}
• On dit que :
– Y dépend fonctionnellement de X ou bien X détermine Y, on note (
X → Y ), si quelle que soit l’instance de R, pour tout tuples T1, T2 de
R, on a :
T1[X]=T2[X] T1[Y]=T2[Y]
avec Ti[X] la valeur de X pour le tuple Ti.
10
Exemple
11
Axiomes d’Armstrong
• Propriétés des dépendances fonctionnelles
1. Réflexivité Y ⊆ X => X → Y
2. Augmentation X → Y => X,Z → Y,Z
3. Transitivité X → Y et Y → Z => X → Z
…
• Conséquences
4. Union X → Y et X → Z => X → Y,Z
5. Pseudo-transitivité X → Y et W,Y → Z => W,X → Z
6. Décomposition X → Y et Z ⊆ Y => X → Z
12
Dépendance fonctionnelle
élémentaire
• Dépendance fonctionnelle élémentaire
X → A telle que
1) A est un attribut unique
2) A ∉ X
3) Il n'existe pas X' ⊆ X tel que X' → A
• Dans la recherche des DF, on peut se limiter sans
restriction aux DFs élémentaires
13
Exemple
14
Autres définitions
15
Autres définitions
• Fermeture d’un ensemble F de DFs :
– Ensemble F’ de DFs obtenu par applications successives des
axiomes d’inférence
• Fermeture transitive d’un ensemble F de DFs :
– Ensemble F+ de DFs élémentaires obtenues par application
des axiomes de transitivité et de pseudo-transitivite
• Couverture minimale d’un ensemble F de DFs :
– Plus petit ensemble de DFs permettant d’obtenir, par
applications successives des axiomes d’inférence, la
fermeture transitive de F
16
Exemple
17
Graphe de dépendance
• X→ Y X Y
X
Y
• X, Z → Y
Z
18
Exemple
19
Dépendance fonctionnelle et Clé
20
Exemple
21
Les Formes Normales
• 1ère Forme Normale (1FN)
• 2ème Forme Normale (2FN)
• 3ème Forme Normale (3FN)
• Etc, ….
22
Première forme normale (1FN)
• Une relation est en 1ère Forme Normale (1FN) si et
seulement si tous ses attributs sont atomiques (non
composés et mono-valués)
• Contre-exemples :
1. PERSONNE (NOM, PRENOMS)
Mise en 1FN : PERSONNE1 (NOM, PRENOM1,
PRENOM2)
2. PERSONNE (NOM, PRENOM, ADRESSE)
Mise en 1FN : PERSONNE2 (NOM, PRENOM, N°RUE,
RUE, CODEPOSTAL, VILLE)
23
Exemple
ETUDIANT est en 1FN
24
Deuxième forme normale (2FN)
• Une relation est en deuxième forme normale
(2FN) si :
1. elle est en 1 FN
2. tout attribut n'appartenant pas à la clé dépend
uniquement de la totalité de la clé
• Exemple :
25
Exemples de relations non 2FN
26
Exemple 2FN par décomposition
27
Troisième forme normale (3FN)
• Une relation est en troisième forme normale (3FN) si:
1. elle est en 2FN
2. tout attribut n'appartenant pas à une clé ne dépend pas
d'un attribut non clé (pas de dépendance fonctionnelle
entre attributs non clés)
• Exemple :
28
Exemple
29
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
1. on crée une relation supplémentaire avec X pour clé et Y1, …, Yn
comme attributs non clés
2. on retire Y1, …, Yn de la relation initiale
• 2FN 3FN : pour chaque attribut non clé Y déterminant
des attributs non clés Z1, …, Zn
1. on crée une relation R' supplémentaire avec Y comme clé et Z1, …, Zn
comme attributs non clés
2. on retire Z1, …, Zn de la relation initiale
R' n'est pas nécessairement en 3 FN. Si c'est le cas, réitérer le processus
sur R'.
30
Propriétés
• 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
31
Autre algorithme de normalisation
32
Etapes de l’Algorithme de Synthèse
1. Regroupement des dépendances de même partie
gauche
2. Construction d’une relation pour chaque
ensemble
– Chacune des relation a pour clé le groupe d’attributs en
partie gauche
33
Exemple
34
Application de l’étape 1 de l’algorithme
35
Application de l’étape 2 de l’algorithme
R1(A, B, C, #D)
R2 (D, E, F)
R3(#A, #G, H, I)
R4(G, J, K)
Clé primaire en gras souligné
Clé étrangère précédée de #
36
Comparaison des 2 algorithmes
37
CONCLUSION
• La normalisation permet de :
– Construire des tables sans redondance
– Vérifier la bonne conception des tables issues de la
modélisation conceptuelle
– Restructurer une base existante
38
