山東大學數(shù)據(jù)庫07數(shù)據(jù)庫設計.ppt

《山東大學數(shù)據(jù)庫07數(shù)據(jù)庫設計.ppt》由會員分享，可在線閱讀，更多相關《山東大學數(shù)據(jù)庫07數(shù)據(jù)庫設計.ppt（180頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、DATABASE SYSTEM CONCEPTS,第七章 關系數(shù)據(jù)庫設計,提綱,7.1好的關系設計的特點 7.2原子域和第一范式 7.3使用函數(shù)依賴的分解 7.4函數(shù)依賴理論 7.5分解的算法 7.6使用多值依賴的分解 7.7更多的范式 7.8數(shù)據(jù)庫設計過程 7.9時態(tài)數(shù)據(jù)建模,2020年9月12日星期六,2,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,2020年9月12日星期六,3,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,第七章 關系數(shù)據(jù)庫設計,RDB設計工程方法的代表：E-R圖方法 繪制E-R E-RRDB模式 模式優(yōu)化 RDB設計工程方法的問題 E-R質量和分析員能力水平相關 E-R質量難以保證

2、，致使E-R方法設計質量難以保證 其它RDB模式工程設計方法存在類似問題 質量保證 質量保證vs高質量 工程方法質量保證困難，受工程人員能力影響大 質量保證常用方法：機械化、形式化,2020年9月12日星期六,4,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,第七章 關系數(shù)據(jù)庫設計,關系模式規(guī)范化研究的背景 為提高RDB設計質量保證，國外學者探尋和研究形式化的RDB設計方法 提出和完善了：關系模式規(guī)范化理論和方法 希望按照規(guī)范化理論和方法， 能夠進行有質量保證的RDB設計 關系模式規(guī)范化的基本思路 泛關系Universal Relation 數(shù)據(jù)間的約束 按照機械算法，得到“好”的關系模式,2020年

3、9月12日星期六,5,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,第七章 關系模式規(guī)范化理論和方法,模式規(guī)范化方法的研究狀況 提出了模式規(guī)范化的標準： 1NF,2NF,3NF,BCNF,4NF,5NF,6NF 給出了泛關系分解到具體范式的算法 算法多為Np算法，無法實際執(zhí)行 規(guī)范化方法學習價值 理解不同范式的優(yōu)缺點 理解相應的模式改進方法 作為重要指導思想指導模式設計 本章講述關系模式規(guī)范化理論、方法,2020年9月12日星期六,6,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.1好的關系設計,本節(jié)初步探討好關系模式的特點 分析大模式的優(yōu)缺點 分析小模式的優(yōu)缺點,2020年9月12日星期六,7,數(shù)據(jù)庫系

4、統(tǒng)概念----關系數(shù)據(jù)庫設計,7.1.1大關系模式分析,大模式示例： R(sno,sname,dno,dname) 大模式的缺點： 數(shù)據(jù)冗余大 容易出現(xiàn)數(shù)據(jù)不一致 插入異常-不能表示某些信息：沒有學生的院系 刪除異常 問題的本質： 兩件事不應使用一個表來表示 應該將這個模式分解為兩個模式 分解必須按照一定的策略，無序分解不可接受,2020年9月12日星期六,8,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.1 小關系模式分析,小模式 小模式不一定是好的模式 SC(sno,cno) TC(tno,cno) TS(tno,sno) 上述表不能表示上課(STC)信息 簡單地模式變小不是追求目標,2020

5、年9月12日星期六,9,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.1好的關系特點,大關系模式、小關系模式都有問題 好的關系模式： 該大則大，該小則小 同數(shù)據(jù)本質結構相吻合 不必存儲不必要的重復信息，同時又可以方便地獲取信息 如何得到好的關系模式？ 方法1：工程化方法 方法2：模式規(guī)范化 本章重點研究模式規(guī)范化方法,2020年9月12日星期六,10,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.2原子域和第一范式,原子域 域元素被認為是不可分的單元，稱域是原子的 域原子性分析示例： 學號域2001CS621, 學號的編碼規(guī)則決定了學號可以分段解釋 (這是數(shù)據(jù)的客觀特點，不能改變) 學號域是原子的嗎？

6、 如果需要DBMS分段解釋學號含義，則學號域不是原子域 否則，學號域是原子域,2020年9月12日星期六,11,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.2原子域和第一范式,1NF 如果關系模式R所有屬性都源自原子域，稱模式屬于1NF 記作：R1NF 違背1NF的模式示例 存在屬性不是原子的 R(SNO,SNAME,ADDR(CITY,STREET)) 經(jīng)典RDBMS中，不會出現(xiàn)如上非原子屬性 存在某屬性來自非原子域 如R(SNO,SNAME)，SNO源于學號域 學號域2001CS621需要DBMS分段解釋值的含義 達不到1NF的缺點 不符合關系理論 編程困難 關系的規(guī)范化基礎：1NF,202

7、0年9月12日星期六,12,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3使用函數(shù)依賴的分解,本節(jié)要點 函數(shù)依賴的定義 BCNF定義 BCNF與保持依賴的關系 3NF定義 7.3.5更高的范式(本小節(jié)略，我們將在7.7節(jié)討論) 下一步學習 7.4.1-3:函數(shù)依賴的性質、理論 7.4.4-5:模式分解的基本性質、要求 7.5:BCNF、3NF的分解算法,2020年9月12日星期六,13,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3.1函數(shù)依賴,函數(shù)依賴 設R(U)是屬性集U上的關系模式，X , Y U， r是R(U) 上的任意一個關系，如果成立 對t , s r，若tX = sX，則tY = s

