【正文】 sno,o→score } 分解 {R1(sno,dno),R2(sno,dname,o,score)} 判斷： R2是否屬于 BCNF? ? 算法復雜性分析： NP 2022年 1月 4日星期二 113 數據庫系統(tǒng)概念 關系數據庫設計 : BCNF分解算法 ?關系模式 R(F)分解為 BCNF的算法 result={R} 計算 F+ While result中存在不屬于 BCNF的模式 Ri do 對 α→β ?Fi,α+→ Ri?F+且 α∩β=?： 令 result:=(resultRi)∪ (Riβ)∪ (αβ) 2022年 1月 4日星期二 114 數據庫系統(tǒng)概念 關系數據庫設計 BCNF分解算法 思想 ? BCNF分解算法的思想 –如果 Ri(Fi)?BCNF, 必有 α→β ?Fi， αFi+ ≠ Ri， 且 α∩β=? 將 Ri分解為： (Riβ)和 (αβ) α β α β α β –對分解結果中不是 BCNF的子模式，循環(huán)進行上述分解，直到全部模式都屬于BCNF –注意： 必須要求 α∩β=? 2022年 1月 4日星期二 115 數據庫系統(tǒng)概念 關系數據庫設計 BCNF分解算法示例 ? BCNF分解示例： – R(sno,sname,dno,dname,o,score) f1:dno→dname f2:sno→sname,dno f3:sno,o→score – 分解結果： R1(dno,dname) R2(sno,sname,dno) R3(sno,o,score) ? 練習： – 請先使用 f2對 R進行分解 – 并分析分解的結果 f1:dno→dname f2:sno→sname,dno sno,sname,dno, dname,o,score dno,dname sno,sname,dno, o,score sno, o,score sno,sname,dno, 2022年 1月 4日星期二 116 數據庫系統(tǒng)概念 關系數據庫設計 BCNF分解算法分析 ? BCNF分解算法分析 – 算法一定可以結束 – 算法復雜性： NP – 分解算法無損 ? 當我們用 (Ri β)和 (αβ)代替模式 Ri時，保持依賴 α?β，而且 (Ri β) ∩(αβ)=α – 分解算法不能保證保持依賴 ? 上例中，首先使用 f1分解，保持依賴 ? 首先使用 f2分解，不保持依賴 – 有些模式 R(F),有無損、保持依賴的 BCNF分解，但分解算法找不出來，如： R(sno,tno,dno) F={sno→dno ； tno→dno} – 有些模式 R(F),沒有無損、保持依賴的 BCNF分解： R(sno,tno,o) F={tno→o ； sno,o→tno} 2022年 1月 4日星期二 117 數據庫系統(tǒng)概念 關系數據庫設計 BCNF分解算法示例 – 示例： U={S， SD， MN， C， G} F={S?SD， S?MN， SD?MN， (S,C)?G} ⒈ U1={S， SD} , F1={S?SD} U2={S, MN, C, G}, F2={S?MN, (S,C)?G} ⒉ U1 = {S, SD}, F1={S?SD} U2 = {S, MN}, F2={S?MN} U3 = {S, C, G}, F3 = {(S,C)?G} 2022年 1月 4日星期二 118 數據庫系統(tǒng)概念 關系數據庫設計 BCNF分解算法示例 – 示例 STC(SNO , TNO , CNO)， F={TNO ? CNO，（ SNO， TNO） ? CNO ， （ SNO， CNO）? TNO} 分解 R1（ TNO， CNO）， FR！ ={TNO ? CNO} R2（ TNO， SNO） 2022年 1月 4日星期二 119 數據庫系統(tǒng)概念 關系數據庫設計 3NF判定算法 ? 3NF判定算法 –按照 3NF的定義 –逐個檢查 F中是否有違背 3NF要求的函數依賴 ?判定算法時間復雜性： Np –判定一個屬性是否為主屬性無多項式算法 2022年 1月 4日星期二 120 數據庫系統(tǒng)概念 關系數據庫設計 3NF的分解算法 – 算法：（達到 3NF且保持函數依賴的分解） ⒈求 F的正則覆蓋 FC ⒉ 若有 X?A?FC ， 且 XA=U， 則算法終止 3. 對 FC中的每一個函數依賴 α→β ，如果沒有任意 Rj包含 αβ，則生成 Ri=αβ。即不能以集合、序列等作為屬性值 {C1， C2， C3} S1 C S C3 S1 C2 S1 C1 S1 C S 2022年 1月 4日星期二 101 數據庫系統(tǒng)概念 關系數據庫設計 2NF 關系模式 S(S , SN , SD , DEAN , C , G) ? 不良特性 –插入異常：如果學生沒有選課，關于他的個人信息及所在系的信息就無法插入 –刪除異常：如果刪除學生的選課信息，則有關他的個人信息及所在系的信息也隨之刪除 –更新異常：如果學生轉系，若他選修了 k門課，則需要修改 k次 –數據冗余：如果一個學生選修了 k門課，則有關他的所在系的信息重復 2022年 1月 4日星期二 102 數據庫系統(tǒng)概念 關系數據庫設計 2NF ?定義 –若 R?1NF， 且每個非主屬性完全依賴于碼，則稱 R?2NF –消除非主屬性對碼的部分依賴 如 S?2NF， 因為 ? ?? p? ?? p（ S， C） SN （ S， C） SD 2022年 1月 4日星期二 103 數據庫系統(tǒng)概念 關系數據庫設計 2NF ?改造 非主屬性有兩種，一種完全依賴于碼，一種部分依賴于碼。 關系實例 r,不滿足 α→β。但是，有時分解是保持依賴的，但是 F上的一個依賴不在分解后的任何一個關系上成立，也有可能是保持依賴的分解。amp。 r A1 A2 … Am B1 B2 … Bn 1 1 … 1 0 0 … 0 1 1 … 1 1 1 … 1 2022年 1月 4日星期二 56 數據庫系統(tǒng)概念 關系數據庫設計 閉包的計算 ?示例 1 R U, F , U = (A, B, C, G, H, I), F = {A?B, A?C, CG?H, CG?I, B?H},計算 所用依賴 A?B AGB A?C AGBC CG?H AGBCH CG?I AGBCH I = AGBCH I ?FAG )(?FAG )(?FAG )(2022年 1月 4日星期二 57 數據庫系統(tǒng)概念 關系數據庫設計 ?示例 2 R U, F , U = (A, B, C, D, E), F = {AB?C, B?D, C?E, CE?B, AC?B},計算 所用依賴 AB?C ABC B?D ABCD C?E ABCDE = ABCDE 閉包的計算 ?FAB )(?FAB )(?FAB )(2022年 1月 4日星期二 58 數據庫系統(tǒng)概念 關系數據庫設計 閉包的計算 ?示例 3 R U, F , U = (A, B, C, D, E, G), F = {A?E, BE?AG, CE?A, G?D},計算 所用依賴 A?E ABE BE?AG ABEG G?D ABEGD = ABEGD ?FAB )(?FAB )(?FAB )(2022年 1月 4日星期二 59 數據庫系統(tǒng)概念 關系數據庫設計 閉包的計算 ?練習 R U, F , U = (C, T, H, R, S), F = {C?T, HR?C, HT?R, HS?R}， HR是碼嗎？ HS呢？ 2022年 1月 4日星期二 60 數據庫系統(tǒng)概念 關系數據庫設計 屬性集的閉包 ?算法作用： 判斷屬性集是否為超碼 通過檢驗 β ? α+是否成立，可以驗證函數依賴 α ? β是否成立 是另一種計算 F+的方法：對任意的屬性集 γ，找出 γ+ ，對于任意的屬性集 S ? γ+ ，得到 γ ?S 2022年 1月 4日星期二 61 數據庫系統(tǒng)概念 關系數據庫設計 (Canonical Cover) ?假設在一個關系模式上有一個函數依賴集 F。 while ( 發(fā)生變化） do for each 函數依賴 A?B in F do begin if A ? then := ?B end 閉包的計算 ?算法（求屬性集的閉包） 2022年 1月 4日星期二 55 數據庫系統(tǒng)概念 關系數據庫設計 計算 α+ ：算法正確性證明 ? 證明：算法結束時， result= α+(即 Armstrong 公理完備性 ) 證明： 0)記算法結束時， result=A1A2…A m， Rresult=B1B2…B n 1)反證法；假設 result≠ α+,必有 result?α+，即： 必存在屬性 (不妨設該屬性為 B1) ： B1?α+,B1?result； 2)構造如圖所示關系 r。 ? 定義三： – 決定因素必含碼 ? 每個關系模式都屬 BCNF，則 DB為 BCNF。 2022年 1月 4日星期二 22 數據庫系統(tǒng)概念 關系數據庫設計 BCNF ? 判定：下列哪個模式是 BCNF? – R1(sno,sname,dno,dname) sno→sname,dno dno→dname – R2(sno,sname,o,score) sno→sname sno,o→score – R3(sno,pid,sname,sage,dept) sno→ pid,sname,sage,dept pid → sno – R4(sno,tno,o) //F= ? – R5(sno,tno,o) tno→o sno,o→tno 2022年 1月 4日星期二 23 數據庫系統(tǒng)概念 關系數據庫設計 BCNF ? BCNF的本質 – (在只考慮函數依賴的前提下 )只講一件事 – 非碼決定因素的相關決定關系講述了另外一件事 ? R1(sno,sname,dno,dname) F:sno→sname,dno dno→dname ? R1講述了“學生”和“院系”兩件事， R1(F)?BCNF – 有多個碼是一件事的不同方面 ,本質仍是一件事 ? R3(sno,pid,sname,sage,dept) F:sno→pid,sname,sage,dept pid →sno ? R3有兩個碼，講述了 ”學生”一件事， R3(F)?BCNF ? 思考：所有的二元聯系都是 BCNF嗎？ 2022年 1月 4日星期二 24 數據庫系統(tǒng)概念 關系數據庫設計 ? 關系模式可以通過分解達到 BCNF ? 示例： – R(sno,sname,dno,dname) F:sno→sname,dno dno→dname – R(F)?BCNF – 分解 R為 {R1,R2} R1(sno,sname,dno) F1={sno→sname,dno} R2(dno,dname) F2={dno→dname } – {R1,R2} ? BCNF – 分解效果良好 2022年 1月 4日星期二 25 數據庫系統(tǒng)概念 關系數據庫設計 ? 有些關系模式分解 BCNF會有問題 ? 示例： – R(sno,tno,o) tno→o sno,o→tno – R(F)?BCNF – 分解 R為 {R1,R2} R1(sno,tno) F1= ? R2(tno,o) F2={tno→o} – {R1,R2} ? BCNF – {R1,R2} 中不易驗證 sno,o→tno ? 保持依賴 – 通俗地說，不依靠關系連接就能驗證依賴關系，稱保持依賴 – 不是所有關系模式都能保持依賴地分解到 BCNF 教師 課程 講授