Discussion :

[switch1]

bonjour tout le monde
j'ai de souci a déterminer la couverture minimum d'un ensemble de DF, je me suis référé a la conversation http://www.developpez.net/forums/d65...ture-minimale/
et je profite pour remercier Monsieur Fsmrel de ces réponses détaillées et convaincantes.
prenons un exemple :
soit F={AB->C , AC->D, A->BC , B->C, A->B}
si on transforme les DF de F sous forme de DF élémentaires on obtient :
F={AB->C , AC->D, A->B,A->C , B->C, A->B}A->B est dupliqué
F={AB->C , AC->D, A->B,A->C , B->C}
**commençant par AB->C :
on a : A+={A,B,C..} puisque C appartient a A+, alors AB->c peut être remplacé par A->C
on peut même s'arrêter des qu'on a trouve que B appartient a A+
puisque : A->B alors AB->C sera remplacé par A->C
F={A->C , AC->D, A->B,A->C , B->C} on a A->C est dupliqué alors :
F={AC->D, A->B,A->C , B->C}
** AC->D :
A+={A,B,C} C appartient a A+ alors on remplace AC->D par A->D
F={A->D, A->B,A->C , B->C}
A->C peut être déduite depuis A->B B->C (transitivité: règles d'amstrong )
F={A->D, A->B, B->C} c'est la couverture minimale de F.
cependant pour un autre exemple : (en fait c'est un exercice )
soit R=(A,B,C,D,E,F) une relation et H l'ensemble de DF définies sur R :
H={AB->CDF, C->ABF, F->GAE}
H peut s'écrire sous forme d'une ensemble de DF élémentaire :
H={AB->C, AB->D, AB->F, C->A, C->B, C->F, F->G, F->A, F->E}
je n'ai pas pu trouvez la couverture minimale de H
SVP j'ai besoin de votre aide.

[fsmrel]

Bonsoir,


La DF : AB -> F ne fait pas partie de la couverture minimale. En effet, de :

AB -> C
C -> F

par transitivité, AB - > F.


La DF : C -> A ne fait pas partie de la couverture minimale. En effet, de :

C -> F
F -> A

par transitivité, C -> A.

Comme D est dépendant dans la seule DF : AB -> D (et ne participe à aucun déterminant), celle-ci fait partie de la couverture minimale.

Comme E est dépendant dans la seule DF : F -> E (et ne participe à aucun déterminant), celle-ci fait partie de la couverture minimale.

Comme G est dépendant dans la seule DF : F -> G (et ne participe à aucun déterminant), celle-ci fait partie de la couverture minimale.

Reste à voir si les DF qui suivent font nécessairement partie de la couverture minimale :

AB -> C
C -> B
C -> F
F -> A.

A vous de jouer, bombardier Switch1, on ne va quand même tirer toutes les conclusions à votre place...

N.B. Il ya une autre couverture minimale.

En effet, de

C -> A
C -> B

par union, on a

C -> AB

et comme

AB -> F,

par transitivité,

C -> F.

[sisiniya]

Bonjour,

Complétant ce que fsmrel a dit ,

Prenons votre exemple :

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

Dans ce cas, vous essayez d'ignorer une DF comme par exemple AB->C de H, et vous cherchez si vous pouvez atteindre à C avec un autre chemin , en se basant cette fois-ci sur H - {AB->C} = {AB->D, AB->F, C->A, C->B, C->F, F->G, F->A, F->E} . dans le cas où on trouve un autre chemin , alors , on considère AB->C comme DF redondante, et du coup , elle n'appartient pas à la Couverture Minimal ( C.M )de H.

Ce sénario , est répété autant de fois que les nombre de DF dans Votre ensemble H.

En effet, la C.M n'est pas unique, vous pouvez trouvez plusieurs C.M pour la même ensemble H.


Bonne Chance Monsieur Swith1.


Sisiniya.

[switch1]

merci

[switch1]

merci de vos réponse .

AB -> C
C -> B
C -> F
F -> A.

A vous de jouer, bombardier Switch1, on ne va quand même tirer toutes les conclusions à votre place...

N.B. Il ya une autre couverture minimale.

En effet, de

C -> A
C -> B

par union, on a

C -> AB

et comme

AB -> F,

par transitivité,

C -> F.

bon ici vous avez utilise la DF C->F pour deduire que C->A et puis on a C->B
alors par union C->AB et finalement vous avez trouve que C->F
mais est ce qu'on peut supprime cette DF?
merci

[fsmrel]

ici vous avez utilise la DF C->F pour deduire que C->A et puis on a C->B
alors par union C->AB et finalement vous avez trouve que C->F
mais est ce qu'on peut supprime cette DF?

Si vous parlez de la 2e couverture minimale, je n’ai pas utilisé la DF C→F pour déduire que C→A et C→B, c’est exactement le contraire. En effet, parce que C→A et C→B, par union C→AB. Et comme AB→F, par transitivité C→F. Cette DF est inférable des autres et n’est pas primitive :

La DF C→F ne fait donc pas partie de la 2e couverture minimale.

Alternativement c’est parce que l’on a conservé la DF C→F pour la 1re couverture minimale que ce sont les DF AB→F et C→A qui ne sont plus primitives car inférables de C→F en association avec AB→C d’une part, et C→F en association avec F→A d’autre part :

Les DF AB→F et C→A ne font donc pas partie de la 1re couverture minimale, alors que la DF C→F en fait cette fois-ci partie.

[switch1]

merci beaucoup fsmrel.