Les dépendances fonctionnelles

I- Notion de Dépendance Fonctionnelle (DF):

Définition : Soient X et Y deux sous-ensembles d’attributs ; on dit que X détermine Y et on note X 
Y si à une
valeur de X (occurrence de X) correspond au plus une valeur de Y. Autrement dit ; pour une valeur donnée x
appartenant à DX on ne peut avoir qu’une valeur unique y appartenant à DY.

Exemple 1: Considérons la relation personne suivante :

Personne (NSS, Nom, Prenom, Adresse)

NSS Nom Prenom Adresse

502 Bentahar Ali 21000 Skikda
503 Abdel Moumen 23000 Annaba
504 Bentahar Mohammed 24000 Guelma
505 Cheb Hocine 21000 Skikda
506 Ammi Rabah 19000 Setif

On voit bien sur cet exemple que NSS 

Nom car à un NSS donné ne correspond qu’un seul Nom. Exemple au NSS
= 504 ne correspond que le nom = ‘Bentahar’, par contre Nom  NSS est faux car, au Nom = ‘Bentahar’
correspondent les NSS 502 et 504.

Exemple 2: Considérons l’extension suivante de la relation R

R A B C
al bl cl
al bl c2
a2 b2 c2

Quelles sont les DFs existant dans R ?

- DF existantes dans R : A  B ( car a1 b1 et a2 
c2 mais pas C car a1 c1 et a1 
c2, ).
- B ne détermine pas C (car b1  c1 et b1 
c2).
- C ne détermine pas A (car c2  a1 et c2 
a2)
- C ne détermine pas B (car c2  b1 et c2 
b2)

Propriétés des dépendances fonctionnelles :

Le tableau suivant résume quelques propriétés des DFs, les exemples sont pris à partir de l’extension de la relation
voiture ci-dessous :

Voiture(NV,Type,Marque,Puissance,Couleur,NSS)

NV Type Marque Puissance Couleur NSS

2104-115-21 Sail Chevrolet 4CV Grise 504
1445-116-23 Symbol Renault 5CV Blanche 505
0058-112-21 Logan Dacia 5CV Blanche 505
1425-113-25 Symbol Renault 5CV Noire 506

1
Propriétés des DFs :
Propriété Définition Exemple
Réflexivité E E et E,F  E NV  NV
Tout ensemble d’attribut détermine NV, Type  Nv
lui-meme ou une partie de lui-meme
Augmentation Type  Marque alors
Si E  F alors ∀ 𝐺, E , G  F NV,Type  Marque
Projection Si E F,G alors NV  Type, couleur alors
E F et E G NV Type et NV 
couleur
Additivité Si E F et E  G alors E F,G NV Type et NV 
couleur alors NV  Type,
couleur
Transitivité Si E  F et F  G alors NV Type et Type 
E  G Marque alors NV  Marque
Pseudo-transitivité Si E  F et F,G  H alors E,G H NV NSS et NSS 
Diplôme alors NV, Diplôme
 Fonction
- Les types de dépendances fonctionnelles :
Type de la DF Définition Exemple
DF canonique E  F est canonique si F ne NV Type
contient qu’un seul attribut NSS Nom
DF élémentaire (DFE) E  F ( avec F ⊄E) est une NV , Type  couleur n’est
DFE s’il n’éxiste aucun sous- pas une DFE puisque NV 
ensemble de E qui détermine couleur
F. Il n’éxiste pas G inclus
dans E pour lequel G  F.
DF directe E  F est directe s’il n’existe NV, Type couleur n’est
pas G tel que E G et G  pas directe car NV  couleur
F

- Graphe de dépendances fonctionnelles :

C’est un moyen de visualisation des DFs. Les sommets correspondent aux attributs et les arcs aux DFEs entre
attributs.

Exemple :

NV NSS

Couleur
Puissance
Marque
Type
2
Axiomes d'Armstrong

A partir d'un ensemble F de dépendances fonctionnelles entre les attributs d'un schéma de relation R, on peut en
déduire d'autres à partir des trois propriétés suivantes (Axiomes d’Armstrong) :

1. transitivité : si X -> Y, et Y -> Z, alors X -> Z,

