IFT187 – THÈME 2
NORMALISATION
Nadia Tahiri, Ph. D.
Professeure adjointe
Université de Sherbrooke
[Link]@[Link]
© Anis Boubaker (2018), Robert Godin (2012)
DÉPENDANCE
FONCTIONNELLE
Source: Marc Frappier (UdeS), IFT187
3
DÉPENDANCE FONCTIONNELLE
▪ les définitions de 2FN, 3FN, BCNF reposent sur la notion de dépendance fonctionnelle
▪ une dépendance fonctionnelle est une fonction entre des listes d’attributs
▪ on dénote une dépendance fonctionnelle comme suit :
(A1, ..., An) → An+1
on dit que An+1 dépend de A1, ..., An
QUE REPRÉSENTE UNE DÉPENDANCE
4
FONCTIONNELLE?
▪ C’est une fonction, donc elle associe à une liste de valeurs des attributs A1, ..., An une et une
seule valeur dans An+1
▪ exemple
▪ dans une université, étant donné le matricule d’un étudiant, on peut donner son nom
▪ il existe donc une dépendance fonctionnelle entre matricule et nom
matricule → nom
▪ l’inverse n’est pas vrai : étant donné un nom, on ne peut déterminer le matricule d’un
étudiant, car il peut y avoir plusieurs matricules, puisque plusieurs étudiants peuvent avoir le
même nom
QUE REPRÉSENTE UNE DÉPENDANCE
5
FONCTIONNELLE?
▪ Attention!
la dépendance matricule → nom
▪ ne signifie pas que le nom associé à un matricule ne change jamais; le nom peut changer, mais,
en tout temps, on peut déterminer le nom d’un étudiant à partir de son matricule
▪ cela ne signifie pas non plus que si on a deux matricules différents, alors leurs noms associés
doivent être différents
▪ cela signifie que deux étudiants ne peuvent avoir le même matricule
6
DÉPENDANCE FONCTIONNELLE MINIMALE
▪ si
(A1, ..., An) → B
alors on a aussi
(A1, ..., An, An+1) → B
▪ pour les fins de normalisation, on considère seulement les dépendances qui sont minimales
selon la liste de gauche
DÉPENDANCE FONCTIONNELLE ET CLÉ
7
CANDIDATE
▪ s’il existe une dépendance fonctionnelle minimale entre (A1, ..., An) et tous les autres attributs
de la relation, alors on peut conclure que (A1, ..., An) est une clé candidate
▪ une dépendance fonctionnelle sera donc traduite en une contrainte primary key ou
unique
QUELQUES LOIS SUR LES DÉPENDANCES 8
FONCTIONNELLES
Soit W, X, Y et Z des ensembles d’attributs
Par soucis de concision, on dénote par XY
l’union X ∪ Y de deux ensembles d’attributs X et Y
l’inclusion X ⊆ Y de deux ensembles d’attributs X et Y
1. Si X' ⊆ X, alors X → X' (DF triviale)
2. Si X → Y, alors X ∪ Z → Y (augmentation)
3. Si X → Y et Y → Z, alors X → Z (transitivité)
4. Si X → Y ∪ Z, alors X → Y et X → Z (décomposition)
5. Si X → Y et X → Z, alors X → Y ∪ Z (union)
6. Si X → Y et W ∪ Y → Z, alors X ∪ W → Z (pseudo-transitivité)
COMMENT DÉTERMINER LES DÉPENDANCES 9
FONCTIONNELLES?
▪ les dépendances fonctionnelles sont des contraintes du domaine d’application
▪ on les détermine à partir de notre connaissance des faits (règles, conditions, etc) du domaine
d’application
▪ on peut déterminer s’il y a une dépendance fonctionnelle
(A1, ..., An) → An+1 en répondant à la question suivante:
▪ étant donné une liste de valeurs pour A1, ..., An , peut-on toujours associer une et une seule
valeur pour An+1?
10
REPRÉSENTATION GRAPHIQUE
▪ sigle → titre
sigle titre
▪ (sigle, session, groupe) → matricule
sigle session groupe matricule
11
EXERCICE
▪ identifiez les dépendances fonctionnelles entre les attributs suivants
▪ sigle, titre, matricule, nom, session, groupe, note, salaire, coteR
DEUXIÈME
FORME
NORMALE (FN2)
13 13
DEUXIÈME FORME NORMALE (FN2)
▪ Une table respecte la 2ième forme normale si:
▪ Elle respecte la FN1
▪ Tout attribut ne faisant pas partie de la clé est complètement dépendant de la clé
primaire (ne dépend pas d’une partie de la clé)
▪ Cette forme normale ne s’applique que dans le cas de clés composées (multi-
colonnes).
14 14
DEUXIÈME FORME NORMALE (FN2)
▪ Exemple non FN2
Souligné : Clé
Table: Employe_Projet
id_employe id_projet role nom_employe nom_projet
10 45 Programmeur Lapierre, A. Caisse de dépôt
12 37 Designer Desjardins, R. Therac
FrontEnd
10 33 Architecte Lapierre, A. Geothermia
18 37 Concepteur Labonté, T. Therac
Source: Cours GPA775 (ÉTS)
15 15
DEUXIÈME FORME NORMALE (FN2)
▪ Table normalisée en FN2
Table: Employe Table: Projet
id_employe nom id_projet nom
10 Lapierre, A. 45 Caisse de dépôt
12 Desjardins, R. 33 Geothermia
18 Labonté, T. 37 Therac
Table: Employe_Projet
id_employe id_projet role
10 45 Programmeur
12 37 Designer FrontEnd
10 33 Architecte
18 37 Concepteur
Source: Cours GPA775 (ÉTS)
CONTRE-EXEMPLE DE FN2
16
Une entité E est en deuxième forme normale ssi tous les attributs non premiers de E
sont en dépendance fonctionnelle complète de chaque clé candidate de E
sigle session groupe matricule titre nom
titre ne dépend pas de toute la clé; il dépend seulement de sigle
Source: Marc Frappier (UdeS), IFT187
17
POURQUOI NORMALISER EN FN2 ?
✓ parce que cela élimine la redondance des données
✓ cela assure une meilleure intégrité des données tout en simplifiant les mise à jour
✓ on ne perd aucune information; on peut recréer la relation originale avec une jointure des deux
relations normalisées
Source: Marc Frappier (UdeS), IFT187
TROISIÈME
FORME
NORMALE (FN3)
19 19
TROISIÈME FORME NORMALE (FN3)
▪ Une table est en troisième forme normale si:
▪ Elle respecte la FN2
▪ Toute colonne non-clé dépend non-transitivement de la clé primaire.
(i.e. ne dépend pas d’un ou plusieurs attributs n’appartenant pas à la clé).
▪ Ou…
Une relation E est en troisième forme normale ssi pour toute dépendance fonctionnelle
X → A de E, une des conditions suivantes est satisfaite:
–X est une super clé
–A est un attribut premier
Source: Cours GPA775 (ÉTS)
20
QUELQUES DÉFINITIONS
▪ Super-clé
▪ Ensemble d'attributs X qui sont uniques à chaque tuple.
▪ Clé (ou clé candidate)
▪ Super-clé minimale.
▪ Super-clé X telle que si on enlève n'importe quel attribut, ce n'est plus une super-clé.
▪ Attribut premier (parfois appelé primaire)
▪ Un attribut qui fait partie d'au moins une clé
▪ Si X est un ensemble d'attributs, il est premier si au moins un de ses attributs est premier.
▪ Attribut non-premier = un attribut qui n'est pas premier
CONTRE-EXEMPLE DE FN3 21
Une relation E est en troisième forme normale ssi pour toute dépendance fonctionnelle
X → A de E, une des conditions suivantes est satisfaite :
–X est une super clé
–A est un attribut premier
sigle session groupe matricule nom
cette relation n’est pas FN3 car :
• matricule n’est pas une super clé
• nom n’est pas premier
Source: Marc Frappier (UdeS), IFT187
NORMALISATION EN FN3
22
Scénario 1 sigle session groupe matricule nom
A1 A2 A3 A4 A5
A1 A2 A3 A4 A4 A5
23
NORMALISATION EN FN3
Scénario 2
sigle session groupe matricule nom matricule salaire
A1 A2 A3 A4 A5 A4 A6
A1 A2 A3 A4 A4 A5 A6
24
POURQUOI NORMALISER EN 3FN
▪ comme pour la 2FN
▪ parce que cela élimine la redondance des données
▪ cela assure une meilleure intégrité des données tout en simplifiant les mise à jour
▪ on ne perd aucune information; on peut recréer la relation originale avec une jointure des deux
relations normaliées
Edgar F. Codd (1923-2003)
FORME NORMALE
BOYCE-CODD
(FNBC)
26 26
FORME NORMALE BOYCE-CODD (FNBC)
▪ Une table est en forme normale Boyce-Codd (FNBC) si:
▪ Elle respecte la FN3
▪ Tous les attributs non-clé ne sont pas source de dépendance vers une partie de la clé.
Ou
▪ Une relation E est en forme normale de Boyce-Codd ssi pour toute dépendance fonctionnelle
X → A de E, la condition suivante est satisfaite :
▪ X est une super clé
27
CONTRE-EXEMPLE DE BCNF
▪ supposons qu’une institution d’enseignement décerne un seul diplôme (SEC, DEC, ou BAC) et
qu’une personne obtient un diplôme d’une et une seule institution; on a les DF suivantes
▪ (personne, diplôme) → institution
▪ institution → diplôme
personne diplôme institution
CONTRE-EXEMPLE DE BCNF 28
Une entité E est en forme normale de
Boyce-Codd ssi pour toute dépendance
fonctionnelle X → A de E, la condition
suivante est satisfaite:
–X est une super clé
Cette entité n’est pas en BCNF, car il y a la DF institution → diplôme,
et institution n’est pas une super clé
personne diplôme institution
NORMALISATION EN BCNF 29
personne diplôme institution
personne institution diplôme institution
Note :
- on ne perd pas d’information,
- on diminue la redondance
-on perd une contrainte d’intégrité
(personne, diplôme) → institution
QUATRIÈME FORME NORMALE
(FN4)
Source: Robert Godin, 2012
QUATRIÈME FORME NORMALE ET
31
DÉPENDANCES MULTIVALUÉES
▪ Film est en FNBC mais pas en 4FN
▪ Redondance due à dépendance multivaluée
▪ titre ↠ nomProducteur Table Film
titre nomProducteur nomActeur
La vie est belle Elda Ferri Roberto Benigni
▪ titre ↠ nomActeur La vie est belle Elda Ferri Nicoletta Braschi
La vie est belle Elda Ferri Giorgio Cantarini
La vie est belle Gianluigi Braschi Roberto Benigni
La vie est belle Gianluigi Braschi Nicoletta Braschi
La vie est belle Gianluigi Braschi Giorgio Cantarini
Patch Adams Barry Kemp Robin Williams
Patch Adams Barry Kemp Monica Potter
Patch Adams Michael Farrell Robin Williams
Patch Adams Michael Farrell Monica Potter
Patch Adams Marvin Minoff Robin Williams
Patch Adams Marvin Minoff Monica Potter
DÉPENDANCE MULTIVALUÉE
32
(MULTIVALUED DEPENDENCY)
▪ A1, A2, …, An ↠ B1, B2, …, Bm
▪ à chacune de valeurs de A1, A2, …, An est associé un ensemble de valeurs de B1, B2, …, Bm
sans relation directe avec les autres colonnes C1, C2, …, Cp de la table
33
DÉFINITION FORMELLE
▪ (a1, a2, …, an, b1, b2, …, bm, c1, c2, …, cp) et (a1, a2, …, an, b'1, b'2, …, b'm, c'1, c'2, …, c'p) T
(a1, a2, …, an, b1, b2, …, bm, c'1, c'2, …, c'p) T
▪ ('La vie est belle', 'EldaFerri', 'Robert Benigni') et ('La vie est belle',
'Gianluigi Braschi', 'Nicoletta Braschi') Film
('La vie est belle', 'EldaFerri', 'Nicoletta Braschi')
Film
34
DÉPENDANCES MULTIVALUÉES
▪ Proposition (règle du complément)
▪ A1, A2, …, An ↠ B1, B2, …, Bm A1, A2, …, An ↠ C1, C2, …, Cp
▪ C1, C2, …, Cp correspond aux autres colonnes de T
▪ Proposition (DF cas particulier de DMV)
▪ A1, A2, …, An → B1, B2, …, Bm A1, A2, …, An ↠ B1, B2, …, Bm
GÉNÉRALISATION DIRECTE DU PATRON DE
35
DÉCOMPOSITION T able T
D épendance m ultivaluée non triviale
qui cause de la redondance
U : l'ensem ble de tous les attributs de T
déterm inant (X ) Y
superclé
T able T 1 T able T 2
U : l'ensem ble de tous les attributs de T
X Y
X Y
36
EXEMPLE : FILM
Dépendance multivaluée non triviale
qui viole 4FN
Film
titre nomProducteur
nomActeur
ActeurFilm ProducteurFilm
titre nomProducteur titre nomProducteur
nomActeur
37
EXEMPLE (SUITE)
Table Film
titre nomProducteur nomActeur
La vie est belle Elda Ferri Roberto Benigni
La vie est belle Elda Ferri Nicoletta Braschi
La vie est belle Elda Ferri Giorgio Cantarini
La vie est belle Gianluigi Braschi Roberto Benigni
La vie est belle Gianluigi Braschi Nicoletta Braschi
La vie est belle Gianluigi Braschi Giorgio Cantarini
Patch Adams Barry Kemp Robin Williams
Patch Adams Barry Kemp Monica Potter
Patch Adams Michael Farrell Robin Williams
Patch Adams Michael Farrell Monica Potter
Patch Adams Marvin Minoff Robin Williams
Patch Adams Marvin Minoff Monica Potter
Table ActeurFilm Table ProducteurFilm
titre nomActeur titre nomProducteur
La vie est belle Roberto Benigni La vie est belle Elda Ferri
La vie est belle Giorgio Cantarini La vie est belle Gianluigi Braschi
La vie est belle Nicoletta Braschi Patch Adams Barry Kemp
Patch Adams Robin Williams Patch Adams Michael Farrell
Patch Adams Monica Potter Patch Adams Marvin Minoff
CINQUIÈME FORME NORMALE
(FN5)
Source: Marc Frappier (UdeS), IFT187
39
DÉFINITION DE 5FN
▪ Une relation E est en cinquième forme normale ssi E ne peut être obtenue par une jointure de
relations E1, ..., En telle que l’une des Ei n’est pas une clé de E
▪ la quatrième forme normale est un cas particulier de 5FN; nous omettons sa définition
40
EXEMPLE DE 5FN
▪ les relations suivantes sont en 5FN
– cours – professeur
– prealablesCours – competence
– accessibilité – disponibilite
– groupeCours – etudiant
– inscription
41
CONTRE-EXEMPLE DE 5FN
▪ offreDeCours(sigle, session, matricule) représente le fait qu’un professeur peut enseigner le
cours à une session donnée
▪ cette relation peut être obtenue par la jointure des 3 relations suivantes:
▪ disponibilité(matricule, session)
▪ compétence(matricule, sigle)
▪ accessibilite(sigle, session)
42
CONTRE-EXEMPLE DE 5FN
accessibilité disponibilité compétence
sigle session matricule session matricule sigle
IFT286 H01 ⧓ 1 E01 ⧓ 1 IFT286
IFT286 E01 2 E01 2 IFT286
=
offreDeCours
sigle session matricule
IFT286 E01 1
IFT286 E01 2
NORMALISATION EN 5FN 43
offreDeCours
sigle session matricule
accessibilité disponibilité compétence
sigle session matricule session matricule sigle
44 44
FORMES NORMALES – RÉSUMÉ
▪ FN1: Pas d’attributs multivalués
▪ FN2: FN1+ Pas de dépendances partielles à la clé
▪ FN3: FN2 + Pas de dépendances vers une colonne non-clé
▪ FNBC: FN3 + Une colonne non-clé n’introduit pas de dépendances vers une partie
de la clé
▪ FN4: FNBC + Pas de dépendances multivaluées
▪ FN5: FN4 + Toute dépendance de jointure dans la table découle des clés
candidates de la table
RECETTE POUR UNE NORMALISATION
45 45
FACILE
▪ Il est généralement assez aisé de créer des tables normalisée en FN4 en
respectant certaines règles simples :
▪ Créer des tables à thème unique.
Ex.: une table Clients ne devrait pas avoir de colonnes autres que des colonnes qui
décrivent directement un client (i.e. pas les factures, etc.)
▪ Éviter des clés primaires composées et favoriser des clés artificielles numériques
▪ Éviter toute forme de dépendances multivaluées : créer une nouvelle table qui
contiendra uniquement chacun des champs multivalués
46 46
LES LIMITES DE LA NORMALISATION
▪ La normalisation permet d’éviter certaines anomalies et des redondances
▪ La normalisation introduit une complexité au niveau du modèle relationnel à
travers les décompositions successives et des associations introduites entre les
tables.
▪ La normalisation n’est pas une fin en soi: On ne vise pas toujours absolument FN6 –
On peut accepter (et tenir compte!) de certaines anomalies au profit de la
performance
➔ Dénormalisation…
▪ Cependant, dans la majorité des cas, les tables devraient être au moins en FNBC.
47
NORMALISATION
FN1 FN2 FN3