Bases de Données: Normalisation

Sergio Peignier

Sergio Peignier Bases de Données: Normalisation 1 / 31

Quelques questions

Pour une même application il est souvent possible de proposer

plusieurs schémas.
Un mauvais schéma conceptuel ⇒ anomalies :
Pendant la phase d’exploitation de la base
(redondances d’information ...).
Lors des opérations de mise à jour
(insertions, suppressions, modifications).
Comment peut-on distinguer un bon schéma d’un mauvais schéma ?
Quel schéma doit-on choisir ?

Sergio Peignier Bases de Données: Normalisation 2 / 31

Un exemple

Considérons le schéma de relation

KEBAB(Nom_kebab, Adresse_kebab, Produit_vendu, Prix).
Cette relation pourra éventuellement contenir plusieurs produits pour
un même kebab.
Quels problèmes identifiez vous ?

Sergio Peignier Bases de Données: Normalisation 3 / 31

Un exemple

L’adresse du Kebab sera répété pour chaque produit vendu par le

Kebab en question (redondance).
Si Kebab change d’adresse il faudra rechercher et modifier tous les
tuples associées à ce Kebab.
Si un Kebab (déjà existant) sort un nouveau produit il faudra vérifier
que l’adresse connue et l’adresse de la nouvelle instances sont les
mêmes.
Si un Kebab fait faillite et disparait il faudra retrouver et supprimer
tous les tuples correspondant à ce Kebab (pour différents produits)
dans la table.

Sergio Peignier Bases de Données: Normalisation 4 / 31

Objectif de la normalisation

Construire un schéma de base de données cohérent et possédant

certaines propriétés vérifiées par la satisfaction de "formes normales"
(évitant ainsi l’apparition des anomalies).

Sergio Peignier Bases de Données: Normalisation 5 / 31

Définition : Dépendances Fonctionnelles (DF)

Un ensemble d’attributs B est dit fonctionnellement dépendant

d’un ensemble d’attributs A si on sait que lorsque deux tuples
quelconques coincidant sur leurs attributs A, alors ils coincident sur
leurs attributs B.
Pour x et y deux tuples quelconques, si xA = yA ⇒ xB = yB alors B
est fonctionnellement dépendant de A.
On dit aussi que A détermine B (on écrit A → B).
Les DF sont des contraintes qui décrivent les relations entre les
attributs d’une relation.
Les formes normales s’appuient sur les DF entre attributs d’un schéma
de base de données.
Une notation habituelle en BD : Soient deux ensembles d’attributs X
et Y On note XY l’union de X et Y (au lieu de X∪Y).

Sergio Peignier Bases de Données: Normalisation 6 / 31

Exemple

Écrire les dépendances fonctionnelles de la relations suivante :

ETUDIANT (No_SS, Nom, Prenom, Adresse, Age).
Que remarquez vous ?

Sergio Peignier Bases de Données: Normalisation 7 / 31

Dépendances Fonctionnelles

Une clé détermine tous les attributs du schéma de relation. Il s’agit

d’une propriété de la clé d’un schéma de relation.
Les dépendances fonctionnelles ne se définissent pas par rapport à une
table en particulier (ou à la table à un instant donné) mais par
rapport aux caractéristiques intrinséques des attributs !
Imaginez la relation suivante :
Kebab :
Nom_kebab Adresse_kebab Produit_vendu Prix
Ambiance bvd blabla miche kebab 5
Mosaique bvd blabla maxi kebab 7.5
Est-ce que le produit détermine le nom, l’adresse et le prix ?

Sergio Peignier Bases de Données: Normalisation 8 / 31

Dépendances Fonctionnelles

Soit la relation suivante r ayant le schéma R(A, B, C , D, E ). Si on imagine

que toutes les dépendances fonctionnelles sont visibles sur le tableau (ce
n’est pas toujours le cas attention ! ! !), quelles sont les dépendances
fonctionnelles satisfaites par R ?

A B C D E
a1 b1 c1 d1 e1
a1 b2 c2 d2 e1
a2 b1 c3 d3 e1
a2 b1 c4 d3 e1
a3 b2 c5 d1 e1

Sergio Peignier Bases de Données: Normalisation 9 / 31

Réponse

A→E
B→E
C → ABDE
D→E
AB → D
AD → B
BD → A

Sergio Peignier Bases de Données: Normalisation 10 / 31

Axiomes d’Armstrong

A partir d’un ensemble F de DF entre les attributs A d’une relation R on

peut en déduire d’autres grâce aux propriétés suivantes :
Réflexivité : si Y ⊆ X , alors X → Y .
Augmentation : si X → Y alors XZ → YZ pour tout ensemble
d’attributs Z appartenant à R
Transitivité : si X → Y , et Y → Z , alors X → Z .
A partir de ces trois axiomes de base, on peut déduire d’autres règles :
Union : si X → Y et Y → Z , alors X → YZ
Pseudo-transitivité : si X → Y et WY → Z , alors WX → Z
Décomposition : si X → Y et Z ⊆ Y , alors X → Z
Retrouver ces 3 régles à partir des axiomes.

