求最小依赖集

这个比较烦，要写好多好多好多QAQ。

例：U=(A,B,C,D,E,G)   F={BG->C,BD->E,DG->C,ADG->BC,AG->B,B->D}，求F最小依赖集。

解：

第一步：右边单一化。

F1={BG->C,BD->E,DG->C,ADG->B,ADG->C,AG->B,B->D}

第二步：逐个求，在去掉它的F中求闭包，如果包含右边属性，则表示这个函数依赖要去掉。

BG->C：求(BG)⁺=BCDEG，包含右边属性C，所以去掉。

BD->E：(BD)⁺=BD，不包含右边E，所以不用去掉。

DG->C：(DG)⁺=DG，也不用去掉。

ADG->B：(ADG)⁺=U，包含B，所以去掉。

ADG->C：(ADG)⁺包含C，去掉。(在这里，求闭包的时候，不能再用前面去掉的函数依赖了，所以如果从后往前判断，可能不用去掉ADG->B，所以最小依赖集不唯一，写出一个即可。)

AG->B：(AG)⁺=AG，不用去掉。

B->D：(B)⁺=B，不用去掉。

所以F2={BD->E,DG->C,AG->B,B->D}

第三步：对左边属性单一化，判断冗余，代替。

BD->E：B->E，求(B)⁺=BD，包含D，所以D冗余。

              D->E，求(D)⁺=D，所以B不冗余。

              所以用B->E代替BD->E。

DG->C：D->C，(D)⁺=D，所以G不冗余。

               G->C，(G)⁺=G，所以D不冗余。

AG->B：A->B，(A)⁺=A，所以G不冗余。

              G->B，(G)⁺=G，所以A不冗余。

所以Fm={B->E,DG->C,AG->B,B->D}。

版权声明：本文为博主原创文章，未经博主允许不得转载。