Lif10 – Fondements des bases de données
TD6 – Formes normales, minimisation, décomposition
Licence informatique – Automne 2014–2015
Les questions marquées du symbole (†) sont à préparer pour la séance
Exercice 1 : normalisation (†)
Donner la forme normale la plus avancée des schémas de relation suivants munis de l’ensemble Σ de
contraintes. Si ce n’est pas fait, normaliser la relation en la décomposant.
1. (†) Employe(NomEmp, NomDept, NomChef )
avec Σ = {NomEmp → NomDept; NomDept → NomChef } ;
2. (†) Employe(NomEmp, NomEnfant, Salaire)
avec Σ = {NomEmp → Salaire; NomEmp NomEnfant} ;
3. (†) Adresse(Rue, Ville, CodePostal)
avec Σ = {Rue, Ville → CodePostal; CodePostal → Ville} ;
Exercice 2 : Couverture minimale (†)
Soit Σ l’ensemble de DFs Σ = {A → B; A → C ; D → E ; C → D; B → C ; BC → A}
1. (†) Donner une couverture minimum de Σ en utilisant l’algorithme vu précédemment dont on rappelle
le principe :
1. calculer Σ0 = {X → X + | X → Y ∈ Σ}
2. supprimer les DFs f ∈ Σ0 redondantes, c’est-à-dire telles que Σ0 \ {f } |= f
2. (†) Réduire la couverture minimum en appliquant l’algorithme de réduction des parties droites et
gauches.
Exercice 3 : modélisation
On souhaite créer une base de données de recettes de cuisine, décrites comme suit :
Une recette est identifiée par son numéro. Elle a un nom et un type particulier (soupe, entrée,
dessert, ...). Elle utilise un ou plusieurs ingrédients (carottes, viande de boeuf, poivre, ...). Un
ingrédient est identifié par son numéro et a un nom. Pour chaque ingrédient dans une recette, on
précisera sa quantité.
1. Dresser l’inventaire des DF valides sur la relation universelle R = {NumR, NomR, TypeR, NumI, NomI, Qte}
2. Exhiber les problèmes de redondance à partir de cet exemple. La DF NumR, NumI → Qte engendre-
t-elle un problème de redondance ?
3. Proposer de façon intuitive une décomposition sans pertes et sans redondance de R.
4. On veut maintenant ajouter à cette modélisation qu’à chaque recette correspond un ensemble d’us-
tensiles (attribut Ustensile). Cette information se traduit-elle par une nouvelle DF ?
5. Que penser de la décomposition R1 = (NumR, NomR, TypeR), R2 = (NumR, NumI, Qte), R3 =
(NumI, NomI), R4 = (NumR, Ustensile).
Exercice 4 : définitions de la troisième forme normale
L’objectif de cette exercice est de montrer que les deux définitions 3FN-1 et 3FN-2 ci-après de la troisième
forme normale sont équivalentes. On considère les paires hR, F i formées d’un schéma de relation R et d’un
ensemble de F de dépendances fonctionnelles sur R. On donne les définitions suivantes :
Directe Une DF X → Y est directe ssi 6 ∃Z .X → Z ∧ Z 6→ X ∧ Z → Y .
Premier Un attribut A ∈ R est premier s’il appartient à au moins une clé minimale de R.
2FN hR, F i est en 2FN ssi il n’existe pas de DF non-triviale X → A ∈ F + avec A non-premier et X
sous-ensemble propre 1 d’une clé minimale.
3FN-1 hR, F i est en 3FN ssi hR, F i est en 2FN et toutes les DFs non-triviales X → A ∈ F + avec A
non-premier sont directes.
3FN-2 hR, F i est en 3FN ssi pour toute DF non-triviale X → A ∈ F + , soit X est (super)clé, soit A est
premier.
1. Montrer que si la condition 2FN n’est pas respectée, alors la 3FN-2 ne l’est pas non plus.
2. Montrer que s’il existe une DF non-triviale non-directe X → A ∈ F + avec A non-premier, alors la
condition 3FN-2 n’est pas respectée.
3. Conclure des deux questions précédentes que la définition 3FN-2 implique la définition 3FN-1.
4. Montrer que s’il existe une DF X → A avec A non-premier et X qui n’est pas (super)clé, alors la
condition 3FN-1 n’est pas satisfaite.
5. Conclure sur l’équivalence des définitions 3FN-1 et 3FN-2.
1. X est un sous-ensemble propre de Y noté X ( Y ssi X ⊆ Y ∧ X 6= Y
Corrections
Solution de l’exercice 1
1. en 2FN : on peut normaliser en R1 = (NomEmp, NomDept) et R2 = (NomDept, NomChef ) qui est
en FNBC
2. en 1FN : on peut normaliser en R1 = (NomEmp, salaire) et R2 = (NomEmp, NomEnfant) qui est en
4FN et donc en FNBC.
3. en 3FN : on ne peut pas faire mieux sans perte de dépendances.
Solution de l’exercice 2
1. On obtient la couverture minimum {B → ABCDE ; D → DE ; C → CDE ; A → ABCDE }
2. On obtient {B → A; D → E ; C → D; A → BC }
Solution de l’exercice 3
1. On a les DFs suivantes F = {NumR → NomR, TypeR; NumI → NomI; NumR, NumI → Qte} :
– Une recette est identifiée par son numéro. Elle a un nom et un type particulier
donne NumR → NomR, TypeR,
– Un ingrédient est identifié par son numéro et a un nom
donne NumI → NomI,
– Pour chaque ingrédient dans une recette, on précisera sa quantité
donne NumI → Qte.
2. Un problème de redondance a lieu lorsqu’une DF prends deux fois la même valeur à gauche et à droite,
autrement dit, si on a une DF X → Y et deux tuples t1 et t2 différents tels que t1 [XY ] = t2 [XY ]. La
dernière DF ne pose pas de problème, puisque la partie gauche est une clé.
3. On va décomposer selon les parties gauches des DFs obtenues R1 = (NumR, NomR, TypeR), R2 =
(NumR, NumI, Qte), R3 = (NumI, NomI).
4. Non, il n’y a pas de nouvelle DF non-triviale.
5. Cette décomposition engendre une perte de jointure... Il suffit pour cela d’exhiber la relation suivante
sur R :
No. Tuple NumR NomR TypeR NumI NomI Qte Ustensile
1 1 Couscous Plat principal 1 Pois Chiches 0,5kg Couscoussière
2 1 Couscous Plat principal 2 Agneau 1kg Plat
On peut vérifier quette relation ne viole aucune DF, elle est donc valide. On construit alors les relations
r1 , r4 en prenant les projections correspondantes. Ensuite, on fait la jointure naturelle entre ces relations.
On obtient :
No. Tuple NumR NomR TypeR NumI NomI Qte Ustensile
1 1 Couscous Plat principal 1 Pois Chiches 0,5kg Couscoussière
3 1 Couscous Plat principal 2 Agneau 1kg Couscoussière
4 1 Couscous Plat principal 1 Pois Chiches 0,5kg Plat
2 1 Couscous Plat principal 2 Agneau 1kg Plat
Cette relation est différente de la première, il y a donc perte de jointure et la décomposition n’est
pas correcte. On devrait préciser que soit l’ustensile dépend de l’ingrédient et de la recette ou alors
introduire une MVD pour préciser l’indépendance entre ustensiles et ingrédients dans une recette.
Solution de l’exercice 4
1. hABC , {AB → C , B → C }i n’est pas en 2FN. hABC , {A → B, B → C }i est en 2FN mais pas en 3FN.
2. Supposons hR, F i viole la 2FN, on a donc une dépendance X → A avec X ( K où K est une clé
minimale et l’attribut A non-premier. Comme K est minimale, X ne peut pas être clé et donc super
clé et la condition 3FN-2 n’est pas respectée.
3. Supposons que hR, F i satisfait une dépendance non-directe X → Z → A avec Z 6→ X avec A
non-premier. Comme Z 6→ X , Z n’est pas clé et viole la condition 3FN-2.
4. On a montré par la contraposée que la 3FN-2 implique la 2FN et la 3FN-2 implique l’absence de
dépendances non directe, c’est-à-dire la définition de la 3FN-1.
5. Supposons qu’il existe une dépendance X → A avec A non-premier et X qui n’est pas (super)clé. Soit
K une clé minimale :
– X ⊆ K et donc X ( K car X n’est pas super clé. On a une violation de la 2FN sur la dépendance
X →A
– X 6⊆ K et X 6→ K car sinon X serait clé. On a donc une dépendance transitive K → X → A qui
viole la condition 3FN-1.
6. La dernière question a montré par la contraposée que la 3FN-1 implique la 3FN-2 et d’après la question
4 on a l’équivalence recherchée.