8、Y 那么稱“X函數(shù)決定Y”，或“Y函數(shù)依賴于X”，記作XY 稱X為決定因素 如S# SN， （S#，C#） G,2020年9月12日星期六,14,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3.1函數(shù)依賴,函數(shù)依賴示例 對關系模式R(sno,sname,dno,dname)，分析下述函數(shù)依賴，哪些成立？哪些不成立？ snamesname dnamedname sname,dnamedname snosname,dno,dname snoR sno,snamedno dnodname snamesno sno,dnoR,2020年9月12日星期六,15,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3

9、.1平凡的函數(shù)依賴,對關系模式R(sno,sname,dno,dname)，下述函數(shù)依賴成立： snamesname dnamedname sname,dnamedname 平凡的函數(shù)依賴： 對所有關系模式R，如果，必有 當時，稱是平凡(trivial)的函數(shù)依賴 否則，稱為非平凡的函數(shù)依賴，稱是的實質決定因素 思考：關系模式R上，平凡函數(shù)依賴的數(shù)量規(guī)模？,2020年9月12日星期六,16,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3.1函數(shù)依賴對模式的約束,對關系模式R(sno,sname,dno,dname)，下述函數(shù)依賴成立： snosname,dno,dname sno,snamedn

10、o dnodname 函數(shù)依賴是對關系模式的約束 對關系實例r=(s1,甲,d1,計), (s2,乙,d1,數(shù)) 如果模式R沒有指明dnodname，r R 如果模式R指明dnodname之后，r R 函數(shù)依賴限制了關系模式可能的實例 關系模式的表示 研究函數(shù)依賴后，關系模式描述應為四元組 R(U,D,dom,F) //F是R成立的函數(shù)依賴集合 關系模式常簡單表示為： R(F),2020年9月12日星期六,17,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3.1不成立的函數(shù)依賴,對關系模式R(sno,sname,dno,dname)，下述函數(shù)依賴不成立： snamesno 函數(shù)依賴是對模式的約束

11、 函數(shù)依賴必須是現(xiàn)實語義約束的反映 也許在一些具體的關系示例上，snamesno成立 不能通過對實例數(shù)據(jù)的分析，總結模式上成立的函數(shù)依賴,2020年9月12日星期六,18,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3.1函數(shù)依賴與碼,對關系模式R(sno,sname,dno,dname)，下述函數(shù)依賴成立： snoR sno,dnoR 使用函數(shù)依賴定義碼： 超碼SuperKey： 對關系模式R， R，如果R,則為超碼 候選碼CandidateKey： 對關系模式R，為超碼，如果任意的真子集 ，R不成立，則稱為候選碼,2020年9月12日星期六,19,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3

12、.1關系實例滿足的函數(shù)依賴,關系實例滿足的函數(shù)依賴 實例r滿足的函數(shù)依賴： snosname snamesno 實例r不滿足函數(shù)依賴： dnosname 實例滿足的依賴 vs 模式上成立的依賴 關系模式R(F),如果rR(F),則： 1、R上成立的所有函數(shù)依賴，r必須滿足； (否則，稱rR(F)) 2、r上滿足的函數(shù)依賴， R上不一定成立；,2020年9月12日星期六,20,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3.1關系實例滿足的函數(shù)依賴,思考，如下關系實例r： r滿足的函數(shù)依賴有哪些？ r不滿足的函數(shù)依賴有哪些？,,2020年9月12日星期六,21,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計

13、,7.3.2 BCNF定義,定義一： 對R(F)，如果R上成立的所有函數(shù)依賴，均有： 1) 或者 2)是超碼 則稱關系模式R為BCNF，記作RBCNF 定義二： 關系模式R(F)，如果(不包含于)成立，則必為超碼，稱RBCNF 。 定義三： 決定因素必含碼 每個關系模式都屬BCNF，則DB為BCNF。,2020年9月12日星期六,22,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3.2 BCNF,判定：下列哪個模式是BCNF? R1(sno,sname,dno,dname) snosname,dno dnodname R2(sno,sname,cno,score) snosname sno,cn

14、oscore R3(sno,pid,sname,sage,dept) sno pid,sname,sage,dept pid sno R4(sno,tno,cno) //F= R5(sno,tno,cno) tnocno sno,cnotno,2020年9月12日星期六,23,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3.2 BCNF,BCNF的本質 (在只考慮函數(shù)依賴的前提下)只講一件事 非碼決定因素的相關決定關系講述了另外一件事 R1(sno,sname,dno,dname) F:snosname,dno dnodname R1講述了“學生”和“院系”兩件事，R1(F)BCNF 有多個

15、碼是一件事的不同方面,本質仍是一件事 R3(sno,pid,sname,sage,dept) F:snopid,sname,sage,dept pid sno R3有兩個碼，講述了”學生”一件事， R3(F)BCNF 思考：所有的二元聯(lián)系都是BCNF嗎？,2020年9月12日星期六,24,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3.3BCNF和保持依賴,關系模式可以通過分解達到BCNF 示例： R(sno,sname,dno,dname) F:snosname,dno dnodname R(F)BCNF 分解R為R1,R2 R1(sno,sname,dno) F1=snosname,dn

16、o R2(dno,dname) F2=dnodname R1,R2 BCNF 分解效果良好,2020年9月12日星期六,25,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3.3BCNF和保持依賴,有些關系模式分解BCNF會有問題 示例： R(sno,tno,cno) tnocno sno,cnotno R(F)BCNF 分解R為R1,R2 R1(sno,tno) F1= R2(tno,cno) F2=tnocno R1,R2 BCNF R1,R2 中不易驗證sno,cnotno 保持依賴 通俗地說，不依靠關系連接就能驗證依賴關系，稱保持依賴 不是所有關系模式都能保持依賴地分解到BCNF,202

