Envoyé par
fsmrel
Envoyé par
Oishiiii
C'est peut-être simplement l'expérience qui permet d'obtenir une décomposition équivalente à la mienne avec moins de relvars.
A mon sens, il s’agit d’une kolossale finesse de l’auteur de l’exercice, qui aurait tout aussi bien pu proposer les décompositions :
({B, C, D}, {A, E}, {A, C}) ou ({B, C, E}, {D, A}, {E, D}), etc.
On a vu que la décomposition Δ = ({A, B, C}, {D, E}, {C, D}) est sans perte d’information, mais avec perte de DF, alors que la décomposition que vous proposez est meilleure puisqu'elle préserve les DF.
Votre décomposition comporte cinq relvars alors que l’autre n’en comporte certes que trois, mais au prix d'un viol de BCNF (en fait de 2NF), ce qui revient à dire que le processus de décomposition doit être poursuivi, en sorte que l’on passe de :
Δ = ({A, B, C}, {D, E}, {C, D})
à :
Δ’ = ({C, A}, {B, C}, {D, E}, {C, D})
Les relvars composant Δ’ respectent cette fois-ci la BCNF (et même la 6NF), mais la décomposition ne préserve pas les DF. Existe-t-il quand même des décompositions qui respectent la BCNF, qui soient sans perte d’information et de DF et comportent moins de relvars que la vôtre ?
Remettons les compteurs à zéro. Les conditions initiales de température et de pression sont toujours les mêmes. L’en-tête de la relvar R est composé des attributs A, B, C, D, E :
R {A, B, C, D, E}
L’ensemble de DF associé (qui est irréductible) est le suivant :
F = {{A}→{E}, {C}→{E}, {D}→{A}, {E}→{D}}
La relvar R ne comporte qu’une clé candidate : {B, C}. Elle viole la 2NF car, par exemple, le dépendant {E} de la DF {C}→{E} dépend d’une partie de la clé. R doit donc subir une décomposition en relvars respectant la BCNF.
Votre propre décomposition est maximale, en ce sens qu'elle ne contient que des relvars binaires :
ΔOishiiii = ({B, C}, {A, E}, {C, E}, {D, A}, {E, D})
Si vous voulez une décomposition comportant moins de relvars, il faut y effectuer des jointures qui préservent la BCNF.
Effectuons par exemple la jointure naturelle {D, A} JOIN {E, D} pour produire la relvar {A, E, D} et permettant de réduire ΔOishiiii à :
ΔOishiii’= ({B, C}, {A, E}, {C, E}, {A, E, D}).
Mais la relvar ternaire {A, E, D} respecte-t-elle la BCNF ?
Avant de répondre à cette question, mettons en évidence un ensemble G qui soit un sous-ensemble de la fermeture F+ de F (avec G+ = F+), limité aux DF non triviales et non réductibles. G présente l’avantage de ne pas être aussi étriqué que F et permet ainsi d’élargir le champ des recherches des décompositions.
Le calcul de G passe par le calcul de la fermeture des attributs de R, à savoir A+, B+, C+, D+, E+. Ainsi :
- {A}+ = {A, D, E}, ce qui permet de découvrir la DF non triviale et non réductible {A}→{D}.
- {B}+ = {B}, ce qui ne nous apporte rien d’intéressant.
- {C}+ = {A, C, D, E}, ce qui permet de découvrir les DF {C}→{A} et {C}→{D}.
- {D}+ = {A, D, E}, ce qui permet de découvrir la DF {D}→{E}.
- {E}+ = {A, D, E}, ce qui permet de découvrir la DF {E}→{A}.
Au final, G est égal à F augmenté des DF que l’on vient de mettre en évidence :
G = {{A}→{E}, {C}→{E}, {D}→{A}, {E}→{D}, {A}→{D}, {C}→{A}, {C}→{D}, {D}→{E}, {E}→{A}}
On peut maintenant répondre positivement à la question : la relvar {A, E, D} respecte-t-elle la BCNF ?
En effet, {A}, {E} et {D} sont clés candidates pour {A, E, D} puisque selon G (et en tenant compte des DF triviales {A}→{A}, {D}→{D}, {E}→{E}) :
{A}→{A, E, D},
{E}→{A, E, D},
{D}→{A, E, D}.
En conséquence, la jointure naturelle {D, A} JOIN {E, D} produit la relvar {A, E, D} respectant la BCNF, ce qui fait que ΔOishiiii peut être effectivement réduite à quatre relvars :
ΔOishiiii’ = ({B, C}, {A, E}, {C, E}, {A, E, D})
Mais {A, E} n’est qu’une projection de {A, E, D} sur les attributs A et E et la décomposition peut être réduite à trois relvars :
Δe = ({B, C}, {C, E}, {A, E, D})
Les relvars {B, C}, {C, E}, {A, E, D} respectent la BCNF. Elles sont aussi sans perte d’information et sans perte de DF (je vous laisse le soin de le vérifier). On vérifie facilement que la décomposition Δe ne peut pas être réduite à deux relvars, mais en revanche il existe d’autres décompositions réduites à trois relvars que l'on peut chercher découvrir.
Remettons donc encore une fois les compteurs à zéro...
Soit la relvar R dont l’en-tête est composé des attributs A, B, C, D, E :
R {A, B, C, D, E}
L’ensemble de DF associé (réductible) est le suivant :
G = {{A}→{E}, {C}→{E}, {D}→{A}, {E}→{D}, {A}→{D}, {C}→{A}, {C}→{D}, {D}→{E}, {E}→{A}}
La relvar ne comporte qu’une clé candidate : {B, C}.
Puisque {E}→{A} et {E}→{D} appartiennent à G, par application de la règle d’union on infère {E}→{A, D}. En vertu du théorème de Heath, R {A, B, C, D, E} est décomposable selon :
R1 {A, E, D} et R2 {E, B, C}.
Et comme {C}
→{E} appartient à G, R2 est décomposable à son tour selon :
R21 {C, E} et R22 {B, C}.
On retrouve ainsi la décomposition :
Δe = ({A, E, D}, {C, E}, {B, C}).
Mais il existe d’autres décompositions du même tonneau.
Puisque {A}→{E} et {A}→{D} appartiennent à G, par application de la règle d’union on infère {A}→{E, D}. En vertu du théorème de Heath, R {A, B, C, D, E} est décomposable selon :
R1’ {A, E, D} et R2’ {A, B, C}.
Et comme {C}
→{A} appartient à G, R2’ est décomposable à son tour selon :
R21’ {C, A} et R22’ {B, C}.
On obtient ainsi la décomposition :
Δa = ({A, E, D}, {C, A}, {B, C}).
Puisque {D}→{E} et {D}→{A} appartiennent à G, par application de la règle d’union on infère {D}→{A, E}. En vertu du théorème de Heath, R {A, B, C, D, E} est décomposable selon :
R1’’ {A, E, D} et R2’’ {D, B, C}.
Et comme {C}
→{D} appartient à G, R2’’ est décomposable à son tour selon :
R21’’ {C, D} et R22’’ {B, C}.
On obtient ainsi la décomposition :
Δd = ({A, E, D}, {C, D}, {B, C}).
Ainsi, on a mis en évidence trois décompositions minimales, Δa, Δd et Δe composées chacune de trois relvars respectant la BCNF, préservant l’information (on a utilisé exclusivement le théorème de Heath pour produire les décompositions) et préservant les DF. A titre d'exemple, montrons que Δd préserve les DF (je vous laisse le soin d’en faire autant pour Δa et Δe).
Pour cela, on dispose de :
Δd = ({A, E, D}, {C, D}, {B, C})
F = {{A}→{E}, {C}→{E}, {D}→{A}, {E}→{D}}
Toutes les DF appartenant à F doivent être préservées (si elles le sont, celles de G le sont aussi, puisqu’inférées de celles de F).
Test de la préservation de la DF {A}→{E}.
Exploitons le 1er élément de Δd, à savoir {A, E, D} :
Z = {A} ∪ (({A} ∩ {A, E, D})+ ∩ {A, E, D}),
Z = {A} ∪ ({A}+ ∩ {A, E, D}), et comme {A}+ = {A, E, D} :
Z = {A} ∪ ({A, E, D} ∩ {A, E, D}),
Z = {A} ∪ {A, E, D},
Z = {A, E, D}.
Le dépendant {E} de la DF {A}→{E} est inclus dans Z : la DF est préservée.
Test de la préservation de la DF {C}→{E}.
Exploitons l’élément {C, D} de Δd :
Z = {C} ∪ (({C} ∩ {C, D})+ ∩ {C, D}),
Z = {C} ∪ ({C}+ ∩ {C, D}), et comme {C}+ = {A, C, D, E} :
Z = {C} ∪ ({A, C, D, E} ∩ {C, D}),
Z = {C} ∪ {C, D},
Z = {C, D}.
Poursuivons avec l’élément {A, E, D} de Δ :
Z = {C, D} ∪ (({C, D} ∩ {A, E, D})+ ∩ {A, E, D}),
Z = {C, D} ∪ ({D}+ ∩ {A, E, D}, et comme {D}+ = {A, E, D} :
Z = {C, D} ∪ ({A, E, D} ∩ {A, E, D}),
Z = {C, D} ∪ {A, E, D},
Z = {C, D, A, E}.
Le dépendant {E} de la DF {C}→{E} est inclus dans Z : la DF est préservée.
Test de la préservation de la DF {D}→{A}.
Exploitons l’élément {A, E, D} de Δ :
Z = {D} ∪ (({D} ∩ {A, E, D})+ ∩ {A, E, D}),
Z = {D} ∪ ({D}+ ∩ {A, E, D}), et comme {D}+ = {A, E, D} :
Z = {D} ∪ ({A, E, D} ∩ {A, E, D}),
Z = {A, E, D}.
Le dépendant {A} de la DF {D}→{A} est inclus dans Z : la DF est préservée.
Test de la préservation de la DF {E}→{D}.
Exploitons l’élément {A, E, D} de Δ :
Z = {E} ∪ (({E} ∩ {A, E, D})+ ∩ {A, E, D}),
Z = {E} ∪ ({E}+ ∩ {A, E, D}), et comme {E}+ = {A, E, D} :
Z = {E} ∪ ({A, E, D} ∩ {A, E, D}),
Z = {E} ∪ {A, E, D},
Z = {A, E, D}.
Le dépendant {D} de la DF {E}→{D} est inclus dans Z : la DF est préservée.
=>
Toutes les DF appartenant à F sont préservées, la décomposition Δd = ({A, E, D}, {C, D}, {B, C}) est donc sans perte de DF.
Maintenant, lorsque sur le terrain on a plus de mille relvars telles que R à vérifier quant au respect de la BCNF, avec des contraintes de délai, on n’a pas trop le temps de rechercher la meilleure décomposition, et si la vôtre n’est pas sur la plus haute marche du podium, elle est néanmoins valide et donc acceptable, contrairement à la décomposition Δ de l’exercice proposé à yaya125. Reconnaissons que le but de cet exercice était seulement de démontrer que Δ est sans perte d’information. Le risque eut été d’en conclure que Δ était valide au plan de la normalisation et de la préservation des DF.
N.B.
F = {{A}→{E}, {C}→{E}, {D}→{A}, {E}→{D}} constitue un ensemble irréductible de DF (couverture minimale) pour la relvar R {A, B, C, D, E}, mais ça n'est pas le seul. Partant de G, on découvre bien sûr F, mais aussi les ensembles irréductibles suivants :
F2 = {{A}→{E}, {C}→{D}, {D}→{A}, {E}→{D}}
F3 = {{A}→{D}, {C}→{A}, {D}→{E}, {E}→{A}}
F4 = {{A}→{D}, {C}→{D}, {D}→{E}, {E}→{A}}
Si le coeur vous en dit, je vous laisse le soin de compléter la liste...
Partager