1

Université Saad DAHLAB BLIDA

Faculté des Sciences
Département d’informatique

Cours 4:
Dépendances Fonctionnelles et Normalisation

Enseignante responsable:
Dr. Nesrine LAHIANI
Public cible : 2ème année Ingénieur
Contact : [Link]@[Link]
Introduction
• Une mauvaise conception des entités et associations
représentant le monde réel modélisé conduit à des relations
problématiques
• Une redondance des données conduit à des risques
d'incohérences lors des mise à jour
• Il s'agit d'éliminer toute anomalie afin de faciliter la
manipulation des relations.

⇒ Normalisation des relations = Eclatement d'une

relation donnée en plusieurs relations normalisées.

2
Normalisation
Définition d’un schéma relationnel afin d’éviter:
La redondance des données
Les incohérences lors des mises à jour
Les anomalies lors des suppressions et/ou des insertions

3
 Analyse des problèmes d’un schéma
relationnel
Commande(numprod, quantité, numfour, adressefour)

numprod quantité numfour adressefour

101 300 901 Cité Benboulaid , Blida

104 280 902 Cité des Orangers,Birkhadem, Alger

112 170 901 Cité Benboulaid, Blida

103 250 904 Rue Garidi mohamed, Kouba

Quelles anomalies pour cette relation ?

 Redondances
 Anomalies de modification
 Anomalies d’insertion
 Anomalies de suppression
4
Dépendances fonctionnelles (1)
• Définition:
R(A1, A2, . . . , An) un schéma relationnel,
X , Y des sous-ensembles de {A1, A2, . . . , An}.

On dit que X détermine Y , ou que Y dépend

fonctionnellement de X s’il existe une fonction qui à
partir de toute valeur de X détermine une valeur unique
de Y .

Notation: X →Y

5
Dépendances fonctionnelles (2)

Exemple1:
PRODUIT (Ref_prod, Libelle_Prod, PU)
Ref_prod → Libellé_prod
Ref_prod → PU

Exemple2:
Evaluation (Matricule, nom, prénom, niveau, module, note_module)

Contient les DFs suivantes :

Matricule → nom, prénom, niveau
Matricule, module → note_module

6
Dépendances fonctionnelles composées

• Pour une dépendance fonctionnelle X → Y , X peut être

formé de plusieurs attributs.

 Un cours est suivi par un ou plusieurs étudiants ;

 un étudiant suit un ou plusieurs cours ;
 il a une note pour chacun.
numétudiant, numcours → note

 Lorsqu’un abonné emprunte un livre, on mémorise la date

d’emprunt et la date de retour.
isbn, numabo → dateemp, dateret

7
Dépendance Fonctionnelle Élémentaire

• Une Dépendance fonctionnelle X → Y est élémentaire si pour tout C

⊂X la dépendance fonctionnelle C → Y n’est pas vraie.
• En d’autres termes, Y ne dépend pas fonctionnellement d’une
partie de X
(X est la plus petite quantité d’information donnant Y).

 Exemple 1:
Ref_Prod, Libelle_Prod→PU
n’est pas élémentaire car Ref_prod →PU
 Exemple 2:

Ref_Article → Nom_Article VRAI

Num_Facture, Ref_Article → Qte_Article VRAI

Num_Facture, Ref_Article → Nom_Article FAUX

8
Dépendance Fonctionnelle Directe
• Soient X, Y deux attributs:
X→Y est une dépendance fonctionnelle directe s’il n’existe pas
un attribut Z qui engendrerait une DF transitive X→Z et Z→Y.

Exemple1:
Num_commande → Num_Client ; est directe
Num_client → Nom_Client ; est directe
Num_commande → Nom_client; n’est pas Directe
car Num_commande → Num_Client → Nom_client

9
Propriétés des dépendances fonctionnelles
(axiomes d’Armstrong)
• Les dépendances fonctionnelles obéissent à certaines
propriétés connues sous le nom d'axiomes d'Armstrong.

 Réflexivité :
 Si X est un ensemble d’attributs de R et Y ⊆ X , alors X → Y .
 En particulier, pour tout X , X → X .
 Augmentation :
 Si X détermine Y , alors (X, Z ) détermine (Y , Z ) pour tout ensemble d’attributs
 Autrement dit, si X → Y , alors pour tout Z , on a (X, Z ) → (Y , Z ).
 Transitivité :
 Si X détermine Y et Y détermine Z , alors X détermine Z
 Autrement dit, si X −→Y et Y −→ Z , alors X −→ Z .

