怎麼求最小函數依賴集？

01-15

關係模式R(U，F)中，U=ABCDEG，F={B-&>D，DG-&>C,BD-&>E,AG-&>B,ADG-&>BC}
求F的最小函數依賴集

步驟：

① 用分解的法則，使F中的任何一個函數依賴的右部僅含有一個屬性；

② 去掉多餘的函數依賴：從第一個函數依賴X→Y開始將其從F中去掉，然後在剩下的函數依賴中求X的閉包X+，看X+是否包含Y，若是，則去掉X→Y；否則不能去掉，依次做下去。直到找不到冗餘的函數依賴；

③去掉各依賴左部多餘的屬性。一個一個地檢查函數依賴左部非單個屬性的依賴。例如XY→A，若要判Y為多餘的，則以X→A代替XY→A是否等價？若A屬於(X)+，則Y是多餘屬性，可以去掉。

解：

(1)判斷右邊是否最簡，得F={B-&>D，DG-&>C,BD-&>E,AG-&>B,ADG-&>B,ADG-&>C}

(2)

①假設B-&>D冗餘，則去掉B-&>D，得:G={DG-&>C,BD-&>E,AG-&>B,ADG-&>B,ADG-&>C}

B+ =B 不包含D，所以不冗餘，不能去掉。

②假設DG-&>C冗餘，則去掉DG-&>C，得:G={B-&>D,BD-&>E,AG-&>B,ADG-&>B,ADG-&>C}

(DG)+ =DG不包含C，所以不冗餘，不能去掉。

③假設BD-&>E冗餘，則去掉BD-&>E，得:G={B-&>D，DG-&>C,AG-&>B,ADG-&>B,ADG-&>C}

(BD)+ =BD不包含E，所以不冗餘，不能去掉。

④假設AG-&>B冗餘，則去掉AG-&>B，得:G={B-&>D，DG-&>C,BD-&>E,ADG-&>B,ADG-&>C}

(AG)+ =AG不包含B，所以不冗餘，不能去掉。

⑤假設ADG-&>B冗餘，則去掉ADG-&>B，得:G={B-&>D，DG-&>C,BD-&>E,AG-&>B,ADG-&>C}

(ADG)+ =ABCDEG包含B，所以冗餘，去掉。

⑥假設ADG-&>C冗餘，則去掉ADG-&>C，得:G={B-&>D，DG-&>C,BD-&>E,AG-&>B}

(ADG)+ =ABCDEG包含C，所以冗餘，去掉。

綜上:F={B-&>D，DG-&>C,BD-&>E,AG-&>B}

(3)①假設D-&>C冗餘，D+ =D不包含C,所以G不能去掉。

②假設G-&>C冗餘，G+ =G不包含C,所以D不能去掉。

③假設B-&>E冗餘，B+ =BD不包含E,所以D不能去掉。

④假設D-&>E冗餘，D+ =D不包含E,所以B不能去掉。

⑤假設A-&>B冗餘，A+ =A不包含B,所以G不能去掉。

⑥假設G-&>B冗餘，G+ =G不包含B,所以A不能去掉。

所以，Fm={B-&>D，DG-&>C,BD-&>E,AG-&>B}

期末複習看到了這種類型題已經解決，方法如下：

1.根據分解規則，將函數依賴的右端分解成單個屬性

該題目的話要將：BC分解成單個屬性。

F={ADG-&>B,ADG-&>C,······}

2.對於F中的每個函數X-&>A,設G=F-{X-&>A},如果A屬於X的閉包，則將X-&>A從中刪除，否則保留。

該題目：

1)G=F-{B-&>D},則B的閉包={B},包不含D,則保留

2)G=F-{DG-&>C},則DG的閉包={DG},不包含C,則保留

3)G=F-{BD-&>E},則BD的閉包={BD},不包含E,則保留

4)G=F-{AG-&>B},則AG的閉包={AG},不包含B,則保留

5)G=F-{ADG-&>B},則ADG的閉包={ADGBCE},包含B,則刪除

6)G=F-{ADG-&>C},則ADG的閉包={ADGBCE},包含C,則刪除

F={B-&>D,DG-&>C,BD-&>E,AG-&>B}

3.對於F中每一個左端包含多個屬性的X-&>A，選擇X的每個子集Z,如果A屬於Z的閉包,則用Z-&>A代替X-&>A

該題目：左端包含多個屬性的函數依賴有DG-&>C,BD-&>E,AG-&>B;

1)DG-&>C的左端子集包含{D}和{G}

D的閉包={D},D的閉包不包含C

G的閉包={G},G的閉包不包含C

F={B-&>D,DG-&>C,BD-&>E,AG-&>B}

