Probléme normalisation relation

Version imprimable

20/06/2010, 01h31
yaya125

Probléme normalisation relation

Bonsoir ,j'essaye de faire d'autre exemple pour la normalisation pour que je comprend plus pour l'examen que j'ai lundi .
pour le 1ere Porbléme je l'vais fais il me manque que le calcule de la fermeture .
II et III Probléme j'ai pas réussi a le faire

1.I.Peut-on démontrer les dépendances fonctionnelles suivantes à partir de F = {AB->C , B->D, CD->E ,CE->GH , G->A }?Si c'est le cas proposez une démonstration détaillée sinon justifiez votre réponse.
1. CE->D

2.BG->C

la réponse fournis pour 1.CE->D je n'ai pas réussi le calcul de {C,E}->D à partir de F , alors elle est impossible mais je pense que je devrais dire que la fermeture de {C,E}+ de {C,E} n'appartient pas à F Mais pour la fermeture je ne sais pas comment la calculer ?

pour la deuxième et vrai explication

R(A,B,C,E,D,G,H}

R satisfait l'ensemble F de DF suivant :
DF1: {A,B} -> {c}
DF2:{B}->D
DF3:{C,D}->{E}
DF4:{C,E} ->{G,H}
DF5 : {G}-> {A}
à l'aide l'axiome d'amstrong on obtiens :
1.{B,G} ->{A,B} (DF5 augmentation )
2.{A,B}->{C}
3.{B,G}->{C} (1 et 2 transition)
donc pour la 2 et vrai

II.Déterminez si les décompositions suivante sont sans perte d'information (SPI).si une décomposition n'est pas SPI vous proposez un contre exemple et montrerez qu'il s'agit bien d'un contre exemple.
1.U=ABCDE , F={A->E,C->E, D->A ,E->D} , Δ=ABC ,DE,CD
2.U= ABCDE ,F = {B->A,CE->B,C->E,D->E},Δ=ABC,DE ,CD

III.Déterminez si la décomposition Δ=AB , BD est sans perte de dépendances par rapport à F = {A->B,B->D}
merci
20/06/2010, 02h02
fsmrel

Citation:

je pense que je devrais dire que la fermeture de {C,E}+ de {C,E} n'appartient pas à F Mais pour la fermeture je ne sais pas comment la calculer ?

Utilisez l'algorithme qu'on vous a déjà fourni :

http://www.developpez.net/forums/d93...n/#post5283108
20/06/2010, 02h08
yaya125

Bonsoir
je pense que la fermeture qu'on j'aurai est ça :
{C,E}+={C,E,G,H,A}
20/06/2010, 12h31
fsmrel

Citation:

Envoyé par yaya125

Bonsoir
je pense que la fermeture qu'on j'aurai est ça :
{C,E}+={C,E,G,H,A}

Exact. Et comme D n'en fait pas partie, la DF {C,E} -> {D} ne peut pas exister.
20/06/2010, 12h59
yaya125

Merci par contre les 2 dernier probléme je sais pas leur solution , peut être je vais avoir comme ce genre d'exercice a mn examen stp pourrai tu me donner une solution bien explicative .
20/06/2010, 13h15
yaya125

II.Déterminez si les décompositions suivante sont sans perte d'information (SPI).si une décomposition n'est pas SPI vous proposez un contre exemple et montrerez qu'il s'agit bien d'un contre exemple.
1.U=ABCDE , F={A->E,C->E, D->A ,E->D} , Δ=ABC ,DE,CD
2.U= ABCDE ,F = {B->A,CE->B,C->E,D->E},Δ=ABC,DE ,CD
pour la 1ere question voilà la réponse que je présente mais je ne pense pas qu'elle est just :

Δ A B C D E

ABC a b c x1 x2

DE x3 x4 x5 d e

CD x6 x7 c d x8

on remarque qu'il y a au moins une ligne sans variable donc SPI
je pense qu'il me manque d'explication !!
20/06/2010, 18h02
fsmrel

1er cas : U=ABCDE , F={A->E, C->E, D->A ,E->D} , Δ=ABC ,DE, CD

La représentation tabulaire que vous utilisez ressemble à celle de Ullman, à la notation près :

http://www.fsmwarden.com/developpez/...tableau_01.jpg

Il faut maintenant que vous exploitiez les dépendances fonctionnelles pour faire évoluer le tableau.

