Bonsoir,
Je vais essayer de répondre au premier problème.
Envoyé par
yaya125
I.En quelle forme normale sont les relation suivante ?Pourquoi?Décomposer les relations 1NF ou 2NF en 3NF puis BCNF et les relations en BCNf. Y a-t-il perte de dépendance?
1. U = ABCD , F = {B-> C ,B-> D}
2.U = ABCD , F = {BD-> AC , BC-> AD ,A-> BC}
3.U =ABCDE ,F ={AB-> C , BC-> D ,CD -> E,A-> B}
En quelles formes normales sont les relvars ?
Si une relvar n'est pas en BNCF, la décomposer pour obtenir plusieurs relvars normalisées en BCNF.
Avant de commencer je vais donner les définitions que j'utilise pour les formes normales.
Toute relvar étant par définition en première forme normale je ne m'en occupe pas.
Deuxième forme normale (2NF ou 2FN):
Une relvar est en deuxième forme normale si chaque attribut n'appartenant à aucune clé candidate est en dépendance totale (irréductible) de chaque clé candidate de la relvar.
Troisième forme normale (3NF ou 3FN):
Soit R une relvar, 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 troisième forme normale si et seulement si, pour chaque dépendance fonctionnelle X → {A} vérifiée dans R, au moins une des conditions suivantes est satisfaite :
- Cette dépendance fonctionnelle est triviale (A est un élément de X).
- X est une surclé de R.
- A appartient à une clé candidate de R.
Forme normale de Boyce-Codd (BCNF ou FNBC):
Une relvar est en BCNF si et seulement si le déterminant de chaque DF non triviale, irréductible à gauche constitue une clé candidate de la relvar.
1er cas
1
2
3
4
| R {A, B, C, D}
F = { {B} → {C}
{B} → {D} } |
Les attributs A et B ne sont présent dans aucun déterminant des dépendances fonctionnelles, ils entrent donc dans la composition des clés candidates de la relvar.
La clé candidate est {A, B}.
On le vérifie en calculant la fermeture {A, B}+ de {A, B} par rapport à F, en utilisant l'algorithme décrit par fsmrel ci-dessus.
{A, B}+ = {A, B, C, D}
Comme l'ensemble d'attributs {A, B} détermine fonctionnellement tous les attributs de la relvar, c'est une surclé. {A, B} étant irréductible c'est une clé candidate.
Les attributs C et D n'appartiennent pas à la clé candidate.
Ils ne sont pas en dépendance totale de la clé, mais plutôt en dépendance partielle, puisqu'un sous-ensemble de la clé (B) détermine fonctionnellement ces attributs.
La relvar R n'est donc pas en 2NF.
J'essaie de décomposer R pour obtenir des relvars en BCNF.
J'obtiens ceci:
1
2
3
| Ra = {A, B}
Rb = {B, C}
Rc = {B, D} |
La décomposition est correct car la jointure naturelle des 3 relvars permet d'obtenir la relvar initiale R.
Les 3 relvars sont en BCNF et il n'y a aucune perte de DF.
2ème cas
1
2
3
4
5
| R {A, B, C, D}
F = { {B, D} → {A, C}
{B, C} → {A, D}
{A} → {BC} } |
Cette fois l'ensemble de DF est un peu plus conséquent.
Je pense qu'il est plus simple de travailler avec un ensemble de DF irréductible, une couverture minimale de dépendances fonctionnelles.
Pour obtenir cet ensemble irréductible il y a trois étapes à suivre.
- Première étape
Il faut réduire le dépendant de chaque DF pour obtenir des singletons (un seul attribut), grâce à la règle de Décomposition des axiomes d'Armstrong.
On obtient ceci:
1
2
3
4
5
6
7
| F = {
DF1 = {B, D} → {A}
DF2 = {B, D} → {C}
DF3 = {B, C} → {A}
DF4 = {B, C} → {D}
DF5 = {A} → {B}
DF6 = {A} → {C} } |
- Deuxième étape
Il faut essayer de réduire le déterminant de chaque DF.
Par exemple:
La DF {B, C} → {A} peut-elle être remplacée par {B} → {A} ou {C} → {A} dans l'ensemble de DF ?
Pour cela on utilise l'algorithme de calcul de la fermeture d'un ensemble d'attribut déjà mentionné.
Ici dans F, aucun dépendant n'est réductible (voir le 3ème cas pour la démarche).
- Troisième étape
Lors de la troisième et dernière étape, on essaye de supprimer chaque DF pour réduire leur nombre au minimum. On utilise toujours cet algorithme.
On commence par la première des DF: DF1.
Le déterminant de DF1 est {B, D}.
Soit I = D - DF1
L'ensemble I de DF est l'objectif à atteindre (si possible), c'est l'ensemble F de DF auquel on retire DF1.
La DF1 peut être supprimée de F si la fermeture {B, D}+ de {B, D} par rapport à F est égale à la fermeture {B, D}+ de {B, D} par rapport à I.
La fermeture {B, D}+ par rapport à F donne {A, B, C, D} grâce à DF1 et DF2.
La fermeture {B, D}+ par rapport à I donne {A, B, C, D} grâce à DF2 et DF3.
Les deux fermeture sont égales, I peut remplacer F.
1
2
3
4
5
6
| F = {
DF2 = {B, D} → {C}
DF3 = {B, C} → {A}
DF4 = {B, C} → {D}
DF5 = {A} → {B}
DF6 = {A} → {C} } |
En utilisant la même méthode avec DF2 on obtient ceci:
La fermeture {B, D}+ par rapport à F donne {A, B, C, D} grâce à DF2 et DF3.
La fermeture {B, D}+ par rapport à I donne {B, D}.
A l'instar des autres DF, DF2 ne peut pas être supprimée.
L'ensemble F est un ensemble irréductible de DF pour R.
Une fois ce travail effectué, je recherche les clés candidates.
Il y en as trois:
1
2
3
| K1 = {A}
K2 = {B, C}
K3 = {B, D} |
En effet, la fermeture de ces 3 ensembles d'attributs par rapport à F donne bien {A, B, C, D}.
Il n'existe aucun attribut qui n'appartienne pas à une clé candidate. R est en 2NF.
R est en 3NF car les points 2 et 3 de la définition sont respectés.
R est en BCNF.
3ème cas
1
2
3
4
5
6
| R {A, B, C, D, E}
F = { {A, B} → {C}
{B, C} → {D}
{C, D} → {E}
{A} → {B} } |
Même démarche que dans le 2ème cas, je cherche un ensemble irréductible de DF avant d'en déduire les clés candidates.
- Première étape
Il n'y a rien à faire, tous les dépendants sont composés d'un seul attribut.
- Deuxième étape
Je cherche à réduire le déterminant de chaque DF.
Je commence par la première DF; la DF {A, B} → {C} peut-elle être remplacée par {A} → {C} ou {B} → {C} ?
Pour vérifier si {A} → {C} peut remplacer {A, B} → {C}, il faut calculer la fermeture {A}+ de {A} par rapport à F et la comparer avec la fermeture {A}+ de {A} par rapport à I.
I est l'ensemble de DF ou {A} → {C} a remplacé {A, B} → {C}
1
2
3
4
5
|
I = { {A} → {C}
{B, C} → {D}
{C, D} → {E}
{A} → {B} } |
La fermeture {A}+ de {A} par rapport à F donne {A, B, C, D, E}.
La fermeture {A}+ de {A} par rapport à I donne {A, B, C, D, E}.
Les fermetures sont égales, I remplace F directement, on passe à la DF suivante.
Aucune autre DF n'est réductible à gauche.
- Troisième étape
La troisième étape montre qu'on ne peut supprimer aucune DF.
Il n'y a qu'une clé candidate, c'est A. En effet {A}+ = {A, B, C, D, E}
Chaque attribut n'appartenant pas à la clé candidate, ici B, C, D et E ne sont pas tous en dépendance totale de la clé, donc R n'est pas en 2NF.
J'ai commencé à décomposer comme ceci:
1
2
3
|
Ra = {A, B, C}
Rb = {B, C, D, E} K= {B, C} |
Mais Rb n'est pas en BCNF. Je re-décompose:
1
2
3
4
|
Ra = {A, B, C}
Rb = {B, C, D} K= {B, C}
Rc = {C, D, E} K= {C, D} |
Les 3 relvars sont en BCNF.
La jointure des trois relvar permet bien d'obtenir R et on ne perd aucune DF. Ça me semble correct.
Voilà un petit pavé, j'espère que c'est compréhensible.
J'interviens sous le contrôle d'fsmrel, qui j'en sus sûr n'hésitera pas à me corriger si j'ai commis des erreurs 
Problème en Normalisation
Répondre avec citation
Partager