小聲bb:如果裡面有錯的地方請提出來~感激不盡XDDDD
一、定義
如果函數依賴集F滿足下列條件,則稱F為一個極小函數依賴集
,亦稱為最小依賴集或最小覆寫(minimal cover)。
(1)F中任一函數依賴的右部僅含有一個屬性
(2)F中不存在這樣的函數依賴X->A,使得F與F-{X->A}等價。
(3)F中不存在這樣的函數依賴X->A,X有真子集Z使得F-{X->A}∪{Z->A}與F等價。
最小依賴集不是唯一的,它與對各函數依賴
及X->A中X各屬性的處置順序有關。
二、分析(求解方法)
對于條件(1),即将比如X->YZ,分解為X->Y和X->Z。
(對于條件2和3為了便于了解我寫出了簡便的了解方式,大家可以通過舉F和F-某個依賴集來驗證以加深了解)
對于條件(2),說明
中不能有多餘的函數依賴,此處多餘即為可以通過推導得到:比如F{A->B,B->C,A->C},則A->C為多餘的。但是
可以是{A->B,B->C,C->A},即把這個函數依賴删去後剩下的F`與F不能相同。
對于條件(3),有兩種情況(因為
不唯一,但這兩種情況不能同時寫在一個
中),即把這個能互推的函數依賴删去後剩下的F`與F不能相同。:
1.
中不存在可以互相依賴的,比如F{A->B,B->A},則其中一個為多餘的,删去其中一個。
2.條件中為“真子集”,真子集不包含它本身,則
可以是{A->B,B->A}。
三、執行個體
【執行個體1:求最小依賴集】
問題:已知F={A->B,B->A,B->C,A->C,C->A},求
。
解答:
1.看條件(1):F函數依賴的右部都隻含有一個屬性,滿足條件(1);
2.結合條件(2)和(3):
F中有 A->B,B->C,A->C,删去A->C,得
={A->B,B->A,B->C,C->A}
删去B->A得
={A->B,B->C,C->A};
留下所有可以互相推導的
={A->B,B->A,A->C,C->A}
【執行個體2:判斷最小依賴集】
問題:U={A,B,C,D,E},判斷
={A->B,B->C,(A,D)->E},
={A->B,A->C,B->C,(A,D)->E,(A,B)->B}是否是最小依賴集。
解答:直接可以判斷出
是最小依賴集,
中有A->B,A->C,B->C,是以不是最小依賴集