17、0年9月12日星期六,26,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3.4 3NF定義,定義一： 對R(F),如果對F+，必有 1) 或者 2)是超碼 或者 3) (-)的每個屬性均包含在某一候選碼中 則稱關系模式R為3NF，記作R3NF,2020年9月12日星期六,27,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3.4 3NF,判定：下列哪個模式是3NF? R1(sno,sname,dno,dname) snosname,dno dnodname R2(sno,sname,cno,score) snosname sno,cnoscore R3(sno,pid,sname,sage,dept

18、) sno pid,sname,sage,dept pid sno R4(sno,tno,cno) //F= R5(sno,tno,cno) tnocno sno,cnotno,2020年9月12日星期六,28,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3.4 3NF,示例模式3NF判定結果： R1，R2：不是3NF R3，R4，R5：是3NF R53NF，因為R5中沒有屬性不屬于候選碼 R5(sno,tno,cno) tnocno sno,cnotno R5的候選碼：(sno,cno)或(sno,tno),2020年9月12日星期六,29,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3.4

19、3NF定義的注意問題,定義一：對R(F),如果對F+，必有 1) 或者 2)是超碼 或者 3) (-)的每個屬性均包含在某一候選碼中 則稱R3NF 注意： 定義中第3)點，不是：(-)包含在某一候選碼中 例如：R(cno,cname,tno,sno) F:cnocname cnamecno cno,snotno tnocno,cname tnocno,cname中,cno,cname不包含在任何一個候選碼, 但“(-)的任一個屬性均包含在某一候選碼中”,R(F)3NF,2020年9月12日星期六,30,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3.4 3NF vs BCNF,BCNF是3

20、NF的真子集 證明： 1、顯然： BCNF 3NF 2、存在R(F)3NF, R(F) BCNF 例如： R5(sno,tno,cno) F: tnocno sno,cnotno,2020年9月12日星期六,31,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3.4 3NF的其它定義,傳遞函數(shù)依賴定義(習題7.14) 關系模式R(F)， R， 屬性AR，A： ，不函數(shù)決定，A,稱A傳遞依賴于 否則，稱稱A直接依賴于 主屬性定義 至少出現(xiàn)在一個候選碼中的屬性，稱為主屬性 否則，稱為非主屬性 3NF定義二 關系模式R(F)，沒有非主屬性傳遞依賴于碼,稱R(F)為3NF 3NF定義三 非主屬性決定因

21、素必含碼 每個關系模式都屬3NF，則DB為3NF,2020年9月12日星期六,32,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3.5 更高的范式,我們將在7.7節(jié)中學習,2020年9月12日星期六,33,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4函數(shù)依賴,本節(jié)要點 函數(shù)依賴集的閉包 邏輯蘊含 Armstrong公理系統(tǒng) 屬性集的閉包 正則覆蓋 無關屬性 無損分解 保持依賴,2020年9月12日星期六,34,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.1函數(shù)依賴的推理規(guī)則,問題 給定一組函數(shù)依賴，是否能導出另外一些函數(shù)依賴，或另外的函數(shù)依賴是否成立。 如FD=A B，B C，A C是否成立？

22、,2020年9月12日星期六,35,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.1邏輯蘊涵,定義 關系模式R，F(xiàn)是其函數(shù)依賴集，X，Y是其屬性子集，如果從F中的函數(shù)依賴能夠推出XY，則稱F邏輯蘊涵XY，記作F XY,2020年9月12日星期六,36,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.1函數(shù)依賴集的閉包,定義 關系模式R(F)中，F(xiàn)邏輯蘊含的所有函數(shù)依賴的集合，稱為F的閉包，記作F+ 關系模式R(F)成立的所有函數(shù)依賴的集合 F+的規(guī)模 Np，任何計算F+的算法一定是np 示例 R(X, Y), F = XY F+ = X， XX， XY， XXY，Y， YY，XY ，XYX，XY

23、Y，XYXY,2020年9月12日星期六,37,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.1 Armstrong公理系統(tǒng),推理規(guī)則系統(tǒng) 正確的、完備的推理規(guī)則集 公理、定理、推論（如歐幾里德集合） Armstrong公理 X，Y，Z是屬性集， 自反律(reflexivity)：若Y X， 則X Y 增廣律(augmentation)：若X Y ，則XZ YZ 傳遞律(transitivity)：若X Y，Y Z，則X Z,2020年9月12日星期六,38,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.1 Armstrong公理系統(tǒng),Armstrong公理的正確性及完備性 A = f |可用

24、Armstrong公理從F中導出的函數(shù)依賴f B = f |被F所邏輯蘊涵的函數(shù)依賴f 正確性：用Armstrong公理從F中導出的函數(shù)依賴必為F所蘊涵 A B 完備性：F所蘊涵的函數(shù)依賴都能用Armstrong公理從F中導出 B A,2020年9月12日星期六,39,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.1 Armstrong公理系統(tǒng),關于Armstrong公理正確性,按函數(shù)依賴定義r是R上的任一關系，t，s r,2020年9月12日星期六,40,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.1 Armstrong公理系統(tǒng),2020年9月12日星期六,41,數(shù)據(jù)庫系統(tǒng)概念----關系

