Programme de licence GIT

Bases de données avancées

Dépendances fonctionnelles et
normalisation

Module 4

Yacouba Goita
 Objectifs d’apprentissage

Expliquer les dépendances

fonctionnelles et leur importance dans
le modèle relationnel.
Décrire les formes normales de base.
Normaliser un schéma relationnel à
l’aide d’algorithmes.
Expliquer le processus de la
dénormalisation et son intérêt

11/11/2019 2
 Plan
Introduction
Dépendances fonctionnelles
Formes normales
Algorithmes de normalisation
Dénormalisation

11/11/2019 3
 Pourquoi normaliser?
Les SGBD-R sont plus efficaces dans les
bases normalisées car tous les moteurs
(Borland Database Engine BDE et serveurs
SQL) sont conçus pour traiter des données
normalisées.
Les requêtes sont plus faciles à écrire.
Les données sont plus faciles à accéder.
Une meilleure intégrité des données (moins
d’erreurs lors de la suppression, insertion..)
Utilisation optimale des ressources.
11/11/2019 4
 Objectif ou outil?
La normalisation n’est pas un objectif
ultime.
Mais plutôt un outil pratique.
Le concepteur doit décider pour chaque
cas si la normalisation est la solution la
plus efficace ou non

11/11/2019 5
 + PUIS
Principe
+ NOM
+ NSS
+ PRIX
+ COULEUR
+ NVH + TYPE
+ PRENOM
+ DATE
+ MARQUE NORMALISATION R1 ( ............. )

RELATION UNIVERSELLE R2 ( ............. )

.
.
.

A PARTIR DE LA RELATION UNIVERSELLE, LE

PROCESSUS DE NORMALISATION CONSISTE A
CASSER (DECOMPOSER) PROGRESSIVEMENT
LES RELATIONS JUSQU'A OBTENIR DES
RELATIONS NORMALISEES

11/11/2019 6
 Principe
Simple:
⚫ Appliquer des règles: Formes normales
Remarque:
⚫ Parfois on a besoin de dénormaliser une
base, ceci doit être justifié.

11/11/2019 7
 Plan
Introduction
Dépendances fonctionnelles
Formes normales
Algorithmes de normalisation
Dénormalisation

11/11/2019 8
 Dépendance
fonctionnelle (1)
Une forme normale (règle de
normalisation) repose sur la notion des
dépendances fonctionnelles (DF).
Une DF entre deux ensembles
d’attributs X et Y, notée X → Y signifie
que si on connaît X, on peut connaître Y
(X détermine Y)
Appelée DF simple

11/11/2019 9
 Dépendance
fonctionnelle (2)
Livre(ISBN*, Titre, Auteurs, Année)
⚫ Si on connaît l’ISBN du livre, on peut trouver son
titre, ces auteurs et l’année de sa sortie.
Un DF est une assertion qui est définie sur
toutes les réalisations possibles d’une
relation.
Une DF traduit une certaine perception de la
réalité, elle correspond à une contrainte sur
les données, qui doit être vérifiée en
permanence.

11/11/2019 10
 Dépendance
fonctionnelle (3)
On note F l’ensemble des DF d’une relation R
Exemple
F={NoProjet→budget; NoProjet→site}
(équivaut à {NoProjet→budget, site})
On insère (proj1, 5000$, Bamako)
L’insertion (proj1, 5000$, Segou) sera
refusée car contredit DF: NoProjet→site
(proj1 correspondrait à deux sites)

11/11/2019 11
 Dépendance
fonctionnelle totale DFT
Si X → Y et si X’→Y et que X’X
alors X → Y est une DFT
Notée X-t->Y ou X==>Y
DFT est une DF dont le determinant est
minimal
Si X → Y n’est pas une DFT alors elle
est une DF partielle (Y dépend d’une
partie de X)

11/11/2019 12
 Avant goût de la
normalisation du MRD
Machine(noMachine*, marque, débit, totServ,
catégorie)
On suppose que:
⚫ Si on connaît noMachine on peut déduire marque,
débit, totServ et catégorie
⚫ Si on connaît la marque et la catégorie, on peut
déduire le débit
Donc F={noMachine → marque, débit,
totServ, catégorie;
marque, catégorie → débit}

11/11/2019 13
 Avant goût de la
normalisation du MRD (2)
La clé est noMachine car tous les attributs
sont en DF avec noMachine (par définition de
la clé).
Pb: si on veut supprimer (M756, Cincinnati,
75, 50, perceuse) parce que la machine
numéro M756 va à la ferraille, alors on
pourrait perdre l’information: la catégorie
perceuse de marque Cincinnati a un débit
de 75