Considérons la dépendance fonctionnelle A -> E. On cherche dans la colonne A du tableau les valeurs égales : il n’y en a pas, donc rien ne se passe.

Considérons la dépendance fonctionnelle C -> E. On cherche dans la colonne C du tableau les valeurs égales : on trouve la valeur c pour la ligne 1 et pour la ligne 3 : on peut rendre égales les valeurs correspondantes dans la colonne E :

http://www.fsmwarden.com/developpez/...tableau_02.jpg

Considérons la dépendance fonctionnelle D -> A. On cherche dans la colonne D du tableau les valeurs égales : on trouve la valeur d pour la ligne 2 et pour la ligne 3 : on peut rendre égales les valeurs correspondantes dans la colonne A :

http://www.fsmwarden.com/developpez/...tableau_03.jpg

Considérons la dépendance fonctionnelle E -> D. On cherche dans la colonne E du tableau les valeurs égales : on trouve la valeur x2 pour la ligne 1 et pour la ligne 3 : on peut rendre égales les valeurs correspondantes dans la colonne D (en privilégiant la valeur forte d plutôt que la valeur faible x1, car le but de la manœuvre est de faite disparaître les xi) :

http://www.fsmwarden.com/developpez/...tableau_04.jpg

On a exploité toutes les dépendances fonctionnelles. On recommence le processus, tant que le tableau peut évoluer.

Considérons à nouveau la dépendance fonctionnelle A -> E. On cherche dans la colonne A du tableau les valeurs égales :

http://www.fsmwarden.com/developpez/...tableau_05.jpg

on trouve la valeur x3 pour la ligne 2 et pour la ligne 3 : on peut rendre égales les valeurs correspondantes dans la colonne E (en privilégiant la valeur forte e plutôt que la valeur faible x2) :

http://www.fsmwarden.com/developpez/...tableau_06.jpg

Considérons la dépendance fonctionnelle C -> E. On cherche dans la colonne C du tableau les valeurs égales : on trouve la valeur c pour la ligne 1 et pour la ligne 3 : on peut rendre égales les valeurs correspondantes dans la colonne E (en privilégiant la valeur forte e plutôt que la valeur faible x2) :

http://www.fsmwarden.com/developpez/...tableau_07.jpg

Sans même poursuivre le processus, sachant que pour que la décomposition soit sans perte, il suffit qu'il existe dans le tableau au moins une ligne sans xi, et comme c’est le cas de la 1re ligne, on conclut que la décomposition est sans perte.
20/06/2010, 18h58
Oishiiii
Citation:

Envoyé par fsmrel

1er cas : U=ABCDE , F={A->E, C->E, D->A ,E->D} , Δ=ABC ,DE, CD
...
on conclut que la décomposition est sans perte.

Bonjour fsmrel,

J'étais sur le point d'envoyer une réponse lorsque j'ai vu votre message.

J'ai pensé que la décomposition n'était pas correcte, elle perd des DF, par exemple, {D} → {A} n'apparaît dans aucune relvar.

Je viens de vérifier si la jointure des relvars {A, B, C}, {D, E} et {C, D} ne produisait pas d'anomalies en les représentant dans des tables avec des valeurs, et il n'y a pas de problèmes effectivement.

Je suis parti de l'ensemble F des DF et en suivant les conseils de Heath et surtout Jorma Rissanen j'ai décomposé U pour obtenir ces relvars:
Code:

1 2 3 4 5 Ua = {B, C} Ub = {A, E} Uc = {C, E} Ud = {D, A} Ue = {E, D}
Finalement j'ai une relvar pour la clé candidate {B, C} et des relvars pour chaque DF — il n'y a littéralement aucune perte de DF.

Comment arrive-t'on à la décomposition donnée dans l'exercice à partir de F ? Quelle est la logique à suivre ?
Je vois bien que pour la relvar composée des attributs D et E on joue avec la transitivité d'Armstrong à partir des DF {D} → {A} et {A} → {E}, mais il ne me serait jamais venu à l'esprit de créer la relvar {A, B, C} par exemple.
C'est peut-être simplement l'expérience qui permet d'obtenir une décomposition équivalente à la mienne avec moins de relvar.
20/06/2010, 20h32
yaya125

Bonsoir Merci beaucoup j'ai tro bien compris par contre le dernier probléme est ce que peut tu me l'expliquer ?
21/06/2010, 03h21
fsmrel