25、數(shù)據(jù)庫設計,7.4.1 Armstrong公理系統(tǒng),2020年9月12日星期六,42,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.1 Armstrong公理系統(tǒng),由Armstrong公理導出的推理規(guī)則 合并律(union rule) 若X Y，X Z，則X YZ 分解律(decomposition rule) 若X YZ ，則X Y，X Z 偽傳遞律(pseudotransitivity rule) 若X Y，WY Z，則WX Z,2020年9月12日星期六,43,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.1 Armstrong公理系統(tǒng),2020年9月12日星期六,44,數(shù)據(jù)庫系統(tǒng)概念-

26、---關系數(shù)據(jù)庫設計,7.4.1 Armstrong公理系統(tǒng),2020年9月12日星期六,45,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.1 Armstrong公理系統(tǒng),2020年9月12日星期六,46,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.1 Armstrong公理系統(tǒng),示例 R, U = (A, B, C, G, H, I), F = AB, AC, CGH, CGI, BH, A H？ CG HI？ AG I？,2020年9月12日星期六,47,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.1 計算F+,F+=F repeat for each 函數(shù)依賴f in F+

27、 在f上應用自反律和增補律將結果加入到F+ for each 一對函數(shù)依賴f1和f2 in F+ if f1和f2可以使用傳遞律連接起來，將結果加入到F+ until F+不再發(fā)生變化,2020年9月12日星期六,48,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.1 計算F+,F=XY,Y Z, F+= X , Y , Z , XY , XZ , YZ , XYZ , X X, Y Y, Z Z, XY X, XZ X, YZ Y, XYZ X, X Y, Y Z , XY Y, XZ Y, YZ Z, XYZ Y, X Z, Y YZ, XY Z, XZ Z,

28、 YZ YZ, XYZ Z, X XY, XY XY, XZ XY, XYZ XY, X XZ, XY YZ, XZ XZ, XYZ YZ X YZ, XY XZ, XZ XY, XYZ XZ, X ZYZ, XY XYZ, XZ XYZ, XYZ XYZ,7.4.1 計算F+,算法的時間復雜性：NP 不可能有計算F+的多項式算法 計算閉包算法的特征 集合按照一定規(guī)則生長、直到不能再生長,2020年9月12日星期六,49,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,2020年9月12日星期六,50,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.2

29、屬性集的閉包,要判斷一個屬性集X是否為超碼，必須設計一個計算由X屬性集函數(shù)確定的屬性集的算法。辦法之一是計算F+,2020年9月12日星期六,51,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.2 屬性集的閉包,屬性集的閉包,設F為屬性集U上的一組函數(shù)依賴，X U， = A | XA能由F根據(jù)Armstrong公理導出 稱 為屬性集X關于函數(shù)依賴集F的閉包,2020年9月12日星期六,52,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.2 屬性集的閉包,示例 屬性集U=A，B，C， 函數(shù)依賴集F=A B，B C 則 A+ = ABC B+ = BC C+ = C,2020年9月12日星期六

30、,53,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,判定XY是否能由F根據(jù)Armstrong公理導出，可轉化為求 ，判定Y 是否成立,7.4.2 閉包的計算,問題：有沒有一般性的算法判定XY是否能由F根據(jù)Armstrong公理導出？,如果計算出F+，再判斷XY是否屬于F+，則由于F+的計算非常復雜，實際上是不可行的,2020年9月12日星期六,54,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,開始：,Input：X，F(xiàn)，U Output： := X; while ( 發(fā)生變化）do for each 函數(shù)依賴 AB in F do begin if A then := B end,7.4

31、.2 閉包的計算,算法（求屬性集的閉包）,2020年9月12日星期六,55,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.2 計算+ ：算法正確性證明,證明：算法結束時，result= +(即Armstrong 公理完備性) 證明： 0)記算法結束時，result=A1A2Am，R-result=B1B2Bn 1)反證法；假設result+,必有result+，即： 必存在屬性(不妨設該屬性為B1) ：B1+,B1result； 2)構造如圖所示關系r。 3)關系r滿足F： 如不然，算法不會結束。 4)關系r不滿足B1； 5) B1+,必有B1F+；r不滿足F+。 6) r滿足F，不滿足F+，

32、矛盾； 假設不成立，證畢。,2020年9月12日星期六,56,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.2 閉包的計算,示例1 R, U = (A, B, C, G, H, I), F = AB, AC, CGH, CGI, BH,計算 所用依賴 ABAGB ACAGBC CGHAGBCH CGIAGBCH I = AGBCH I,,2020年9月12日星期六,57,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,示例2 R, U = (A, B, C, D, E), F = ABC, BD, CE, CEB, ACB,計算 所用依賴 ABCABC BDABCD CEABCDE

33、 = ABCDE,7.4.2 閉包的計算,,2020年9月12日星期六,58,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.2 閉包的計算,示例3 R, U = (A, B, C, D, E, G), F = AE, BEAG, CEA, GD,計算 所用依賴 AEABE BEAGABEG GDABEGD = ABEGD,,2020年9月12日星期六,59,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.2 閉包的計算,練習 R, U = (C, T, H, R, S), F = CT, HRC, HTR, HSR，HR是碼嗎？HS呢？,2020年9月12日星期六,60,數(shù)

34、據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.2 屬性集的閉包,算法作用： 1、判斷屬性集是否為超碼 2、通過檢驗 +是否成立，可以驗證函數(shù)依賴 是否成立 3、是另一種計算F+的方法：對任意的屬性集，找出+ ，對于任意的屬性集S + ，得到 S,2020年9月12日星期六,61,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.3正則覆蓋(Canonical Cover),假設在一個關系模式上有一個函數(shù)依賴集F。當用戶對于關系進行更新時，數(shù)據(jù)庫系統(tǒng)將保證此操作不會破壞任何一個函數(shù)依賴,可以通過測試與給定函數(shù)依賴集有相同閉包的簡化集的方式，來降低檢測的開銷,2020年9月12日星期六,62,數(shù)據(jù)