11/11/2019 14
 Avant goût de la
normalisation du MRD (3)
Solution: normalisation (décomposition)
⚫ R1(noMachine, marque, totServ, catégorie)
avec la DF: noMachine → marque, totServ,
catégorie
⚫ R2(marque, catégorie, débit) avec la DF:
marque, catégorie → débit
Le schéma obtenu est redondant mais
diminue la redondance des données

11/11/2019 15
 Propriétés sur les DFs
Les DFs obéissent aux règles suivantes:
Axiomes d’Amstrong: DF: X détermine Y
⚫ Réflexivité: YX  X→Y
⚫ Augmentation: X→Y  XZ → YZ
⚫ Transitivité:X→Y  Y→Z  X→Z
Règles simplifiées:
⚫ Union X→Y  X→Z  X→YZ
⚫ Pseudo-transitivité
X→Y et (YW →Z)  XW → Z
⚫ Décomposition X →YZ  X→Y et X→Z
11/11/2019 16
 Exemple: la
Décomposition
{matricule} →{NomPropriétaire}  {Marque}
Voiture(matricule, NomPropriétaire, Marque)
est décomposée en:
⚫ R1(matricule, NomPropriétaire)
⚫ R2(matricule, Marque)
Ce genre de décomposition est à la base de
l’algo de décomposition (cf. plus loin).

11/11/2019 17
 Définitions
X→Y est élémentaire si X’X, X’→Y
n’est pas vrai.
⚫ Exemple:
NumService, NomService → NomChef (non
élémentaire)
⚫ Cette notion de DF sert à conserver les seules
DFs utiles.

11/11/2019 18
 Définitions (suite)
R(U,F):
⚫ R: relation
⚫ U liste d’attribut de R

⚫ F liste des DFs vraies dans R

R(U,F) est appelée relation universelle

11/11/2019 19
 Graphes de dépendances
fonctionnelles
Nœuds: les attributs
Arcs: les dépendances
Exemple des internautes qui évaluent des
livres:
Nom Titre
Prénom IdLivre
Email
Année

Note
11/11/2019 20
 La fermeture
Dérivabilité: une Df f est dérivable de F
si on peut dériver f à partir des Dfs de F
en utilisant les axiomes d’Amstrong
Exemple: dériver f: I,C,D→Z de
F={A,B,C→Z; D,B→A; I,C→B}
⚫ Il faut démontrer f en partant de F

11/11/2019 21
 démonstration
1: I,C→B par hypothèse
2: D→D trivial
3: I,C,D→D, B par augmentation de 1 et 2
4: D,B→A hypothèse
5: I,C,D→A transitivité
6: C→C
7: I,C,D→A,C augmentation
8: I,C→B hypothèse
9: I,C,D→A,C,B addition de 7 et 8
10: A,B,C→Z hypothèse
11: I,C,D→Z de 9 CQFD
11/11/2019 22
 Fermeture
La fermeture est l’ensmble de toutes les
DFs dérivables de F par les axiomes
d’Amstrong, notée F+

11/11/2019 23
 Couverture
Une couverture C de F avec CF est un
ensemble de DF / C+ = F+

11/11/2019 24
 Couverture minimale (ou non
redondante)
La couverture minimale C* d’un ensemble F
est tel que:
⚫ CF
⚫ C équivalent à F (C+ = F+)
⚫ C est minimal i.e. il n’existe pas C’ F tel que C’
équivalent à F (C’+ = F+)
C’est un sous-ensemble de DFs permettant
de générer toutes les autres.
C* est l’ensemble des DFs les plus
“pertinents”

11/11/2019 25
 Couverture minimale
La recherche de la couverture minimale
d’un ensemble de DF est un élément
essentiel du processus de
normalisation, afin de décomposer une
relation en plus petites relations.

11/11/2019 26
 Exemple
E = {NumAvion→type, type→capacité,
type →constructeur,
NumAvion→propriétaire}
C* = E

11/11/2019 27
 Algorithme de calcul de
C*
Faire C=F (les déterminés de F sont
supposés monoattributs)
Faire tant que F!=vide
⚫ Choisir une f (ie X→A) dans F (f est une DF de F)
⚫ Faire F=F-f
⚫ Si f(C-f)+ alors C=C-f
Afficher C
Fin

11/11/2019 28
 Clef
R (A1, A2, ..., An) et X sous-ensemble
de A1, A2, …An
X est une CLE de R si et ssi :
1) X -> A1 A2 ... An
2)  Y  X / Y -> A1 A2 ... An

Une clef est un ensemble minimum