Renvoi vers l'algorithme qui va bien.

Citation:

Envoyé par yaya125

j'ai tro bien compris par contre le dernier probléme est ce que peut tu me l'expliquer ?

Déterminez si la décomposition Δ=AB , BD est sans perte de dépendances par rapport à F = {A->B, B->D}

Ayant lu trop vite la question posée par yaya, je renvoie vers le message qui va bien :

http://www.developpez.net/forums/d94...n/#post5307151

Ce qui suit vaut pour la décomposition sans perte de données mais ne concerne pas la perte des dépendances...

Appliquer le théorème de Heath :

Soit la relvar R {A, B, C} dans laquelle A, B et C sont des ensembles d’attributs de R. Si R satisfait à la dépendance fonctionnelle A -> B, alors R est égale à la jointure de ses projections sur {A, B} et {A, C}.

En tenant compte de la recommandation de Rissanen :

Soit la relvar R {A, B, C} dans laquelle A, B et C sont des ensembles d’attributs de R. 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}.
21/06/2010, 03h25
fsmrel

Citation:

Envoyé par Oishiiii

il ne me serait jamais venu à l'esprit de créer la relvar {A, B, C}

A moi non plus ! En effet, je viens du terrain, et quand j’ai commencé dans le métier, l’informatique n’était pas encore enseignée à l’Université...

J’ai expertisé, « soigné » des monceaux de modèles conceptuels et de bases de données, et je n’ai jamais eu le temps de jouer à au petit jeu des décompositions multiples, car les délais, les contraintes financières et autres considérations bassement matérielles imposées par nos clients m’obligeaient à aller vite. Pour ne pas me planter, j’ai toujours suivi Heath et Rissanen et je n’ai jamais été déçu.

Quant à produire des décompositions comportant moins de relvars, ça n’est pas forcément un bon plan. Dans le contexte d’une production informatique, ça n’est qu’en effectuant un prototypage des performances que l’on peut trancher en faveur d’une structure.

Cela dit, je mets encore Ullman à contribution. Il propose en effet une variante du théorème de Heath qui peut vous intéresser. Ullman précise que cette variante est due à Delobel et Casey ainsi qu’à Rissanen. Le théorème est le suivant :

Si ρ = (R1, R2) est une décomposition de R, et F est ensemble de dépendances fonctionnelles, alors ρ a une décomposition sans perte par rapport à F si et seulement si

(R1 ∩ R2) → (R1 — R2) ou (R1 ∩ R2) → (R2 — R1)
En notant que ces dépendances ne font pas nécessairement partie de F, il suffit qu’elles appartiennent à la fermeture F+.

Pour reprendre l’exemple qui vous interpelle, considérons la décomposition ρ = ({A, B, C}, {C, D, E}). Pour qu’elle soit sans perte, on doit vérifier :

({A, B, C} ∩ {C, D, E}) → ({A, B, C} — {C, D, E}) ou ({A, B, C} ∩ {C, D, E}) → ({C, D, E} — {A, B, C})
On a :

{A, B, C} ∩ {C, D, E} = {C}
{C, D, E} — {A, B, C} = {D, E}
Or {C} → {D, E} appartient à F+ puisque {C}+ = {A, C, D, E} : la décomposition est bien sans perte.

A son tour, le triple {C, D, E} est-il décomposable sans perte en {C, D} et {D, E} ? Si oui, on doit vérifier :

({C, D} ∩ {D, E}) → ({C, D} — {D, E}) ou ({C, D} ∩ {D, E}) → ({D, E} — {C, D})
On a :

{C, D} ∩ {D, E} = {D}
{D, E} — {C, D} = {E}
Or {D} → {E} appartient à F+ puisque {D}+ = {A, D, E} : la décomposition est bien sans perte.

Ainsi, R = {A, B, C, D, E} peut être décomposée en ρ = ({A, B, C}, {C, D}, {D, E}). La variante du théorème de Heath permet de produire de nouvelles décompositions, mais notre brave théorème initial suffit quand on construit des bases de données pour de vrai.
25/06/2010, 03h07
fsmrel

Citation:

Envoyé par yaya125

Déterminez si la décomposition Δ=AB , BD est sans perte de dépendances par rapport à F = {A->B, B->D}

