Université Abderrahmane Mira - Bejaia Année universitaire : 2020/2021

Faculté des Sciences Exactes Niveau : L3 RN SI

Département d'informatique Module : Bases de données

CHAPITRE 2 – Les dépendances fonctionnelles et la

normalisation

1. Introduction
La normalisation est une étape très importante dans la conception d'une base de
données. Elle consiste à décomposer une relation, sans perte d'informations, en plusieurs
relations, qui ne possèdent pas de problème de redondance, de mise à jour, d'insertion ou
de suppression de données.

2. La redondance de données
Le phénomène de redondance de données est problématique dans les bases de
données relationnelles. En effet, un schéma relationnel possédant une redondance ou une
incohérence de données est considéré comme étant mal conçu. En vue d'éliminer les
redondances ou du moins, les limiter, on procède à la normalisation de celle-ci, en se basant
sur le principe de dépendance fonctionnelle.

Exemple :
Soit le schéma relationnel SUIVI (Matricule, Nom, Prénom, Adresse, CodeModule, Intitulé,
Coef, Note). La relation définit le suivi des modules par des étudiants.

Le tableau suivant est l'extension de la relation SUIVI.

SUIVI
Matricule Nom Prénom Adresse CodeModule Intitulé Coef Note
001 SAKI Mourad Bejaia F124 BDD 04 10
002 AYAD Yasmine Bejaia M128 Réseaux 03 12
003 MALKI Leila Alger F130 GL 05 14
001 SAKI Mourad Bejaia M128 Réseaux 03 11
002 AYAD Yasmine Bejaia F130 GL 05 15

Table 1. Extension de la relation SUIVI

1
Université Abderrahmane Mira - Bejaia Année universitaire : 2020/2021
Faculté des Sciences Exactes Niveau : L3 RN SI
Département d'informatique Module : Bases de données

Quels sont les problèmes rencontrés avec la modélisation de cette relation ?

 Redondance : on remarque que les informations sont redondantes.

 Mise à jour : si on décide de changer l'adresse de l'étudiante "MALKI Leila", on devra
le faire sur tous les tuples où elle figure.
 Suppression : si on décide de supprimer l'étudiant "SAKI Mourad", le module dont
l'intitulé est "BDD" va être perdu vu qu'il dépend de l'inscription de l'étudiant "SAKI
Mourad".
 Insertion : si on décide d'ajouter un étudiant, on doit connaître toutes ses informations
et les cours qu'il suit (sauf si les valeurs manquantes sont permises).