2. augmentation : si X -> Y, alors XZ -> Y pour tout groupe Z d'attributs appartenant au
schéma de relation,
3. réflexivité : si X contient Y, alors X -> Y (X X)

A partir de ces trois axiomes de base, on peut déduire d'autres règles telles que les suivantes qui sont couramment
utilisées :

1. union : si X -> Y et Y -> Z, alors X -> YZ,

2. pseudo-transitivité : si X -> Y et WY -> Z, alors WX -> Z,
3. décomposition : si X -> Y et Z contenu dans Y, alors X -> Z.

La fermeture d'un ensemble d'attributs X, notée (X)+, représente l'ensemble des attributs de R qui peuvent être
déduits de X à partir d'une famille de dépendances fonctionnelles en appliquant les axiomes d'Armstrong. Ainsi, Y
sera inclus dans (X)+ ssi X -> Y.

Algorithme de calcul de la fermeture d'un ensemble d'attributs :

Soit R(U) une relation, X ⊆ U et F l’ensemble des dépendances fonctionnelles sur R, l’algorithme suivant permet de
chercher la fermeture transitive X+ de X (c.a.d l’ensemble de tous les attributs de R qui sont déterminés par X de
façon directe ou indirecte).

1. initialiser (X)+ à X,
2. trouver une dépendance fonctionnelle de F possédant en partie gauche des attributs inclus
dans (X)+,
3. ajouter dans (X)+ les attributs placés en partie droite de la dépendance fonctionnelle,
4. répéter les étapes b) et c) jusqu'à ce que (X)+ n'évolue plus.

Exemple 1 :

Soit F = { A -> D ; AB -> E ; BI -> E ; CD -> I ; E -> C }.

Question : calculer la fermeture, sous F, de AE.

Solution : au départ, (AE)+ = AE,

A -> D permet d'ajouter D : (AE)+ = AED,

E -> C permet d'ajouter C : (AE)+ = AEDC,

CD -> I permet d'ajouter I : (AE)+ = AEDCI.

Question : calculer la fermeture, sous F, de BE.

Solution : au départ, (BE)+ = BE,

E -> C permet d'ajouter C : (BE)+ = BEC.

3
Exemple 2:

Soit F = { AB -> C ; B -> D ; CD -> E ; CE -> GH ; G -> A }.

Question : en utilisant la notion de fermeture d'un ensemble d'attributs, montrer que AB -> E,

Solution : B -> D |= AB -> D par augmentation,

AB -> C et AB -> D |= AB -> CD par union,

AB -> CD et CD -> E |= AB -> E par transitivité.

Question : en utilisant la notion de fermeture d'un ensemble d'attributs, montrer que BG -> C,

Solution : G -> A |= BG -> A par augmentation,

BG -> BG |= BG -> B par projection,

BG -> A et BG -> B |= BG -> AB par union,

BG -> AB et AB -> C |= BG -> C par transitivité.

Question : en utilisant la notion de fermeture d'un ensemble d'attributs, montrer que AB -> G.

Solution : AB -> E et AB -> C |= AB -> CE par additivité,

AB -> CE et CE -> GH |= AB -> GH par transitivité,

AB -> GH |= AB -> G par projection.

Inversement, on peut simplifier F en supprimant les dépendances fonctionnelles redondantes, c'est à dire celles qui
peuvent être déduites à partir d'un ensemble minimal F' appelé couverture minimale de F.

II- La normalisation

. Introduction

L'objectif de la normalisation est de construire un schéma de base de données cohérent et possédant certaines
propriétés vérifiées par la satisfaction de formes normales.

Pour une application spécifique, il est en effet possible de proposer plusieurs schémas. Les questions qui se posent
alors sont les suivantes :

o qu'est-ce qu'un bon schéma ?

o quel schéma choisir ?

10
Un mauvais schéma défini lors de la phase de conception peut conduire à un certain nombre d'anomalies pendant la
phase d'exploitation de la base :

o des redondances d'information,

o des anomalies lors des opérations de mise à jour (insertions, suppressions,
modifications).

Exemple 1:

Soit le schéma de relation FOURNISSEUR (Nom_Fournisseur, Adresse, Produit, Prix).