A l’occasion de ma réponse précédente, j’ai lu trop vite, et je n’ai pas vu qu’il s’agissait de perte de dépendances. C’est vrai que la décomposition Δ est sans perte de dépendance, mais le théorème de Heath n’a rien à voir dans cette affaire. On va donc mettre en oeuvre le marteau-pilon qui va bien pour répondre à la question.

On définit un ensemble G qui est l’union des projections sur F des éléments de Δ, à savoir AB et BD : G = πAB(F) U πBD(F).

Ensuite on applique l’algorithme suivant :

http://www.fsmwarden.com/developpez/...vation_DF).jpg

X est le déterminant d’une DF X -> Y appartenant à F. Ri représente successivement les éléments de Δ, à savoir AB puis BD.

En fin de parcours, si Y est un sous-ensemble de Z, alors X -> Y appartient à G.

Si chaque DF telle que X -> Y appartenant à F appartient aussi à G, alors Δ préserve F, sinon il y a perte de dépendance.

On commence avec le déterminant A de la DF A -> B et le 1er élément de Δ, à savoir AB.

http://www.fsmwarden.com/developpez/...tion_DF)02.jpg

Le dépendant B de la DF A -> B constitue un sous-ensemble de Z, donc A -> B appartient à G.

On passe au déterminant B de la DF B -> D et le 1er élément de Δ, à savoir AB : en fin d’itération Z est seulement égal à B, aussi on poursuit avec le 2e élément de Δ, à savoir BD :

http://www.fsmwarden.com/developpez/...tion_DF)03.jpg

Le dépendant D de la DF B -> D constitue un sous-ensemble de Z, donc B -> D appartient à G.

Toutes les DF appartenant à F appartiennent aussi à G, donc la décomposition Δ préserve les dépendances par rapport à F.
25/06/2010, 13h07
Oishiiii

Bonjour fsmrel,

Excusez-moi pour cette question certainement triviale, mais que fait l'opérateur — ?

Citation:

Envoyé par fsmrel

({A, B, C} ∩ {C, D, E}) → ({A, B, C} — {C, D, E}) ou ({A, B, C} ∩ {C, D, E}) → ({C, D, E} — {A, B, C})
On a :

{A, B, C} ∩ {C, D, E} = {C}
{A, B, C} — {C, D, E} = {A}

A priori je pencherai sur une Différence, mais {A, B, C} — {C, D, E} donnerait {A, B} dans ce cas ?

A+
25/06/2010, 15h31
fsmrel

Citation:

Envoyé par Oishiiii

A priori je pencherai sur une Différence, mais {A, B, C} — {C, D, E} donnerait {A, B} dans ce cas ?

Il s'agit bien d'une opération de différence et donc {A, B, C} — {C, D, E} a pour résultat {A, B}.

Merci d'avoir tout relu. Je rectifie en conséquence :

Considérons la décomposition ρ = ({A, B, C}, {C, D, E}). Pour qu’elle soit sans perte, on doit vérifier :

({A, B, C} ∩ {C, D, E}) → ({A, B, C} — {C, D, E}) ou ({A, B, C} ∩ {C, D, E}) → ({C, D, E} — {A, B, C})
On a :

{A, B, C} ∩ {C, D, E} = {C}
{C, D, E} — {A, B, C} = {D, E}
Or {C} → {D, E} appartient à F+ puisque {C}+ = {A, C, D, E} : la décomposition est bien sans perte.

Si ça ne vous ennuie pas de bien relire, je suis tout endormi...

Attention aux pertes de DF...

Citation:

Envoyé par Oishiiii

Je viens de vérifier si la jointure des relvars {A, B, C}, {D, E} et {C, D} ne produisait pas d'anomalies en les représentant dans des tables avec des valeurs, et il n'y a pas de problèmes effectivement.

Comment arrive-t'on à la décomposition donnée dans l'exercice à partir de F ? Quelle est la logique à suivre ?

Concernant la logique à suivre, ou plutôt la tactique, il y en a plus d'une, car il y a un bon paquet de DF inférables permettant de produire des décompositions plus ou moins valables...

Utilisons par exemple les DF {D}→{E} et {C}→{D} inférées au moyen des règles d'Armstrong (les DF {D}→{A} et {A}→{E} étant données, par transitivité on produit {D}→{E}, de même les DF {C}→{E} et {E}→{D}, étant données, par transitivité on produit la DF {C}→{D}).

