[工學]第四章_數(shù)據(jù)依賴與關系模式規(guī)范化(編輯修改稿)
2024-11-09 18:19 本頁面
【文章內(nèi)容簡介】 ,I ?HG+(G=F{H→I}) ∴ 保留該函數(shù)依賴 I→H ∵I G+＝ I,H ? IG+(G=F{I→H}) ∴ 保留該函數(shù)依賴 H→B ∵H G+＝ HIE,B? HG+(G=F{H→B})∴ 保留該函數(shù)依賴 H→E ∵H G+＝ HBCDE,E∈H G+(G=F{H→E}) ∴ 不保留該函數(shù)依賴 最后剩下的 F是最小函數(shù)依賴集， Fmin= {A→B, B→C, B→E,C→D, H→I, I→H, H→B} 關系模式分解 關系模式分解 (1)表明經(jīng)過投影連接后得到的關系一定不會小于原有關系 (2)表明 r經(jīng)過投影連接得到的關系再次投影后的子關系與原有的 ri是相等的。 (3)表明了投影連接運算同樣是冪等的 關系模式分解 關系模式分解 算法 ：判別無損連接的模式分解 輸入：關系模式 R(U， F)， U＝ {A1， … ， An}， F是最小函數(shù)依賴集，R的一個分解 ＝ {R1， … ， Rm}； 輸出： YES/NO 步驟： (1)根據(jù) R及 ρ 構(gòu)造一個 m n的符號表 T，符號表每行對應一個子關系模式，每列對應 R上的一個屬性，符號表取值規(guī)則為： T[i， j]＝ ?????RiAjb ijRiAjaj 關系模式分解 步驟： (2)根據(jù) F對 T進行變換，逐個掃描 F中的函數(shù)依賴 Xi→Ai ，根據(jù)Xi→Ai 對 T進行變換，如果 T中存在不滿足該函數(shù)依賴的行（即在 Xi列上的取值相同，而在 Ai列上的取值不同），則修改這些行在 Ai屬性列上的取值，具體修改方法為：如果這些行中存在某行在 Ai列上的取值為 a，則將其它行在 Ai列上的取值也改為相同的 a，否則改為 i、j最小的 bij； 關系模式分解 步驟： (3)掃描一遍后檢驗 T是否發(fā)生變化，如果 T中已有全 ’ a’ 行或 T較之于上一遍掃描結(jié)果未發(fā)生變化，則掃描終止，如 T有變化且未出現(xiàn)全 ’ a’ 行，則返回 (2)； (4)算法終止時，若 T中有全 ’ a’ 行，則輸出 YES，否則輸出 NO 關系模式分解 例 R(A， B， C， D， E， G)， F＝ {AB→C ， B→D ，D→E ， B→G} 的一個分解 ＝ {R1(A， B， C)， R2(B， D)， R3(D， E， G)}是否是無損連接的。 解： (1)首先根據(jù) R構(gòu)造出符號表 T： T A B C D E G R1 R2 R3 a1 b21 b31 a2 a2 b32 a3 b23 b33 b14 a4 a4 b15 b25 a5 b16 b26 a6 關系模式分解 解： (2)根據(jù) F對 T進行變換： F＝ {AB→C ， B→D ， D→E ， B→G} AB→C 不改變 T， B→D 將 b14改為 a4， D→E 將 b1 b25改為 a5， B→G 將b26改為 b16， T A B C D E G R1 R2 R3 a1 b21 b31 a2 a2 b32 a3 b23 b33 b14 a4 a4 b15 b25 a5 b16 b26 a6 T A B C D E G R1 R2 R3 a1 b21 b31 a2 a2 b32 a3 b23 b33 a4 a4 a4 a5 a5 a5 b16 b16 a6 關系模式分解 定理 ：關系模式 R的一個分解 ＝ {R1(U1)， R2(U2)}無損連接的充分必要條件是 (U1∩U2)→(U1 － U2)∈F ＋ 或者 (U1∩U2)→(U2 － U1)∈F ＋ 。 關系模式分解 無損連接和保持函數(shù)依賴是模式分解時的兩個重要性質(zhì)，如果一個分解既是無損連接的，同時又保持函數(shù)依賴，那么這樣的分解將是一個非常理想的分解，既保證了關系的等價，又保證了函數(shù)依賴的等價。如果分解不能保證這兩個性質(zhì)同時滿足，那么分解至少應該是無損連接的。 關系模式規(guī)范化 算法 ：計算關系模式上的全部候選鍵 輸入：關系模式 R(U， F)，其中 F是最小覆蓋 輸出： R上的所有候選鍵 步驟： (1)首先將 R的全部屬性分為四類，分別是 C1：不在任何函數(shù)依賴
教學課件相關推薦
鄂ICP備17016276號-1