Solution : Pour remédier aux problèmes cités plus haut, on décompose la relation
SUIVI en trois relations : ETUDIANTS, MODULES et SUIVRE. Puisqu'un étudiant peut
suivre plusieurs modules, et un module est suivi par plusieurs étudiants.
ETUDIANTS (Matricule, Nom, Prénom, Adresse).
MODULES (CodeModule, Intitulé, Coef).
SUIVRE (#Matricule,#CodeModule,Note).

ETUDIANTS MODULES

Matricule Nom Prénom Adresse Code Intitulé Coef

001 SAKI Mourad Bejaia Module

002 AYAD Yasmine Bejaia F124 BDD 04

003 MALKI Leila Alger M128 Réseaux 03

F130 GL 05

SUIVRE
Matricule CodeModule Note
001 F124 10
001 M128 11
002 M128 12
002 F130 15
003 F130 14
Table 2. Décomposition de la relation SUIVI sans redondance de données

2
Université Abderrahmane Mira - Bejaia Année universitaire : 2020/2021
Faculté des Sciences Exactes Niveau : L3 RN SI
Département d'informatique Module : Bases de données

Les trois nouvelles tables issues de la décomposition de la table SUIVI préservent la

cohérence des données du schéma relationnel initial, et limitent leur redondance en
utilisant la notion de références entre les tables.

3. Les dépendances fonctionnelles

3.1. Définition
Soit un schéma de relation 𝑅(𝐴1 , . . . , 𝐴𝑛 ) . Soient X, Y deux sous-ensembles tels que
𝑋, 𝑌 ⊆ {𝐴1 , . . . , 𝐴𝑛 }. On dit que X détermine Y ou que Y dépend fonctionnellement de X si
pour tous tuples 𝑡1 , 𝑡2 de l'extension de R : si 𝑡1 (𝑋) = 𝑡2 (𝑋) alors 𝑡1 (𝑌) = 𝑡2 (𝑌). Une
dépendance fonctionnelle est notée X  Y où X est le déterminant et Y la conclusion de la DF.

Exemple :

3.2. Axiomes d'Armstrong

Soit la relation 𝑅(𝐴, 𝐵, 𝐶, 𝐷). Les axiomes d'Armstrong sont des règles de déduction qui
permettent d'obtenir de nouvelles dépendances fonctionnelles qui satisfont la relation 𝑅 à
partir d'un ensemble donné 𝐹 de dépendances fonctionnelles.

3.2.1. La transitivité
Si AB et BC alors AC.
3.2.2. La réflexivité
Si B ⊆ A, alors A  B.
On appelle dépendances fonctionnelles triviales les DF qui sont issues de la réflexivité
(l'attribut A détermine lui-même ou une partie de lui-même)
3.2.3. La pseudo-transitivité
Il s'agit d'une généralisation de la transitivité. Si A  B et BC  D alors AC  D.

3.2.4. L'union
Lorsque deux dépendances fonctionnelles ont le même déterminant, il est possible de les
regrouper dans une seule et même dépendance fonctionnelle tel que :
Si A  B et A  C alors A  BC.

3.2.5. La décomposition
Permet de décomposer la conclusion d'une DF composée de deux attributs ou plus en
plusieurs DF tel que Si A  BC alors A  B et A  C.

3
Université Abderrahmane Mira - Bejaia Année universitaire : 2020/2021
Faculté des Sciences Exactes Niveau : L3 RN SI
Département d'informatique Module : Bases de données

3.2.6. L'augmentation
Permet d'ajouter un ou plusieurs attributs au déterminant et à la conclusion de la
dépendance fonctionnelle tel que : Si A  B, alors AC  BC et/ou AC  B.

3.3. Fermeture d'un ensemble d'attributs

Soit X un ensemble d’attributs de la relation 𝑅 et 𝐹 un ensemble de dépendances
fonctionnelles. On appelle fermeture de l’ensemble d’attributs X sous 𝐹, notée X + ,
l’ensemble des attributs déterminés par X (qui dépendent fonctionnellement de X) en utilisant
les dépendances de 𝐹.
L'algorithme suivant permet de calculer la fermeture X+ de l'ensemble d'attributs X.

Algorithme 1 – Fermeture d’un ensemble d’attributs. [KHAN 2019]

Entrée : Un ensemble d’attributs X.

Un ensemble de dépendances fonctionnelles F.
Début

1. Initialiser X + à X ;
2. Initialiser un ensemble F′ avec les dépendances fonctionnelles de F ;
3. Chercher une dépendance fonctionnelle u  v ∈ F′ telle que u ⊆ X + ;
Si la dépendance u  v existe Faire
Si v ∉ X +
X + = X + ∪ {v} ;
Finsi
4. F ′ = F ′ − { u v } ;
5. Aller à l’instruction 3.
Finsi
Fin
Sortie : X + la fermeture de X.

Exemple :

Soit la relation R( A, B, C, D, E) avec l'ensemble de dépendances fonctionnelles F={ACD,

CBDE, DCE}. Calculer A+ , C+ et (CD)+ .

 A+ = {A} , F' ={ ACD, CBDE, DCE}.

ACD : C ∉ A+ et D ∉ A+ alors A+ = {A, C, D} , F' ={CBDE, DCE}.

4
Université Abderrahmane Mira - Bejaia Année universitaire : 2020/2021
Faculté des Sciences Exactes Niveau : L3 RN SI
Département d'informatique Module : Bases de données

CBDE : B ∉ A+ et E ∉ A+ alors A+ = {A, C, D, B, E} , F' ={ DCE}.

DCE : E ∈ A+ et C ∈ A+ alors A+ = {A, C, D, B, E} , F' ={}.

 C+ ={C} , F' ={ ACD, CBDE, DCE}.

CBDE : B ∉ C+ et D ∉ C + et E ∉ C + alors C+ = {C, D, B, E} , F' ={ ACD, DCE}.
DCE : E ∈ C+ et C ∈ C + alors C + = {C, D, B, E} , F' ={ACD}.
A ∉ C + donc la DF ACD ne sera pas prise en compte.
C+ = {C, D, B, E}.
 (CD)+ = {C, D} , F' ={ ACD, CBDE, DCE}.
CBDE : B ∉ (CD)+ et E ∉ (CD)+ alors (CD)+ = {C, D, B, E} , F' = {ACD, DCE}.
DCE : E ∈ (CD)+ et C ∈ (CD)+ alors (CD)+ = {C, D, B, E}, F' = {ACD}.
A ∉ (CD)+ donc la DF ACD ne sera pas prise en compte.
(CD)+ = {C, D, B, E}.

3.4. Types de dépendances fonctionnelles

3.4.1. Dépendance fonctionnelle canonique
Une dépendance fonctionnelle X  Y est dite canonique si Y ne comporte qu'un seul
attribut.
Un ensemble F est dit canonique s'il est constitué de dépendances fonctionnelles canoniques.
Exemple : Matricule, Nom  Prénom.

3.4.2. Dépendance fonctionnelle élémentaire (réduite à gauche)

Une dépendance fonctionnelle X Y est dite élémentaire (ou réduite à gauche) si Y ne
dépend pas d'une partie de X. Tel que si X Y et X' ⊆ X alors X'↛ Y .

Exemple : ISBN, Auteur  Titre. Dans cette DF, le titre d'un livre peut être déduit par l'ISBN
qui est un identifiant unique. Donc l'attribut Titre dépend fonctionnellement de l'attribut
ISBN. Alors cette DF n'est pas élémentaire.

3.4.3. Dépendance fonctionnelle redondante (déduite)

Une dépendance fonctionnelle X  Y est dite redondante si elle peut être déduite
depuis d'autres dépendances fonctionnelles de F – {XY}. L'algorithme suivant permet de
déterminer si une DF est redondante ou pas.

5
Université Abderrahmane Mira - Bejaia Année universitaire : 2020/2021
Faculté des Sciences Exactes Niveau : L3 RN SI
Département d'informatique Module : Bases de données

Algorithme 2 : Déterminer la redondance d’une dépendance fonctionnelle. [KHAN 2019]

Entrée : Un ensemble F de dépendances fonctionnelles.

Une dépendance fonctionnelle XY dont la redondance est à vérifier.

Début
1. Calculer X+ dans 𝐅– {𝐗  𝐘} en utilisant l’algorithme 1.
2. Si Y ∈ X + Alors ;
3. La dépendance X  Y est redondante.
4. Sinon
5. La dépendance X  Y n’est pas redondante.
6. Finsi

Fin
Sortie : La dépendance X  Y est redondante dans F ou non.

Exemple :
Soit le schéma de relation R (A, B, C, D, E, F) et l'ensemble de dépendances fonctionnelles F =
{A B, ABC, ABC, BD A, A  EF, DE}. Les DF A B , ABC, DE sont redondantes.

 A B est-elle redondante ?
On calcule A+ dans F – {A B}
A+ = {A, B, C, E, F} on remarque que B ∈ A+ alors A B est redondante.
 ABC est-elle redondante ?
On calcule (AB)+ dans F – {ABC}
(AB)+ = {A, B, C, E, F} on remarque que C ∈ (AB)+ alors ABC est redondante.
 DE est-elle redondante ?
On calcule D+ dans F – {DE}
D+ = {D} on remarque que E ∉ D+ alors DE n'est pas redondante.

3.5. Couverture minimale d'un ensemble de dépendances fonctionnelles

La couverture minimale F′ d'un ensemble de dépendances fonctionnelles F est un
ensemble minimum de DF élémentaires à partir desquelles on peut déduire toutes les
dépendances fonctionnelles de F avec les axiomes d'Armstrong.

L'algorithme suivant permet de calculer la couverture minimale F′ d'un ensemble de

dépendances fonctionnelles F.

6
Université Abderrahmane Mira - Bejaia Année universitaire : 2020/2021
Faculté des Sciences Exactes Niveau : L3 RN SI
Département d'informatique Module : Bases de données

Algorithme 3– Couverture minimale d’un ensemble de dépendances [KHAN 2019]

Entrée : Un ensemble de dépendances fonctionnelles F

Début

1. Initialiser F′ à F ;
2. Mettre les dépendances de F′ sous forme canonique.
Toute dépendance X A1 , … , An est remplacée par n dépendances X Ai .
3. Réduire à gauche les dépendances non élémentaires.
Pour toute dépendance X Y ∈ F′ faire
Si ∃ Z ⊂ X / Y ∈ Z + alors
F′ = F′ − {X  Y} ∪ {Z  Y } ;
Finsi
Finpour
4. Éliminer les dépendances redondantes.
Pour toute dépendance XY ∈ F′ faire
Calculer X + dans F′ – {XY} ;
Si Y ∈ X + alors
XY est redondante ;
F′ = F′ − {XY} ;
Finsi
Finpour
Fin.
Sortie : La couverture minimale F′.

Exemple :
Soit le schéma relationnel R (A, B, C, D, E, F) et l'ensemble de dépendances fonctionnelles

F = {A→B, ABC, BDE, AD, AGE, BE G}.

Déterminer une couverture minimale de l'ensemble F.

1. Initialiser F ' à F
F′ = {AB, ABC, BDE, AD, AGE, BE G}.
2. Mettre les DF de F′ à la forme canonique
F′ = {AB, ABC, BD, BE, AD, AGE, BEG}
3. Réduire à gauche les dépendances non élémentaires
 Les dépendances fonctionnelles : AB, BD, BE, AD sont élémentaires.
 ABC

7
Université Abderrahmane Mira - Bejaia Année universitaire : 2020/2021
Faculté des Sciences Exactes Niveau : L3 RN SI
Département d'informatique Module : Bases de données

A+ = {A, B, C, D, E, G} , B+ = {B, D, E, G} On remarque que C ∈ A+

Alors ABC n'est pas élémentaire. On la remplace par la DF AC.
 AGE
A+ = {A, B, C, D, E, G} , G+ = {G} On remarque que E ∈ A+
Alors AGE n'est pas élémentaire. On la remplace par la DF AE.
 BE G
B+ = {B, D, E, G} , E + = {E} On remarque que G ∈ B+
Alors BEG n'est pas élémentaire. On la remplace par la DF BG.
L'ensemble F′ des DF réduites à gauche:
F′= {AB, BD, BE, AD, AC, AE, BG}
4. Eliminer les dépendances redondantes
 AB redondante ?
On calcule A+ dans F′– {AB}
A+ = {A, D, C, E} , B ∉ A+ On en conclut que AB n'est pas redondante.
 BD redondante ?
On calcule B + dans F′ – {BD}
B+ = {B, E, G} , D ∉ B + On en conclut que BD n'est pas redondante.
 BE redondante?
On calcule B + dans F′ – {BE}
B+ = {B, D, G} , E ∉ B + On en conclut que BE n'est pas redondante.
 AD redondante?
On calcule A+ dans F′ – {AD}
A+ = {A, B, C, D, E, G} , D ∈ A+ On en conclut que AD est redondante.
 AC redondante?
On calcule A+ dans F′ – {AC}
A+ = {A, B, D, E, G} , C ∉ A+ On en conclut que AC n'est pas redondante.
 AE redondante?
On calcule A+ dans F′ – {AE}
A+ = {A, B, D, C, E, G} , E ∈ A+ On en conclut que AE est redondante.
 BG redondante?
On calcule B + dans F′ – {BG}

8
Université Abderrahmane Mira - Bejaia Année universitaire : 2020/2021
Faculté des Sciences Exactes Niveau : L3 RN SI
Département d'informatique Module : Bases de données

B+ = {B, D, E} , G ∉ B + On en conclut que BG n'est pas redondante.

La couverture minimale F′ de l'ensemble de DF F :
F′ = {AB, BD, BE, AC, BG}.

3.6. Fermeture transitive d'un ensemble de dépendances fonctionnelles

La fermeture transitive d'un ensemble F de dépendances fonctionnelles, notée F + est
l'ensemble F auquel on ajoute les DF obtenues par l'axiome de transitivité.
F + = F ∪ {X Z} où X Y est une DF issue de l'application de l'axiome de transitivité
d'Armstrong.
Exemple :
Soit le schéma de relation R (A, B, C, D, E) et l'ensemble de DF F = {AB, BC, BD, AE}.
Déterminer la fermeture transitive F + de l'ensemble F.
AB et BC ⇒ A C en appliquant l'axiome de transitivité.
AB et BD ⇒ A D.
La fermeture transitive F + = {AB, BC, BD, AE, 𝐀 𝐂, 𝐀 𝐃}

3.7. Graphe des dépendances fonctionnelles

Le graphe des dépendances fonctionnelles représente les DF d'un ensemble
canonique F sous forme d'arcs orientés où les sommets représentent les déterminants et les
conclusions et les arcs représentent les dépendances fonctionnelles.
L'origine d'un arc peut être multiple alors que la cible doit être un sommet unique (étant
donné qu'il s'agit de dépendances fonctionnelles canoniques).
Exemple : Soit le schéma de la relation VEHICULE (NumVéhicule, Marque, Type, Puissance,
Couleur) et l'ensemble de dépendances fonctionnelles 𝐹 = {NumVéhiculeType,
TypeMarque, TypePuissance, NumVéhiculeCouleur}.

