山東大學(xué)數(shù)據(jù)庫(kù)07數(shù)據(jù)庫(kù)設(shè)計(jì).ppt

《山東大學(xué)數(shù)據(jù)庫(kù)07數(shù)據(jù)庫(kù)設(shè)計(jì).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《山東大學(xué)數(shù)據(jù)庫(kù)07數(shù)據(jù)庫(kù)設(shè)計(jì).ppt（180頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

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

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

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

7、0年9月12日星期六,12,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.3使用函數(shù)依賴的分解,本節(jié)要點(diǎn) 函數(shù)依賴的定義 BCNF定義 BCNF與保持依賴的關(guān)系 3NF定義 7.3.5更高的范式(本小節(jié)略，我們將在7.7節(jié)討論) 下一步學(xué)習(xí) 7.4.1-3:函數(shù)依賴的性質(zhì)、理論 7.4.4-5:模式分解的基本性質(zhì)、要求 7.5:BCNF、3NF的分解算法,2020年9月12日星期六,13,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.3.1函數(shù)依賴,函數(shù)依賴 設(shè)R(U)是屬性集U上的關(guān)系模式，X , Y U， r是R(U) 上的任意一個(gè)關(guān)系，如果成立 對(duì)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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.3.1函數(shù)依賴,函數(shù)依賴示例 對(duì)關(guān)系模式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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.3

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

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

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

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

13、,7.3.2 BCNF定義,定義一： 對(duì)R(F)，如果R上成立的所有函數(shù)依賴，均有： 1) 或者 2)是超碼 則稱關(guān)系模式R為BCNF，記作RBCNF 定義二： 關(guān)系模式R(F)，如果(不包含于)成立，則必為超碼，稱RBCNF 。 定義三： 決定因素必含碼 每個(gè)關(guān)系模式都屬BCNF，則DB為BCNF。,2020年9月12日星期六,22,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.3.2 BCNF,判定：下列哪個(gè)模式是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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.3.2 BCNF,BCNF的本質(zhì) (在只考慮函數(shù)依賴的前提下)只講一件事 非碼決定因素的相關(guān)決定關(guān)系講述了另外一件事 R1(sno,sname,dno,dname) F:snosname,dno dnodname R1講述了“學(xué)生”和“院系”兩件事，R1(F)BCNF 有多個(gè)

15、碼是一件事的不同方面,本質(zhì)仍是一件事 R3(sno,pid,sname,sage,dept) F:snopid,sname,sage,dept pid sno R3有兩個(gè)碼，講述了”學(xué)生”一件事， R3(F)BCNF 思考：所有的二元聯(lián)系都是BCNF嗎？,2020年9月12日星期六,24,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.3.3BCNF和保持依賴,關(guān)系模式可以通過(guò)分解達(dá)到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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.3.3BCNF和保持依賴,有些關(guān)系模式分解BCNF會(huì)有問(wèn)題 示例： 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 中不易驗(yàn)證sno,cnotno 保持依賴 通俗地說(shuō)，不依靠關(guān)系連接就能驗(yàn)證依賴關(guān)系，稱保持依賴 不是所有關(guān)系模式都能保持依賴地分解到BCNF,202

17、0年9月12日星期六,26,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.3.4 3NF定義,定義一： 對(duì)R(F),如果對(duì)F+，必有 1) 或者 2)是超碼 或者 3) (-)的每個(gè)屬性均包含在某一候選碼中 則稱關(guān)系模式R為3NF，記作R3NF,2020年9月12日星期六,27,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.3.4 3NF,判定：下列哪個(gè)模式是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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.3.4 3NF,示例模式3NF判定結(jié)果： R1，R2：不是3NF R3，R4，R5：是3NF R53NF，因?yàn)镽5中沒(méi)有屬性不屬于候選碼 R5(sno,tno,cno) tnocno sno,cnotno R5的候選碼：(sno,cno)或(sno,tno),2020年9月12日星期六,29,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.3.4

19、3NF定義的注意問(wèn)題,定義一：對(duì)R(F),如果對(duì)F+，必有 1) 或者 2)是超碼 或者 3) (-)的每個(gè)屬性均包含在某一候選碼中 則稱R3NF 注意： 定義中第3)點(diǎn)，不是：(-)包含在某一候選碼中 例如：R(cno,cname,tno,sno) F:cnocname cnamecno cno,snotno tnocno,cname tnocno,cname中,cno,cname不包含在任何一個(gè)候選碼, 但“(-)的任一個(gè)屬性均包含在某一候選碼中”,R(F)3NF,2020年9月12日星期六,30,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.3.4 3NF的其它定義,傳遞函數(shù)依賴定義(習(xí)題7.14) 關(guān)系模式R(F)， R， 屬性AR，A： ，不函數(shù)決定，A,稱A傳遞依賴于 否則，稱稱A直接依賴于 主屬性定義 至少出現(xiàn)在一個(gè)候選碼中的屬性，稱為主屬性 否則，稱為非主屬性 3NF定義二 關(guān)系模式R(F)，沒(méi)有非主屬性傳遞依賴于碼,稱R(F)為3NF 3NF定義三 非主屬性決定因

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