10
Conséquences des axiomes d’Armstrong
 On peut déduire des propriétés supplémentaires à partir des
axiomes d’Armstrong.

 Union (addition) X →Y, X → Z ⇒ X →YZ,

 Pseudo-transitivité X → Y,WY →Z ⇒ WX→ Z

 Décomposition X →YZ ⇒ X →Y, X →Z

 Composition X →Y ,V →Z ⇒ XV→YZ

 Augmentation à gauche X→Y ⇒ XW→Y

11
La Fermeture Transitive des DFs d’une relation

• Définition :
Si F est un ensemble de DFs sur R, la fermeture transitive de
F notée F+ est l'ensemble des DFs qui peuvent être inférées
de F.

Exemple pour Voiture on a :

F={Châssis → Type; Type → Marque; Type → Puissance}
F+=F UNION {Châssis → Marque; Châssis → Puissance}

Remarque:
Deux ensembles de DF sont équivalents s’ils ont la même
fermeture transitive.

12
Fermeture d'un attribut sous F
• Définition :
• La fermeture d'un attribut X par rapport à F notée
X+(F) est l'ensemble des attributs fonctionnellement
dépendant de X sous la couverture fonctionnelle F.

• Employé(NE, ENom, NP, PNom, Loc,Temps)

F = { NE → ENom ; NP →{PNom, Loc} ; {NE,NP} → Temps}
 NE+ = {NE , ENom }
NP+ = {NP, PNom, Loc }
{NE,NP}+ = {NE,NP,ENom,PNom,Loc,Temps}

13
Couverture minimale
Définition :
une couverture minimale est l’ensemble F de DF élémentaires
associé à un ensemble d’attributs vérifiant les propriétés
suivantes:
 Aucune dépendance dans F n’est redondante;
 Toute DF élémentaire des attributs est dans F+;

 C’est le sous-ensemble minimal de DF permettant de générer

tous les autres.
 Exemple:
F={Châssis Type;Type  Marque; Type  Puissance ; Châssis 
Marque; Châssis  Puissance ; Châssis  Couleur;Type  Marque}

F={Châssis Type;Type  Marque;Type  Puissance; Châssis Couleur}

14
Clé candidate
• Clé primaire
Si plusieurs clés existent dans une relation, on en choisit une parmi celles-ci. Cette clé
est appelée clé primaire.

La clé primaire est généralement choisie de façon à ce qu'elle soit la plus simple, c'est à
dire portant sur le moins d'attributs et sur les attributs de domaine les plus basiques
(entiers ou chaînes courtes typiquement).

• Clé Candidate
On appelle clés candidates l'ensemble des clés d'une relation qui n'ont pas été choisies
comme clé primaire (elles étaient candidates à cette fonction).

15
 Partie 2:
la normalisation des relations

16
Normalisation
 Normaliser un schéma relationnel =>le remplacer par un schéma équivalent
dont le schéma ne présente pas d’anomalie.
 Outils : analyse des dépendances fonctionnelles.
 Objectifs :
 éviter les redondances,
 éviter les problèmes de mises à jours.
 Formes normales (de plus en plus contraignantes) :
• première forme normale (1FN)
• deuxième forme normale (2FN)
• troisième forme normale (3FN)
• forme normale Boyce Codd (BCNF)

17
Première forme normale (1NF)

• Définition
Une relation est en première forme normale si et seulement si
tous ses attributs ont des valeurs simples (non multiples, non
composées)
• Conséquences
Un attribut représente une donnée élémentaire du monde
réel
Un attribut ne peut désigner, ni une donnée composée
d’entités de nature quelconque, ni une liste de données de
même nature.

• Exemple
Pers1(nom, prénom, rueEtVille, prénomEnfants)
PErs2(nom, prénom, nombreEnfants)

18
Normaliser en 1NF

• 1ère solution:
Créer autant d’attributs que le nombre maximum de valeurs de
l’attribut multi-valué (stockage horizontal).