d’attributs qui détermine tous les autres
11/11/2019 29
 Plan
Introduction
Dépendances fonctionnelles
Formes normales
Algorithmes de normalisation
Dénormalisation

11/11/2019 30
 Introduction
Les FN sont appliquées:
⚫ Lors de la conception d’une base pour assurer sa
cohérence.
⚫ Pour vérifier la cohérence d’une base déjà
existante.
Normaliser une base revient à appliquer des
règles (1NF, 2NF…)
On sous entend que chaque table possède
une clef primaire.

11/11/2019 31
 1re Forme Normale
(1NF)
Les champs doivent être atomiques
Pas de champs répétitifs.
La signification de chaque champ est
précise et constante dans le temps.

11/11/2019 32
 Exemple1 1NF
Nom Adresse Ville

Traore Dramane Rue20 Missira Ségou, BPE1000

Coulibaly Moussa Rue 614 Djico-ACI Bamako, BPE 3100

Pourquoi cette table n’est pas à la 1NF?

Nom Prénom Adresse Ville Code

Traore Dramane Rue20 Missira Ségou BPE1000

Coulibaly Moussa Rue614 Djico-ACI Bamako BPE 3100

Rq: le champ Adresse peut également être découpé mais ceci ne se fait pas pour la
plupart des applications, mais ça peut exister

11/11/2019 33
 Exemple2 1NF
Num. Livre 1 Livre 2 Livre 3
- Pb pour gérer 4
Emprunteur
livres
36002 L’appel de la L’alchimiste Les entités -Il faut saisir le titre
forêt du livre à chaque
36015 Mission sur la emprunt
lune -…

Livre Emprunté par

Num. Emprunteur Nom Emprunteur
L’appel de la forêt 36002
36002 Traore
Mission sur la lune 36015
36015 Coulibaly
L’alchimiste 36002

Les entités 36002

Relation de jointure

11/11/2019 34
 Exemple3 1NF
Animal Date Quantité

Poule2 16/02/2016 2

Vache3 16/02/2016 15

Vache4 16/02/2016 17

Poule10 16/02/2016 3

La table est-elle 1NF?

◼ «Quantité» représente à la fois des œufs et des
litres de lait!! Pas de signification constante et précise
dans le temps
◼ Il faut restructurer les données

11/11/2019 35
 Exemple3 1NF (suite)
Poule Date Œufs
2 16/2/2016 2
10 16/2/2016 3

Vache Date Litres

3 16/2/2016 15
4 16/2/2016 17

11/11/2019 36
 2e forme normale 2NF
Une relation est 2NF ssi:
⚫ Elle est 1NF
⚫ Toutes ses propriétés non-clé sont
totalement dépendantes fonctionnellement
de la la totalité de la clé primaire. (i)
«Totalité»:
⚫ Si XZ clé et y non-clé, alors XZ → y mais
si Z → Y alors la relation n’est pas 2NF

11/11/2019 37
 Exemple 2NF
NumSalarié Nom NumProjet Heures
310 Coulibaly 1 14
310 Coulibaly 2 15
450 Traore 2 10
450 Traore 3 8

Déterminons la clé! NumSalarié + NumProjet

Or le Nom ne dépend que de NumSalarié donc la

table n’est pas en 2NF

11/11/2019 38
 Exemple 2NF (suite)
NumSalarié NumProjet Heures
NumSalarié Nom
310 1 14
310 Coulibaly
310 2 15
450 Traore
450 2 10
450 3 8
Jointure

11/11/2019 39
 3e forme normale 3NF
Une relation est 3NF si:
⚫ Elle est 2NF
⚫ Aucun champ non-clé n’est en dépendance
transitive avec la clé primaire
Soit A clé, A → B, B → C
⚫ Si A → C alors la table n’est pas 3NF
Attention! La 3NF n’est pas une extension de
la 2NF!
BNCF (Boyce Codd Normal Form) impose
que la 3NF soit vérifiée pour toute clé
primaire.
11/11/2019 40
 Exemple 3NF
Nom NumSalarié Date Naiss Service NomService NumChef

Coulibaly 310 18/9/1963 1 Vente Cissé

Traore 450 11/4/1960 2 Informatique Ballo

«NomService» et «NumChef» peuvent être déterminés à partir de la

valeur du champ «Service», donc la table n’est pas en 3NF
Pourquoi c’est un problème:
Si on supprime tous les employés d’un service, on supprime
le service (anomalie de suppression)
Si on crée un nouveau service, il faut d’abord insérer un
employé de ce service (anomalie d’insertion)
11/11/2019 41
 Exemple 3NF (suite)
