【正文】 損連接分解 –保持函數(shù)依賴(lài) 2022年 1月 4日星期二 76 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 模式分解中存在的問(wèn)題 R(A, B, C) 1 2 2 2 1 1 C B A 2 2 1 1 B A 1 2 2 1 C B 1 2 2 2 1 1 C B A ∏ AB(R) ∏ BC(R) ∏ AB(R) ∏ BC(R) R(A, B, C) 2 1 2 1 1 1 C B A 1 2 1 1 B A 2 1 1 1 C B 2 1 1 1 1 2 2 1 2 1 1 1 C B A ∏ AB(R) ∏ BC(R) ∏ AB(R) ∏ BC(R) 有損分解 無(wú)損分解 2022年 1月 4日星期二 77 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 模式分解中存在的問(wèn)題 c1 b3 a4 c2 b2 a3 c1 b1 a2 c1 b1 a1 C B A {A ? B, B ? C} a4 a3 a2 a1 A b3 b2 b1 B c2 c1 C b3 a4 b3 a5 b2 a3 b1 a2 b1 a1 B A c1 a4 c3 a5 c2 a3 c1 a2 c1 a1 C A = c1 b3 a4 c3 b3 a5 c2 b2 a3 c1 b1 a2 c1 b1 a1 C B A 插入 違反 B ? C 2022年 1月 4日星期二 78 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 模式分解中存在的問(wèn)題 b3 a4 b2 a3 b1 a2 b1 a1 B A c1 b3 c2 b2 c1 b1 C B c1 a4 c2 a3 c1 a2 c1 a1 C A c1 b3 c2 b2 c1 b1 C B = = c1 b1 a4 c1 b3 a2 c1 b3 a1 c1 b3 a4 c2 b2 a3 c1 b1 a2 c1 b1 a1 C B A c1 b3 a4 c2 b2 a3 c1 b1 a2 c1 b1 a1 C B A 2022年 1月 4日星期二 79 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 無(wú)損連接分解 ?保持無(wú)損的模式分解 –有損分解的例子 R(A, B, C) 2 1 2 1 1 1 C B A 1 2 1 1 B A 2 1 1 1 C B 2 1 1 1 1 2 2 1 2 1 1 1 C B A ∏ AB(R) ∏ BC(R) ∏ AB(R) ∏ BC(R) 2022年 1月 4日星期二 80 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 無(wú)損連接分解 ?定義 關(guān)系模式 RU , F ， U = Ui ， ? = {R1U1 , F1 , R2U2 , F2, … , RnUn , Fn}是 RU , F的一個(gè)分解， r是 RU , F的一個(gè)關(guān)系定義 m?(r) = ∏ Ri(r) ,若對(duì)于RU , F的任一個(gè)關(guān)系 r， 都有 r = m?(r)，則稱(chēng) ?是 RU , F的一個(gè)無(wú)損連接分解。 – F+ = G+ ? F ? G+， G ? F+ 2022年 1月 4日星期二 63 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 正則覆蓋 ? 滿(mǎn)足下列條件的函數(shù)依賴(lài)集 F稱(chēng)為正則覆蓋，記作 Fc： – Fc 與 F 等價(jià) – Fc 中任何函數(shù)依賴(lài)都不含無(wú)關(guān)屬性 – Fc 中函數(shù)依賴(lài)的左半部都是唯一的 2022年 1月 4日星期二 64 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 無(wú)關(guān)屬性 ?如果去除一個(gè)函數(shù)依賴(lài)中的屬性，不會(huì)改變?cè)摵瘮?shù)依賴(lài)集的閉包，則稱(chēng)該屬性是無(wú)關(guān)的(extraneous) 2022年 1月 4日星期二 65 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 無(wú)關(guān)屬性 ?對(duì)于函數(shù)依賴(lài)集 F及 F中函數(shù)依賴(lài) α ?β – 屬性 A在 α 中是無(wú)關(guān)的，如果 A∈α ，并且 F├ ( F {α ?β})∪{(α A) ?β} – 屬性 A在 β 中是無(wú)關(guān)的，如果 A∈β ，并且 ( F {α ?β})∪{α ?(β A) } ├ F 2022年 1月 4日星期二 66 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 無(wú)關(guān)屬性 ?在 {AB ? C， A ? C}中 ?在 {AB ? CD， A ? C}中 ?B在 AB ? C中是無(wú)關(guān)屬性 ?C在 AB ? CD中是無(wú)關(guān)屬性 2022年 1月 4日星期二 67 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 檢驗(yàn)無(wú)關(guān)屬性的方法 ?考慮 α ?β 中的屬性 A – 如果 A? β ， F’= ( F {α ?β}∪{α ?(β A) } ,檢驗(yàn) α ?A是否能由 F’推出，即計(jì)算 F’下的 α +， 如果 α +包含 A， 則 A在 β 是無(wú)關(guān)的 – 如果 A? α ， 令 ? = α{A}， 并計(jì)算 ? ?β是否可以由 F推出，即計(jì)算在 F下的 ?+，如果 ?+包含 β 的所有屬性，則 A在 α 是無(wú)關(guān)的 2022年 1月 4日星期二 68 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 檢驗(yàn)無(wú)關(guān)屬性的方法 ? F={AB ? CD, A ? E, E ? C},C在 AB ? CD上是否是無(wú)關(guān)屬性？ ? F’={AB ? D, A ? E, E ? C}下 AB的屬性閉包為 {ABCDE}，包含 CD，因此 C在 AB ? CD上是無(wú)關(guān)屬性 2022年 1月 4日星期二 69 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 正則覆蓋 ?算法 —求函數(shù)依賴(lài)集 F的正則覆蓋 FC REPEAT 合并 α ?β 和 α ?γ 為 α ?βγ 找出在 α 、 β 中含 無(wú)關(guān)屬性的函數(shù)依賴(lài) α ?β 刪除 α ?β 中的無(wú)關(guān)屬性 UNTIL F 不再改變 注意：檢查無(wú)關(guān)屬性是在當(dāng)前 Fc中的函數(shù)依賴(lài)，而不是 F 不能同時(shí)討論 F中的兩個(gè)屬性的無(wú)關(guān)性，一次只能討論一個(gè)屬性 2022年 1月 4日星期二 70 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 正則覆蓋 ?如果一個(gè)函數(shù)依賴(lài)的右半部只包含一個(gè)屬性，例如， A ? C，并且右邊的屬性是無(wú)關(guān)的，那么將得到一個(gè)右部為空的函數(shù)依賴(lài)，這樣的函數(shù)依賴(lài)應(yīng)該刪除 ?從某種意義上說(shuō)， FC是最小的，它不含無(wú)關(guān)屬性，并且具有相同左半部的函數(shù)都已經(jīng)被合并，所以驗(yàn)證 FC比驗(yàn)證 F本身更容易 2022年 1月 4日星期二 71 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 正則覆蓋 ?示例 F = {A?BC， B?C， A?B， AB?C}，求 FC – 合并 A?BC， A?B為 A?BC – A在 AB?C中是無(wú)關(guān)的 – C在 A?BC中是無(wú)關(guān)的 因此 FC = {A?B， B?C} 2022年 1月 4日星期二 72 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 正則覆蓋 ?正則覆蓋未必唯一 ?示例 – F={A→ BC, B→ AC, C→ AB} Fc1={A→ B, B→ C, C→ A} Fc2={A→ B, B→ AC, C→ B} Fc3={A→ C, C→ B , B→ A} Fc4={A→ C, B→ C, C→ AB} 2022年 1月 4日星期二 73 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) amp。當(dāng)用戶(hù)對(duì)于關(guān)系進(jìn)行更新時(shí)，數(shù)據(jù)庫(kù)系統(tǒng)將保證此操作不會(huì)破壞任何一個(gè)函數(shù)依賴(lài) ?可以通過(guò)測(cè)試與給定函數(shù)依賴(lài)集有相同閉包的簡(jiǎn)化集的方式，來(lái)降低檢測(cè)的開(kāi)銷(xiāo) 2022年 1月 4日星期二 62 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 函數(shù)依賴(lài)集的等價(jià)和覆蓋 ?函數(shù)依賴(lài)集的等價(jià)性 – 函數(shù)依賴(lài)集 F， G，若 F+= G+，則稱(chēng) F與 G等價(jià)。 6) r滿(mǎn)足 F，不滿(mǎn)足 F+，矛盾； 假設(shè)不成立，證畢。 3)關(guān)系 r滿(mǎn)足 F： 如不然，算法不會(huì)結(jié)束。辦法之一是計(jì)算 F+ 2022年 1月 4日星期二 51 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 屬性集的閉包 ?屬性集的閉包 ?FX?FX設(shè) F為屬性集 U上的一組函數(shù)依賴(lài)， X ? U， = {A | X?A能由 F根據(jù) Armstrong公理導(dǎo)出 } 稱(chēng) 為屬性集 X關(guān)于函數(shù)依賴(lài)集 F的閉包 2022年 1月 4日星期二 52 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 屬性集的閉包 ?示例 屬性集 U={A， B， C}， 函數(shù) 依賴(lài)集 F={A ? B， B ? C} 則 A+ = ABC B+ = BC C+ = C 2022年 1月 4日星期二 53 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 判定 X?Y是否能由 F根據(jù) Armstrong公理導(dǎo)出，可轉(zhuǎn)化為求 ，判定 Y? 是否成立 閉包的計(jì)算 ?FX ?FX問(wèn)題：有沒(méi)有一般性的算法判定 X?Y是否能由 F根據(jù) Armstrong公理導(dǎo)出？ 如果計(jì)算出 F+，再判斷 X?Y是否屬于 F+，則由于 F+的計(jì)算非常復(fù)雜，實(shí)際上是不可行的 2022年 1月 4日星期二 54 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) ?FX?FX?FX?FX ?FX ?FX開(kāi)始 ： Input： X， F， U Output： := X。 2022年 1月 4日星期二 22 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) BCNF ? 判定：下列哪個(gè)模式是 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 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) BCNF ? BCNF的本質(zhì) – (在只考慮函數(shù)依賴(lài)的前提下 )只講一件事 – 非碼決定因素的相關(guān)決定關(guān)系講述了另外一件事 ? R1(sno,sname,dno,dname) F:sno→sname,dno dno→dname ? R1講述了“學(xué)生”和“院系”兩件事， R1(F)?BCNF – 有多個(gè)碼是一件事的不同方面 ,本質(zhì)仍是一件事 ? R3(sno,pid,sname,sage,dept) F:sno→pid,sname,sage,dept pid →sno ? R3有兩個(gè)碼，講述了 ”學(xué)生”一件事， R3(F)?BCNF ? 思考：所有的二元聯(lián)系都是 BCNF嗎？ 2022年 1月 4日星期二 24 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) ? 關(guān)系模式可以通過(guò)分解達(dá)到 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 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) ? 有些關(guān)系模式分解 BCNF會(huì)有問(wèn)題 ? 示例： – 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} 中不易驗(yàn)證 sno,o→tno ? 保持依賴(lài) – 通俗地說(shuō)，不依靠關(guān)系連接就能驗(yàn)證依賴(lài)關(guān)系，稱(chēng)保持依賴(lài) – 不是所有關(guān)系模式都能保持依賴(lài)地分解到 BCNF 教師 課程 講授 學(xué)生 上課 2022年 1月 4日星期二 26 數(shù)據(jù)庫(kù)系統(tǒng)概念 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì) 3NF定義 ?定義一： 對(duì) R(F),如果對(duì) ?α→β ?F+，必有 1)β?α 或者 2)α是超碼 或者 3) (βα)的每個(gè)屬性均包含在某一候選碼中 則稱(chēng)關(guān)系模式 R為 3N