Envoyé par
wotan2009
Je reviens donc sur le 1er exercice :
R{ABCD}
F={AB → C, B → D, C → A}
Donner une décomposition qui préserve les dépendances de F.
Est ce que cette décomposition est sans perte d'information.
Voici ma démarche:
Cloture de {AB} par rapport à F: {AB}+ = {ABCD}
Cloture de {B} par rapport à F: {B}+ = {BD}
Cloture de {C} par rapport à F: {C}+ = {AC}
Y a t il des dépendances fonctionnelles non élémentaires ?
Peut on remplacer {AB → C} par {A → C} et/ou {B → C}
Cloture de {A} par rapport à F'={A → C, B → D, C → A}: {A}+ = {AC}
Cloture de {B} par rapport à F''={B → C, B → D, C → A}: {B}+ = {ABCD}
{AB → C} n'est pas élémentaire et peut etre remplacé par {B → C}
Les autres DF sont des singletons et sont donc élémentaires.
Y a t il des dépendances fonctionnelles redondantes ?
Peut on retirer {B → C} tels que F'=(F – {B → C}) et F'+ = F+
Cloture de {B} par rapport à F': {B}+ = {BD}. Différent de {B}+ par rapport à F.
Peut on retirer {B → D} tels que F'=(F – {B → D}) et F'+ = F+
Cloture de {B} par rapport à F': {B}+ = {ABC}. Différent de {B}+ par rapport à F
Peut on retirer {C → A} tels que F'=(F – {C → A}) et F'+ = F+
Cloture de {C} par rapport à F': {C}+ = {BCD}. Différent de {C}+ par rapport à F.
Aucune DF redondante.
Couverture minimale:
I={B → C, B → D, C → A} avec B comme clef.
Selon le théorème de Heat la relation peut être décomposée en :
R1{BD} et R2{ABC} sans perte d'information et de DF.
Elle peut aussi être décomposée en :
R1{BC} et R2{ABC}. Cette décomposition engendre une perte de DF, en effet {B → D} a disparu, ainsi qu'une perte d'information avec l'attribut {D}.
Considérons votre énoncé :
R{ABCD}
F={AB → C, B → D, C → A}
Donner une décomposition qui préserve les dépendances de F.
Est ce que cette décomposition est sans perte d'information.
1) Comme je ne sais pas si ABCD est le nom d’un attribut ou d’un sous-ensemble d’attributs, je réécris R sous la forme (en considérant que A, B, C et D sont des noms d’attributs) :
R {A, B, C, D}
Ça ne mange pas de pain.
2) Vous avez cherché la couverture minimale de R et c’est très bien. Seul problème, vous vous êtes planté en découvrant une prétendue DF :
{B} → {C}
En effet, la clôture de {B} par rapport à F est égale à {B, D},
Et la clôture de {B} par rapport à F’’ = {B → C, B → D, C → A} est égale à {A, B, C, D}.
Les clôtures de {B} par rapport à F et F’’ n’étant pas égales, la DF : B → C n’existe pas.
En menant l'opération à son terme, on constate que F est une couverture minimale.
3) Décomposition de R.
Comme vous l’avez fait, il suffit d’appliquer le théorème de décomposition de Heath (et pas Heat) pour décomposer R en :
R1 {B, D} et R2 {A, B, C}
Du fait de la dépendance fonctionnelle {C} → {A} et toujours en vertu du théorème de Heath, R2 est décomposable à son tour en :
R21 {A, C} et R22 {B, C}
La décomposition est sans perte d’information, c'est-à-dire qu’en vertu du théorème, R = R1 JOIN R21 JOIN R22.
Mais, comme vous l’avez noté, en décomposant R2 on perd la DF : {A, B} → {C}, et on peut alors préférer ne pas décomposer.
Au sujet de la perte de DF : il est bon d’avoir en tête une règle que l’on doit à Jorma Rissanen et qui permet d’éviter la perte de certaines dépendances fonctionnelles :
Soit la relation R {A, B, C} dans laquelle A, B et C sont des ensembles d’attributs. Si R satisfait aux dépendances fonctionnelles A → B et B → C, alors plutôt que de décomposer R en {A, B} et {A, C}, on décomposera R en {A, B} et {B, C}.
Envoyé par
wotan2009
Je sais calculer la fermeture d'un attribut (voir exercice), mais j'ai lu que l'on pouvait aussi calculer la fermeture de l'ensemble des DF. Je n'ai pas compris comment la calculer.
Comme je l’ai écrit dans un message précédent :
Envoyé par
fsmrel
la fermeture F+ de R est constituée — par définition — de l’ensemble des DF inférables de l’ensemble initial F donné de DF. La limite supérieure du nombre de DF éléments de F+ est égale à 2 puissance 2n soit 256 pour les 4 attributs.
Pour obtenir la liste, vous appliquez les règles d’Armstrong, jusqu’à ce que vous... craquiez.
Ainsi, vous commencez par fournir l’ensemble des DF triviales :
{A, B, C, D} → {A, B, C, D}
{A, B, C, D} → {A, B, C}
{A, B, C, D} → {A, B, D}
{A, B, C, D} → {A, C, D}
{A, B, C, D} → {B, C, D}
{A, B, C, D} → {A, B}
{A, B, C, D} → {A, C}
...
{A, B, C, D} → {A}
{A, B, C, D} → {B}
{A, B, C, D} → {C}
{A, B, C, D} → {D}
{A, B, C, D} → {}
{A, B, C} → {A, B, C}
{A, B, C} → {A, B}
{A, B, C} → {A, C}
...
{A, B, C} → {A}
{A, B, C} → {B}
{A, B, C} → {C}
{A, B, C} → {}
...
{A} → {A}
{A} → {}
{B} → {B}
{B} → {}
{C} → {C}
{C} → {}
{D} → {D}
{D} → {}
{} → {}
Ceci fait, appliquez les règles d’Armstrong aux DF données :
{A, B} → {C}
{A, B, C} → D (augmentation)
{A, B, D} → C (augmentation)
{B, C} → D (augmentation)
etc.
Bref, il vous reste à programmer un système expert pour arriver au bout de vos peines. Vous noterez que la finalité de tout cela est quand même de d’assurer que les relations respectent au moins la 3NF. Il est donc urgent de décomposer les relations, car plus le nombre d’attributs d’une relation est réduit, plus on est à même à de s’en assurer.
[Normalisation]Couverture minimale et dépendances fonctionnelles
Répondre avec citation
).
Partager