• 2ème solution:
Créer une nouvelle relation comportant la clef de la relation
initiale et l’attribut multi-valué puis éliminer l’attribut multi-
valué de la relation initiale (stockage vertical).

19
Deuxième Forme Normale (2NF)
Définition
Une relation est en deuxième forme normale si et
seulement si:
Elle est en première forme normale
Tout attribut n’appartenant pas à une clé ne dépend pas
que d’une partie de cette clé.

• Exemple
Enseignement (NUM, CODE_MATIERE, NOM,VOLUME, HORAIRE)
Avec: NUM → Nom

20
Normaliser en 2NF

Isoler la DF partielle dans une nouvelle relation

Eliminer l’attribut cible de la DF de la relation initiale

Exemple:
ENSEIGNEMENT(NUM,CODE,VOLUME_HORAIRE)
ENSEIGNANT(NUM, NOM)

Une relation en 1NF dont la clef est mono-attribut est forcément en 2NFG

21
Troisième Forme Normale (3NF)

• Définition
Une relation est en troisième forme normale si et seulement si:
 Elle est en deuxième forme normale:
 Tout attribut n’appartenant pas à une clé ne dépend pas d’un
autre attribut non clés.

Exemple:
⚫ ENSEIGNANT (NUM, NOM, CATEGPROE,CLASSE,SALAIRE) avec

CATEGORIE, CLASSE→ SALAIRE

22
Normaliser en 3NF
 Isoler la DF transitive dans une nouvelle relation
 Eliminer la cible de la DF de la relation initiale

Exemple:
⚫ ENSEIGNANT (NUM, NOM, CATEGPROE, CLASSE)
⚫ SALAIRE (CATEGPROE, CLASSE, SALAIRE)

23
Forme Normale de Boyce et Codd (BCNF)
Une relation est en BCNF si et seulement si:
Elle est en 3NF
Toute source de DF est une clé primaire minimale

• Exemple :
ADRESSE (Rue, ville, Bureau-Postal, CodePostal)

• Attributs atomiques 1NF

• Toutes les DF de sources AB sont minimales  2NF
• Pas de transitivité entre attribut non clé  3NF
• Mais Cette relation n’est pas en BCNF car l’attribut ‘’Ville’’ (qui
fait partie de la clé) dépend fonctionnellement de CodePostal
(qui est un attribut non membre de la clé).
24
Normaliser en BCNF
• ADRESSE (Rue, ville, Bureau-Postal, CodePostal)
Rue, Commune, Bureau-Postal  CodePostal
CodePostal  Commune

• Ville(CodePostal, nom)
• Adresse (Rue, CodePostal, BureauPostal)

25
Résumé

1NF 2NF 3NF BCNF

Eliminer toute
Eliminer toute
Eliminer toute dépendance à partir
dépendance entre
dépendance non d’un attribut
deux attributs ne
totale des attributs ordinaire vers une
faisant pas partie de
sur la clé primaire partie de la clé
la clé pimaire
primaire

26
Approche par synthèse

Recomposition des relations

à partir d’un ensemble
d’attributs indépendants.

27
Algorithme de synthèse
Enentrée: R(U, F) /* relation universelle*/

Ensortie: S= {Ri} 1 ≤ i ≤ n, schéma relationnel où chaque Ri est en 3NF

débutalgorithme

1. Rechercher une couverture minimale F0 de F

2. Partitionner F0 en groupes G1,…, Gk telles que toutes les dépendances fonctionnelles

d’un même groupe aient la même partie gauche.

3. Pour chaque groupe Gi construire une relation Ri dont la clé est la partie gauche.

4. Si aucune des relations obtenues à l’étape précédente ne contient (ou ne permet pas d’obtenir) la clé de la
relation initiale, on ajoute une relation composé des attributs de la clé.

fin algorithme
28
Exemple
Produit(prod_id, libellé, pu, dep_id, qte, adr, voulme)
Hypothèse: un produit est stocké dans un seul dépôt

f1: prod_id → libellé, pu

f2: prod_id, dep_id → qte

f3: prod_id → dep_id

f4: dep_id → adr, volume

f5: prod_id → adr

f6: prod_id → qte

