04/10/2018

Bases de données Relationnelles

Normalisation des
relations - FN

E. Zemmouri – ENSAM 2017

Plan
§ Objectif
§ Exemple d’introduction (motivations)
§ Normalisation – Formes normales
§ Dépendance Fonctionnelle
§ 1FN
§ 2FN
§ 3FN
§ BCNF
§ Méthodes de normalisation

Modèle Relationnel - Normalisation des relations 2

1
 04/10/2018

Normalisation des relations

§ Objectif :
• Concevoir un bon schéma relationnel.
ü Plusieurs schémas possibles
ü Comment choisir (concevoir) le meilleurs ?
• Un bon schéma relationnel est un schéma ne contenant pas
d’anomalies.

Modèle Relationnel - Normalisation des relations 3

Exemple d’introduction
§ Gestion des candidatures aux écoles post-Bac.
• Données manipulées :
ü CNE, nom et tel de l’étudiant
ü Lycée et ville d’origine
ü Série de Bac
ü Écoles demandées
§ On peut utiliser la relation:
• Candidature (CNE, NomEtud, Tel, NomEcole, Lycée, Ville, Série).

Modèle Relationnel - Normalisation des relations 4

2
 04/10/2018

Exemple d’introduction
§ Quelques tuples possibles :
• Candidature (CNE, NomEtud, Tel, NomEcole, Lycée, Ville, Série).
ü 123 Ali 05333 ENSAM Najah Meknès S.Maths
ü 123 Ali 05333 EST Najah Meknès S. Maths
ü 123 Ali 05333 FST Najah Meknès S. Maths
ü 234 Ahmed 06222 ENSAM Sijilmassa Errachidia S. Exp
ü 234 Ahmed 06222 FST Sijilmassa Errachidia S. Exp
ü 345 Majid 06444 ENSAM Najah Meknès LS. Humaines
ü … … … … … … …

§ Y a-t-il des anomalies ?

§ Oui !!
Modèle Relationnel - Normalisation des relations 5

Exemple d’introduction
§ Anomalies :
• Redondances
ü Des informations qui se répètes. (123 Ali 05333)
• Mise à jour
ü Ex. Modifier le tél d’un étudiant (modification de plusieurs
occurrences).
• Suppression
ü Ex. Supprimer la série LS. Humaines de la candidature ENSAM.
è supprimer complètement la série et/ou l’étudiant.

Modèle Relationnel - Normalisation des relations 6

3
 04/10/2018

Anomalies
§ Un bon schéma è pas d’anomalies :
• Redondances
ü Plusieurs fois la même information.
ü => des valeurs peuvent être éliminées sans perte d’information
• Anomalie de mise à jour
ü Une occurrence d’une information est modifié et pas les autres.
• Anomalie de suppression
ü Une information pertinente est perdue en supprimant un tuple.
§ La normalisation des relations permet d’éviter ces
anomalies.
Modèle Relationnel - Normalisation des relations 7

Normalisation des relations

§ Normalisation = Ensemble de règles introduites dans
le modèle relationnel dès son origine qui, une fois
appliquées, garantissent :
• La non redondance des données
• La cohérence lors de la manipulation des données
(insertion, mise à jour, suppression).
§ Ces règles sont appelées : Formes Normales (FN)

Modèle Relationnel - Normalisation des relations 8

4
 04/10/2018

Formes Normales
§ Les FN sont dépendantes :
1FN
2FN
3FN
BCNF
4FN

§ Une relation en 4FN est nécessairement en BCNF, 3FN, 2FN et 1FN.

Modèle Relationnel - Normalisation des relations 9

Dépendance fonctionnelle
§ Normaliser un schéma relationnel passe
essentiellement par l’étude des dépendances
fonctionnelles.
§ Concept clé dans la conception de bon schémas
relationnels.
• Mais aussi pour :
ü Stockage de données : compression
ü Optimisation des requêtes.

Modèle Relationnel - Normalisation des relations 10

