Spécialité : informatique/ base de données Date :
Module : SGBDR N° Séance : 06
Titre : Couverture minimale Durée : 4 h
Professeur : Boudiar Boudjemaa Niveau : 5
1) Le Graphe des dépendances fonctionnelles :
Le graphe des dépendances fonctionnelles permet de mettre en évidence toutes les DFs élémentaires, et
directes qui existent entre l’ensemble des propriétés du domaine étudié.
Le graphe ainsi obtenu est appelé Structure d’accès Théorique (SAT).
Exemple :
Soient les DFs suivantes :
Numero_matiere →libelle_matiere
Numero_etudiant →nom_etudiant
Numero_etudiant →prenom_etudiant
Numero_etudiant , Numero_matiere,date_examen →note
date_examen Numero_matiere
Numero_etudiant
• •
•
• • •
Nom_etudiant prenom_etudiant
libelle_matiere
•
Note
Soient les DFs suivantes :
Num_four→R_s_four
Num_four→rue_four
Num_four→Ville_four
Num_four→P_four
Num_dep→lieu_dep
Ref_prod→lib_prod
Ref_prod→pu_prod
Num_com→date_com
Num_com→num_four
Num_com→num_liv
Num_liv→date_liv
Num_liv→num_com
Num_com, Ref_prod →Qte_com
Num_liv, Ref_prod →Qte_liv
Num_dep, Ref_prod →Qte_stk
Donnez le graphe de DFs (SAT) ?
Num_four Num_com
• •
•
Date_com
• •
R_S_four
Adr_four
• Num_liv • Ref_prod
• • Lib_prod
Qté_com
• Pu_prod
• Num_dep
•
• •
date_liv
Qté_liv
•
Qté_stk Lieu_dep
2) Couverture minimale (irréductible) :
La couverture minimale d’un ensemble de DF est un sous ensemble minimum de DF élémentaires
permettant de générer toutes les autres.
Tout ensemble de DF admet une couverture minimale en général non unique.
Exemple :
1. Cod_mod →cod_filiere
2. cod_filiere →libelle_filiere
3. Cod_mod → libelle_filiere
4. Jour,heure,local →num_ens
5. Jour,heure,local → cod_filiere
6. Jour,heure,local →section
7. Jour,heure,local →groupe
8. Jour,heure,local →an_etude
9. Jour,heure,local →cod_mod
10. Jour,heure,local , num_ens → cod_filiere
La couverture minimale de cet ensemble de DF consiste à éliminer les DFs
Numéro 3 : obtenue par transitivité de 1 et 2
Numéro 10 : obtenue par augmentation de 5
Numéro 5 : obtenue par transitivité de 1 et 9
3) Fermeture transitive :
On appelle fermeture transitive d’un ensemble F de DF, l’ensemble F+ constitué de F lui-même et de
l’ensemble des DFs déduites par transitivité.
Exemple :
Soit l’ensemble de DF, F= {num_ens →grade, grade →salaire, grade →nbre_heures}
La fermeture transitive de F sera :
F+ =F {num_ens →salaire, num_ens →nbre_heures}
F+= {num_ens →grade, grade →salaire, grade →nbre_heures, num_ens →salaire, num_ens
→nbre_heures}
Exercice d’application :
On considère un ensemble de DF relatif à la gestion d’un ensemble de centres de formations
1. Numcentre →Nomcentre
2. Numcentre →superficie
3. Numcentre →Nbrelocaux
4. Numcentre →Numdirecteur
5. Numcentre →Nomdirecteur
6. Numcentre →Nbr_eleves
7. Numcentre →Adresse
8. Numcentre, Adresse→Nomcentre
9. Numdirecteur →Nomdirecteur
10. Numspecialité → Libellésspec
1) Trouvez la couverture minimale de cet ensemble de DF ?
2) Construire la SAT ?
Solution :
1) Couverture minimale de l’ensemble de DF :
On élimine les DFs 5 et 8 car elles peuvent être déduites des autres.
La DF 5 est déduite par la transitivité des DF 4 et 9
La DF 8 est déduite par augmentation de la DF 1
Donc l’ensemble de couverture minimale est :
Numcentre →Nomcentre
Numcentre →superficie
Numcentre →Nbrelocaux
Numcentre →Nbr_eleves
Numcentre →Numdirecteur
Numdirecteur →Nomdirecteur
Numcentre →Adresse
Numspecialité → Libellésspec
Le graphe de DFs (SAT)
Numcentre • Numdirecteur
•
• Nbr_eleves
• Nomdirecteur
• Nomcentre • superficie
• Adresse
• Nbrelocaux • Numspecialité
• Libellésspec