2)BD-&>E的左端子集包含{B}和{D}

B的閉包={B},B的閉包不包含E

D的閉包={DC},D的閉包不包含E

F={B-&>D,DG-&>C,BD-&>E,AG-&>B}

3)AG-&>B的左端自己包含{A}{G}

A的閉包={A},A的閉包不包含B

G的閉包={G},G的閉包不包含B

F={B-&>D,DG-&>C,BD-&>E,AG-&>B}

所以，綜上Fm={B-&>D,DG-&>C,BD-&>E,AG-&>B}

樓上都說的很好，就是一個求對的都沒有（笑）

結果不是f=｛b-＞d，dg-＞c，b-＞e，ag-＞b｝么(?? . ??)

在看了大家的回答和評論區的討論之後，感覺似乎仍然存在一些疑問，我個人也正在學習相關內容，嘗試回答一下，下面引用的是我所使用的教材的截圖。

新編資料庫原理習題與解析李春葆

(1) 單一化：F={B-&>D，DG-&>C，BD-&>E，AG-&>B，ADG-&>B，ADG-&>C}

(2) 去掉左邊多餘屬性，如圖所示，只針對非單屬性

DG-&>C：判斷D (G)+ = G 保留；判斷G (D)+ = D 保留；
BD-&>E：判斷B (D)+ = D 保留；判斷D (B)+ = BD 由 B-&>E代替；
AG-&>B：判斷A (G)+ = G 保留；判斷G (A)+ = A 保留；
ADG-&>B：判斷A (DG)+ = DGC 保留；判斷D (AG)+ = AGB 由 AG-&>B代替；
ADG-&>C：判斷A (DG)+ = DGC 由DG-&>C代替；

所以結果是 F={B-&>D，DG-&>C，B-&>E，AG-&>B，AG-&>B，DG-&>C}

(3) F={B-&>D，DG-&>C，B-&>E，AG-&>B}

(B)+ = BE：B-&>D保留
(DG)+ = DG：DG-&>C保留
(B)+ = BD ：B-&>E保留
(AG)+ = AG ：AG-&>B保留

所以 F={B-&>D，DG-&>C，B-&>E，AG-&>B}

第二步之所以這樣做的原因而沒有直接閉包是因為書上的例題

已知F={AB-&>C，C-&>A，BC-&>D，ACD-&>B，D-&>EG，BE-&>C，CG-&>BD，CE-&>AG}
在這個題目處理的第二步中，按照直接求閉包法的話
ACD-&>B，(ACD)+ =ACDEGB，所以刪除
但答案中給的是因為(CD)+ =ACDEGB，所以使用CD-&>B代替，ACD-&>B
再加上CE-&>A被C-&>A代替所以結果是
F={AB-&>C，C-&>A，BC-&>D，CD-&>B，D-&>E，D-&>G，BE-&>C，CG-&>B，CG-&>D，CE-&>G}

最終因為(CG)+ =ABCDEG，刪除CG-&>B
最小依賴為
F={AB-&>C，C-&>A，BC-&>D，CD-&>B，D-&>E，D-&>G，BE-&>C，CG-&>D，CE-&>G}

我其實也不是特別明白究竟怎麼做是對的，但我又覺得書在這種問題上應該不至於有錯吧，第一次認真答題，歡迎大家指正。

#COMP9311

#cuo le wo zhi bo chi xiang!

The minimal cover is

Fmin={B-&>D, B-&>E, AG-&>B,G-&>C}

To get the minimal cover, you have to make third steps. To demonstrate, I"ll first split the dependencies into multiple (only one attribute on the right side) to make it more clean.

Note that there might be more than one correct result, it depends on the order in which you do the reduction.

When you do the second step, which is about reducing the left reduction, you can"t delete the value immediately ,when the whole step has been finished, complete the deletion .You can use the full dep. you are currently reducing, this is sometimes confusing at first, but if you think about it, it will become clear that you can do that.

After this step, we get:

F"={B-&>D, DG-&>C,B-&>E, AG-&>B, AG-&>B,G-&>C}

It could be argued that you can (obviously) remove one of the duplicate rules AG-&>B, but strictly speaking, you can use the algorithm also. Hide only one of the two same rules, then take the left side , and use the other to deduce the right side. Therefore you can remove AG-&>B(only once of course

When you do the third step. Now for each rule, try to remove it, and see if you deduce the same rule by only using others. In this step you, of course, cannot use the dep. you"re currently trying to remove (you could in the previous step). when you find one can remove, you must remove it immediately,because it can influence other reductions.

Finally,the result is:

Fmin={B-&>D, B-&>E, AG-&>B,G-&>C}