Grâce à la DF {D}→{E}, par application du théorème de Heath, on peut décomposer R en :

R1 {D, E} et R2 {A, B, C, D}
Grâce à la DF {C}→{D}, par application du théorème de Heath, on peut décomposer R2 en :

R21 {C, D} et R22 {A, B, C}
On retrouve ainsi la décomposition proposée à yaya125 : {A, B, C}, {D, E}, {C, D}.

Mais il y a un os : R22 (de clé {B, C}) viole la 2NF à cause de la DF {C}→{A} (du fait des DF {C}→{E} et {E}→{D} par transitivité on produit la DF {C}→{D} et comme on a {D}→{A} par transitivité à nouveau, on produit la DF {C}→{A}).

La décomposition doit être poursuivie, et au final on obtient la décomposition :

R221 {C, A}, R222 {B, C}, R1 {D, E}, R21 {C, D}
Pour laquelle chaque relvar respecte la BCNF, mais qui n'est pas forcément à recommander elle non plus comme on le verra ci-dessous.

Citation:

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.
Le problème est que, contrairement à la vôtre, toutes ces décompositions violent elles aussi la 2NF et même si on en poursuit la décomposition, elles ne vont pas non plus sans perte de DF (y-compris évidemment la décomposition proposée à yaya125).

Par contraste, votre décomposition est la bonne et convient pour les bases de données en production, tandis que les subtilités du monde académique ne sont pas forcément de mise dans ce contexte.

Je consigne dans ce qui suit tout ce que nous avons pu dire quant à la décomposition sans perte d’information et sans perte de DF, le but étant bien sûr de produire des relvars respectant la BCNF. Oyez !

Décomposition sans perte d’information et sans perte de DF.

Reprenons l’exercice II.1 proposé à yaya125. Soit la relvar R dont l’en-tête est composée 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 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 qui respectent la BCNF.

1) Cas de la décomposition proposée par Oishiiii

Ua = {B, C}
Ub = {A, E}
Uc = {C, E}
Ud = {D, A}
Ue = {E, D}
Les relvars Ua, ..., Ue respectent la BCNF (et même la 6NF puisqu’elles ne comportent que des paires d’attributs). Montrons que cette décomposition est sans perte d’information et sans perte de DF.

La décomposition est sans perte d’information. Pour le montrer, utilisons par exemple la méthode du tableau.

La situation initiale est la suivante (la colonne la plus à gauche contient les relvars issues de la décomposition, chaque autre colonne contient le nom de la colonne sous forme de lettre minuscule si ce nom figure dans la relvar apparaissant dans la colonne la plus à gauche, sinon c’est sous la forme d’un nombre non encore utilisé dans le tableau) :
Code:

1 2 3 4 5 6 7 | A B C D E -----------------|--------------------------- {A, E} | a 1 2 3 e {C, E} | 4 5 c 6 e {D, A} | a 7 8 d 9 {E, D} | 10 11 12 d e {B, C} | 13 b c 14 15
Utilisons les DF appartenant à F. Dans le cas de la DF {A}→{E}, comme la lettre a figure dans les lignes 1 et 3, le chiffre 9 de la ligne 3 peut être remplacé par la lettre e figurant dans la ligne 1 :
Code:

1 2 3 4 5 6 7 {A}→{E} | A B C D E -----------------|--------------------------- {A, E} | a 1 2 3 e {C, E} | 4 5 c 6 e {D, A} | a 7 8 d e {E, D} | 10 11 12 d e {B, C} | 13 b c 14 15
Avec les DF suivantes :
Code:

1 2 3 4 5 6 7 {C}→{E} | A B C D E -----------------|--------------------------- {A, E} | a 1 2 3 e {C, E} | 4 5 c 6 e {D, A} | a 7 8 d e {E, D} | 10 11 12 d e {B, C} | 13 b c 14 e
Code:

1 2 3 4 5 6 7 {E}→{D} | A B C D E -----------------|--------------------------- {A, E} | a 1 2 d e {C, E} | 4 5 c d e {D, A} | a 7 8 d e {E, D} | 10 11 12 d e {B, C} | 13 b c d e
Code:

1 2 3 4 5 6 7 {D}→{A} | A B C D E -----------------|--------------------------- {A, E} | a 1 2 d e {C, E} | a 5 c d e {D, A} | a 7 8 d e {E, D} | a 11 12 d e {B, C} | a b c d e
La dernière ligne ne contient que des lettres : la décomposition est sans perte d’information. A signaler que sans la présence de la relvar {B, C}, il y aurait perte d’information.