NumSalarié Nom Date Naiss Service
310 Coulibaly 18/9/1963 1
450 Traore 11/4/1960 2

jointure

Service NomService NumChef

1 Vente Cissé

2 Informatique Ballo

11/11/2019 42
 Définition simplifiée de
BCNF
une relation est en 3BCNF ssi
⚫ elle est en 3FN et
⚫ si les seules DF élémentaires sont celles de la
forme C -> X avec C clé (seules les clés sont en
partie gauche de DF).

Théorème: Toute relation admet une

décomposition en BNCF sans perte
d’information

11/11/2019 43
 Résumons
1NF: tous les attributs sont atomiques
2NF: 1NF + tout attribut non clé dépend
entièrement de la totalité de la clé
primaire.
3NF: 2NF + pas de dépendance entre
attributs non clé
BCNF: Toute partie gauche d’une DF
est une clé

11/11/2019 44
 Plan
Introduction
Dépendances fonctionnelles
Formes normales
Algorithmes de normalisation
Dénormalisation

11/11/2019 45
 Comment concevoir un
schéma en 3NF ou BCNF?
Deux algorithmes:
⚫ Algorithme de décomposition (faire des
décompositions successives pour obtenir
un arbre). Son inconvénient est qu’il
dépend des DFs choisies au départ.
⚫ Algorithme de synthèse (basé sur les
graphes de dépendance)

11/11/2019 46
décomposition
 Exemple
VOITURE (MATRICULE, MARQUE, TYPE,
PUISSANCE, COULEUR)
PEUT SE DECOMPOSER EN :

1) R1 (MATRICULE, TYPE, COULEUR)

R2 (TYPE, MARQUE, PUISSANCE)

2) R'1 (MATRICULE, TYPE)

R'2 (TYPE, PUISSANCE, COULEUR)
R'3 (TYPE, MARQUE)
11/11/2019 48
 Décomposition sans
perte d’information SPI
Une DECOMPOSITION d’une relation
R en N relations R1, R2, ... , RN est
sans perte, ssi pour toute réalisation
r de R et pour toutes les réalisations
r1, ... , rn de R1, R2, ... , RN , on a :

r = r1 x r2 x ... x rN

11/11/2019 49
 Décomposition
préservant les DFs
Une décomposition (R1, ..., Rn) de R
préserve les DFs si la fermeture des DFs
est la même que celle de l’union des DFs
des relations R1, ..., Rn
1)R1 (MATRICULE, TYPE, COULEUR)
=> F1 = {MATRICULE -> TYPE,
MATRICULE -> COULEUR }
R2 (TYPE, MARQUE, PUISSANCE)
=> F2 = {TYPE -> MARQUE,
TYPE -> PUISSANCE}
11/11/2019 50
 Décomposition
préservant les DFs
2) R'1 (MATRICULE , TYPE)
=> F'1 = {MATRICULE -> TYPE }
R'2 (TYPE, PUISSANCE , COULEUR)
=> F'2 = {TYPE -> PUISSANCE }
R'3 (TYPE, MARQUE)
=> F'3 = { TYPE ->MARQUE }

==> ON A PERDU LA DF :
PUISSANCE ->COULEUR
11/11/2019 51
 Conclusion
