TD n°4 : Normalisation

Correction

Objectifs :
➢ Etudier les dépendances fonctionnelles.
➢ Normaliser une base de données relationnelle.

Exercice n°1 :
Soit R1 (A, B, C, D, E, F) une relation avec l'ensemble de dépendances suivant :
DF = {AB → C, AB → D, AB → E, AB → F, B → C, D → E, D → F}
1. Donner le graphe (ensemble) minimum de dépendances. Quelles est la clé de R1 ?

L'ensemble minimum de dépendances fonctionnelles de R1 est le suivant :

DF = { AB → D, B → C, D → E, D → F }
2. Quelle est la forme normale de R1 ?

La clé de cette relation est (A,B). Cette relation est en première forme normale mais pas en deuxième
forme normale car il y a un attribut qui ne fait pas partie de la clé (l’attribut C) qui dépend d'une partie
de la clé (l’attribut B).
3. On décompose la relation R1 en R11 et R12 : R11(A, B, D, E, F) et R12(B,C). Quelles sont les
formes normales des relations R11 et R12 ?

La relation R11 (A, B, D, E, F) est en deuxième forme normale et pas en troisième normale car il
subsiste une dépendance transitive. La relation R12(B,C) est en BCNF.
4. Proposer une décomposition sans perte d'information de R11.
On peut décomposer R11 en R111 (D, E, F) et R112(A,B,D) sans perte d'information.

Exercice n°2:
Soit le schéma de la relation R(A, B, C, D, E, G) et un ensemble donné de dépendances fonctionnelles
DF pour cette relation:
DF = {A → B,C ; A,C → E ; A,D,E → B,G ; C,G → D ; B,G → C ; C → B}
1

1. Donner la couverture minimale des dépendances fonctionnelles de R.

Page

Couverture minimale des dépendances fonctionnelles de R :

➢ Avec A → C et A, C →E, on constate que A, C → E n'est pas élémentaire et que l'on peut la
remplacer par A →E sans perte de dépendance.
➢ Avec A →E et A, D, E → B, G, on constate que A, D, E → B, G n'est pas élémentaire et que
l'on peut la remplacer par A, D → B, G sans perte de dépendance.
➢ Avec A → B et A, D → B, on constate que A, D → B est redondante et que l'on peut la
supprimer. Avec A → B, C → B et A →C, on constate que A → B peut être déduite et que l'on peut
donc la supprimer.

L'ensemble minimum des dépendances fonctionnelles de R est donc le suivant :

✓ A → C, E
✓ A, D → G
✓ C, G → D
✓ B, G → C
✓ C→B

2. Donner une décomposition de R en relations 3NF sans perte d'informations et sans perte de
dépendances.
Voici une décomposition sans perte de dépendance ni d'information :
➢ R1 (A, E, C) en BCFN
➢ R2 (A, D, G) en BCFN
➢ R3 (C, G, D) en BCFN
➢ R4 (B, G, C) en 3FN
3. Précisez l'identifiant de chaque relation obtenue.
Les clés de chaque relation :
➢ Pour R1 – la Clé est A
➢ Pour R2 – la Clé est le couple(A,D)
➢ Pour R3 – la Clé est le couple (C, G)
➢ Pour R4 – la Clé est le couple (B, G)

Exercice n°3:
On considère une relation R construite sur les attributs Propriétaire, Occupant, Adresse, Noapt,
Nbpièces, Nbpersonnes, un nuplet (P, O, A, N, NB1, NB2) ayant la signification suivante :
La personne O habite avec NB2 personnes l'appartement de numéro N ayant NB1 pièces dont le
propriétaire est P et l’adresse A.
2
Page
Une analyse de cette relation nous fournit un ensemble initial E de dépendances fonctionnelles :
E = {O → A ; O → N; O → NB2 ; A, N → P ; A, N → O ; A, N → NB1}
1. Donner l'ensemble des dépendances fonctionnelles élémentaires engendrées par E.
Fermeture transitive de E :
On a : O → A ; O → N donc O → A, N
Par transitivité on a donc : O → P et O → NB1
On a donc : O → A, N, NB2, P, NB1 et A, N → P, O, NB1, NB2
La DF A, N → NB2 est obtenue par transitivité avec O
2. Quelles sont les clés potentielles de R ?
Clés potentielles de R?
Une clé est un attribut (ou ensemble d’attribut) qui dérive tous les autres. Si on regarde la fermeture
transitive de E, on voit que :
O ainsi que A, N sont dans ce cas. Il y a donc deux clés potentielles.
3. R est-elle en 3ème forme normale ?
Forme normale de R :
Pour déterminer la forme normale de R, il faut d'abord distinguer les attributs clés des attributs non
clés :
✓ Attributs clés : A, O, N

✓ Attributs non clés : NB2, P, NB1

Une relation est forcément en 1FN. Elle est en 2FN si tous les attributs non clés dépendent pleinement
des clés. Ici c'est le cas, aucun attribut non clé ne dépend que de A ou N.
Une relation est en 3eme forme normale s'il n'existe pas de dépendance fonctionnelle entre deux
attributs non clés. C'est le cas ici. R est donc en 3FN.

Exercice n°4:
On considère le schéma relationnel R défini sur les attributs suivants :
C : cours
P : professeur
H : heure
S : salle
E : étudiant
3
Page