22、,2020年9月12日星期六,35,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.4.1邏輯蘊(yùn)涵,定義 關(guān)系模式R，F(xiàn)是其函數(shù)依賴集，X，Y是其屬性子集，如果從F中的函數(shù)依賴能夠推出XY，則稱F邏輯蘊(yùn)涵XY，記作F XY,2020年9月12日星期六,36,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.4.1函數(shù)依賴集的閉包,定義 關(guān)系模式R(F)中，F(xiàn)邏輯蘊(yùn)含的所有函數(shù)依賴的集合，稱為F的閉包，記作F+ 關(guān)系模式R(F)成立的所有函數(shù)依賴的集合 F+的規(guī)模 Np，任何計(jì)算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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.4.1 Armstrong公理系統(tǒng),Armstrong公理的正確性及完備性 A = f |可用

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

25、數(shù)據(jù)庫(kù)設(shè)計(jì),7.4.1 Armstrong公理系統(tǒng),2020年9月12日星期六,42,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.4.1 Armstrong公理系統(tǒng),由Armstrong公理導(dǎo)出的推理規(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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.4.1 Armstrong公理系統(tǒng),2020年9月12日星期六,44,數(shù)據(jù)庫(kù)系統(tǒng)概念-

26、---關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.4.1 Armstrong公理系統(tǒng),2020年9月12日星期六,45,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.4.1 Armstrong公理系統(tǒng),2020年9月12日星期六,46,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.4.1 計(jì)算F+,F+=F repeat for each 函數(shù)依賴f in F+

27、 在f上應(yīng)用自反律和增補(bǔ)律將結(jié)果加入到F+ for each 一對(duì)函數(shù)依賴f1和f2 in F+ if f1和f2可以使用傳遞律連接起來(lái)，將結(jié)果加入到F+ until F+不再發(fā)生變化,2020年9月12日星期六,48,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.4.1 計(jì)算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 計(jì)算F+,算法的時(shí)間復(fù)雜性：NP 不可能有計(jì)算F+的多項(xiàng)式算法 計(jì)算閉包算法的特征 集合按照一定規(guī)則生長(zhǎng)、直到不能再生長(zhǎng),2020年9月12日星期六,49,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),2020年9月12日星期六,50,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.4.2

29、屬性集的閉包,要判斷一個(gè)屬性集X是否為超碼，必須設(shè)計(jì)一個(gè)計(jì)算由X屬性集函數(shù)確定的屬性集的算法。辦法之一是計(jì)算F+,2020年9月12日星期六,51,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.4.2 屬性集的閉包,屬性集的閉包,設(shè)F為屬性集U上的一組函數(shù)依賴，X U， = A | XA能由F根據(jù)Armstrong公理導(dǎo)出 稱 為屬性集X關(guān)于函數(shù)依賴集F的閉包,2020年9月12日星期六,52,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),判定XY是否能由F根據(jù)Armstrong公理導(dǎo)出，可轉(zhuǎn)化為求 ，判定Y 是否成立,7.4.2 閉包的計(jì)算,問(wèn)題：有沒(méi)有一般性的算法判定XY是否能由F根據(jù)Armstrong公理導(dǎo)出？,如果計(jì)算出F+，再判斷XY是否屬于F+，則由于F+的計(jì)算非常復(fù)雜，實(shí)際上是不可行的,2020年9月12日星期六,54,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),開(kāi)始：,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 閉包的計(jì)算,算法（求屬性集的閉包）,2020年9月12日星期六,55,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.4.2 計(jì)算+ ：算法正確性證明,證明：算法結(jié)束時(shí)，result= +(即Armstrong 公理完備性) 證明： 0)記算法結(jié)束時(shí)，result=A1A2Am，R-result=B1B2Bn 1)反證法；假設(shè)result+,必有result+，即： 必存在屬性(不妨設(shè)該屬性為B1) ：B1+,B1result； 2)構(gòu)造如圖所示關(guān)系r。 3)關(guān)系r滿足F： 如不然，算法不會(huì)結(jié)束。 4)關(guān)系r不滿足B1； 5) B1+,必有B1F+；r不滿足F+。 6) r滿足F，不滿足F+，

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

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

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

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

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