35、庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.3 函數(shù)依賴集的等價和覆蓋,函數(shù)依賴集的等價性 函數(shù)依賴集F，G，若F+= G+，則稱F與G等價。 若F與G等價，則稱F是G的一個覆蓋，G是F的一個覆蓋。 F+ = G+ F G+，G F+,2020年9月12日星期六,63,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.3 正則覆蓋,滿足下列條件的函數(shù)依賴集F稱為正則覆蓋，記作Fc： Fc 與 F 等價 Fc 中任何函數(shù)依賴都不含無關屬性 Fc 中函數(shù)依賴的左半部都是唯一的,2020年9月12日星期六,64,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.3 無關屬性,如果去除一個函數(shù)依賴中的屬性，不會

36、改變該函數(shù)依賴集的閉包，則稱該屬性是無關的(extraneous),2020年9月12日星期六,65,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.3 無關屬性,對于函數(shù)依賴集F及F中函數(shù)依賴 屬性A在中是無關的，如果A，并且 F ( F - )(- A) 屬性A在中是無關的，如果A ，并且 ( F - )( - A) F,2020年9月12日星期六,66,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.3 無關屬性,在AB C，A C中 在AB CD， A C中,B在AB C中是無關屬性 C在AB CD中是無關屬性,2020年9月12日星期六,67,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.

