Discussion :

[fsmrel]

Le dîner était très bon, aussi je somnole un peu et j'espère ne pas raconter de bêtises...

Avant de passer au 4e point, j'en reviens à votre 1er message :

3)On se propose de décomposer la relation R en 6 relations:
R1(A,C) , R2(B,E), R3(A,E) , R4 (C,E,D) , R5(C,D,B) . Rappelez la condition pour qu'une décomposition soit sans perte d'informations. La décomposition proposée est elle sans perte d'information? justifiez.

Je ne vois pas 6 relations, mais seulement 5 et j'ai mon idée sur le piège qui se cache sous la coquille, qu'elle soit volontaire ou non, mais passons (à l'occasion, il faudrait remplacer le terme « relation » par celui de « relvar » (variable relationnelle), car une relation est une valeur prise par une variable relationnelle, mais une fois de plus, passons).

Comme on l’a vu, cette décomposition préserve les données (lossless join decomposition). Mais préserve-t-elle les dépendances fonctionnelles, c'est-à-dire les règles de gestion des données, point essentiel !

Pour apporter une réponse, comme je l’ai déjà écrit, on est obligé d’en passer par l’algorithme décrit au paragraphe « E.7.2. Préservation des dépendances fonctionnelles » de l’article.

Pour résumer, on utilise l’algorithme suivant :

Pour chaque dépendance fonctionnelle DFx X -> Y appartenant à F 
    Z= X
    Pour chaque Projection Ri
        Z = Z  ∪  ((X ∩ Ri)+ ∩ Ri)  par rapport à F

Où Z représente un ensemble d’attributs et R_i une des « relations » R1, R2, R3, R4, R5.


Illustrons...

On reprend l’ensemble F initial (pour réduire le nombre d’itérations, on pourrait utiliser une couverture irréductible, mais on n’est pas des feignants...) :

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

Considérons la DF {A} -> {D}. La paire {A, D} n’appartient à aucune des projections R1 à R5, aussi doit-on être en mesure d’inférer cette DF. Pour cela utilisons l’algorithme et effectuons les intersections, en commençant par R1 = {A, C} :

Z = {A}
  = {A}  ∪  (({A} ∩ {A, C})+ ∩ {A, C})
  = {A}  ∪  ({A}+ ∩ {A, C})
  = {A}  ∪  ({A, D, E} ∩ {A, C})
  = {A}  ∪  {A}
  = {A}

On n’a rien ramassé au passage...

Essayons avec la projection suivante, R2 = {B, E} :

Z = {A}
  = {A}  ∪  (({A} ∩ {B, E})+ ∩ {B, E})
  = {A}  ∪  (Ø ∩ {B, E})
  = {A}

Ça n’est pas terrible...

Essayons avec la projection suivante, R3 = {A, E} :

Z = {A}
  = {A}  ∪  (({A} ∩ {A, E})+ ∩ {A, E})
  = {A}  ∪  ({A}+ ∩ {A, E})
  = {A}  ∪  ({A, D, E} ∩ {A, E})
  = {A}  ∪  {A, E}
  = {A, E}

Z s’est un peu enrichi, mais on n’a pas inféré {A} -> {D}...

Essayons avec la projection suivante, R4 = {C, E, D} :

Z = {A, E}
  = {A, E}  ∪  (({A, E} ∩ {C, E, D})+ ∩ {C, E, D})
  = {A, E}  ∪  ({E}+ ∩ {C, E, D})
  = {A, E}  ∪  ({E} ∩ {A, E})
  = {A, E}  ∪  {E}
  = {A, E}

Bof...

Essayons avec la projection suivante, R5 = {C, D, B} :

Z = {A, E}
  = {A, E}  ∪  (({A, E} ∩ {C, D, B})+ ∩ {{C, D, B})
  = {A, E}  ∪  (Ø ∩ {C, D, B})
  = {A, E}

On repartirait pour un 2e tour de manège avec les projections R1 à R5 pour essayer de retrouver la DF {A} -> {D} que ça ne donnerait toujours rien...

Conclusion :

La décomposition de R en R1{A, C}, R2 {B, E}, R3{A, E}, R4{C, E, D}, R5{C, D, B} ne permet pas d’inférer la DF {A} -> {D}, et même si elle préserve la décomposition des données comme on l’a montré dans un message précédent, elle ne préserve pas les dépendances fonctionnelles : c’est affreux, affreux...


Sur ces paroles peu rassurantes, je vais m'occuper du 4e point

[fsmrel]

4) Donner une décomposition légèrement différente qui soit à la fois sans perte et en 3ème forme normale.

J’en reviens au théorème de Biskup, Dayal et Bernstein :

Soit G une couverture irréductible de R et K une clé de R. G ∪ {K} est une décomposition dont chaque relvar est en 3e forme normale ; G est une décomposition sans perte de données et qui préserve les dépendances fonctionnelles.

On connaît au moins une couverture irréductible (minimale, irredondante, ...) de R :

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

On connaît une clé de R (qui du reste n’en a pas d’autre) : K = {A, C}, come on l’a démontré dans le message #5.

Par application du théorème, la décomposition suivante préserve les données et les dépendances fonctionnelles, et en plus chaque relvar R1, R2, R3, R4, R5, R6 est en 3NF (clés soulignées) :

R1 = {A, D}, R2 = {D, E}, R3 = {B, E}, R4 = {C, E, D}, R5 = {C, D, B}, R6 = {A, C}

Tiens ? Cette fois-ci on a bien 6 relvars... Vous avez dit bizarre ? Comme c'est bizarre

Fermez le ban.

En prime : on montre très facilement que chacune de ces relvars est en BCNF (forme normale de Boyce-Codd), et même en 5NF...

Pour la petite histoire, on a deux autres couvertures irréductibles :

G’ = { {A} -> {D}, {D} -> {E}, {B} -> {E}, {C, E} -> {B, D} }

G’’ = { {A} -> {D}, {D} -> {E}, {B} -> {E}, {C, E} -> {B}, {B, C} -> {D} }

Et peut-être d’autres, mais je somnole...

En tout cas, bon courage !

[fsmrel]

Un point auquel je n’ai pas prêté attention :

j'ai compris la Forme normale 2 mais la forme normale 3 me laisse perplexe.
Car on a décomposé R en R1(A, C) , R2(B, E), R3(A, E) , R4 (C, E, D) , R5(C, D, B) mais comment connaît-on les DF ? Ce sont les mêmes que celles données au début de l'exercice?

Dans cette décomposition, les DF sont héritées de F (l’ensemble des DF associées valant pour R).

Ainsi pour R2, on a bien {B} -> {E}, pour R3 on a bien {A} -> {E}, pour R4 on a bien {C, E} -> {D} et {D} -> {E}, et pour R5 on a bien {C, D} -> {B}.

Petit problème : R4 ne respecte pas la BCNF, car cette relvar a pour clé {C, E}, mais la DF {D} -> {E} fait qu’un attribut non clé détermine une partie de la clé.

D’où la suggestion qui, je pense, vous est faite implicitement de décomposer R4 en R41 {D, E} et R42 {C, D} (« Donner une décomposition légèrement différente »). Comme R42 est incluse dans R5 elle est absorbée, et la décomposition devient :

R1{A, C} , R2{B, E}, R3{A, E} , R41 {D, E} , R5{C, D, B}

Gros problème : si la décomposition est sans perte de données, elle ne préserve pas les DF : comme on l’a vu, la DF {A} -> est perdue, et ça :

[lou93]

Bonjour!

Tout est très clair
Encore merci pour votre aide, j'ai examen dans 3 heures et je n'y serais surement pas arrivé sans vous!
Je vous souhaite une bonne journée !

Lou.

[fsmrel]

Bonjour Lou,


Tenez-moi au courant, j'espère ne pas vous avoir enduit avec plein d'erreurs, car je ne suis qu'un DBA, un homme de terrain baguenaudant chez les instruits...

Courage !