Une relation (table) correspondant à ce schéma pourra éventuellement contenir plusieurs produits pour un même
fournisseur. Dans ce cas, il faudra faire face à un certain nombre de problèmes :

 l'adresse du fournisseur sera dupliquée dans chaque n-uplet (redondance),

 si on souhaite modifier l'adresse d'un fournisseur, il faudra rechercher et mettre à jour tous
les n-uplets correspondant à ce fournisseur,
 si on insère un nouveau produit pour un fournisseur déjà référencé, il faudra vérifier que
l'adresse est identique,
 si on veut supprimer un fournisseur, il faudra retrouver et supprimer tous les n-uplets
correspondant à ce fournisseur (pour différents produits) dans la table

Exemple 2 :
Exemple de mauvais schéma. Considérons la relation ENSEIGNANT suivante :

ENSEIGNANT NUMERO NOM CATEGORIE CLASSE SALAIRE

l Dupont Maître de Conférences l l2000
2 Martin Maître de Conférences l l2000
3 Smith Professeur 2 l7000
4 Dupont Assistant l l0000
5 Durant Assistant l l0000

On a en fait la contrainte suivante : tous les enseignants de même catégorie et de même classe gagent
le même salaire, i.e. :
CATEGORIE, CLASSE  SALAIRE

Il y a dans cette relation redondance de données. Ceci conduit à des anomalies de stockage
(anomalies lors des opérations de mise à jours).
 Anomalie de modification :
ere
S’il y a une modification du salaire pour MC l classe, on fait autant d’opérations de

modification qu’il y a d’enseignant de cette catégorie et

de cette classe.
 Anomalie d’insertion :
Pour pouvoir stocker le salaire des MC 2eme classe, il faut qu’il y ait au moins un
enseignant dans cette catégorie et de cette classe.
 Anomalie de suppression :
Si l’unique professeur de 2eme classe part, on perd l’information sur le salaire des
professeurs de classe 2.

Ces anomalies n'apparaitront pas si on décompose le schéma initial de base de données. Par contre, la décomposition
d'un schéma relationnel au cours de la normalisation risque d'entrainer une dégradation des performances, du fait
des opérations de jointure nécessaires.
11
Principe : La normalisation consiste à décomposer une relation en plusieurs autres en fonction des dépendances
fonctionnelles afin d’en èliminer les redondances et les anomalies.

Les 3 premières formes normales ont été proposées par E.F. Codd ("inventeur" du modèle relationnel) en 1972. La
forme normale dite de Boyce-Codd a été proposée en 1974. Les 4ème(1977) et 5ème (1979) formes normales ont été
proposées ensuite par Fagin, mais elles ne concernent que des cas rares et très spécifiques.

Les formes normales s'appuient sur les dépendances fonctionnelles entre attributs d'un schéma de base de données.
Dans ce cours, nous nous interesserons uniquement aux 3 premières formes normale et à la forme de Boyce Codd.

DFs et normalisation : Les DFs guident la normalisation. Une normalisation sans perte est une normalisation qui
préserve les DFS.

Les formes normales :

 La première forme normale (1FN) :
- Tout attribut dépend fonctionnellement de la clé.
- La relation ne contient que des attributs atomiques.

Exemple : véhicule(NSS ,NV,Prenom,Nom,Couleur,Puissance,Type,Marque)

NV Prenom
Nom
Couleur
NSS Marque
Puissance
Type
 La deuxième forme normale (2 FN) :

- La relation doit etre sous 1FN .

- Tout attribut dépend de toute la clé et non pas d’une de ses parties.
- Il existe uniquement des DFEs entre les attributs non clés et la clé.

Exemple :
NSS Nom
Prenom
NV Couleur
Puissance
Marque
Type

Cette relation sera décomposée en deux autres :

R1(NSS,Nom,Prenom) et R2(NV ,NSS ,Couleur,Puissance,Marque,Type)

12
  La troisième forme normale (3FN) : (DFs élèmentaires et directes)

- La relation doit etre en 2FN

- Il n’existe aucune DF entre les attributs non-clés.
- Il existe uniquement des DFs elementaires et directes entre les attributs non clés.

Exemple :

NV NSS Nom
Prenom
Couleur
Type Marque
Puissance

Cette relation sera décomposée comme suit :

R1(NSS,Nom,Prenom)

R2(NV,NSS,Couleur,Type)

R3(Type,Puissance,Marque)