29
Exemple
Produit(prod_id, libellé, pu, dep_id, qte, adr, voulme)
Hypothèse: unproduit est stocké dans unseul dépôt
f1: prod_id → libellé, pu, f2: prod_id, dep_id → qte
f3: prod_id → dep_id , f4:dep_id → adr, volume
f5:prod_id → adr F6:prod_id → qte
Déterminer unecouverture minimale(rendre DFélémentaires directes et canoniques)

1. DFélémentaire
(f1, f4) par décomposition:
f11: prod_id libellé, f12: prod_id pu
f41: dep_id adr, f42: dep_id volume
2. Éliminer f2 (à cause de notre hypothèse).
3. Eliminer les dépendancestransitives:

(f3: prod_id dep_id) et (f41: dep_id adr) donne (f5: prod_id adr)
supprimerf5

f11, f12, f3, f41, f42, f6 sont élémentaires directes et canoniques

30
Suite exemple
4. Traçons le graphe associé :

5. Grouper les attributs ayant la mêmesource de DFet la source dans une relation

31
Graphe des Dépendances Fonctionnelles
• Les DF peuvent être représentées à l’aide d’un graphe
dont les nœuds sont les attributs impliqués dans les
dépendances et les arcs représentent les dépendances
elles-mêmes.
• Les arcs sont orientés de la partie gauche de la dépendance
vers sa partie droite.

• L’origine d’un arc peut être multiple mais sa cible doit être
un noeud unique.

De ce fait il est nécessaire d’avoir pour la construction d’un

graphe de dépendance fonctionnelle un ensemble canonique
(conforme) de dépendances fonctionnelles.

32
Exemple
• F1 : RefProduit->LibelleProduit
• F2 : RefProduit -> PU
• F3 : NumService -> Adresse, Capacité
• F4 : RefProduit, NumService -> Quantité

33
Traduction du Graphe vers shéma E/A

34
Traduction du Graphe vers shéma E/A

35
Exercice 1
Démontrer queAD → BE en ayant les dépendances fonctionnelles
suivantes :
• A→ B
• B, C → D
• A,C → E
• D→ E

Démonstration:
 A→ B par augmentation avec D
 AD → BD(1)
 D → E par augmentation avec B
=> BD → BE (2)
 par transitivité = > AD → BE
36
Exercice 2
• Livre (code, titre, année, auteurs)
code titre année auteurs
100 Principe des 2000 CROCUS
SE KRACOVI

Décomposition:
Livre (code ,titre, année)
Auteur (code, auteur)
code titre année code auteurs
100 Principe des 2000 100 CROCUS
SE 100 KRACOVI

37
Exercice 3
• R(A,B,C,D,E)
• F={CDEFA, ACE B, CE DF, F C, D E}

▫ Trouvez une couverture minimale de F.

▫ Trouvez toutes les clés minimales de R munies de
F
▫ Quelles formes normales R muni de F vérifie?
▫ Décomposez en 3FN et BCFN

38
Exercice 4
• R=(Match, Arbitre, Heure, Date, Stade, Ville,
Joueur, Equipe)
• Clé : {H D J}
• F={MA, HDS M, HDA S, HDJ S, S V,
J E}

▫ Décomposez en BCFN

39
Exercice 5
• R={Spectacle, Auteur, Catégorie, Date, Heure}

▫ Quelles sont les dépendances fonctionnelles?

▫ Donnez une couverture minimale.
▫ Donnez une clé pour R
▫ Quelles formes normales R vérifie?

40
Exercice 6 : les commandes
• Soit la relation suivante :
Commande(NumCommande, NumProduit, QuantitéCommandée, NumClient,
NumReprésentant)
• dans laquelle les dépendances fonctionnelles valides sont les suivantes :
 NumCommande, NumProduit → QuantitéCommandée, NumClient, NumReprésentant
 NumCommande → NumClient, NumReprésentant
 NumClient → NumReprésentant

1. Proposer une clé primaire valide pour cette relation.

2. Expliquer pourquoi cette relation n’est pas en 2FN.
3. Décomposer la relation Commande en deux relations distinctes pour obtenir un schéma
relationnel en 2FN, tout en préservant les dépendances. Attention, on ne demande ici
que la 2FN.
4. Les tables obtenues sont-elles en 3FN ? Expliquer votre réponse. Si ce n’est pas le cas,
modifier le schéma afin d’obtenir un résultat en 3FN.

41