Donner le graphe des dépendances fonctionnelles de la relation VEHICULE.

Puissance
Type

NumVéhicule Marque
Couleur

Figure 1. Graphe des dépendances fonctionnelles de la relation VEHICULE

9
Université Abderrahmane Mira - Bejaia Année universitaire : 2020/2021
Faculté des Sciences Exactes Niveau : L3 RN SI
Département d'informatique Module : Bases de données

3.8. Notion de clés d'une relation

3.8.1. Clé minimale
Soit R (A1 , … , An ) une relation. X un sous ensemble d'attributs {A1 , … , An }. On dit que
X est une clé minimale de la relation R, si les deux conditions suivantes sont satisfaites :

Condition 1 (Unicité) : X détermine tous les attributs de R X + = {A1 , A2 , … , An }

Condition 2 (Irréductibilité/minimalité) : Tous les attributs de R ne doivent pas être

déterminés par une partie de X. En d'autres termes : ∄ X ′ ⊂ X tel que X’  A1 , A2 , … , An

Remarque : Si la relation R possède plusieurs clés minimales elles sont appelées "clés
candidates. La clé primaire, qui est unique, est choisie parmi les clés candidates.

3.8.2. Propriétés d'une clé minimale

Soit R une relation et F un ensemble de dépendances fonctionnelles.
Propriété 1. Tout attribut de R ne figurant pas dans les conclusions des dépendances
fonctionnelles doit appartenir à toutes les clés minimales

