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 → N, HE → S}
Il faudrait déjà voir si la relation est en deuxième forme normale. Prenons la définition qu’en a donnée son inventeur Ted Codd (1971), je cite :
A relation R is in second form normal if it is in first normal form and every non-prime attribute of R is fully dependant on each candidate key of R.
Ce que l’on peut ainsi traduire ainsi :
Une relation R est en deuxième forme normale si elle est en première forme normale et si chaque attribut n’appartenant à aucune clé candidate de R est en dépendance totale de chaque clé candidate de R.
En l’occurrence, dire qu’une dépendance fonctionnelle X → Y est totale revient à dire qu’elle est élémentaire (revoyez les définitions que j’ai données à l’occasion de mon premier message).
Je rappelle en passant la définition de la clé candidate :
Une clé candidate est un sous-ensemble d’attributs K de l’en-tête d’une relation R, respectant les deux contraintes suivantes :
Unicité. Deux n-uplets distincts de R ne peuvent avoir même valeur de K.
Irréductibilité (ou minimalité). Il n’existe pas de sous-ensemble strict de K garantissant la règle d’unicité.
Corollaire : K détermine fonctionnellement chaque {attribut} de R.
N.B. Si un sous-ensemble d’attributs S de l’en-tête de R respecte la contrainte d’unicité, alors S représente une surclé pour R. Ainsi, une clé candidate est une surclé devant en plus respecter la contrainte d’irréductibilité.
Il s’agit maintenant de fournir la liste des clés candidates de la relation, puis de passer en revue les parties droites des dépendances fonctionnelles qui nous sont données, afin de vérifier que chacune de ces parties droites n’appartient pas à une dépendance fonctionnelle dont la partie gauche serait un sous-ensemble strict d’une clé candidate.
Il faut donc commencer par découvrir les clés candidates de R. En principe, on commence par vérifier si les singletons {C}, {E}, {H}, {N}, {P}, {S} peuvent représenter de telles clés.
Par exemple, si c’était le cas de {C}, alors on aurait la dépendance fonctionnelle {C} → {C, E, H, N, P, S}, c'est-à-dire que la fermeture {C}+ de {C} par rapport à F serait nécessairement égale à {C, E, H, N, P, S}, ce qui n’est évidemment pas le cas ici, et vous savez désormais vérifier que cette fermeture est seulement égale à {C, P}.
Il faudrait ensuite en passer aux paires (il y en a une douzaine), puis aux triplets (il y en a aussi un paquet), etc., mais la tâche risque d’être longue et décourageante...
Essayons de réduire drastiquement les recherches. Je vous demande maintenant de réfléchir au point suivant :
Si un attribut A n’appartient à aucune partie droite d’une dépendance fonctionnelle de F, il ne pourra jamais faire partie de la fermeture par rapport à F, pour une d’une dépendance fonctionnelle D dont la partie gauche est elle aussi dépourvue de l’attribut A. Quoi qu’on fasse, cette fermeture sera désespérément et sempiternellement incomplète, elle ne pourra donc jamais donner lieu à une quelconque clé candidate.
Prenons le cas de l’attribut E : il n’appartient à aucune partie droite de quelque dépendance fonctionnelle que ce soit de F. Autrement dit, si l’on considère les dépendances fonctionnelles pour lesquelles E est aussi absent à gauche :
{C} → {P}
{H, S} → {C}
{H, P} → {S}
Alors les fermetures correspondantes {C}+, {H, S}+, {H, P}+ ne contiendront jamais E, quoi qu’on fasse. Parmi la multitude des combinaisons d’attributs, dans la quête des clés candidates, on peut donc se désintéresser des singletons {C}, {H}, {S}, {P}, des paires et des triplets qu’on peut en inférer, sans oublier le quadruplet {C, H, S, P}.
De la même façon, prenons le cas de l’attribut H : lui aussi n’appartient à aucune partie droite de quelque dépendance fonctionnelle que ce soit de F. Autrement dit, si l’on considère les dépendances fonctionnelles pour lesquelles H est aussi absent à gauche :
{C} → {P}
{C, E} → {N}
Là aussi on peut se désintéresser des singletons {C}, {E}, des paires et du triplet qu’on peut en inférer.
A la réflexion, les attributs E et H étant tous deux absents de l’ensemble des parties droites, un sous-ensemble d’attributs X de fermeture X+ par rapport à F doit avoir au moins E et H comme éléments pour que l’on ait une chance que X+ = {C, E, H, N, P, S} donc que X représente une clé candidate.
Dans notre exemple, on doit donc commencer par se focaliser sur le calcul de la fermeture {H, E}+ de la paire {H, E} par rapport à F. Si elle est égale à {C, E, H, N, P, S}, on aura gagné. Sinon, il faudra procéder par augmentation de {H, E} jusqu’à ce que l’on arrive à produire cet ensemble.
Calculons donc {H, E}+. Au départ (les places correspondent ici à l’ordre alphabétique des noms des attributs, à savoir C, E, H, N, P, S) :
{H, E}+ = _ E H _ _ _
Puis, grâce à la dépendance fonctionnelle {H, E} → {S} :
{H, E}+ = _ E H _ _ S
Puis, grâce à la dépendance fonctionnelle {H, S} → {C} :
{H, E}+ = C E H _ _ S
Puis, grâce à la dépendance fonctionnelle {C} → {P} :
{H, E}+ = C E H _ P S
Puis, grâce à la dépendance fonctionnelle {C, E} → {N} :
{H, E}+ = C E H N P S
La fermeture {H, E}+ de {H, E} par rapport à F contient l’ensemble des attributs de la relation, donc — morceau de chance ! — {H, E} est clé candidate. Elle est même la seule. En effet, si l’on ajoutait un attribut à {H, E}, on produirait une surclé ne respectant pas la contrainte d’irréductibilité à laquelle sont soumises les clés candidates, et si l’on retranchait H ou E de {H, E}, on ne respecterait pas la contrainte d’unicité.
{H, E} est l’unique clé candidate de la relation et pour que la deuxième forme normale soit violée, il faudrait que {H} et/ou {E} déterminent fonctionnellement un des attributs C, N, P, S, ce qui n’est pas le cas : la deuxième forme normale est respectée.
Venons-en à la troisième forme normale. Prenons la définition qu’en a donnée son inventeur Ted Codd (1971), je cite :
A relation R is in third form normal if it is in second normal form and every non-prime attribute of R is non-transitively dependant on each candidate key of R.
Ce que l’on peut ainsi traduire ainsi :
Une relation R est en troisième forme normale si elle est en deuxième forme normale et si chaque attribut n’appartenant à aucune clé candidate ne dépend directement que des clés candidates de R.
A partir de la fermeture {H, E}+ de {H, E} qui est égale à {C, E, H, N, P, S}, en vertu de la règle de décomposition (cf. les axiomes d’Armstrong), il existe la dépendance fonctionnelle :
{H, E} → {P}
Mais, {P} ne dépend pas que de {H, E}, puisqu’il existe la dépendance fonctionnelle {C} → {P} alors que {C} ne représente pas une clé candidate :
La troisième forme normale est violée. Elle l’est même copieusement, puisque les autres dépendances fonctionnelles sont délinquantes elles aussi :
{H, S} → {C}
{H, P} → {S}
{C, E} → {N}
On fait souvent intervenir les dépendances fonctionnelles transitives dans les (multiples) définitions de la troisième forme normale. Chacun sa sauce. En tout état de cause, voici un exemple de dépendance fonctionnelle transitive impliquée dans le viol :
De {H, E} → {H, S} et {H, S} → {C} on infère par transitivité {H, E} → {C}.
Personnellement, je préfère utiliser la définition de la troisième forme normale qu’en a donnée Carlo Zaniolo, car elle permet notamment de répondre à votre question sans faire d’abord appel à la deuxième forme normale, mais on restera là pour aujourd’hui...
Calcul d'une couverture minimale
Répondre avec citation
Partager