N : note
Un nuplet (C, P, H, S, E, N) a pour signification que le cours C est fait par le professeur P à l'heure H
dans la salle S par l'étudiant E qui a reçu la note N.
L'ensemble DF des dépendances fonctionnelles initiales est le suivant :
DF = {C → P ; H, S → C; H, P → S; C, E → N; H, E → S
1. Donner l'ensemble des dépendances fonctionnelles élémentaires engendrées par E.

Fermeture transitive de E :
C → P et H, P → S donc H, C → S
H, S → C et C → P donc H, S → P
H, P → S et H, S → C donc H, P → C
H, E → S et H, S → C donc H, E → C donc H, E → P
H, E → C et C, E → N donc H, E → N
En résumé on a :
C→P
H, C → S
H, S → C, P
H, P → S, C
C, E → N
H, E → S, C, P, N
2. Quelle est la clé de la relation R ? Montrer qu'elle est unique.

Clé de R :
De la fermeture transitive on déduit que H, E est une clé potentielle (dérive tous les autres attributs).
Elle est unique car H, E sont les seuls attributs qui ne sont pas en partie droite de DF. Donc ils
appartiennent forcément à toutes les clés.
Comme H, E est déjà une clé, il ne peut y en avoir d'autres.
3. Quelle est la forme normale de la relation R ? Si elle n'est pas en 3FN proposer une décomposition
en 3FN.
Décomposition de R :
R1, R2, R3 et R4 sont obtenues en décomposant R :
➢ R1 est obtenue en décomposant le schéma initial selon la DF C, E → N.
C'est la seule DF de R1 donc la clé est C, E. R1 est bien évidemment en 3FN (une seule DF).
➢ R2 est obtenue par la DF C → P. Là encore une seule DF, donc C est la clé de R2 et R2 est en
4
Page

3FN.
➢ R3 est obtenue par la DF H, S → C ou la DF H, C → S. Deux clés possibles H, S ou bien H, C.
R3 est aussi en 3FN.

➢ R4 est obtenue par la DF H, E → C. La clé est donc H, E et R4 est en 3FN.

Exercice n°5 :
Soit la relation « Client » qui possède le schéma suivant :
Client (numcli, codepostal, nom, prenom, tel, ville)
➢ Normaliser cette relation jusqu’à la BCFN.

Soit la relation : Client (numcli, codepostal, nom, prenom, tel, ville)

➢ 1FN : La relation « Client » est en 1FN puisqu’elle ne contient aucun attribut composé ou
multivalué.

➢ 2FN : La relation « Client » n’est pas en 2FN étant donné que la DF :

numcli, codepost → ville n’est pas élémentaire (seul le code postal suffit pour déterminer la ville).
Pour éviter ce problème, on peut réduire la clé au numéro du client. Le schéma de la relation Client
devient ainsi :
Client1 (numcli, nom, prenom, tel, ville, # codepostal)
➢ 3FN : La relation « Client1 » n’est pas en 3FN étant donné que la DF numcli → ville n’est pas
directe (numcli → codepostal et codepostal → ville).
Pour faire passer la relation « Client1 » en 3FN, il faut la décomposer en deux, ce qui donne les deux
schémas suivants :
Client2 (numcli, nom, prenom, tel, # codepostal)
Adresse (codepostal, ville)
➢ BCFN : les deux relations « Client2 » et « Adresse » sont en BCFN (aucun attribut autre que la
clé n’est déterminant)

Exercice n°6 :
Soit R une relation et X, Y, Z et W sont les ensembles d’attributs associés : R(X, Y, Z, W).
A-t-on les implications logiques suivantes ? Si la réponse est vrai préciser les axiomes d’Armstrong ou
les propriétés utilisés ?
5

1- {X → Y ; Z → W} => XZ → YW
Page
2- {XY → Z ; Z → X} => Z → Y

3- {X → Y ; W → Z} et Y  W => X → Z

4- {W → Y ; X → Z} => WX → Y

5- {XY → Z ; Y → X} => XW → Z

6- {X → Y ; X → W ; WY → Z} => X → Z

Pour examiner les implications logiques proposées, nous allons utiliser les axiomes d'Armstrong
(qui incluent la réflexivité, l'augmentation et la transitivité) et d'autres propriétés de la théorie des
ensembles.

1. {X → Y ; Z → W} => XZ → YW
o Vrai. On peut le démontrer en utilisant l'augmentation. À partir de X→Y, nous
pouvons ajouter Z pour obtenir XZ→YZ. Ensuite, à partir de Z→W, on peut
déduire YZ→YW. Par transitivité, on a XZ→YW.
2. {XY → Z ; Z → X} => Z → Y
o Faux. La proposition n'est pas toujours vraie. On peut avoir XY→Z sans que Z
entraîne nécessairement Y.
3. {X → Y ; W → Z} et Y ⊆ W => X → Z
o Vrai. Ici, on peut appliquer la propriété de la complémentarité : comme Y est inclus
dans W et que X→Y, cela signifie que X entraîne aussi W. Donc X→W, et en
utilisant W→Z, on peut conclure que X→Z.
4. {W → Y ; X → Z} => WX → Y
o Vrai. On peut utiliser l'augmentation. Comme X→Z, alors WX→YZ en utilisant
W→Y. En réduisant, on a WX→Y.
5. {XY → Z ; Y → X} => XW → Z
o Faux. Même si Y→X, cela ne garantit pas que XW→Z parce que l'implication ne
se transmet pas directement de cette manière.
6. {X → Y ; X → W ; WY → Z} => X → Z
6
Page
 o Vrai. On utilise ici la propriété de transitivité. De X→Y et X→W, on peut obtenir
X→WY. Ensuite, en utilisant WY→Z, par transitivité, X→Z.

En résumé :

1. Vrai
2. Faux
3. Vrai
4. Vrai
5. Faux
6. Vrai

7
Page