Sergio Peignier Bases de Données: Normalisation 11 / 31

Axiomes d’Armstrong (Union)

X → Y par augmentation : XZ → YZ
X → Z par augmentation : XX → XZ
Or XX = X donc X → XZ
Par transitivité : X → YZ

Sergio Peignier Bases de Données: Normalisation 12 / 31

Axiomes d’Armstrong (Pseudo-transitivité)

X → Y par augmentation : WX → WY
Or WY → Z par transitivité : WX → Z

Sergio Peignier Bases de Données: Normalisation 13 / 31

Axiomes d’Armstrong (Décomposition)

Z ⊆ Y par réfléxivité : Y → Z
Or X → Y par transitivité : X → Z

Sergio Peignier Bases de Données: Normalisation 14 / 31

Retour sur les DF

DF triviale 7→ Obtenue par réfléxivité (donner un exemple).

DF simple 7→ Un seul élément à droite (donner un exemple).
DF directe 7→ Qui ne peut pas être obtenue par transitivité :
A → B est directe si @C tel que A → C et C → B
DF élémentaire (DFE) 7→ Simple et dont la partie gauche n’est pas
décomposable :
A → B est DFE @C ⊂ A tel que C → B et si |B| = 1.
DF complète ou pleine (dans le cas contraire on parle de DF partielle)
7 Dont la partie gauche n’est pas décomposable
→
X → Y est complète si Y n’est pas fonctionnellement dépendant d’un
sous-ensemble de X.

Sergio Peignier Bases de Données: Normalisation 15 / 31

Fermeture

Soit R un schéma de relation.

Soit X un ensemble d’attributs.
X + fermeture de X 7→
Ensemble des attributs de R qui peuvent être déduits de X à partir
d’une famille de DF en appliquant les axiomes d’Armstrong.
Y sera inclus dans X + ssi X → Y

Sergio Peignier Bases de Données: Normalisation 16 / 31

Fermeture

Calcul de la fermeture d’un ensemble d’attributs :

Initialisation X + = X
Trouver une dépendance fonctionnelle possédant en partie gauche des
attributs inclus dans X +
Ajouter dans X + les attributs placés en partie droite de la dépendance
fonctionnelle.
Répéter les deux étapes précédentes jusqu’à ce que X + n’évolue plus.

Sergio Peignier Bases de Données: Normalisation 17 / 31

Exercice 1

Soit l’ensemble de DF suivant :

F = {A → D; AB → E ; BI → E ; CD → I ; E → C }

Calculer la fermeture sous F , de AE et de BE .

Sergio Peignier Bases de Données: Normalisation 18 / 31

Exercice 2

Soit l’ensemble de DF suivant :

F = {AB → C ; B → D; CD → E ; CE → GH; G → A}.

Montrer que AB → E ,

Sergio Peignier Bases de Données: Normalisation 19 / 31

Fermeture Transitive (F + ) et couverture minimale

Soit F un ensemble de DFE.

Quels opérations peut-on appliquer à F pour trouver toutes les DFE
qui en découlent ?
F + fermeture transitive de F 7→
Plus grand ensemble (non trivial) de DFE obtenu à partir des DFE de
F.
F ∪ { DFE obtenues par transitivité ou pseudo transitivité }
2 ensembles de DF sont équivalents s’ils ont la même F +
MIN(F ) Couverture minimale de F
Ensemble minimal MIN(F ) de F obtenu en supprimant les dépendances
fonctionnelles redondantes, c’est à dire celles qui peuvent être déduites
à partir de MIN(F ).
+
(MIN(F ))+ = F + et @F 0 ⊂ MIN(F ) tel que F 0 = F +
Théorème : Tout ensemble de DFE admet une couverture minimale, en
général non unique.
Sergio Peignier Bases de Données: Normalisation 20 / 31
Algorithme de calcul de la couverture minimale

Écrire les DF sous la forme X → A. X étant un ensemble d’attributs et

A un attribut élémentaire. (Écrire toutes les DF de ce type que vous
pouvez → fermeture transitive)
Les DF du type X → A1 A2 . . . An sont remplacé par n DF du type
X → Ai (parfois utile mais ce n’est pas nécéssaire)
Supprimer des DF grâce aux opérations liés à la notion de fermeture
(trouver l’ensemble de DF le plus simple qui permet de retrouver la
fermeture transitive).

Sergio Peignier Bases de Données: Normalisation 21 / 31

Retour à la normalisation

Normalisation 7→ Méthodologie de conception descendante pour

