【正文】 則稱 R?3NF – 關(guān)系模式 R U , F 中，對(duì)于屬性組 X， Y，若 X?Y且 Y X時(shí)至少有以下之一成立：① X必含有碼② YX的每一個(gè)屬性 A都包含在 R的候選碼中，則稱 R?3NF ??2022年 1月 4日星期二 106 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) 3NF ?消除非主屬性對(duì)碼的傳遞依賴 如 S_SD ?3NF， 因?yàn)橛?S?SD， SD?DEAN ?改造 將 S_SD分解為 STUDENT(S , SN , SD) DEPT(SD , DEAN) 2022年 1月 4日星期二 107 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) BCNF ?示例 STC(S , T , C)， T ? C， 每位老師只教授一門課 （ S， T） ? C （ S， C） ? T， 學(xué)生選定一門課，就對(duì)應(yīng)一位老師 （ S， T），（ S， C） 為候選碼。 ?思考 STC ? 3NF ？ 2022年 1月 4日星期二 108 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) BCNF ?不良特性 – 插入異常：如果沒有學(xué)生選修某位老師的任課，則該老師擔(dān)任課程的信息就無法插入 – 刪除異常：刪除學(xué)生選課信息，會(huì)刪除掉老師的任課信息 – 更新異常：如果老師所教授的課程有所改動(dòng)，則所有選修該老師課程的學(xué)生元組都要做改動(dòng) – 數(shù)據(jù)冗余：每位學(xué)生都存儲(chǔ)了有關(guān)老師所教授的課程的信息 ? 癥由： 主屬性對(duì)碼的不良依賴 2022年 1月 4日星期二 109 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) BCNF ?定義 – 關(guān)系模式 R U , F 中，對(duì)于屬性組 X， Y，若 X?Y且 Y X時(shí) X必含有碼，則 R U , F ?BCNF 如 SPC ? BCNF， 因?yàn)?T ? C， 而 T不含有碼 ?改造 將 S分解為（ S， T），（ T， C） ?2022年 1月 4日星期二 110 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) BCNF ?思考 (S , C , ORDER)， 表示學(xué)生選修課程的名次，有函數(shù)依賴 (S， C)? ORDER， (C，ORDER) ? S， 它屬于 BCNF嗎？ ?全碼屬于 BCNF嗎？ 2022年 1月 4日星期二 111 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) BCNF的判定 ? 模式 R(F)是否為 BCNF的判定算法 – 對(duì)所有 α→β ?F，判定下述條件是否成立： ? β?α 或者 ? α為超碼 (即 α+=R) – 如果對(duì) ?α→β ?F， ? 上述判定均成立，則 R(F) ?BCNF ? 否則， R(F)?BCNF ? 注意： – 判定算法只檢查 F中 (不是 F+中 )的函數(shù)依賴 – 可以證明，只檢查 F中函數(shù)依賴是正確的 ? 算法復(fù)雜性分析： Polynomial 2022年 1月 4日星期二 112 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) 子模式 BCNF的判定 ? 子模式 Ri 是否為 BCNF的判定 – 即： {R1,R2,…R n}是 R(F)的分解， Ri是否為 BCNF的判定 – 需要對(duì)所有 α→β ?Fi： 檢查 α→β 是否使 Ri違背 BCNF定義 ? 注意： – 判定 Ri是否為 BCNF， 不能只檢查 F中相關(guān)函數(shù)依賴 – 必須對(duì) Fi中所有函數(shù)依賴進(jìn)行檢查 – 示例： R(sno,dno,dname,o,score) F={sno→dno。dno→dname。sno,o→score } 分解 {R1(sno,dno),R2(sno,dname,o,score)} 判斷： R2是否屬于 BCNF? ? 算法復(fù)雜性分析： NP 2022年 1月 4日星期二 113 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) : BCNF分解算法 ?關(guān)系模式 R(F)分解為 BCNF的算法 result={R} 計(jì)算 F+ While result中存在不屬于 BCNF的模式 Ri do 對(duì) α→β ?Fi,α+→ Ri?F+且 α∩β=?： 令 result:=(resultRi)∪ (Riβ)∪ (αβ) 2022年 1月 4日星期二 114 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) BCNF分解算法 思想 ? BCNF分解算法的思想 –如果 Ri(Fi)?BCNF, 必有 α→β ?Fi， αFi+ ≠ Ri， 且 α∩β=? 將 Ri分解為： (Riβ)和 (αβ) α β α β α β –對(duì)分解結(jié)果中不是 BCNF的子模式，循環(huán)進(jìn)行上述分解，直到全部模式都屬于BCNF –注意： 必須要求 α∩β=? 2022年 1月 4日星期二 115 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) BCNF分解算法示例 ? BCNF分解示例： – R(sno,sname,dno,dname,o,score) f1:dno→dname f2:sno→sname,dno f3:sno,o→score – 分解結(jié)果： R1(dno,dname) R2(sno,sname,dno) R3(sno,o,score) ? 練習(xí)： – 請(qǐng)先使用 f2對(duì) R進(jìn)行分解 – 并分析分解的結(jié)果 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 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) BCNF分解算法分析 ? BCNF分解算法分析 – 算法一定可以結(jié)束 – 算法復(fù)雜性： NP – 分解算法無損 ? 當(dāng)我們用 (Ri β)和 (αβ)代替模式 Ri時(shí)，保持依賴 α?β，而且 (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 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) 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 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) 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 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) 3NF判定算法 ? 3NF判定算法 –按照 3NF的定義 –逐個(gè)檢查 F中是否有違背 3NF要求的函數(shù)依賴 ?判定算法時(shí)間復(fù)雜性： Np –判定一個(gè)屬性是否為主屬性無多項(xiàng)式算法 2022年 1月 4日星期二 120 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) 3NF的分解算法 – 算法：（達(dá)到 3NF且保持函數(shù)依賴的分解） ⒈求 F的正則覆蓋 FC ⒉ 若有 X?A?FC ， 且 XA=U， 則算法終止 3. 對(duì) FC中的每一個(gè)函數(shù)依賴 α→β ，如果沒有任意 Rj包含 αβ，則生成 Ri=αβ。 設(shè) Ri的屬性全體為Ui， 令 Fi為 FC在 Ui上的投影，則 ? = {R1U1 , F1 , R2U2, F2 , … , RkUk , Fk}是 RU , F的一個(gè)保持函數(shù)依賴的分解，并且每個(gè)RiUi , Fi ?3NF 2022年 1月 4日星期二 121 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) 3NF的分解算法 – 示例 U={S， SD， MN， C， G} F={S?SD， S?MN， SD?MN，(S,C)?G} ⒈ FC={S?SD， SD?MN ， (S,C)?G} ⒉ 分組 {(S， SD)， S?SD} {(SD， MN)， SD?MN} {(S， C， G)， (S,C)?G} 2022年 1月 4日星期二 122 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) 3NF的分解算法 – 示例： R（ ABC； A?C， B?C） ⒈ 按保持無損連接分解 碼為 AB， 分解為 {AC； A?C}， {AB}。 丟失了函數(shù)依賴 B?C ⒉ 按保持函數(shù)依賴分解 進(jìn)行分組， {AC； A?C}， {BC； B?C} 分解是有損的 1 2 2 1 1 2 1 1 1 C B A 1 2 1 1 C A 1 2 1 1 C B 1 1 1 1 2 2 1 1 2 1 2 1 C B A 2022年 1月 4日星期二 123 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) 3NF的分解算法 – 算法：（達(dá)到 3NF且同時(shí)保持無損連接與函數(shù)依賴的分解） 設(shè) ? = {R1U1 , F1 , … , RkUk , Fk}是RU , F的一個(gè)保持函數(shù)依賴的 3NF分解 設(shè) X為 RU , F的碼， 若有某個(gè) Ui， X ? Ui， 則 ?即為所求， 否則令 τ = ?∪{R ? X， FX}， τ 即為所求 2022年 1月 4日星期二 124 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) 3NF分解算法示例 ? 算法示例： – R(sno,sname,o,ame,tno,bno,bname) f1:sno→sname f2:o→ame f3:sno,sname,o→tno, ame f4:tno→o f5:bno→bname – Step1: 計(jì)算 Fc – Step2:對(duì)每一 α→β ?Fc ，構(gòu)造關(guān)系 (α→β) R1(sno,sname) R4(tno,o) R2(o,ame) R5(bno,bname) R3(sno,tno,o) – Step3:如果構(gòu)造的模式都不含 R的碼，選一個(gè)候選碼構(gòu)造關(guān)系： 選候選碼構(gòu)造關(guān)系 R6(sno,o,bno) – {R1,R2,R3,R5,R6}是 R(F)的 3NF分解 2022年 1月 4日星期二 125 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) 3NF分解算法要注意的問題 ? 3NF分解算法要注意的問題： – Step2必須是對(duì) Fc中的函數(shù)依賴構(gòu)造關(guān)系 (不能是 F中函數(shù)依賴 ) 如果對(duì) F中函數(shù)依賴構(gòu)造關(guān)系， R3=(sno,sname,tno,o,ame) ?3NF –必須進(jìn)行 Step3的檢查并在必要時(shí)構(gòu)造候選碼關(guān)系模式 否則，分解不是無損分解 上例中， {R1,R2,R3,R5}是有損分解 2022年 1月 4日星期二 126 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) 3NF分解算法證明 ? 證明：分解算法是無損、保持依賴的 3NF分解算法 證明：結(jié)果模式集合是 R(F)的分解 (任何沒有出現(xiàn)在 Fc中的屬性，必屬于 R(F)的每一個(gè)候選碼 ) 證明：分解保持依賴 (Fc中每一個(gè)依賴構(gòu)造一個(gè)模式，必然保持 Fc，即保持依賴 ) 證明：分解無損 分解保持依賴 ,且至少一個(gè)子模式含 R的候選碼，則無損 (定理 ) (?t’?r’,必有 t?r(t[.]=t’[.],可以證明 t=t’,即 t’?r) 證明：對(duì) α→β ?Fc ，構(gòu)造的關(guān)系 Ri(αβ)，必有 Ri ?3NF (如果 Ri ? 3NF，則 α→β 有無關(guān)屬性，與 α→β ?Fc矛盾 ) 證明：如果針對(duì) R的一個(gè)候選碼，構(gòu)造了關(guān)系 Rn,則 Rn?3NF (候選碼構(gòu)造的關(guān)系 Rn,Fn中沒有非平凡的函數(shù)依賴 ) 2022年 1月 4日星期二 127 數(shù)據(jù)庫系統(tǒng)概念 關(guān)系數(shù)據(jù)庫設(shè)計(jì) 算法正確性分析（結(jié)果模式集合是