37、4.3 檢驗無關屬性的方法,考慮中的屬性A 如果A ，F(xiàn)= ( F - ( - A) ,檢驗A是否能由F推出，即計算F下的+，如果+包含A，則A在是無關的 如果A ，令 = -A，并計算 是否可以由F推出，即計算在F下的+，如果+包含的所有屬性，則A在是無關的,2020年9月12日星期六,68,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.3 檢驗無關屬性的方法,F=AB CD, A E, E C,C在AB CD上是否是無關屬性？,F=AB D, A E, E C下AB的屬性閉包為ABCDE，包含CD，因此C在AB CD上是無關屬性,2020年9月12日星期六,69,數(shù)據(jù)庫系統(tǒng)概念----關系

38、數(shù)據(jù)庫設計,7.4.3 正則覆蓋,算法求函數(shù)依賴集F的正則覆蓋FC REPEAT 合并和為 找出在、中含無關屬性的函數(shù)依賴 刪除中的無關屬性 UNTIL F 不再改變 注意：檢查無關屬性是在當前Fc中的函數(shù)依賴，而不是F 不能同時討論F中的兩個屬性的無關性，一次只能討論一個屬性,2020年9月12日星期六,70,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.3 正則覆蓋,如果一個函數(shù)依賴的右半部只包含一個屬性，例如， A C，并且右邊的屬性是無關的，那么將得到一個右部為空的函數(shù)依賴，這樣的函數(shù)依賴應該刪除 從某種意義上說， FC是最小的，它不含無關屬性，并且具有相同左半部的函數(shù)都已經(jīng)被合并，

39、所以驗證FC比驗證F本身更容易,2020年9月12日星期六,71,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.3 正則覆蓋,示例 F = ABC，BC，AB，ABC，求FC 合并ABC， AB為ABC A在ABC中是無關的 C在ABC中是無關的 因此FC = AB，BC,2020年9月12日星期六,72,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.3 正則覆蓋,正則覆蓋未必唯一 示例 F=ABC, BAC, CAB Fc1=AB, BC, CA Fc2=AB, BAC, CB Fc3=AC, CB , BA Fc4=AC, BC, CAB,2020年9月12日星期六,73,數(shù)

40、據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.4無損連接 3、關系實例r,不滿足; 故：分解沒有能保持依賴關系,2020年9月12日星期六,97,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.4.4-5無損分解dnodname;sno,cnoscore 分解R1(sno,dno),R2(sno,dname,cno,score) 判斷：R2是否屬于BCNF? 算法復雜性分析：NP,2020年9月12日星期六,113,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.5.1.2: BCNF分解算法,關系模式R(F)分解為BCNF的算法 result=R 計算F+ While result中存在不屬于BCNF的模

41、式Ri do 對Fi,+RiF+且=： 令result:=(result-Ri)(Ri-)(),2020年9月12日星期六,114,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.5.1.2 BCNF分解算法思想,BCNF分解算法的思想 如果Ri(Fi)BCNF, 必有Fi，F(xiàn)i+ Ri，且= 將Ri分解為：(Ri-)和(),對分解結果中不是BCNF的子模式，循環(huán)進行上述分解，直到全部模式都屬于BCNF 注意：必須要求=,2020年9月12日星期六,115,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.5.1.2 BCNF分解算法示例,BCNF分解示例： R(sno,sname,dno,dname,cn

42、o,score) f1:dnodname f2:snosname,dno f3:sno,cnoscore 分解結果： R1(dno,dname) R2(sno,sname,dno) R3(sno,cno,score) 練習： 請先使用f2對R進行分解 并分析分解的結果,2020年9月12日星期六,116,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.5.1.2 BCNF分解算法分析,BCNF分解算法分析 算法一定可以結束 算法復雜性：NP 分解算法無損 當我們用(Ri - )和()代替模式Ri時，保持依賴，而且(Ri - ) ()= 分解算法不能保證保持依賴 上例中，首先使用f1分解，保持依賴 首

43、先使用f2分解，不保持依賴 有些模式R(F),有無損、保持依賴的BCNF分解，但分解算法找不出來，如： R(sno,tno,dno) F=snodno；tnodno 有些模式R(F),沒有無損、保持依賴的BCNF分解： R(sno,tno,cno) F=tnocno；sno,cnotno,2020年9月12日星期六,117,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.5.1.2 BCNF分解算法示例,示例：U=S#，SD，MN，C#，G F=S#SD，S#MN，SDMN，(S#,C#)G U1=S#，SD , F1=S#SD U2=S#, MN, C#, G, F2=S#MN, (S#,C#)

44、G U1 = S#, SD, F1=S#SD U2 = S#, MN, F2=S#MN U3 = S#, C#, G, F3 = (S#,C#)G,2020年9月12日星期六,118,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.5.1.2 BCNF分解算法示例,示例 STC(SNO , TNO , CNO)， F=TNO CNO，（SNO，TNO） CNO ，（SNO，CNO） TNO 分解 R1（TNO，CNO），F(xiàn)R！=TNO CNO R2（TNO，SNO）,2020年9月12日星期六,119,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.5.2 3NF判定算法,3NF判定算法 按照3NF的定

45、義 逐個檢查F中是否有違背3NF要求的函數(shù)依賴 判定算法時間復雜性：Np 判定一個屬性是否為主屬性無多項式算法,2020年9月12日星期六,120,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.5.2 3NF的分解算法,算法：（達到3NF且保持函數(shù)依賴的分解） 求F的正則覆蓋FC 若有XAFC ，且XA=U，則算法終止 3. 對FC中的每一個函數(shù)依賴，如果沒有任意Rj包含，則生成Ri=。設Ri的屬性全體為Ui，令Fi為FC在Ui上的投影，則 = R1 , R2 , , Rk是R的一個保持函數(shù)依賴的分解，并且每個Ri 3NF,2020年9月12日星期六,121,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,

46、7.5.2 3NF的分解算法,示例 U=S#，SD，MN，C#，G F=S#SD，S#MN，SDMN，(S#,C#)G FC=S#SD，SDMN ，(S#,C#)G 分組 (S#，SD)，S#SD (SD，MN)，SDMN (S#，C#，G)， (S#,C#)G,2020年9月12日星期六,122,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.5.2 3NF的分解算法,示例：R（ABC；AC，BC） 按保持無損連接分解 碼為AB，分解為AC；AC，AB。 丟失了函數(shù)依賴BC 按保持函數(shù)依賴分解 進行分組，AC；AC，BC；BC 分解是有損的,2020年9月12日星期六,123,數(shù)據(jù)庫系統(tǒng)概念---

47、-關系數(shù)據(jù)庫設計,7.5.2 3NF的分解算法,算法：（達到3NF且同時保持無損連接與函數(shù)依賴的分解） 設 = R1 , , Rk是R的一個保持函數(shù)依賴的3NF分解 設X為R的碼， 若有某個Ui，X Ui，則即為所求， 否則令 = R ，即為所求,2020年9月12日星期六,124,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.5.2 3NF分解算法示例,算法示例： R(sno,sname,cno,cname,tno,bno,bname) f1:snosname f2:cnocname f3:sno,sname,cnotno,cname f4:tnocno f5:bnobname Step1: 計

48、算Fc Step2:對每一Fc ，構造關系() R1(sno,sname)R4(tno,cno) R2(cno,cname)R5(bno,bname) R3(sno,tno,cno) Step3:如果構造的模式都不含R的碼，選一個候選碼構造關系： 選候選碼構造關系R6(sno,cno,bno) R1,R2,R3,R5,R6是R(F)的3NF分解,2020年9月12日星期六,125,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.5.2 3NF分解算法要注意的問題,3NF分解算法要注意的問題： Step2必須是對Fc中的函數(shù)依賴構造關系(不能是F中函數(shù)依賴) 如果對F中函數(shù)依賴構造關系， R3=(sn

49、o,sname,tno,cno,cname) 3NF 必須進行Step3的檢查并在必要時構造候選碼關系模式 否則，分解不是無損分解 上例中，R1,R2,R3,R5是有損分解,2020年9月12日星期六,126,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.5.2 3NF分解算法證明,證明：分解算法是無損、保持依賴的3NF分解算法 1、證明：結果模式集合是R(F)的分解 (任何沒有出現(xiàn)在Fc中的屬性，必屬于R(F)的每一個候選碼) 2、證明：分解保持依賴 (Fc中每一個依賴構造一個模式，必然保持Fc，即保持依賴) 3、證明：分解無損 分解保持依賴,且至少一個子模式含R的候選碼，則無損(定理) (tr

50、,必有tr(tc.k.=tc.k.,可以證明t=t,即tr) 4、證明：對Fc ，構造的關系Ri()，必有Ri 3NF (如果Ri 3NF，則有無關屬性，與Fc矛盾) 5、證明：如果針對R的一個候選碼，構造了關系Rn,則Rn3NF (候選碼構造的關系Rn,Fn中沒有非平凡的函數(shù)依賴),2020年9月12日星期六,127,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,算法正確性分析（結果模式集合是R的分解）,任何沒有出現(xiàn)在Fc中的屬性，必屬于R(F)的每一個候選碼,2020年9月12日星期六,128,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,算法正確性分析（保持依賴）,算法保持函數(shù)依賴 通過為一個給定的正則

51、覆蓋中的每一個函數(shù)依賴顯式構造一個模式，該算法確保了函數(shù)依賴 該算法結果不唯一,2020年9月12日星期六,129,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,算法正確性分析（無損連接）,該算法對于關系模式的分解是無損連接的分解。通過保證至少有一個模式包含了被分解模式的候選碼，該算法保證了分解是一個無損連接分解 假設t Ri(r) ,但不屬于r。假設是候選碼,被包含于ri中。則在 Ri(r)中, 是候選碼;tri,則必有t1r, t1 = t, t1r必有t1 Ri(r);則t=t1,即tr,矛盾,,,,2020年9月12日星期六,130,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,算法正確性分析（屬

52、于3NF）,如果一個關系Ri在由綜合算法產(chǎn)生的分解中，則Ri3NF，考慮Ri 上的任意函數(shù)依賴 B滿足3NF的定義 假定綜合算法中產(chǎn)生Ri的函數(shù)依賴是，B Ri，則B或者B，考慮下列三種情況 BB：因為B在中是無關屬性，所以不會出現(xiàn)在Fc中，這種情況不成立 B B 是一個超碼，則Ri3NF,2020年9月12日星期六,131,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,算法正確性分析（屬于3NF）,不是一個超碼，則中一定包含一些不在中的屬性。因為 B在F+中，通過B +Fc得到的。該推導不會用到，否則 +Fc，因為假定不是超碼，所以上述結論是不成立的?，F(xiàn)在，使用(-B)和 B，得到B，這表明B在中

53、是右無關屬性，這也是不可能的(因為是Fc中的函數(shù)依賴)。所以，如果B，則一定是超碼 B B ：因為是候選碼，3NF的第三個條件滿足,2020年9月12日星期六,132,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.5.3 BCNF分解 vs 3NF分解,對R(F)，模式分解： 可以無損分解到BCNF,但不一定能保持依賴 可以無損、保持依賴地分解到3NF 示例： R(sno,cno,tno) F:tnocno;sno,cnotno R(F)不能無損、保持依賴地分解到BCNF R(F)可以無損、保持依賴地分解到3NF,2020年9月12日星期六,133,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,關系模式的

54、分解,結論： 若要求分解保持函數(shù)依賴，那么分解后的模式總可以達到3NF，但不一定能達到BCNF,2020年9月12日星期六,134,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.5.3 BCNF分解 vs 3NF分解,當不能保持依賴地分解到BCNF時，應當選擇BCNF分解，還是3NF分解？ 沒有定論； 教材認為一般選擇BCNF，值得商榷； 試分析R(F)應該分解到BCNF?還是3NF? R(sno,cno,tno) F:tnocno; sno,cnotno,2020年9月12日星期六,135,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6 使用多值依賴進行模式分解,本節(jié)要點 多值依賴的定義 多值依賴

55、的性質和特點 4NF定義 4NF vs BCNF R無損分解為兩個關系模式的充分必要條件 4NF分解算法,2020年9月12日星期六,136,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.1 多值依賴,關系模式TEACH（C#，T#，B#），一門課程由多個教員擔任，一門課程使用相同的一套參考書。 它的碼是（C#，T#，B#），所以屬于BCNF,2020年9月12日星期六,137,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.1 多值依賴,不良特性 插入異常：當某門課程增加一名教員時，該門課程有多少本參考書就必須插入多少個元組；同樣當某門課程需要增加一本參考書時，它有多少個教員就必須插入多少個元

56、組 刪除異常：當刪除一門課程的某個教員或者某本參考書時，需要刪除多個元組 更新異常：當一門課程的教員或參考書作出改變時，需要修改多個元組 數(shù)據(jù)冗余：同一門課的教員與參考書的信息被反復存儲多次,2020年9月12日星期六,138,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.1 多值依賴,定義 描述型：關系模式R(U)，X、Y、Z U，并且Z = U X Y，多值依賴X Y成立當且僅當對R(U)的任一關系r，給定的一對（x，z）值有一組Y的值，這組值僅僅決定于x值而與z值無關 如在關系模式TEACH中，對(C1 , B1)有一組T#值(T1 , T2)，對(C1 , B2)也有一組T#值(T1

57、, T2)，這組值僅取決于C#的取值，而與B#的取值無關。因此，T#多值依賴于C#，記作C#T#，同樣有C#B#,2020年9月12日星期六,139,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.1 多值依賴,形式化：關系模式R(U)，X、Y、ZU，Z=UX Y，對于R(U)的任一關系r，若存在元組t1，t2，使得t1X = t2X，那么就必然存在元組t3，t4，使得： t3X = t4X = t1X = t2X t3Y = t1Y， t4Y = t2Y t3Z = t2Z， t4Z = t1Z 則稱Y多值依賴于X，記作X Y 若(C#, T#, B#)滿足C#T#，含有元組t1=(C1, T

58、1, B1)，t2=(C1, T2, B2)，則也一定含有元組t3=(C1, T1, B2)，t2=(C1, T2, B1)。,2020年9月12日星期六,140,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.1 多值依賴,找出關系上所滿足的多值依賴,CB？若使BC成立，需加入哪些元組？,t1 t2,t3 t4,t3 t4,2020年9月12日星期六,141,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.1 多值依賴,性質 多值依賴具有對稱性，即 若XY，則XZ，其中Z=UXY 函數(shù)依賴是多值依賴的特例，即 若XY，則XY 若Y X或UXY=，則稱XY為平凡的多值依賴,2020年9月12日星期