5
 04/10/2018

Dépendance fonctionnelle
§ Exemple : Candidature aux écoles post-bac
• Etudiant (CNE, NomEtud, Adresse, Moy, Mention,
CodeLycée, NomLycée, VilleLycée)
• Candidature (CNE, NomEcole, VilleEcole, Date, Filière)
§ On suppose la mention déterminée par la Moy :
• 16 ≤ Moy à mention = T. bien
• 14 ≤ Moy < 16 à mention = Bien
• 12 ≤ Moy < 14 à mention = A. bien
• 10 ≤ Moy < 12 à mention = Passable
Modèle Relationnel - Normalisation des relations 11

Dépendance fonctionnelle
§ Deux Tuples ayant la même Moy doivent avoir la
même mention.
• Ʉ (t, u) ϵ étudiant :
t.moy = u.moy => t.mention = u.mention
§ On dit que la mention dépend fonctionnement de moy
(ou moy détermine mention)
§ On note : Moy à Mention

Modèle Relationnel - Normalisation des relations 12

6
 04/10/2018

Dépendance fonctionnelle
§ Soit R une relation et A, B deux attribut
§ A à B si
• Ʉ (t, u) ϵ R (deux tuples de R) :
t.A = u.A => t.B = u.B
§ Deux tuples ayant le même A doivent avoir le même B
§ B dépend fonctionnellement de A
§ A détermine B
§ La connaissance de la valeur de A entraîne la
connaissance de la valeur de B.
Modèle Relationnel - Normalisation des relations 13

Dépendance fonctionnelle
§ A1, A2, …, An à B1, B2, …, Bm
• Ʉ (t, u) ϵ R (deux tuples de R) :
t.[A1, A2, …, An ] = u.[A1, A2, …, An] =>
t.[B1, B2, …, Bm] = u.[B1, B2, …, Bm ]

Modèle Relationnel - Normalisation des relations 14

7
 04/10/2018

