Envoyé par
redsaint0
J'aurais besoin d'aide pour comprendre le calcul d'une couverture minimale.
Soit F={
1 AB→C
2 C→A
3 BC→D
4 D→B
5 D→EG
6 BE→C
7 CG→BD
8 CE→AG}
Quelques rappels
1) Dépendance fonctionnelle élémentaire
Étant donné deux sous-ensembles d’attributs X et Y de l’en-tête d’une relation R, la dépendance fonctionnelle X → Y est élémentaire (ou irréductible, ou totale) si :
— Y est singleton (Y ne contient qu’un seul élément, c'est-à-dire un seul attribut de l’en-tête de R) ;
— La dépendance fonctionnelle n’est pas triviale, c'est-à-dire que Y n’est pas inclus dans X (tout ou partie) ;
— Il n’existe pas Z strictement inclus dans X tel que Z → Y.
2) Fermeture d’un ensemble de dépendances fonctionnelles
Un ensemble F de dépendances fonctionnelles défini pour une relation R possède une fermeture F+ qui est l’ensemble des dépendances fonctionnelles inférables de F, au moyen des règles d’Armstrong.
3) Couverture minimale d’un ensemble de dépendances fonctionnelles
Une couverture minimale (ou irréductible) I+ de F consiste en l’ensemble irréductible I de dépendances fonctionnelles élémentaires tel que I+ = F+. (Note : Pour l’ensemble F on peut avoir plus d’une couverture minimale).
La connaissance de la couverture minimale est utile dans la mesure où elle permet de vérifier qu’une relation vérifie la forme normale de Boyce-Codd (BCNF) :
Soit R une relation, X un sous-ensemble d’attributs de l’en-tête de R et A un attribut de cet en-tête. R est en forme normale de Boyce-Codd (BCNF) si et seulement si le déterminant chaque dépendance fonctionnelle élémentaire X → {A} vérifiée dans R est une clé candidate de R.
Il existe d’autres définitions de la BCNF, mais dans votre cas, celle-ci convient.
Avant de se prononcer sur le respect par R du respect de la BCNF, l’objectif est donc de calculer la couverture minimale I+ de l’ensemble F, ou au moins l’ensemble des dépendances fonctionnelles élémentaires, tâche faisant partie du calcul de cette couverture.
Pour reprendre votre exemple, je vais supposer que les éléments A, B, C, D, E et G qui figurent dans l’ensemble F de dépendances fonctionnelles que vous proposez sont les attributs d’une relation R. Dans ces conditions, F contient donc les éléments suivants :
DF01 : {A, B} → {C}
DF02 : {C} → {A}
DF03 : {B, C} → {D}
DF04 : {D} → {B}
DF05 : {D} → {E, G}
DF06 : {B, E} → {C}
DF07 : {C, G} → {B, D}
DF08 : {C, E} → {A, G}
Calcul de la couverture minimale. 1re étape.
On commence par rendre irréductibles (c'est-à-dire singletons) les parties droites des dépendances fonctionnelles. Ceci est vite réalisé et rendu possible par application de la règle de décomposition (cf. les axiomes d’Armstrong). L’ensemble F des DF est ainsi transformé :
DF01 : {A, B} → {C}
DF02 : {C} → {A}
DF03 : {B, C} → {D}
DF04 : {D} → {B}
DF05a : {D} → {E}
DF05b : {D} → {G}
DF06 : {B, E} → {C}
DF07a : {C, G} → {B}
DF07b : {C, G} → {D}
DF08a : {C, E} → {A}
DF08b : {C, E} → {G}
Calcul de la couverture minimale. 2e étape.
L’affaire se corse (chef-lieu Ajaccio). Il s’agit de tenter de rendre irréductibles à gauche, donc élémentaires, l’ensemble de dépendances fonctionnelles énumérées ci-dessus. Sont concernées les dépendances fonctionnelles dont les déterminants (parties gauches) ne sont pas des singletons : DF01, DF03, DF06, DF07a, DF07b, DF08a, DF08b.
Voyons par exemple si {A, B} → {C} peut se réduire à {A} → {C} ou {B} → {C}.
La DF {A, B} → {C} est-elle réductible à réductible à {A} → {C} ? Pour s’en assurer, on procède de la façon suivante :
{A} étant la partie gauche de la dépendance fonctionnelle {A} → {C}, on calcule la fermeture {A}+ de {A} par rapport à F. Cette fermeture est constituée de l’ensemble des attributs de R dépendant fonctionnellement de {A}. De façon pragmatique, on peut procéder ainsi pour obtenir cet ensemble, en écrivant de façon symbolique :
{A}+ = _ _ _ _ _ _
En sorte que chaque symbole « _ » représente une place pour un des attributs A, B, C, D, E, G. Parce que {A} → {A} (1er axiome d’Armstrong, dit de réflexivité), on en « capture » la partie droite, donc l’attribut A et on l’« installe » à sa place :
{A}+ = A _ _ _ _ _
Puis on passe en revue l’ensemble des DF en y cherchant celles dans lesquelles {A} représente la partie gauche. Il n’existe aucune telle DF : le calcul de {A}+ par rapport à F est terminé et l’on écrit {A}+ = {A}.
Pour vérifier si la dépendance fonctionnelle DF01 {A, B} → {C} peut se réduire à la dépendance fonctionnelle DF01a {A} → {C}, on effectue exactement le même travail, mais en remplaçant F par F’, qui diffère de F du fait qu’on y remplace DF01 par DF01a :
DF01a : {A} → {C}
DF02 : {C} → {A}
DF03 : {B, C} → {D}
DF04 : {D} → {B}
DF05a : {D} → {E}
DF05b : {D} → {G}
DF06 : {B, E} → {C}
DF07a : {C, G} → {B}
DF07b : {C, G} → {D}
DF08a : {C, E} → {A}
DF08b : {C, E} → {G}
On applique le même procédé que précédemment, en amorçant la pompe :
{A}+ = A _ _ _ _ _
Puis on passe en revue l’ensemble des DF de F’ en y cherchant celles dans lesquelles {A} représente la partie gauche. C’est le cas de DF01a, dont on « capture » la partie droite {C} :
{A}+ = A _ C _ _ _
Puis on passe en revue l’ensemble des autres DF de F’ en y cherchant celles dans lesquelles {A} ou {C} ou {A, C} représente la partie gauche. C’est le cas de DF02, mais elle ne permet pas d’enrichir {A}+. Comme il n’existe aucune autre dépendance fonctionnelle répondant à la condition posée, le travail est terminé et la fermeture {A}+ de {A} par rapport à F’ est égale à {A, C}.
Or un théorème dit que F’ peut se substituer à F si seulement si la fermeture {A}+ de {A} par rapport à F’ est égale à la fermeture {A}+ de {A} par rapport à F : ici, tel n’est pas le cas, puisque la fermeture {A}+ de {A} par rapport à F’ est égale à {A, C}, tandis que la fermeture {A}+ de {A} par rapport à F est égale à {A} :
La DF {A, B} → {C} n’est pas réductible à {A} → {C}. Je vous laisse le soin de montrer qu’elle n’est pas non plus réductible à {B} → {C}. Ainsi, la DF {A, B} → {C} est élémentaire (mon cher Watson).
Concernant les autres dépendances fonctionnelles, on peut montrer que DF08a : {C, E} → {A} est réductible à {C} → {A}. En effet, par rapport à F et F’, dans les deux cas :
{A}+ = A _ C _ _ _
Que DF08a puise débarrasser le plancher est du reste évident quand on applique directement les règles d’augmentation et de décomposition :
Si {C} → {A} alors {C, E} → {A, E} (augmentation)
puis {C, E} → {A} (décomposition).
Je vous laisse aussi le soin de montrer qu’il n’y a pas d’autre dépendance fonctionnelle qui soit réductible à gauche.
Calcul de la couverture minimale. 3e étape.
Courage. Si nous n’avons pas commis d’étourderie lors de la 2e étape, l’ensemble initial F est à remplacer par le suivant, appelons-le G :
DF01 : {A, B} → {C}
DF02 : {C} → {A}
DF03 : {B, C} → {D}
DF04 : {D} → {B}
DF05a : {D} → {E}
DF05b : {D} → {G}
DF06 : {B, E} → {C}
DF07a : {C, G} → {B}
DF07b : {C, G} → {D}
DF08b : {C, E} → {G}
Ce que l’on veut maintenant, c’est découvrir les dépendances fonctionnelles qui sont parfaitement inférables des autres et peuvent donc disparaître. Cherchons par exemple à voir si DF01 peut disparaître. En plus de G, considérons l’ensemble I = G – DF01 : I est égal à G débarrassé de DF01.
DF01 peut disparaître seulement si sa partie gauche {A, B} est telle que la fermeture {A, B}+ de {A, B} par rapport à G est égale à la fermeture {A, B}+ de {A, B} par rapport à I.
Calculons la fermeture {A, B}+ de {A, B} par rapport à G. Comme lors de l’étape précédente, on amorce la pompe :
{A, B}+ = A B _ _ _ _
Puis, du fait de DF01 :
{A, B}+ = A B C _ _ _
Puis, du fait de DF03 :
{A, B}+ = A B C D _ _
Puis, du fait de DF05a et DF05b :
{A, B}+ = A B C D E G
On a capturé tous les attributs de R : le calcul de {A, B}+ est terminé. La fermeture {A, B}+ de la paire {A, B} par rapport à F est égale à {A, B, C, D, E, G}. Autrement dit on vérifie {A, B} → {A, B, C, D, E, G}. En passant, comme tous les attributs de R sont fonctionnellement dépendants de la paire {A, B}, celle-ci constitue une clé candidate de R.
Calculons la fermeture {A, B}+ de {A, B} par rapport à I en se souvenant que DF01 n’en fait pas partie. On amorce la pompe :
{A, B}+ = A B _ _ _ _
Mais par la suite, on ne peut plus rien capturer car il n’existe pas d’autre dépendance fonctionnelle dont la partie gauche soit contenue dans {A, B}. La fermeture {A, B}+ de {A, B} par rapport à G est différente de la fermeture {A, B}+ de {A, B} par rapport à I et l’on doit conserver la dépendance fonctionnelle DF01.
Montrons que la dépendance fonctionnelle DF05b : {D} → {G} peut disparaître. Considérons l’ensemble I = G – DF05b :
DF01 : {A, B} → {C}
DF02 : {C} → {A}
DF03 : {B, C} → {D}
DF04 : {D} → {B}
DF05a : {D} → {E}
DF06 : {B, E} → {C}
DF07a : {C, G} → {B}
DF07b : {C, G} → {D}
DF08b : {C, E} → {G}
Calculons la fermeture {D}+ de {D} par rapport à I. Comme lors de l’étape précédente, on amorce la pompe :
{D}+ = _ _ _ D _ _
Comme {D} → {B} (cf. DF04), l’attribut B peut être capturé et {D}+ devient :
{D}+ = _ B _ D _ _
Comme {D} → {E} (cf. DF05a), l’attribut E peut être capturé et {D}+ devient :
{D}+ = _ B _ D E _
Comme la paire {B, E} fait partie de {D}+ et que {B, E} → {C} (cf. DF06), l’attribut C peut être capturé et {D}+ devient :
{D}+ = _ B C D E _
Comme la paire {C, E} fait partie de {D}+ et que {C, E} → {G} (cf. DF08b), l’attribut G peut être capturé et {D}+ devient :
{D}+ = _ B C D E G
Donc {D}→ {G}, en conséquence de quoi la dépendance fonctionnelle DF05b peut disparaître : on n’a même pas eu besoin d’aller au bout du calcul de la fermeture {D}+ de {D} par rapport à I et de calculer la fermeture {D}+ de {D} par rapport à G.
Ainsi, G peut être réduit à :
DF01 : {A, B} → {C}
DF02 : {C} → {A}
DF03 : {B, C} → {D}
DF04 : {D} → {B}
DF05a : {D} → {E}
DF06 : {B, E} → {C}
DF07a : {C, G} → {B}
DF07b : {C, G} → {D}
DF08b : {C, E} → {G}
A partir de ce nouvel ensemble G, on montre de la même façon que la dépendance fonctionnelle DF07a peut disparaître à son tour, G se réduisant alors à :
DF01 : {A, B} → {C}
DF02 : {C} → {A}
DF03 : {B, C} → {D}
DF04 : {D} → {B}
DF05a : {D} → {E}
DF06 : {B, E} → {C}
DF07b : {C, G} → {D}
DF08b : {C, E} → {G}
Je vous laisse le soin de montrer qu’il n’y a plus de réduction possible donc que cet ensemble de dépendances fonctionnelles constitue une couverture minimale.
Cerise sur le gâteau : cette couverture n’est pas unique. En effet, si au lieu de s’intéresser au sort de la dépendance fonctionnelle DF07a on préfère s’intéresser à celui de la dépendance fonctionnelle DF07b, l’ensemble suivant constitue aussi une couverture minimale tout aussi respectable :
DF01 : {A, B} → {C}
DF02 : {C} → {A}
DF03 : {B, C} → {D}
DF04 : {D} → {B}
DF05a : {D} → {E}
DF06 : {B, E} → {C}
DF07a : {C, G} → {B}
DF08b : {C, E} → {G}
_________________________________________________________________
Envoyé par
redsaint0
Je voulais également savoir si ce schéma est de forme 3NF et pourquoi?
E(C, P, H, S, E, N)
F = {C → P, HS → C, HP → S, CE → F, HE → S}
Il y a quelque chose qui cloche dans votre système : la relation a pour en-tête {C, P, H, S, E, N}, mais F comporte une dépendance fonctionnelle CE → F dont le dépendant F ne fait pas partie de l’en-tête. Et pour faire bonne mesure, l’en-tête de la relation comporte un attribut N qui n’apparaît dans aucune dépendance fonctionnelle.
Calcul d'une couverture minimale
Répondre avec citation
Partager