Normalisation des relations

PARTIE I
Dépendances et formes normales
rédaction : [Link]@[Link]
Plan
 Pourquoi des formes normales ?
 Dépendances fonctionnelles
 Définitions
 Calculs
 Clés d'une relation
 Formes normales : 3FN et BCNF

2
Formes normales : pourquoi ?
 Lors de la gestion de la base, certaines
relations peuvent poser un certain nombre de
problèmes.
 Les formes normales caractérisent les
relations qui présentent moins de problèmes
que d'autres.
 Les formes normales sont définies à partir de
l'analyse des « liens » entre les valeurs des
attributs de la relation : les dépendances
fonctionnelles.
3
Problèmes (anomalies)
 de redondance : la même valeur d’un sous-
ensemble d’attributs apparaît plusieurs fois.
 à l’ajout : l’ajout de certaines informations
n’est possible que si d’autres sont présentes.
 à la suppression : la suppression de certaines
informations entraîne celle d’autres infos (que
l'on aurait bien aimé conserver !)
 à la mise à jour : la modification d’une info
doit être répercutée autant de fois qu’elle
apparaît dans la relation.
4
 Exemple (B. Defude, C. Date)

Produit Quantité Couleur Fournisseur Adresse

parapluie 110 rouge Labaleine Paris

chapeau 50 vert Lemelon Nantes

ceinture 65 noir ToutCuir Nantes

parasol 15 jaune Labaleine Paris

ombrelle 5 rouge Labaleine Paris

ceinture 25 vert Letour Lyon

5
Exemple
 L’information « le fournisseur Labaleine est sur
Paris » apparaît autant de fois que l’on a commandé
de produit à ce fournisseur (redondance).
 Si « Labaleine » change d’adresse, il faudra modifier
autant de tuples qu’il y a de commandes (mise à
jour)
 Si l’on supprime le produit « ceinture » on supprime
toutes les infos relatives au fournisseur « Letour »
(suppression).
 Pour insérer un nouveau fournisseur, il faut lui avoir
commandé un produit (ajout).
6
Liens entre les attributs ?
➢
Entre «fournisseur» et «adresse» ?
Si on connait le fournisseur, on connaît
l'adresse correspondante.
 Entre « produit » et « fournisseur » ?
Si on connaît le produit, on ne connaît
pas forcément le fournisseur.
 Il y a une dépendance fonctionnelle
entre fournisseur et adresse.
7
Notations et conventions
 U : ensemble d’attributs ;
 R(U) : schéma de relation ;
 Par abus de langage, R parfois appelé
« relation ».
 r : un ensemble de tuples particulier (instance
du schéma R(U))
 X, Y, Z, W : sous-ens d’attributs de U, non
vides.
 A, B, C : attributs particuliers.
8
Dépendance fonctionnelle
Soit R(U) un schéma de relation ;
Soit r une instance de R ;
Soient X et Y deux sous-ens de U.
La dépendance fonctionnelle
X->Y est vraie sur r
ssi
tous les tuples de r qui ont même
valeur pour X ont même valeur pour Y.
9
Dépendance fonctionnelle (df)
Soit R(U) un schéma de relation ; soient X et Y deux
sous-ens de U.
La dépendance fonctionnelle
X->Y est vraie sur R
ssi
quelle que soit r instance de R,
X->Y est vraie sur r.

10
Dépendance fonctionnelle
 On dit aussi X détermine Y, Y dépend
fonctionnellement de X.
 C’est uniquement la 2e définition qui
intéresse le concepteur : une df est une
propriété qui doit être extraite de la
connaissance que l’on a de l’application.
 L’ensemble des dépendances fonctionnelles
vérifiées constitue des informations à rajouter
au schéma pour affiner la caractérisation.
R(U), DF
11
Exemple
 Un séminaire a un type. Il est
programmé pour un seul jour d'un mois
précis. On ne programme qu'un seul
séminaire par jour.

 Quelles dépendances fonctionnelles ?

12
 Dépendance élémentaire (dfe)
Soit R(U), DF et soit la dépendance
fonctionnelle X->Y appartenant à DF,
avec Y non inclus dans X.

X->Y est élémentaire, s’il n’existe pas

de sous-ensemble strict de X qui
détermine Y.
(On dit que Y dépend pleinement de X)
13
Propriétés des dfs
Règles de dérivation d’Armstrong

 Réflexivité
Si X est inclus dans Y alors Y -> X
 Transitivité

Si X ->Y et Y -> Z alors X-> Z

 Augmentation

Si X-> Y alors X,Z-> Y,Z

14
Propriétés des dfs
Règles déduites (exemple)

 Union
Si X ->Y et X -> Z alors X->Y,Z
 Pseudo-transitivité

Si X ->Y et W,Y -> Z alors W,X -> Z

15
Preuves
 Démonstration directe
(pour les règles de dérivation de base)

 Démonstration à l’aide des règles de

base pour les autres règles.

16
Clôture d’un ensemble de df
 Soit DF un ensemble de df.
La clôture (ou fermeture) DF+ de DF est
l’ensemble de toutes les df déductibles
à partir de DF avec les règles de
dérivation.
 La clôture comprend toutes les dfs
déductibles, y compris les plus triviales.

17
Fermeture d’un ensemble d’attributs
 Etant donné un ensemble d’attributs X,
quels sont tous les autres attributs qui
sont déterminés par X?
 Soit R(U), DF ; soit X inclus dans U,

X+ est l’ensemble des attributs A tels que

X -> A est déductible de DF.
(équiv. à X → A appartient à DF+)

18
Algorithme de calcul de X +

X+ <- X
Repeter
pour chaque df Y -> Z de DF faire
+ + +
si Y inclus dans X , alors X <- X U Z
+
jusqu'à ce que X ne soit plus modifiable

19
Clés d'un schéma R(U),DF
 Ensemble minimal d’attributs qui
détermine tous les autres attributs.
 X est une clé de R(U), DF ssi :
 X -> U est déductible de DF (X+ = U)

 Il n’existe pas Y, Y strictement inclus

dans X tel que Y ->U ( X-> U dfe)

 Il peut y avoir plusieurs clés. Un attribut
qui appartient à une clé est parfois
appelé « attribut clé ». 20
Couverture minimale de DF
Soit DF un ensemble de df. Une couverture
minimale de DF, noté CV(DF) est un ensemble
de df tel que :
 CV(DF)+ = DF+

 Toutes les df de CV(DF) sont élémentaires et

de la forme X -> A (où A dénote un seul

attribut)
 Quelle que soit X-> A de CV(DF),

( CV(DF) – {X->A} )+ ≠ DF+

21
Formes normales 1 et 2
 1FN : tous les attributs sont atomiques
 Il ne peut y avoir de listes de valeurs

 2FN : 1FN + tous les attributs non-clés

dépendent pleinement des clés (toutes
les dépendances entre une clé et un attribut
non clé sont élémentaires).

22
3e formes normale (v1)

Soit R(U), DF ;
R est en 3FN si quelle que soit X-> A
appartenant à CV(DF) :
- soit X est une clé
- soit A appartient à une des clés.

23
3e forme normale (v2)

Tous les attributs non clés sont

pleinement et directement dépendant
des clés (tout attribut non clé ne
dépend pas d'un autre attribut non clé)

24
Boyce-Cood-Kent
 La 3e forme normale n’élimine pas tous
les problèmes.
 R(U) , DF est en FNBCK si chaque fois
que la df X-> A (A n’appartenant pas à
X) est vérifiée, X est une clé de R.
 Remarque :
 FNBCK -> 3FN ; 3FN -> 2FN ; 2FN -> 1FN

25
Conclusion
 En étudiant le schéma R(U), DF d'une
relation, il est possible de déterminer sa
forme normale « la plus haute ».
 Que faire si le schéma n'a pas la forme
normale souhaitée (ex : 2FN et non
3FN) ?
 Remplacer R(U), DF par un ensemble de
schémas « équivalents » : Normalisation
26