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