La décomposition est aussi sans perte de DF, car chaque DF appartenant à F est présente dans la décomposition proposée par Oishiiii.

2) Cas de la décomposition proposée à yaya125

La décomposition proposée est la suivante : Δ = ({A, B, C}, {D, E}, {C, D}).

Les 3 relvars {A, B, C}, {D, E}, {C, D} respectent la BCNF. La décomposition est-elle sans perte d’information et sans perte de DF ?

Montrons que la décomposition est sans perte d’information. Pour cela, utilisons à nouveau la méthode du tableau. La situation initiale est la suivante :
Code:

1 2 3 4 5 | A B C D E -----------------|--------------------------- {A, B, C} | a b c 1 2 {D, E} | 3 4 5 d e {C, D} | 6 7 c d 8
Utilisons les DF appartenant à F :
Code:

1 2 3 4 5 {C}→{E} | A B C D E -----------------|--------------------------- {A, B, C} | a b c 1 2 {D, E} | 3 4 5 d e {C, D} | 6 7 c d 2
Code:

1 2 3 4 5 {E}→{D} | A B C D E -----------------|--------------------------- {A, B, C} | a b c d 2 {D, E} | 3 4 5 d e {C, D} | 6 7 c d 2
Code:

1 2 3 4 5 {D}→{A} | A B C D E -----------------|--------------------------- {A, B, C} | a b c d 2 {D, E} | a 4 5 d e {C, D} | a 7 c d 2
Code:

1 2 3 4 5 {A}→{E} | A B C D E -----------------|--------------------------- {A, B, C} | a b c d e {D, E} | a 4 5 d e {C, D} | a 7 c d e
La 1re ligne ne contient que des lettres : la décomposition est sans perte d’information.

Montrons qu’il y a en revanche perte de DF.

Utilisons à cet effet l’algorithme ad-hoc, en exploitant
Δ = ({A, B, C}, {D, E}, {C, D})
Cas de la DF {A}→{E}

Exploitons {A, B, C} :
Z = {A} ∪ (({A} ∩ {A, B, C})⁺ ∩ {A, B, C}),
Z = {A} ∪ ({A}⁺ ∩ {A, B, C}), et comme {A}⁺ = {A, D, E} :
Z = {A} ∪ ({A, D, E} ∩ {A, B, C}),
Z = {A} ∪ {A},
Z = {A}.

Exploitons {D, E} :
Z = {A} ∪ (({A} ∩ {D, E})⁺ ∩ {D, E}),
Z = {A} ∪ (Ø ∩ {D, E}),
Z = {A}.

Exploitons {C, D} :
Z = {A} ∪ (({A} ∩ {C, D})⁺ ∩ {C, D}),
Z = {A} ∪ (Ø ∩ {C, D}),
Z = {A}.
On a exploité Δ sans que le dépendant {E} de la DF {A}→{E} puisse être inclus dans Z : la DF n’est pas préservée, donc la décomposition Δ proposée n’est pas à recommander.

Ça serait la même chose si on décomposait Δ en ({C, A}, {B, C}, {D, E}, {C, D}).

(On montre de la même façon de la DF {D}→{A} n’est pas non plus préservée.)

Bien sûr, l'exercice proposé à yaya125 ne portait que sur la préservation de l'information, mais j'espère, Oishiiii, que vous voilà rassuré.

N.B. Merci de me signaler les coquilles qui pourraient traîner...

17/07/2010, 19h08
fsmrel

Le feuilleton des décompositions, suite...
Citation:

Envoyé par fsmrel

Citation:

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...
25/07/2010, 22h10
Oishiiii

Merci fsmrel pour toutes ces informations et explications très intéressantes et utiles. :ccool:

Vous faites la distinction entre les concepts de décompositions sans perte d'information et décomposition sans perte de dépendances et j'ai peur de m'emmêler les pinceaux.

La décomposition d'une relvar en plusieurs autres relvars (projections) doit être réversible.
On doit retrouver la relvar initiale en utilisant l'opérateur de jointure naturelle sur ses projections.
L'utilisation des dépendances fonctionnelles est indispensable pour effectuer une décomposition correctement puisque se sont les règles de gestions, ce sont elles qui donnent un sens à la relvar.

