天天看點

【資料庫】極小函數依賴集/最小依賴集/最小覆寫 定義+求解方法+執行個體

小聲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,是以不是最小依賴集