Il est souhaitable qu'une
décomposition:
préserve les DF
(sinon on perd des contraintes
d'intégrité)
soit SPI
(risque : réponses erronées sur
jointure)

11/11/2019 52
 Algorithme de décomposition

Procédure DécompositionFNBC (T, S)

Entrée:
T : une table avec ses dépendances fonctionnelles élémentaires
Sortie
S : un schéma relationnel pour T en FNBC
DÉBUT
Ajouter T à S
TANT QU'il y a une table T dans S qui n'est pas en FNBC
Décomposer T selon une dépendance élémentaire X →T Y qui ne respecte
pas la condition de FNBC
et remplacer T par T1(U-Y) et T2(X  Y) dans S
FIN TANT QUE
FIN

11/11/2019 53
 Exemple
E = {noClient → nomClient, noTéléphone ; noCommande → noClient,
dateCommande ; noCommande, noArticle → quantité ; noArticle →
description, prixUnitaire}

dateCommande

noCommande nomClient
noClient
noTéléphone

noArticle
description

prixUnitaire
Ce diagramme à bulles
est équivalent au
quantité diagramme des DF.

11/11/2019 54
 Vente

Exemple dateCommande
nomClient
noCommande
noClient
noTéléphone

noArticle
description
prixUnitaire

quantité

Dépendance élémentaire
qui viole FNBC

VenteReste Client
nomClient
noClient
dateCommande noTéléphone
noCommande nomClient
noClient
noTéléphone

noArticle
description
prixUnitaire

quantité

11/11/2019 55
 Dépendance élémentaire qui VenteReste
viole FNBC

Exemple noCommande
dateCommande

noClient

noArticle
description

prixUnitaire

quantité

VenteReste2 Commande

dateCommande dateCommande
noCommande noCommande
noClient noClient

noArticle
description

prixUnitaire

quantité

11/11/2019 56
Exemple
VenteReste2 Dépendance élémentaire
qui viole FNBC
noCommande

noArticle
description

prixUnitaire

quantité

LigneCommande Article

noCommande noArticle
description
noArticle
description prixUnitaire

prixUnitaire

quantité

11/11/2019 57
 Résultat
Client (noClient, nomClient, noTéléphone)
Commande(noCommande, dateCommande,
noClient)
LigneCommande(noCommande, noArticle,
quantité)
Article(noArticle, description, prixUnitaire)

11/11/2019 58
Algorithme de synthèse
 Algorithme de synthèse
Condition d’application: pas d ’attribut isolé (si X est isolé alors
ajouter une DF X ?{} )
En entrée: R(U, F)
En sortie: S = {Ri} 1in, schéma relationnel où chaque Ri est en
3NF
début
1. Rechercher une couverture minimale Ê0 de E0
2. Partitionner Ê0 en groupes G1,…, Gn tels que toutes les
dépendances fonctionnelles d’un même groupe aient la même partie
gauche.
3. Fusionner les Gi ayant des clés équivalentes et éliminer les
dépendances transitives qui pourraient résulter de la fusion. On
obtient une nouvelle partition R1,…, Rm.
4. Construire une relation par Ri. La partie gauche de chaque groupe
est la clé de la relation associée
fin

11/11/2019 60
 Exemple
E={
noClient → noClient, nomClient, noTéléphone ;
noCommande → noClient ;
noCommande → dateCommande ;
noCommande, noArticle, noClient → quantité ;
noArticle → description, prixUnitaire ;
noCommande → nomClient }

Ê= {
noClient → nomClient, noTéléphone ;
noCommande → noClient , dateCommande ;
noCommande, noArticle → quantité ;
noArticle → description, prixUnitaire }

11/11/2019 61
 Résultat
Commande(noCommande, dateCommande, noClient) Client (noClient, nomClient, noTéléphone)

dateCommande

noCommande nomClient
noClient
noTéléphone

noArticle
description

prixUnitaire

quantité Article(noArticle, description, prixUnitaire)

LigneCommande(noCommande, noArticle, quantité)

11/11/2019 62
 Dépendance de Plusieurs
Valeurs
Dépendance de Plusieurs Valeurs (DPV):
⚫ si on connaît la valeur de l’attribut A, on
peut déterminer les valeurs d’un ensemble
d’autres attributs
⚫ Notation A  B (A détermine plusieurs B)

Exemple de DPV:
⚫ Si on connaît le nom d’un professeur (A) on peut
trouver la liste de ses étudiants (B)

11/11/2019 63
 4e FN
Définition: Une relation est en quatrième
forme normale si et seulement si,
lorsqu'il existe une dépendance
multivaluée élémentaire, celle-ci est
unique

11/11/2019 64
 Exemple 4e FN

Si on veut ajouter une nouvelle tâche, il

faut créer plusieurs nouvelles lignes
(toutes les combinaisons possibles avec
projet)
11/11/2019 65
 5e FN

Définition: Une relation R est en

cinquième forme normale si et
seulement si toute dépendance de
jointure est impliquée par des clés
candidates de R
Forme assez compliquée nécessitant
des notions pas encore abordées dans
ce cours
11/11/2019 66
 Plan
Introduction
Dépendances fonctionnelles
Formes normales
Algorithmes de normalisation
Dénormalisation

11/11/2019 67
 Définition
La dénormalisation est le fait d’ajouter
(par le concepteur de la BD) des
attributs présents dans d’autres
relations afin d’éviter le calcul de
certaines jointures.

11/11/2019 68
 Exemple
L,exemple démontre que le fait de
dupliquer l’attribut catégorie dans la
table LigneFiche, évite au SGBD de
faire une jointure et donc diminue le
temps de calcul pour certaines requêtes

11/11/2019 69
 Mais inconvénients
Cependant, la dénormalisation présente
certains inconvénients:
⚫ Utilisation de trigger (pour propager la MAJ
et vérifier les contraintes) ralentit le SGBD
⚫ Espace disque plus grand

⚫ Risque d’incohérence plus grand

⚫ Etc.

11/11/2019 70