Finalement le concept de décomposition sans perte d'information sert uniquement à s'assurer que l'opération de jointure permettra d'obtenir une relation dont l'en-tête est strictement identique à celui de la relvar faisant l'objet de la décomposition, ou y-a-t'il d'autres subtilités ?

Pour revenir sur l'exercice, voici ma copie ;) :

Citation:

Envoyé par fsmrel

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).

Pour vérifier que la décomposition Δe est bien sans perte de dépendances j'ai utilisé l’algorithme que vous nous avez décrit.

J'utilise toujours l'ensemble de DF suivant:
F = { {A}→{E}, {C}→{E}, {D}→{A}, {E}→{D} }

Première DF, {A}→{E}
J'exploite l’élément {A, D, E} de Δe :
Z = {A} ∪ (({A} ∩ {A, D, E})+ ∩ {A, D, E}),
Z = {A} ∪ ({A}+ ∩ {A, D, E}), et comme {A}+ = {A, D, E} :
Z = {A} ∪ ({A, D, E} ∩ {A, D, E}),
Z = {A} ∪ {A, D, E},
Z = {A, D, E}.

Le dépendant {E} de la DF {A}→{E} est inclus dans Z : la DF est préservée.
Seconde DF, {C}→{E}
J'exploite {C, E} :
Z = {C} ∪ (({C} ∩ {C, E})+ ∩ {C, E}),
Z = {C} ∪ ({C}+ ∩ {C, E}), et comme {C}+ = {A, C, D, E} :
Z = {C} ∪ ({A, C, D, E} ∩ {C, E}),
Z = {C} ∪ {C, E},
Z = {C, E}.

Le dépendant {E} de la DF {C}→{E} est inclus dans Z : la DF est préservée.
Troisième DF, {D}→{A}
J'exploite {A, D, E} :
Z = {D} ∪ (({D} ∩ {A, D, E})+ ∩ {A, D, E}),
Z = {D} ∪ ({D}+ ∩ {A, D, E}), et comme {D}+ = {A, D, E} :
Z = {D} ∪ ({A, D, E} ∩ {A, D, E}),
Z = {D} ∪ {A, D, E},
Z = {A, D, E}.

Le dépendant {A} de la DF {D}→{A} est inclus dans Z : la DF est préservée.
Dernière DF, {E}→{D}
J'exploite {A, D, E} :
Z = {E} ∪ (({E} ∩ {A, D, E})+ ∩ {A, D, E}),
Z = {E} ∪ ({E}+ ∩ {A, D, E}), et comme {E}+ = {A, D, E} :
Z = {E} ∪ ({A, D, E} ∩ {A, D, E}),
Z = {A, D, E}.

Le dépendant {D} de la DF {E}→{D} est inclus dans Z : la DF est préservée.
Toutes les DF de F sont préservées, la décomposition Δe est sans perte de dépendances.

Citation:

Envoyé par fsmrel

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...

Il ne manque que deux nouveaux ensembles pour compléter la liste :

F1 = {{A}→{E}, {C}→{E}, {D}→{A}, {E}→{D}}
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}}
F5 = {{A}→{D}, {C}→{E}, {D}→{E}, {E}→{A}}
F6 = {{A}→{E}, {C}→{A}, {D}→{A}, {E}→{D}}
26/07/2010, 02h35
fsmrel

Bonsoir,

Citation:

Envoyé par Oishiiii

La décomposition d'une relvar en plusieurs autres relvars (projections) doit être réversible.
On doit retrouver la relvar initiale en utilisant l'opérateur de jointure naturelle sur ses projections.

Exact. C’est ce que les camarades Date, Ullman et consorts, appellent une nonloss decomposition, une décomposition sans perte d’information (que j’abrège souvent en décomposition sans perte, pour faire comme eux). Mais, par référence à ce que vous écrivez :

« le concept de décomposition sans perte d'information sert uniquement à s'assurer que l'opération de jointure permettra d'obtenir une relation dont l'en-tête est strictement identique à celui de la relvar faisant l'objet de la décomposition, ou y-a-t'il d'autres subtilités ? »
Je me rends compte que je ferais mieux de parler de décomposition sans perte de contenu (à l’instar de Delobel et Adiba, qui mettent les points sur les i en parlant plus précisément de préservation du contenu de la base de données).

