Discussion :

[bambi98]

Bonjour à tous
Esperant que je poste bien dans le bon forum,jai quelques difficultés à trouver des solutions en ce qui concerne la couverture minimale et la fermeture transitive.
j'ai lu les algorithme et essayer de trouver quelques exercices sur le net mais je n'arrive toujours pas à comprendre ces deux notions(le calcul des fermeture transitive et calcul de la couverture minimale)
voici un exercice

Question n° 1 (5 points)
Soient deux relations ALPHA et BETA et leur schéma de relation*:
ALPHA = <U1, V1>
avec U1 = {A, B, C, D, E} et V1 = {df1, df2, df3, df4, df5}
où df1*: A → B*; df2*: A → D*; df3*: A → E*; df4*: E → C et df5*: A → C
BETA = <U2, V2>
Avec U2*= {X, Y, Z, T, U} et V2 = {df6, df7, df8}
où df6*: X → Y*; df7*: Z → U et df8*: X, Z → T
a) Calculez la couverture minimale de V1 et de V2.
b) Tracez le graphe de dépendances de V2.
c) Donnez la forme normale de ALPHA et BETA.
d) Transformez ces deux relations en deux ensembles de relations en troisième forme normale

j'ai vu dans certains exercices du net comment on utilise la fermeture d'une dependance fonctionnelle mais les conclusion sont vagues. à cet effet comment utiliser la fermeture d'une dépendance fonctionnelle pour supprimer une dépendance redondante ou pour calculer les fermetures transitives?
merci de vos réponses

[fsmrel]

Bonsoir,


Ce que vous appelez couverture minimale et fermeture transitive sont des concepts utilisés dans les cercles académiques mais auxquels on n’a malheureusement guère de temps à consacrer sur le terrain (je parle d’expérience). Quoi qu’il en soit, leur objet est de nous aider à produire « mécaniquement » des bases de données composées de tables respectant la troisième forme normale (3FN ou 3NF), voire la forme normale de Boyce-Codd (FNBC ou BCNF) et il est préférable que le concepteur de bases de données sache de quoi il en retourne.

Un point sur lequel tout le monde est d’accord est que ne pas normaliser est la cause de redondances, de difficultés et d’anomalies de mise à jour des bases de données, et cela a toujours valu, même avant que Ted Codd, Ian Heath, Claude Delobel, Ron Fagin et tutti quanti aient livré leurs travaux sur le sujet !

Il faut donc normaliser au moins en 3NF. La production mécanique de tables en 3NF fait appel à un algorithme que l’on doit à Philip Bernstein, remercions-le ! (personnellement, le théorème de Heath me suffit, mais ceci est une autre affaire). Cet algorithme met à profit un ensemble de DF associé à un en-tête (schéma) de relation pour lequel on veut s’assurer de la 3NF, mais cet ensemble doit nécessairement être une couverture minimale : avant de décrire l’algorithme, il s’agit de savoir ce qu’est une couverture minimale (ou irréductible). Il existe un certain nombre de définitions de la chose, prenons par exemple celle de Georges Gardarin (in Bases de données, les systèmes et leurs langages) :

Couverture minimale (Minimal cover) :
Ensemble F de DF élémentaires associé à un ensemble d’attributs vérifiant les propriétés suivantes :
1. Aucune dépendance dans F n’est redondante ; c'est-à-dire, pour toute DF f de F, F — f n’est pas équivalent à F ;
2. Toute DF élémentaire des attributs est dans la fermeture transitive de F (notée F+).

Voilà trois points à éclaircir... Qu’est-ce qu’une fermeture transitive ? Qu’est-ce qu’une DF élémentaire ? Qu’entend-on précisément par équivalence de F et F — f ?

Suivons Georges Gardarin.

Dépendance fonctionnelle élémentaire (Elementary functional dependency)
Dépendance fonctionnelle de la forme X -> A où A est un attribut unique non inclus dans X et où il n’existe pas X’ ⊂ X tel que X’ -> A.
Par exemple, si l’ensemble des DF associé à l’en-tête {A, B, C, D, E} de la relation R est le suivant :

F = { {A, B} -> {C}, {A, B} -> {D}, {A} -> {C}, {C} -> {E} }

Les DF {A, B} -> {D}, {A} -> {C} et {C} -> {E} sont élémentaires, mais la DF {A, B} -> {C} ne l’est pas.

Toujours avec Georges Gardarin :

Fermeture transitive (Transitive closure)
Ensemble des DF élémentaires considérées enrichi de toutes les DF élémentaires déduites par transitivité.

Dans l’exemple qui précède, la fermeture transitive F+ est la suivante :

F+ = { {A, B} -> {D}, {A} -> {C}, {C} -> {E}, {A} -> {E} }

Reprenons maintenant la définition de la couverture minimale :

Couverture minimale (Minimal cover) :
Ensemble F de DF élémentaires associé à un ensemble d’attributs vérifiant les propriétés suivantes :
1. Aucune dépendance dans F n’est redondante ; c'est-à-dire, pour toute DF f de F, F — f n’est pas équivalent à F ;
2. Toute DF élémentaire des attributs est dans la fermeture transitive de F (notée F+).

Dans l’exemple précédent, F+ contient toute les DF élémentaires, le point 2 est donc satisfait. Ce n’est pas le cas du point 1 car la DF {A} -> {E} est redondante. En effet, on sait la retrouver en appliquant l’axiome d’Armstrong de transitivité :

De {A} -> {C} et {C} -> {E} on infère {A} -> {E}. On peut donc légitimement produire un nouvel ensemble F’ de DF moins bavard :

F’ = F — {{A} -> {E}}, c'est-à-dire F’ = { {A, B} -> {D}, {A} -> {C}, {C} -> {E} }.

Maintenant, l'ensemble F’ représente-t-il une couverture minimale ? Oui, car cette fois-ci aucune DF lui appartenant ne peut être inférée des autres.

Vous me direz : Mais pourquoi calculer la fermeture transitive, puisqu’ensuite la couverture minimale est à débarrasser des DF transitives ? Disons qu’à partir de la fermeture transitive, un ensemble de DF peut donner lieu à plusieurs couvertures minimales, mais en plus grand nombre (du moins je le pense) si l'on part de la fermeture transitive. Ainsi, dans l’exemple que je développe (Pluralité des ensembles irréductibles pour une relvar), je m’attarde sur deux couvertures minimales (ensembles irréductibles) proposées par Jeff Ullman (Principles of Database Systems, second edition, chez Computer Science Press), mais en grattant, j’en ai trouvé plus de cinquante autres, en mettant à profit ou non la fermeture transitive, et j’ai arrêté mes recherches par lassitude... Bref, on peut aller à la pêche aux fermetures transitives, mais ça n’est pas une obligation pour calculer des couvertures minimales.

Pour voir comment on calcule une couverture minimale, reportez-vous à Ensemble irréductible de dépendances fonctionnelles, en ayant préalablement appris à vous servir du seau à dépendants. Ensuite soumettez-nous vos résultats concernant ALPHA et BETA.

Pour l’algorithme de Bernstein, voyez ici.

A titre indicatif, la relvar (variable relationnelle) ALPHA respecte seulement la 1NF, mais la couverture minimale à laquelle elle donne lieu est décomposable en deux relvars respectant la BCNF (et même la 5NF).

N’hésitez pas à poser vos questions.