59、六,142,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.1 Armstrong公理,W、X，Y，Z是R上的屬性集， 自反律：若Y X， 則X Y 增廣律：若X Y ，則XZ YZ 傳遞律：若X Y，Y Z，則X Z 補充律：若XY，則XU X Y 多值增補律：若XY且W Z，則XZ YW 多值傳遞律：若XY且YZ，則X Z Y 復制律：若XY，則XY 聯(lián)合律：若XY，Z Y，WY= 且W Z，則X Z,2020年9月12日星期六,143,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.1 Armstrong公理,推論 多值合并律：若XY且X Z ，則X YZ 取交律：若XY且X Z ，則X Y

60、Z 取差律：若XY且X Z ，則X Y Z， X Z Y,2020年9月12日星期六,144,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.1 多值依賴 Vs 函數(shù)依賴,區(qū)別 函數(shù)依賴規(guī)定某些元組不能出現(xiàn)在關系中，也稱為相等產(chǎn)生依賴 多值依賴要求某種形式的其它元組必須在關系中，稱為元組產(chǎn)生依賴 有效性范圍 XY的有效性僅決定于X、Y屬性集上的值，它在任何屬性集W（XY W U）上都成立 若XY在R(U)上成立，則對于任何Y Y，均有XY 成立,2020年9月12日星期六,145,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.1 多值依賴 Vs 函數(shù)依賴,XY的有效性與屬性集范圍有關 XY在屬性