Considérons par exemple la relvar R {A, B, C, D} avec F = {{A}→{B}, {C}→{D}}.

Si on décompose R en R1 {A, B} et R2 {C, D}, c'est-à-dire sans tenir compte du théorème de Heath, l'opération R1 JOIN R2 produit une relvar dont l'en-tête {A, B, C, D} est exactement celui de R, mais le contenu de la base de données n’est pas préservé (on a plutôt effectué l’opération R1 TIMES R2, car la jointure dégénère en produit quand le nombre d’attributs participant à la jointure est égal à 0). Par référence à mon message du 21 juin dernier, vous pouvez aussi vous en assurer en observant que les DF (R1 ∩ R2) → (R1 — R2) et (R1 ∩ R2) → (R2 — R1) n’appartiennent ni l’une ni l’autre à F+.

Prenons maintenant l’exemple de la relvar suivante : R {A, B, C} avec F = {{A, B}→{C}, {C}→{B}} et appliquons sagement le théorème de Heath : R est décomposable en R1 {B, C} et R2 {A, C} et cette décomposition préserve le contenu de la base de données. Vous pouvez aussi vous en assurer en observant que, par rapport à F+, (R1 ∩ R2) → (R1 — R2)).
En revanche, vous pouvez vérifier que cette décomposition ne préserve malheureusement pas la dépendance fonctionnelle {A, B}→{C}, d’où le dilemme : soit on décompose et on perd une règle de gestion (avec des assertions ou des triggers SQL en perspective pour pallier), soit on ne décompose pas mais la BCNF est alors violée (toujours avec des assertions ou des triggers en perspective pour garantir les redondances...)

Si vous avez encore peur de vous emmêler les pinceaux ou si vous avez des angoisses métaphysiques, n’hésitez pas à poser des questions.

Citation:

Envoyé par Oishiiii

Pour revenir sur l'exercice, voici ma copie ;)

Pour citer Jean (in Les tontons flingueurs) : vingt sur vingt, et en cotant vache...
(Mais un lecteur attentif et patient fera peut-être mieux, auquel cas il aura droit à au moins un point de plus que nous...:D)
26/07/2010, 18h37
Oishiiii

Bonjour,

Citation:

Envoyé par fsmrel

Considérons par exemple la relvar R {A, B, C, D} avec F = {{A}→{B}, {C}→{D}}.

Si on décompose R en R1 {A, B} et R2 {C, D}, c'est-à-dire sans tenir compte du théorème de Heath, l'opération R1 JOIN R2 produit une relvar dont l'en-tête {A, B, C, D} est exactement celui de R, mais le contenu de la base de données n’est pas préservé (on a plutôt effectué l’opération R1 TIMES R2, car la jointure dégénère en produit quand le nombre d’attributs participant à la jointure est égal à 0). Par référence à mon message du 21 juin dernier, vous pouvez aussi vous en assurer en observant que les DF (R1 ∩ R2) → (R1 — R2) et (R1 ∩ R2) → (R2 — R1) n’appartiennent ni l’une ni l’autre à F+.

Je pensait que la préservation des dépendances impliquait forcément la préservation de l'information/du contenu mais ce n'est pas le cas, on le voit très bien dans cet exemple.

Citation:

Envoyé par fsmrel

Prenons maintenant l’exemple de la relvar suivante : R {A, B, C} avec F = {{A, B}→{C}, {C}→{B}} et appliquons sagement le théorème de Heath : R est décomposable en R1 {B, C} et R2 {A, C} et cette décomposition préserve le contenu de la base de données. Vous pouvez aussi vous en assurer en observant que, par rapport à F+, (R1 ∩ R2) → (R1 — R2)).
En revanche, vous pouvez vérifier que cette décomposition ne préserve malheureusement pas la dépendance fonctionnelle {A, B}→{C}, d’où le dilemme : soit on décompose et on perd une règle de gestion (avec des assertions ou des triggers SQL en perspective pour pallier), soit on ne décompose pas mais la BCNF est alors violée (toujours avec des assertions ou des triggers en perspective pour garantir les redondances...)

C'est donc ça le fameux problème de la BCNF. C'est facile à comprendre lorsqu'on a toutes les clés :)

Et bien merci encore, il n'y a plus aucune zone d'ombre, c'est très clair.
A bientôt pour le prochain épisode ;)