37、4.3 檢驗(yàn)無(wú)關(guān)屬性的方法,考慮中的屬性A 如果A ，F(xiàn)= ( F - ( - A) ,檢驗(yàn)A是否能由F推出，即計(jì)算F下的+，如果+包含A，則A在是無(wú)關(guān)的 如果A ，令 = -A，并計(jì)算 是否可以由F推出，即計(jì)算在F下的+，如果+包含的所有屬性，則A在是無(wú)關(guān)的,2020年9月12日星期六,68,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.4.3 檢驗(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)屬性,2020年9月12日星期六,69,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系

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

39、所以驗(yàn)證FC比驗(yàn)證F本身更容易,2020年9月12日星期六,71,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.4.3 正則覆蓋,示例 F = ABC，BC，AB，ABC，求FC 合并ABC， AB為ABC A在ABC中是無(wú)關(guān)的 C在ABC中是無(wú)關(guān)的 因此FC = AB，BC,2020年9月12日星期六,72,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.4.4無(wú)損連接 3、關(guān)系實(shí)例r,不滿足; 故：分解沒(méi)有能保持依賴關(guān)系,2020年9月12日星期六,97,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.4.4-5無(wú)損分解dnodname;sno,cnoscore 分解R1(sno,dno),R2(sno,dname,cno,score) 判斷：R2是否屬于BCNF? 算法復(fù)雜性分析：NP,2020年9月12日星期六,113,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.5.1.2: BCNF分解算法,關(guān)系模式R(F)分解為BCNF的算法 result=R 計(jì)算F+ While result中存在不屬于BCNF的模

41、式Ri do 對(duì)Fi,+RiF+且=： 令result:=(result-Ri)(Ri-)(),2020年9月12日星期六,114,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.5.1.2 BCNF分解算法思想,BCNF分解算法的思想 如果Ri(Fi)BCNF, 必有Fi，F(xiàn)i+ Ri，且= 將Ri分解為：(Ri-)和(),對(duì)分解結(jié)果中不是BCNF的子模式，循環(huán)進(jìn)行上述分解，直到全部模式都屬于BCNF 注意：必須要求=,2020年9月12日星期六,115,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(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 分解結(jié)果： R1(dno,dname) R2(sno,sname,dno) R3(sno,cno,score) 練習(xí)： 請(qǐng)先使用f2對(duì)R進(jìn)行分解 并分析分解的結(jié)果,2020年9月12日星期六,116,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.5.1.2 BCNF分解算法分析,BCNF分解算法分析 算法一定可以結(jié)束 算法復(fù)雜性：NP 分解算法無(wú)損 當(dāng)我們用(Ri - )和()代替模式Ri時(shí)，保持依賴，而且(Ri - ) ()= 分解算法不能保證保持依賴 上例中，首先使用f1分解，保持依賴 首

43、先使用f2分解，不保持依賴 有些模式R(F),有無(wú)損、保持依賴的BCNF分解，但分解算法找不出來(lái)，如： R(sno,tno,dno) F=snodno；tnodno 有些模式R(F),沒(méi)有無(wú)損、保持依賴的BCNF分解： R(sno,tno,cno) F=tnocno；sno,cnotno,2020年9月12日星期六,117,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.5.2 3NF判定算法,3NF判定算法 按照3NF的定

45、義 逐個(gè)檢查F中是否有違背3NF要求的函數(shù)依賴 判定算法時(shí)間復(fù)雜性：Np 判定一個(gè)屬性是否為主屬性無(wú)多項(xiàng)式算法,2020年9月12日星期六,120,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.5.2 3NF的分解算法,算法：（達(dá)到3NF且保持函數(shù)依賴的分解） 求F的正則覆蓋FC 若有XAFC ，且XA=U，則算法終止 3. 對(duì)FC中的每一個(gè)函數(shù)依賴，如果沒(méi)有任意Rj包含，則生成Ri=。設(shè)Ri的屬性全體為Ui，令Fi為FC在Ui上的投影，則 = R1 , R2 , , Rk是R的一個(gè)保持函數(shù)依賴的分解，并且每個(gè)Ri 3NF,2020年9月12日星期六,121,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.5.2 3NF的分解算法,示例：R（ABC；AC，BC） 按保持無(wú)損連接分解 碼為AB，分解為AC；AC，AB。 丟失了函數(shù)依賴BC 按保持函數(shù)依賴分解 進(jìn)行分組，AC；AC，BC；BC 分解是有損的,2020年9月12日星期六,123,數(shù)據(jù)庫(kù)系統(tǒng)概念---

47、-關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.5.2 3NF的分解算法,算法：（達(dá)到3NF且同時(shí)保持無(wú)損連接與函數(shù)依賴的分解） 設(shè) = R1 , , Rk是R的一個(gè)保持函數(shù)依賴的3NF分解 設(shè)X為R的碼， 若有某個(gè)Ui，X Ui，則即為所求， 否則令 = R ，即為所求,2020年9月12日星期六,124,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(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: 計(jì)

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

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

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

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

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

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

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

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

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

57、, T2)，這組值僅取決于C#的取值，而與B#的取值無(wú)關(guān)。因此，T#多值依賴于C#，記作C#T#，同樣有C#B#,2020年9月12日星期六,139,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.6.1 多值依賴,形式化：關(guān)系模式R(U)，X、Y、ZU，Z=UX Y，對(duì)于R(U)的任一關(guān)系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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.6.1 多值依賴,找出關(guān)系上所滿足的多值依賴,CB？若使BC成立，需加入哪些元組？,t1 t2,t3 t4,t3 t4,2020年9月12日星期六,141,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.6.1 多值依賴,性質(zhì) 多值依賴具有對(duì)稱性，即 若XY，則XZ，其中Z=UXY 函數(shù)依賴是多值依賴的特例，即 若XY，則XY 若Y X或UXY=，則稱XY為平凡的多值依賴,2020年9月12日星期

59、六,142,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(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 補(bǔ)充律：若XY，則XU X Y 多值增補(bǔ)律：若XY且W Z，則XZ YW 多值傳遞律：若XY且YZ，則X Z Y 復(fù)制律：若XY，則XY 聯(lián)合律：若XY，Z Y，WY= 且W Z，則X Z,2020年9月12日星期六,143,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.6.1 多值依賴 Vs 函數(shù)依賴,區(qū)別 函數(shù)依賴規(guī)定某些元組不能出現(xiàn)在關(guān)系中，也稱為相等產(chǎn)生依賴 多值依賴要求某種形式的其它元組必須在關(guān)系中，稱為元組產(chǎn)生依賴 有效性范圍 XY的有效性僅決定于X、Y屬性集上的值，它在任何屬性集W（XY W U）上都成立 若XY在R(U)上成立，則對(duì)于任何Y Y，均有XY 成立,2020年9月12日星期六,145,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.6.1 多值依賴 Vs 函數(shù)依賴,XY的有效性與屬性集范圍有關(guān) 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)上成立，則不能斷言對(duì)于Y Y，是否有XY 成立,2020年9月12日星期六,146,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.6.1 多值依賴 Vs 函數(shù)依賴,,,,,,,,,,,,,,AB在ABC上成立，而在ABCD上不成立,ABC 成立AB不成立,2020年9月12日星期六,147,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.6.1 閉包,令D表示函數(shù)依賴和多值依賴的集合，D的閉包D+

62、是由D邏輯蘊(yùn)涵的所有函數(shù)依賴和多值依賴的集合,2020年9月12日星期六,148,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.6.2 4NF,定義 關(guān)系模式R 1NF，若XY（YX）是非平凡的多值依賴，且X含有碼，則稱R4NF 如關(guān)系模式CTB，C#T#，C#B#，碼為(C#, T#, B#)，所以CTB4NF 如果一門課Ci有m個(gè)教員，n本參考書(shū)，則關(guān)系中分量為Ci的元組共有mn個(gè)，數(shù)據(jù)冗余非常大 改造 將CTB分解為CT（C#，T#），CB（C#，B#），在分解后的關(guān)系中分量為Ci的元組共有m + n個(gè),2020年9月12日星期六,149,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.3.2 4NF本質(zhì),4NF的本質(zhì) (在只考慮函數(shù)和多值依賴的前提下) 4NF只講一件事 非碼的多值決定關(guān)系講述了另外一件事 R3(cno,

64、bno,tno) cnobno cnotno R3講述了(cno,bno)和(cno,tno)兩件事 思考：所有的二元聯(lián)系都是4NF嗎？,2020年9月12日星期六,151,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.6.2 依賴的限定

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

66、解為=S1，S1，其中US1 = XA， US2 = Ui A 以代替Ri ，返回到,2020年9月12日星期六,154,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(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ù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(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#，原來(lái)一個(gè)學(xué)生選修一門課程時(shí)，只能對(duì)應(yīng)一個(gè)老師；在新的關(guān)系模式下現(xiàn)在一個(gè)學(xué)生選修一門課程時(shí)，可能會(huì)對(duì)應(yīng)多個(gè)老師,2020年9月12日星期六,156,數(shù)據(jù)庫(kù)系統(tǒng)概念----關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì),7.6.3 無(wú)損連接分解,定理 關(guān)系模式R(U)的分解=R1，R2，則是一個(gè)無(wú)損連接分解的充要條件是