61、集W（XY W U）上成立，但在U上不一定成立 XY在U上成立 XY在屬性集W（XY W U）上成立 若在R(U)上，XY在屬性集W(XY W U)上成立，則稱XY為R(U) 的嵌入式多值依賴 若XY在R(U)上成立，則不能斷言對于Y Y，是否有XY 成立,2020年9月12日星期六,146,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.1 多值依賴 Vs 函數(shù)依賴,,,,,,,,,,,,,,AB在ABC上成立，而在ABCD上不成立,ABC 成立AB不成立,2020年9月12日星期六,147,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.1 閉包,令D表示函數(shù)依賴和多值依賴的集合，D的閉包D+

62、是由D邏輯蘊涵的所有函數(shù)依賴和多值依賴的集合,2020年9月12日星期六,148,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.2 4NF,定義 關系模式R 1NF，若XY（YX）是非平凡的多值依賴，且X含有碼，則稱R4NF 如關系模式CTB，C#T#，C#B#，碼為(C#, T#, B#)，所以CTB4NF 如果一門課Ci有m個教員，n本參考書，則關系中分量為Ci的元組共有mn個，數(shù)據(jù)冗余非常大 改造 將CTB分解為CT（C#，T#），CB（C#，B#），在分解后的關系中分量為Ci的元組共有m + n個,2020年9月12日星期六,149,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.2 4

63、NF判定示例,判定：下列哪些模式是BCNF?哪些是4NF? R1(sno,sname,dno,dname) snosname,dno dnodname R2(cno,bno,tno,tname) tnotname cnotno,tname R3(cno,bno,tno) cnotno R4(sno,cno,score) sno,cnoscore R5(sno,tno) //D= ,2020年9月12日星期六,150,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.3.2 4NF本質,4NF的本質 (在只考慮函數(shù)和多值依賴的前提下) 4NF只講一件事 非碼的多值決定關系講述了另外一件事 R3(cno,

64、bno,tno) cnobno cnotno R3講述了(cno,bno)和(cno,tno)兩件事 思考：所有的二元聯(lián)系都是4NF嗎？,2020年9月12日星期六,151,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.2 4NF vs BCNF,4NF BCNF 證明： 1、4NFBCNF 決定因素是多值決定因素； 多值決定因素必含碼，則決定因素必含碼 即：4NF必為BCNF 2、存在R(D)BCNF, R(D)4NF 例如： R3(cno,bno,tno) cnobno cnotno,2020年9月12日星期六,152,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.2 依賴的限定

65、,依賴 (含函數(shù)依賴、多值依賴)的限定定義： 關系模式R(D),R1,R2Rn是R的一個分解； 集合Di包括： 1)D+中所有只包含Ri中屬性的函數(shù)依賴； 2)Ri (其中D+，Ri) 稱Di為D在Ri上的限定 依賴限定的含義： Ri上成立的所有依賴的集合 Di的規(guī)模：NP,2020年9月12日星期六,153,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.3 4NF的分解算法,算法：（達到4NF無損連接分解算法） 給定關系模式R ， 令 = R 檢查中各關系模式是否屬于4NF，若是，則算法終止。 設 中Ri不屬于4NF， 則存在非平凡多值依賴XA，X不是Ri的碼，則XA是Ri的真子集，將Ri分

66、解為=S1，S1，其中US1 = XA， US2 = Ui A 以代替Ri ，返回到,2020年9月12日星期六,154,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.3 4NF的分解算法,示例：U=A，B，C，D，E，G F=ABCG，BAC，CG U1=A，E，D U2=A，B，C，G , F2=ABCG，BAC，CG U1=A，E，D U2=C，G , F2=CG U3=A，B，C, F3=BAC,2020年9月12日星期六,155,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.3 4NF的分解算法,示例：U=(S#，T#，C#)， F=(S#，C#)T#, T#C# 不屬于BCNF，分解為 U1=(S#，T#)， U2=(T#，C#)，F(xiàn)2=T#C# 丟失了函數(shù)依賴(S#，C#)T#，原來一個學生選修一門課程時，只能對應一個老師；在新的關系模式下現(xiàn)在一個學生選修一門課程時，可能會對應多個老師,2020年9月12日星期六,156,數(shù)據(jù)庫系統(tǒng)概念----關系數(shù)據(jù)庫設計,7.6.3 無損連接分解,定理 關系模式R(U)的分解=R1，R2，則是一個無損連接分解的充要條件是