produire un "bon schéma" par décomposition d’un schéma d’origine
Le schéma produit doit :
Éviter des anomalies lors de la mise à jour de la BD (forme normale)
Preserver la sémantique du schéma d’origine sans perdre de
l’information ni les DF
Cependant, la décomposition entraine parfois une dégradation des
performances (besoin de faire des jointures pour faire des recherches).
Il existent plusieurs formes normales. Nous allons voir les 3 premières
formes normales (NF1, NF2 et NF3) proposées par E.F. Codd en 1972.

Sergio Peignier Bases de Données: Normalisation 22 / 31

NF1

Une relation est NF1 si elle ne contient que des "valeurs atomiques"
non multi-valuées.
Exemple : "01-01-2000" pour l’attribut Jour.
Contre-exemple : "01-01-2000, 06-06-2006" pour l’attribut Jour.
Non-respect de 1NF ⇒ recherche parmi les données plus lente (il faut
analyser le contenu des attributs)
Pensez à un exemple ou cette retriction peut être contraignante.

Sergio Peignier Bases de Données: Normalisation 23 / 31

NF2

NF2 s’appuie sur la notion de dépendance fonctionnelle "complète"

(ou "pleine").
Une relation est NF2 si elle est NF1, et si tout attribut n’appartenant
pas à la clé (primaire) dépend complètement de cette clé, c’est-à-dire
si toutes les dépendances fonctionnelles s’appliquant sur R sont
complètes.
En gros une relation est NF2 si elle est NF1 et les attributs non-clé ne
doivent pas deépendre que d’une partie de la clé mais de sa totalité.
Remarque : si toutes les DF ont un seul attribut en partie gauche, ou
si les clés sont atomiques, alors la relation est NF2.
Non-respect de 2NF ⇒ Redondance encombrant inutilement la
mémoire.

Sergio Peignier Bases de Données: Normalisation 24 / 31

NF2

Soit Employe(idEmp, idService, nom, salaire, nomService) avec

[idEmp, idService] étant la clé de la table et on sait que
idEmp → idService, nom, salaire, nomService Est-ce que cette relation est
NF2 ?

Sergio Peignier Bases de Données: Normalisation 25 / 31

NF3
Une relation est NF3 si elle est NF2 et si les attributs non clés ne
dépendent pas d’un attribut non clé.
Une relation est NF3 si tous les attributs non clé sont en DFE directe
avec la clé. Il ne doit pas y avoir de dépendance fonctionnelle entre
des attributs non clé.
Il peut rester des dépendances fonctionnelles entre attributs de la clé
et entre attributs non clé vers des attributs de la clé
Une relation est NF3 si, pour toute DF X → A s’appliquant sur R
avec A non inclus dans X, soit X est clé de R, soit A fait partie d’une
clé de R.
Pour rendre la relation NF3, il faut donc éliminer les dépendances
fonctionnelles transitives en plaçant certains attributs dans une autre
relation.
Non-respect de 3NF ⇒ Redondance encombrant inutilement la
mémoire.
Sergio Peignier Bases de Données: Normalisation 26 / 31
NF3

Soit R(NomF , AdresseF , Produit, Prix) et

DF = {NomF → AdresseF ; NomF , Produit → Prix} La clé de R étant
[NomF , Produit]. La relation est-elle NF3 ?

Sergio Peignier Bases de Données: Normalisation 27 / 31

Théorème de Heat

Soit la relation R{A, B, C } dans laquelle A, B et C sont des

sous-ensembles d’attributs de R. Si R satisfait la DF A → B, alors R est
égale à la jointure de ses projections sur {A, B} et {A, C }.

Sergio Peignier Bases de Données: Normalisation 28 / 31

Décomposition
Soit F un ensemble de DF définies sur l’ensemble des attributs de la
relation
Déterminer la couverture minimale MIN(F) de F
Construire la relation universelle R, relation composée de tous les
attributs
Déterminer la clé primaire de R à partir de MIN(F)
Pour chaque DF, tant que la DF ne contient pas tous les attributs de
la relation, décomposer la relation en deux nouvelles relations en
utilisant le théorème de Heat :
Si la relation R(A, B, C ) avec la DF B → C n’est pas en NF3, elle
sera décomposée en R(A, B) set R2(B, C )
Appliquer ce processus de décomposition sur les relations jusqu’à
l’obtention de relations en NF3. La décomposition peut être représenté
sous forme d’arbre, les feuilles de l’arbre constituent les relations de la
base.
Sergio Peignier Bases de Données: Normalisation 29 / 31
Exercice : Decomposer la relation pour qu’elle soit en NF3

Relation universelle R : R(A, B, C , D, E , F , G , H, I , J, K )

Couverture minimale : F = {AB → CE ; A → F ; F → DGH; D → IJK }

Sergio Peignier Bases de Données: Normalisation 30 / 31

Correction

Sergio Peignier Bases de Données: Normalisation 31 / 31