Propriété 2. Si les attributs qui ne figurent pas dans les conclusions des dépendances
fonctionnelles forment une clé minimale, alors elle est unique.

3.8.3. Super clé

Soit X la clé minimale d'une relation R. La super clé K d’une relation R est un sous-
ensemble d’attributs tel que : X ⊂ K.
La super clé K ne satisfait pas la condition de minimalité (Condition 2).
Exemple :
Soit le schéma de relation R (A,B,C,D,E) et l'ensemble de dépendances fonctionnelles

F = {A  BC ; CD  E ; B  D ; E A}

Donner les clés minimales de R.

On a : A+ = {A, B, C, D, E}

La condition 1 est vérifiée puisque l'attribut A détermine tous les attributs de R, alors il s'agit
d'une clé minimale.

10
Université Abderrahmane Mira - Bejaia Année universitaire : 2020/2021
Faculté des Sciences Exactes Niveau : L3 RN SI
Département d'informatique Module : Bases de données

E + = {E, A, B, C, D} l'attribut E détermine tous les attributs de R, Alors il s'agit d'une clé
minimale.

(BC)+ = {B, C, D, E, A} et B+ = {B, D} C+ ={C} Les conditions 1 et 2 sont vérifiées, alors BC est
une clé minimale.

(CD)+ = {C, D, E, A, B}, C+ ={C} et D+ = {D} Les conditions 1 et 2 sont vérifiées alors CD est
une clé minimale.

11