Dépendance fonctionnelle
§ DF et Clés de la relation :
• Si un attribut (ou un groupe d'attributs) détermine par DF
tous les autres attributs de la même relation, c'est une clé
de la relation.

Modèle Relationnel - Normalisation des relations 15

Dépendance fonctionnelle
§ N.B.
• Les DF sont basées sur la compréhension du monde réel.
• Si on a une DF sur une relation R, toutes les instances de R
doivent adhérer à cette DF.
ü Ʉ (t, u) ϵ R.

Modèle Relationnel - Normalisation des relations 16

8
 04/10/2018

Dépendance fonctionnelle
§ Propriétés :
• A à B, C => A à B et A à C (Décomposition)
• A à B et A à C => A à B,C (Combinaison)
• A à B et B à C => A à C (transitivité)
• A à B => A à A ∩ B
• A à B => A à A U B
• Si B est une partie de A alors AàB (dépendance triviale)

Modèle Relationnel - Normalisation des relations 17

Dépendance fonctionnelle
§ Dépendance fonctionnelle élémentaire
• une DF, A à B, est une dépendance fonctionnelle
élémentaire si B est un attribut unique, et si A est un
ensemble minimum d'attributs (ou un attribut unique).
• => B ne dépend pas d’une partie de A.

Modèle Relationnel - Normalisation des relations 18

9
 04/10/2018

Première Forme Normale 1FN

§ Une relation est en première forme normale si :
• Elle possède une clé
• Les domaines de ces attributs sont constitués de valeurs atomiques :
chaque valeur d’un attribut provienne d’un domaine non structuré.
ü Pas d’ensemble.
ü Pas de type énuméré.
ü Pas de groupes répétitifs.
§ Si les relations résultant de la modélisation ne sont pas déjà en
1FN, il serait approprié de retourner à l’étape de modélisation!
§ Une modélisation de qualité minimale devrait toujours être en
1FN.
Modèle Relationnel - Normalisation des relations 19

1FN

Un schéma R est en 1NF Si et seulement si les domaines

de tous ses attributs sont atomiques (mono-valués)

Modèle Relationnel - Normalisation des relations 20

10
 04/10/2018

1FN
§ Exemple 1: employés – projets
• MembreProjet (ID, Nom, Fonction, IDProjet)
§ Relation non normalisée § Relation en 1FN
ID Nom Fonction IDProjet ID Nom Fonction IDProjet

E7 Ali Développement {P1, P3} E7 Ali Développement P1

E2 Hassan Management {P2} E7 Ali Développement P3

E10 Ahmed Marketing {P1, P2, P3} E2 Hassan Management P2

E10 Ahmed Marketing P1

E10 Ahmed Marketing P2

E10 Ahmed Marketing P3

Modèle Relationnel - Normalisation des relations 21

1FN
§ Exemple 2 :
• LIVRES(N°Auteur, titre, auteur, genre, langue)

N° Auteur Titre Auteur Genre Langue

123 DataBases Wisdom Technique Anglais

234 Misérables, Dernier Jour Hugo Roman Français

345 Bourgeois, Fourberies Molière Roman Français

Modèle Relationnel - Normalisation des relations 22

11
 04/10/2018

1FN
§ N.B.
• La première forme normale impose que chaque ligne d’une
relation ait une seule valeur pour chaque colonne (i.e.
attribut), ce qui est justement la définition d’une table.
Donc, une table est nécessairement en première forme
normale au sens du modèle relationnel.

Modèle Relationnel - Normalisation des relations 23

Deuxième Forme Normale : 2FN

§ Une relation est en deuxième FN si :
• Elle est en 1FN
• Il existe une dépendance fonctionnelle élémentaire reliant la
clé à chaque attribut non clé.
• è tout attribut hors clé ne dépend pas d’une partie de la clé

Modèle Relationnel - Normalisation des relations 24

12
 04/10/2018

2FN

Un schéma R est en 2FN Si et seulement si Tout attribut de R,

n’appartenant pas à la clé primaire , est en dépendance
fonctionnelle totale de la clé primaire

Modèle Relationnel - Normalisation des relations 25

2FN
§ Soit R (A,B,C,D) :
A, B

DF partielle

C D

Modèle Relationnel - Normalisation des relations 26

13
 04/10/2018

2FN
§ Comment normaliser en 2 NF par décomposition :
• Isoler la DF partielle dans une nouvelle relation
• Eliminer la cible de la DF de la relation initiale
§ è R1 (A, B, D) et R2 (A, C)

A,B A

D C

Modèle Relationnel - Normalisation des relations 27

2FN
§ Exemple 1 :
• MembreProjet (ID, Nom, Fonction, IDProjet, intituléProjet,
pourcentage)
ü Clé de la relation : (ID, IDProjet)
• On note :
ü IDàNom, IDà Fonction
§ Une table doté d’une clé composée, qui n’est pas en 2FN
doit être décomposée en sous-tables.
• Employé (ID, Nom, Fonction)
• Projet (IDProjet, Intitulé)
• Participation (*ID, *IDProjet, pourcentage)
Modèle Relationnel - Normalisation des relations 28

14
 04/10/2018

2FN
§ Exemple 2: gestion de compte bancaire
• OPERATION(N°Compte, CodeOp, DateOp, Nom, Prenom,
LibelléOp, Somme)
§ La relation est-elle en 1FN ? Oui
§ Est-elle en 2FN ? Non

Modèle Relationnel - Normalisation des relations 29

2FN
§ Exemple 2 : gestion de compte bancaire
• OPERATION(N°Compte, CodeOp, DateOp, Nom, Prenom,
LibelléOp, Somme)
• On note que :
ü N°Compte à Nom et N°Compte à Prénom
ü CodeOp à LibelléOp
§ Correction :
• COMPTE(N°Compte, Nom, Prénom)
• LIBELLE(CodeOp, LibelléOp)
• OPERATION(N°Compte, DateOp, CodeOp, somme)
Modèle Relationnel - Normalisation des relations 30

15
 04/10/2018

Troisième Forme Normale : 3FN

§ Une relation est en troisième forme normale si :
• Elle est en 2 FN
• Tout attribut hors clé est en DF directe par rapport à la clé
(pas de transitivité)

Modèle Relationnel - Normalisation des relations 31

3FN

§ Un schéma R est en 3NF ssi

• R est en 2NF,
• Aucun attribut ne dépend transitivement de la clé primaire,
(tout attribut de R, n’appartenant pas à la clé, ne dépend
que de la clé),

Modèle Relationnel - Normalisation des relations 32

16
 04/10/2018

3FN
§ Soit R (A,B,C,D) :

A
DF transitive

B C D

Modèle Relationnel - Normalisation des relations 33

3FN
§ Comment normaliser en 3 NF par décomposition :
• Isoler la DF transitive dans une nouvelle relation
• Eliminer la cible de la DF de la relation initiale
§ è R1 (A, B, C) et R2 (C, D)

A C

B C D

Modèle Relationnel - Normalisation des relations 34

17
 04/10/2018

3FN
§ Exemple 1 :
• Employé (Matricule, NomEmp, Fonction, CodeService, NomService).
§ La relation est en 2FN.
§ Mais :
• MatriculeàCodeServiceàNomService
§ ==>
• Employé (Matricule, Nom, Fonction, CodeService*)
• Service(CodeService, NomService)

Modèle Relationnel - Normalisation des relations 35

3FN
§ Exemple 2:
• Etudiant (CNE, Nom, Prénom, CodeLycée, Lycée, Ville, Moy,
Mention)
§ La relation est en 2FN ?
§ Mais :
• CodeLycée à Lycée, CodeLycéeàVille
• Moy à Mention

Modèle Relationnel - Normalisation des relations 36

18
 04/10/2018

Forme Normale de Boyce-Codd : BCNF

§ Une relation est en BCNF si :

• Pour toute dépendance fonctionnelle (non triviale) AàB sur
les attributs de R, A est une clé de R.

• C’est-à-dire :
ü Tout attribut non clé de la relation n'est pas source de DF.

ü Les seules DF élémentaires qu’elle comporte sont celle où une clé

détermine un attribut.

Modèle Relationnel - Normalisation des relations 37

BCNF
§ Une relation est en BCNF si et seulement si :
• Elle est en 2 NF
• Toute source de DF est une clef primaire minimale
§ N.B.
• Si une relation R est en BCNF alors elle est en 3 NF.
• Si R est en 3 NF alors elle n’est pas forcément en BCNF

Modèle Relationnel - Normalisation des relations 38

19
 04/10/2018

BCNF
§ Soit R (A,B,C,D, E) :

A, B

C D E

R est en 1, 2, et 3FN, mais pas en BCNF

Modèle Relationnel - Normalisation des relations 39

BCNF
§ Comment normaliser en BCNF par décomposition :
• Isoler la DF problématique dans une nouvelle relation
• Eliminer la cible de la DF problématique et la remplacer par
sa source dans la relation initiale
§ è R1 (A,E, C, D) et R2 (E, B)
A, E E

C D B

Modèle Relationnel - Normalisation des relations 40

20
 04/10/2018

BCNF
§ Exemple : soit la relation
• ADRESSE( Lieu, Rue, Ville, CodePostal)
§ Quelles sont les DF existant dans cette relation ?
§ En quelle forme normale est la relation ?

Modèle Relationnel - Normalisation des relations 41

BCNF
§ Exemple : ADRESSE
§ DF :
• Ville, Rue à CodePostal
• CodePostal à Ville
§ La relation n’est pas en 2FN:
• ADRESSE( Lieu, Rue, Ville)
• CP (Rue, Ville, CodePostal)
§ Adresse et CP sont en 2FN et en 3FN
• Mais CP n’est pas en BCNF

Modèle Relationnel - Normalisation des relations 42

21
 04/10/2018

BCNF
§ CP (Rue, Ville, CodePostal)
• N’est pas en BCNF, car CodePostalàVille.
§ Normalisation :
• CodeVille (CodePostal, Ville)
• CodeRue (Rue, CodePostal)
§ Problème :
• La dépendance Rue, Villeà CodePostal est perdue.
§ Toute relation a une décomposition en BCNF sans perte
d’information, par contre, une décomposition en BCNF ne
préserve pas généralement les DF.
Modèle Relationnel - Normalisation des relations 43

Formes Normales – Résumé

Modèle Relationnel - Normalisation des relations 44

22
 04/10/2018

Méthodes de Normalisation
§ Il est souhaitable qu’un schéma relationnel ne
comporte que des relations en 3FN ou BCNF.
§ Des algorithmes de constructions permettent
d’obtenir de tels schémas.
§ Ils sont de deux catégories :
• Méthode de décomposition
• Méthode synthétique

Modèle Relationnel - Normalisation des relations 45

Méthodes de Normalisation
§ Méthode de décomposition :
• Elle se base sur la décomposition de relations en utilisant les DF
entre les données.
• Cette méthode conduit à des relations en 3NF ou BCNF.
• Elle présente 2 problèmes :
ü Identification exhaustive des DF
ü Le résultat dépend de l’ordre d’application des décompositions et
peut ne pas préserver les DF

Modèle Relationnel - Normalisation des relations 46

23
 04/10/2018

Méthodes de Normalisation
§ Méthode synthétique :
• Elle se base sur la représentation des DF en terme de graphe.
• À partir du graphe on déduit des relations normalisées en 3FN.

Modèle Relationnel - Normalisation des relations 47

Méthode synthétique
§ Point de départ
• L’ensemble de tous les attributs
• L’ensemble des DF entre attributs qui sont représentées dans un graphe
avec comme nœud un attribut et comme arc une DF
§ Ce qu’il faut faire
• Trouver la couverture minimale du graphe c’est-à-dire éliminer les
circuits ainsi que les DF non élémentaires et non directes
§ Résultat
• Une collection de relation en 3NF. Chaque schéma est obtenu en
prenant comme :
ü Clé une source de DF
ü Attributs, les cibles des DF correspondant

Modèle Relationnel - Normalisation des relations 48

24
 04/10/2018

Méthode synthétique – exemple

§ Service d’immatriculation de voitures dans une préfecture
• Soient les DF suivantes :
ü N°Immat -> Couleur, Type, Puissance, Marque
ü N°Pers -> Nom, Prénom, Adresse
ü N°Immat -> N°Pers et Type -> Marque, Puissance
• On crée le graphe :

N°Pers N°Immat Type

Puissance
Nom Prénom Adresse Couleur
Marque

Modèle Relationnel - Normalisation des relations 49

Méthode synthétique – exemple

§ On obtient :
• Personne (N°Pers, Nom, Prénom, Adresse)
• Voiture (N°Immat, Couleur, Type*, N°Pers*)
• Types (Type, Puissance, Marque)

Modèle Relationnel - Normalisation des relations 50

25
 04/10/2018

Exercice 1
Soit la relation :
• Commande (NumCommande, RefProduit, Quantité, IDClient, IDReprésentant)
Avec les dépendances fonctionnelles suivantes :
• NumCommande, RefProduit à Quantité, IDClient, IDReprésentant
• NumCommande à IDClient, IDReprésentant
• IDClient à IDReprésentant

1. Indiquer les clés candidates de la relation R

2. Citer les anomalies et les redondances qui se trouvent dans la relation R
3. Décomposer la relation R afin de supprimer les anomalies.
4. Vérifier que la décomposition est sans perte d’information et sans perte de dépendances

Modèle Relationnel - Normalisation des relations 51

Exercice 2
On considère la relation suivante décrivant les employés travaillant sur des projets dans
des laboratoires.
• Employé ( N°Emp, N°Lab, N°Proj, NomEmp, NomProj, adresse)
Avec les dépendances fonctionnelles suivantes:
• (N°Emp, N°Lab) → N°Proj, NomProj, NomEmp
• N°Emp → NomEmp
• N°Emp → adresse
• N°Proj → NomProj
1. Identifier les redondances éventuelles,
2. Etablir le graphe minimum des DF,
3. Définir les clés candidates,
4. Définir la forme normale et la justifier,
5. Proposer une décomposition optimale.

Modèle Relationnel - Normalisation des relations 52

26
 04/10/2018

Exercice 3
§ Soit la relation R(A,B,C,D,E,F,G,H) avec l’ensemble F des
dépendances fonctionnelles suivantes:
• F={ ABàC, BàD, CDàE, CEàGH, GàA}
§ Démontrer les affirmations suivantes :
• ABàEH et BGàGH
§ Dessiner le graphe de dépendance
§ Donner toutes les clefs candidates de la relation R
§ Donner la forme normale de la relation R
§ Rendre la relation R en 3FN

Modèle Relationnel - Normalisation des relations 53

Exercice 4
§ Soit R (A, B, C, D, E, F, G) la relation suivante, avec les
dépendances:
• B → D, DE → A, AB → C, CE → G, CE → H, G → E
1. Démontrer en justifiant votre réponse les dépendances
fonctionnelles suivantes :
1. BE → HC et BG → HA
2. Etablir le graphe minimum de dépendances.
3. Donner toutes les clefs candidates de la relation R.
4. Quelle est la forme normale de R? Justifier votre réponse.
5. Proposer une décomposition optimale de R.
Modèle Relationnel - Normalisation des relations 54

27
 04/10/2018

Exercice 5
§ Soit la relation suivante qui décrit les affectations des conducteurs de bus aux
lignes pour les jours du mois en cours.
Affectation ( N°ligne , N°conducteur , jour )
§ Considérons indépendamment les règles de gestion suivantes:
1. Un conducteur ne peut pas travailler sur deux lignes différentes le même jour;
2. Un conducteur ne fait qu'une seule ligne;
3. Une ligne n'est parcourue que par un seul conducteur;
4. Un conducteur ne fait pas la même ligne deux jours différents.
§ Pour chacune des règles : définir les DF, la FN, une clé minimale puis
normaliser la relation.

Modèle Relationnel - Normalisation des relations 55

Exercice 6
§ Soit la relation
• RESTAURANT (NuméroMenu, NomMenu, NuméroPlat, NomPlat, TypePlat)
§ Avec l’ensemble de Dépendances Fonctionnelles:
• NuméroMenu à NomMenu
• NuméroMenu à NuméroPlat
• NuméroPlat à NomPlat
• NuméroPlat à TypePlat

§ Déterminer une clé pour la relation RESTAURANT. Justifier votre réponse.

§ Sous quelle Forme Normale se trouve la relation RESTAURANT ? Justifier.
§ Proposer une décomposition de la relation RESTAURANT en 3FN sans perte
d’information.

Modèle Relationnel - Normalisation des relations 56

28
 04/10/2018

Exercice 7
§ On considère la relation Prime: liste des primes attribuées au
personnel technique en fonction des machines sur lesquelles il
travaille
• Prime (N°machine, atelier, N°techn, montant-prime, nom-techn)
§ avec les dépendances fonctionnelles suivantes:
• N°machine → atelier
• N°techn → nom-techn
• (N°machine, N°techn) → montant-prime
1. Etablir le graphe minimum de dépendances.
2. Donner toutes les clefs candidates de la relation .
3. Quelle est la forme normale de la relation? Justifier votre réponse.
4. Proposer une décomposition optimale de la Relation Prime.

Modèle Relationnel - Normalisation des relations 57

29