第四章關(guān)系數(shù)據(jù)理論

1、4.1 關(guān)系模式的設(shè)計(jì)問(wèn)題,4.2 關(guān)系模式的規(guī)范化,4.3 數(shù)據(jù)依賴的公理系統(tǒng),4.4 關(guān)系模式的分解,第四章 關(guān)系數(shù)據(jù)理論,本章小結(jié),4.5 規(guī)范化的問(wèn)題,4.1 關(guān)系模式的設(shè)計(jì)問(wèn)題,如何對(duì)現(xiàn)實(shí)世界建模形成數(shù)據(jù)庫(kù)模式？層次模型和網(wǎng)狀模型：由設(shè)計(jì)者憑借經(jīng)驗(yàn)進(jìn)行建模，沒(méi)有固定的規(guī)則和理論可循。關(guān)系模型：可以利用關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論來(lái)規(guī)范數(shù)據(jù)庫(kù)的邏輯設(shè)計(jì)，使之更加合理。例：學(xué)生關(guān)系模式S(S#,SN

2、AME,CLASS,C#,TNAME,TAGE,ADDRESS,GRADE)其中主碼是(S#,C#),4.1 關(guān)系模式的設(shè)計(jì)問(wèn)題,,問(wèn)題？,4.1 關(guān)系模式的設(shè)計(jì)問(wèn)題,學(xué)生關(guān)系S存在的問(wèn)題：數(shù)據(jù)冗余度高學(xué)生與課程之間是多對(duì)多的關(guān)系，SNAME,CLASS,TNAME,TAGE,ADDRESS在S中需要被多次重復(fù)存儲(chǔ)。數(shù)據(jù)修改復(fù)雜數(shù)據(jù)冗余導(dǎo)致數(shù)據(jù)修改復(fù)雜。插入異常沒(méi)有選課之前學(xué)生不能被插入。刪除異常

3、如果刪除某門(mén)課程的選課信息，該課程任課老師的信息也丟失。,4.1 關(guān)系模式的設(shè)計(jì)問(wèn)題,問(wèn)題產(chǎn)生的原因：S中存在多余的數(shù)據(jù)依賴（不夠規(guī)范）解決：分解為四個(gè)關(guān)系ST, CT, TA和SC。,4.2 關(guān)系模式的規(guī)范化,關(guān)系規(guī)范化的目的：控制數(shù)據(jù)冗余、避免插入和刪除異常?增強(qiáng)數(shù)據(jù)庫(kù)結(jié)構(gòu)的穩(wěn)定性和靈活性。規(guī)范化過(guò)程：用結(jié)構(gòu)更單純、規(guī)范的關(guān)系逐步取代原有關(guān)系。一、函數(shù)依賴的概念數(shù)據(jù)依賴是實(shí)體內(nèi)部各屬性間的聯(lián)系。分為：

4、函數(shù)依賴多值依賴定義4.1: 屬性集U上關(guān)系模式R(U)，X、Y是U的子集，r是R的任一關(guān)系。若對(duì)于r中任意兩個(gè)元組s,t有：由s[X]=t[X]可以得到s[Y]=t[Y]，稱X函數(shù)決定Y或Y函數(shù)依賴X，記為X?Y。,4.2 關(guān)系模式的規(guī)范化,注意：(1)函數(shù)依賴屬于語(yǔ)義范疇，無(wú)法通過(guò)形式化證明；(2)關(guān)系模式所有的具體關(guān)系都需要滿足關(guān)系模式的函數(shù)依賴。例: 指出學(xué)生關(guān)系S中的函數(shù)依賴關(guān)系。存在如下函數(shù)依賴

5、：S#?SNAME(每個(gè)學(xué)號(hào)只能有一個(gè)學(xué)生姓名)S#?CLASS(每個(gè)學(xué)號(hào)只能有一個(gè)班級(jí))TNAME?TAGE(每個(gè)教師只能有一個(gè)年齡)TNAME?ADDRESS(每個(gè)教師只能有一個(gè)地址)(S#,C#)?GRADE(每個(gè)學(xué)生學(xué)習(xí)一門(mén)課程只能有一個(gè)成績(jī))C#?TNAME(每門(mén)課程只能有一個(gè)老師教授),4.2 關(guān)系模式的規(guī)范化,一般，函數(shù)依賴與屬性間的關(guān)系有：(1)若X, Y是1:1關(guān)系，則存在 X?Y或Y

6、?X；(2)若X, Y是m:1關(guān)系，則存在 X?Y但不存在Y? X；(3)若X, Y是m:n關(guān)系，則X，Y間不存在函數(shù)依賴關(guān)系。常用術(shù)語(yǔ)和記號(hào)：(1)X?Y，但Y ? X，則稱X?Y是非平凡的函數(shù)依賴；(2)X?Y，但Y ? X，則稱X?Y是平凡的函數(shù)依賴；(3)若X?Y，稱X是決定因素；(4)若X?Y, Y?X，記作：X Y；(5)若Y不函數(shù)依賴于X，記作：X Y。,4.2 關(guān)系模

7、式的規(guī)范化,定義4.2: 關(guān)系模式R(U)，函數(shù)依賴的分類如下。完全函數(shù)依賴: 是指 X?Y，且對(duì)任何X的真子集X’， 都有X’ Y，記作：X Y。部分函數(shù)依賴: 是指X?Y，且存在X’?Y， 記作：X Y。傳遞函數(shù)依賴：是指若X?Y (Y ? X)， Y

8、X ， 而Y ? Z。記作： X Z 。,4.2 關(guān)系模式的規(guī)范化,例: 指出學(xué)生關(guān)系S中存在的完全和部分函數(shù)依賴。左部為單屬性的函數(shù)依賴一定是完全函數(shù)依賴，所以S#?SNAME, S#?CLASS, TNAME?TAGE, TNAME?ADDRESS, C#?TNAME都是完全函數(shù)依賴。(S#, C#)?GRADE 是一

9、個(gè)完全函數(shù)依賴，因?yàn)镾#+>GRADE且C#+>GRADE。(S#, C#)?SNAME，(S#, C#)?CLASS，(S#, C#)?TNAME，(S#, C#)?TAGE，(S#, C#)?ADDRESS都是部分函數(shù)依賴，因?yàn)? S#?SNAME，S#?CLASS，C#?TNAME，C#?TAGE，C#?ADDRESS。,例: 試指出學(xué)生關(guān)系S中存在的傳遞函數(shù)依賴。因?yàn)镃#?TNAME，TNAME+>C

10、#，TNAME?TAGE，所以C#?TAGE 是一個(gè)傳遞函數(shù)依賴。C#?ADDRESS也是一個(gè)傳遞函數(shù)依賴。二、碼的精確定義 用函數(shù)依賴的概念來(lái)定義碼。定義4.4: 設(shè)X為R中的屬性或?qū)傩越M合，若 X U 則X為R的候選碼。說(shuō)明：X?U說(shuō)明X能決定整個(gè)元組，X’+>U說(shuō)明X中沒(méi)有多余屬性。,4.2 關(guān)系模式的規(guī)范化,4.2 關(guān)系模式的規(guī)范化,術(shù)語(yǔ)主碼：被選中的候選碼主屬性：候選碼中的屬性

11、非主屬性：不在任何一個(gè)候選碼中的屬性全碼：關(guān)系模式的整個(gè)屬性組為碼 例: R(顧客，商品，日期)例: 指出下列關(guān)系R中的候選碼、主屬性和非主屬性關(guān)系R的候選碼為：A，(D,E)關(guān)系R的主屬性為：A，D，E關(guān)系R的非主屬性：無(wú),4.2 關(guān)系模式的規(guī)范化,三、函數(shù)依賴與基礎(chǔ)范式關(guān)系的規(guī)范化是將一個(gè)低級(jí)范式的關(guān)系模式，通過(guò)關(guān)系模式的分解轉(zhuǎn)換為若干個(gè)高級(jí)范式的過(guò)程。(1)第一范式：1NF定義:

12、 若R的每個(gè)分量都是不可分的數(shù)據(jù)項(xiàng)，則R∈1NF。 從型上看：不存在嵌套結(jié)構(gòu) 從值上看：不存在重復(fù)組 1NF是關(guān)系模式的最低要求。例: 學(xué)生關(guān)系S(S#, SNAME, CLASS, C#, TNAME, TAGE, ADDRESS, GRADE)是1NF關(guān)系，但它存在數(shù)據(jù)冗余，插入異常和刪除異常等問(wèn)題。,4.2 關(guān)系模式的規(guī)范化,(2)第二范式： 2NF 定義:若R∈1NF，且R中的每一個(gè)非主屬性都完全

13、函數(shù)依賴于R的任一候選碼，則R∈2NF。例: 學(xué)生關(guān)系S(S#,SNAME,CLASS,C#,TNAME,TAGE,ADDRESS,GRADE)，候選碼為(S#,C#)。非主屬性和候選碼之間的函數(shù)依賴關(guān)系：(S#, C#) SNAME，(S#, C#) CLASS，(S#, C#) TNAME，(S#, C#) TAGE，(S#, C#) ADDRESS，

14、(S#, C#) GRADE由此可見(jiàn)，在這個(gè)關(guān)系中存在非主屬性對(duì)候選碼的部分函數(shù)依賴，所以S?2NF。,4.2 關(guān)系模式的規(guī)范化,分解為2NF的方法： 將滿足部分函數(shù)依賴和滿足完全函數(shù)依賴的屬性分解到不同的關(guān)系中。例: 關(guān)系S分解為三個(gè)關(guān)系：ST(S#, SNAME, CLASS)（只依賴S#的屬性分解到一個(gè)子模式中）CTA(C#, TNAME, TAGE, ADDRESS) （

15、只依賴C#的屬性分解到另一個(gè)子模式中）SC(S#, C#, GRADE) （完全函數(shù)依賴于候選碼的屬性分解到第三個(gè)子模式中）關(guān)系ST、CTA和SC都為2NF。若關(guān)系R的候選碼是單屬性的，則R必定是2NF。,4.2 關(guān)系模式的規(guī)范化,達(dá)到2NF的關(guān)系仍然可能存在問(wèn)題。例: 在關(guān)系CTA中還存在以下問(wèn)題：①數(shù)據(jù)冗余。一個(gè)教師承擔(dān)多門(mén)課程時(shí)，教師的姓名、年齡、地址要重復(fù)存儲(chǔ)。②修改復(fù)雜。一個(gè)教師更換地

16、址時(shí)，必須修改相關(guān)的多個(gè)元組。③插入異常。一個(gè)新教師報(bào)到，需將其有關(guān)數(shù)據(jù)插入到CTA關(guān)系中，但該教師暫時(shí)還未承擔(dān)任何教學(xué)任務(wù)，則因缺碼C#值而不能進(jìn)行插入操作。④刪除異常。刪除某門(mén)課程時(shí)，會(huì)丟失該課程任課教師的姓名、年齡和地址信息。,4.2 關(guān)系模式的規(guī)范化,(3)第三范式： 3NF定義: 如果關(guān)系R的任何一個(gè)非主屬性都不傳遞函數(shù)依賴于它的任何一個(gè)候選碼，則R∈3NF。例: 關(guān)系CTA是2NF，但不是3NF。因

17、為C#是候選碼，TNAME、TAGE、ADDRESS是非主屬性，由于C#?TNAME，TNAME+>C#，TNAME?TAGE，所以C# TAGE ，同樣有C# ADDRESS， 即存在非主屬性對(duì)候選碼的傳遞函數(shù)依賴。分解為3NF的方法：將涉及傳遞函數(shù)依賴中的兩個(gè)依賴中的屬性分解到不同的關(guān)系中。例: 將CTA分解為：CT(C#, TNAME)，TA(TNAME, TAGE, ADDRESS)則

18、關(guān)系CT和TA都是3NF，關(guān)系CTA中存在的問(wèn)題得到了解決。,4.2 關(guān)系模式的規(guī)范化,(4)BCNF 定義: 關(guān)系模式R∈1NF。若函數(shù)依賴集合F中的所有函數(shù)依賴X?Y（Y?X）的左部都包含R的任一候選碼，則R∈BCNF。 例: 如果假定：每一學(xué)生可選修多門(mén)課程，一門(mén)課程可由多個(gè)學(xué)生選修，每一課程可有多個(gè)教師任教，但每個(gè)教師只能承擔(dān)一門(mén)課程。判斷下列給出的關(guān)系SCT(S#, CNAME, TNAME) 最高屬于第幾范式？

19、并分析該模式存在的問(wèn)題。,4.2 關(guān)系模式的規(guī)范化,①關(guān)系SCT的候選碼：(S#, CNAME)和(S#, TNAME)②非主屬性：無(wú) （SCT至少是一個(gè)3NF關(guān)系)③因?yàn)門(mén)NAME?CNAME，其左部未包含該關(guān)系的任一候選碼，所以它不是BCNF。因此，SCT∈3NF。若關(guān)系R的所有屬性都是主屬性，則R必定是3NF。,4.2 關(guān)系模式的規(guī)范化,達(dá)到3NF的關(guān)系仍然可能存在問(wèn)題。在關(guān)系SCT中還存在以下問(wèn)題

20、：插入異常。如，一個(gè)新課程和任課教師的數(shù)據(jù)，在沒(méi)有學(xué)生選課時(shí)不能插入數(shù)據(jù)庫(kù)。刪除異常。如，刪除某門(mén)課的所有選課記錄，會(huì)丟失課程與教師的數(shù)據(jù)。解決：模式分解。SCT可分解為SC(S#，CNMAE)和CT(CNAME，TNAME)，都是BCNF。一個(gè)BCNF的關(guān)系必定是3NF，但一個(gè)3NF不一定屬于BCNF。任何的二元關(guān)系必定是BCNF。,4.2 關(guān)系模式的規(guī)范化,四、多值依賴與第四范式函數(shù)依賴有效地表達(dá)了

21、屬性間的多對(duì)一的聯(lián)系，但不能表示屬性間的一對(duì)多聯(lián)系。例: 一門(mén)課C可由多個(gè)教員T講授，他們使用相同的一套參考書(shū)X；每個(gè)教員可講授多門(mén)課，每種參考書(shū)可供多門(mén)課使用。問(wèn)：R(C,T,X) 屬于第幾范式？CTX的候選碼是：(C, T, X)∈BCNFCTX表存在冗余、插、刪、改不便,4.2 關(guān)系模式的規(guī)范化,,4.2 關(guān)系模式的規(guī)范化,(1)多值依賴定義: 設(shè)R(U)是屬性集U上的一個(gè)關(guān)系模式，X、Y、Z是U

22、的子集，并且Z=U-X-Y，當(dāng)且僅當(dāng)對(duì)于R(U)的任一關(guān)系r，給定的一對(duì)(x, z)值，有一組Y的值與之對(duì)應(yīng)，且這組Y值僅僅決定于X值而與Z值無(wú)關(guān)，則稱Y多值依賴于X ，或稱X多值決定Y，記為X??Y 。例: CTX關(guān)系中，對(duì)于一個(gè)(數(shù)學(xué), 微分方程)有一組T值{李勇,張平}，但這組T值僅取決于課程C的值。對(duì)于另一個(gè)(數(shù)學(xué), 高等代數(shù))所對(duì)應(yīng)的T值還是{李勇,張平}。因此CTX表中：C??T，同樣的道理可以知道C ??X。,4.2

23、 關(guān)系模式的規(guī)范化,例: 設(shè)關(guān)系模式R(A,B,C)上有一個(gè)多值依賴A??B。如果已知R的當(dāng)前關(guān)系中存在三個(gè)元組(a,b1,c1)、(a,b2,c2)和(a,b3,c3)，那么這個(gè)關(guān)系中至少還應(yīng)該存在哪些元組？平凡多值依賴：對(duì)于屬性集U上的一個(gè)多值依賴X??Y(X，Y是U的子集)，如果Y?X或者XY=U，則稱X??Y是一個(gè)平凡多值依賴。,當(dāng)前關(guān)系中還應(yīng)該存在六個(gè)元組：(a, b1, c2)、(a, b1, c3)、(a

24、, b2, c1)、(a, b2, c3)、(a, b3, c1)、(a, b3, c2)。,4.2 關(guān)系模式的規(guī)范化,多值依賴與函數(shù)依賴的區(qū)別：X??Y 涉及U中其他屬性Z；而 X?Y 僅由X、Y的屬性值所決定。若X?Y成立，則對(duì)于任何Y’ Y均有X?Y’成立；而若X??Y成立，卻不能斷言對(duì)于任何Y’ Y有X??Y’成立。(2)第四范式：4NF定義: 若R∈1NF，如果對(duì)于R的每個(gè)非平凡多值依賴

25、 X??Y (Y?X)，X都含有碼，R∈4NF。定理: 如果關(guān)系模式R∈4NF，則R必為BCNF。,U,U,,(3)5種范式的關(guān)系：,4.2 關(guān)系模式的規(guī)范化,,1NF,2NF,3NF,BCNF,4NF,4.3 數(shù)據(jù)依賴的公理系統(tǒng),1.阿氏公理 設(shè)F是關(guān)系模式R的函數(shù)依賴集，X、Y是R的屬性子集。 定義：在R 中，從F的函數(shù)依賴中能夠推出的函數(shù)依賴全體叫F的閉包，記為：F+。 F+={ ① F；

26、 ② F中推出的非平凡的函數(shù)依賴； ③ F中推出的平凡的函數(shù)依賴： A->φ、A->A、AB-> A….. } 例：有關(guān)系模式R(A，B，C)，F(xiàn)={A→B，B→C}，計(jì)算F的閉包。Armstrong公理(阿氏公理)： 對(duì)R 有：A1自反律：若Y?X ，則X?Y。A2增廣律：若X?Y，則XZ?YZ。A3傳遞律：若

27、X?Y、Y?Z，則X?Z。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),證明:設(shè)s，t是r的任意兩個(gè)元組，r是R的任意一個(gè)關(guān)系A(chǔ)1自反律：若Y?X ，則X?Y。 若s[x]=t[x]，則在s和t中的x的任何子集也必相等。 ∵ Y?X，∴ s[y]=t[y] ∴ X?Y。A2增廣律：若X?Y，則XZ?YZ。 若s[xz]=t[xz]，即s[x]s[z]=t[x]t[z] 則 s[x]=t[x] 且 s[z]=t[z

28、] ∵ X?Y， ∴ s[y]=t[y] ∴ s[yz]=s[y]s[z]=t[y]t[z]=t[yz] ∴ XZ?YZ,4.3 數(shù)據(jù)依賴的公理系統(tǒng),A3傳遞律：若X?Y、Y?Z，則X?Z。 若s[x]=t[x] ∵ X?Y ∴ s[y]=t[y] 又∵ Y?Z ∴ s[z]=t[z] ∴ X?Z。公理的推論則： 合并規(guī)則：若X?Y 、 X?Z，則X?Y

29、Z。 分解規(guī)則：若X?YZ，則X?Y,X?Z。 偽傳遞規(guī)則：若X?Y 、WY?Z，則WX?Z。 證明：合并規(guī)則：∵ X?Y ∴ X?XY (A2) 又∵ X?Z ∴ XY?YZ (A2) ∴ X?YZ (A3),4.3 數(shù)據(jù)依賴的公理系統(tǒng),分解規(guī)則： ∵ Y?Y Z ∴ YZ?Y (A1)

30、 又∵ X?YZ(已知） ∴ X?Y (A3) 同理可證X?Z。偽傳遞規(guī)則：∵ X?Y ∴ WX?WY (A2) 又∵ WY?Z (已知) ∴ WX?Z (A3)定理: X?A1A2…AK成立的充分必要條件是X?Ai成立。,4.3 數(shù)據(jù)依賴的公理

31、系統(tǒng),定義: XF+={A| X?A能由F用阿氏公理導(dǎo)出} XF+稱為屬性集X關(guān)于F的閉包。 例：R(A,B,C) F={A?B,B?C} 則A+=ABC B+=BC C+=C定理： X?Y能從F中用阿氏公理導(dǎo)出的充要條件是：Y?XF+ 證明：充分性（ Y?XF+ -> X?Y） 設(shè)Y?XF+ ，并設(shè)Y=A1A2…

32、An 由屬性閉包定義可知， X?A1， X?A2…， X?An由阿氏公理導(dǎo)出，再由合并規(guī)則得X? A1A2…An， 即X?Y。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),必要性： （ X?Y -> Y?XF+ ） 設(shè)X?Y能由阿氏公理導(dǎo)出。Y=A1A2…An 由分解規(guī)則得： X?A1， X?A2…， X?An 由X+ 的定義可知，Ai?X+ (i=1,2,…,n) 即Y?XF+ 。,4

33、.3 數(shù)據(jù)依賴的公理系統(tǒng),2. 屬性閉包的計(jì)算 算法4.1 : 求屬性集X關(guān)于F的閉包XF+(X+)。簡(jiǎn)化算法： 設(shè) R，A為U中屬性(集)。 (1) X(0)=X (2) X(i+1)=X(i)∪A 其中：對(duì)F中任一個(gè)Y->A ，且Y?X(i)； 求得X(i+1) 后，對(duì)Y->A 做刪除標(biāo)記。 (3)若X(i+1)=X(i) 或 X(i+1) =U則結(jié)束

34、，否則轉(zhuǎn)(2)。例：設(shè)有關(guān)系模式R，其中U={A，B，C，D，E，I}， F={A→D，AB→E，BI→E，CD→I，E→C} 計(jì)算(AE)+。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),3.函數(shù)依賴集的等價(jià)和覆蓋定義: 如果F+=G+ ,就說(shuō)函數(shù)依賴集F覆蓋G或F與G等價(jià)定理: F+=G+ 的充分必要條件是F?G+，和G?F+。（1）必要性∵F和G等價(jià)，∴F+=G+，又∵F?F+，∴F?G+同理，∵G?G+，∴G?F+。

35、（2）充分性任取X→Y∈F+，則有Y?XF+ (定理4.6)又∵F?G+（已知），∴Y?XG++∴X→Y∈(G+)+=G+，∴F+?G+。同理可證G+?F+，∴F+=G+，即F和G等價(jià)。定理證畢。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),如何判斷函數(shù)依賴集F和G是否等價(jià)呢？ 只要驗(yàn)證F中的每一個(gè)函數(shù)依賴X→Y都在G+中，同時(shí)驗(yàn)證 G中的每一個(gè)函數(shù)依賴V→W都在F+中。這不需要計(jì)算F+和 G+，只要計(jì)算XG+驗(yàn)證Y?XG

36、+，再計(jì)算VF+，驗(yàn)證W?VF+即可。 例：F={A→B, B→C}, G={A→BC, B→C}，判斷F和G是否等價(jià) 解：（1）先檢查F中的每一個(gè)函數(shù)依賴是否屬于G+。 ∵AG+=ABC，∴B?AG+，∴A→B∈G+ 又∵BG+=BC，∴C?BG+，∴B→C∈G+ ∴F?G+ （2）然后檢查G中的每一個(gè)函數(shù)依賴是否屬于F+。

37、 ∵AF+=ABC，∴BC?AF+，∴A→BC∈F+ 又∵BF+=BC，∴C?BF+，∴B→C∈F+ ∴G?F+ 由（1）和（2）可得F和G等價(jià)。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),4.最小函數(shù)依賴集定義:若F滿足下列條件，則稱其為最小函數(shù)依賴集Fm。 (1) F中每個(gè)函數(shù)依賴的右部都是單屬性； (2) 對(duì)F中的任一函數(shù)依賴X→A，F(xiàn)-{X→A}與F都不等價(jià) (

38、3) 對(duì)于F中的任一函數(shù)依賴X→A和X的真子集Z， (F-(X→A))U{Z→A}與F都不等價(jià)。 （1）保證在函數(shù)依賴的右部沒(méi)有多余的屬性；（2）保證F中不存在多余的函數(shù)依賴；（3）保證F中每個(gè)函數(shù)依賴的左部沒(méi)有多余的屬性。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),定理: 每個(gè)F與Fm等價(jià)。如何求最小函數(shù)依賴集Fm？ (1)分解：使F中任一函數(shù)依賴的右部?jī)H含有單屬性。 (2)去掉函數(shù)依賴左邊多余的屬性：

39、 方法：對(duì)F中任一XY?A，在F中求X+， 若A?X+ ，則Y為多余的。 (3)去掉多余函數(shù)依賴： 方法：對(duì)F中任一X?A，在F-{X?A}中求X+， 若A?X+，則X?A為多余的。,4.3 數(shù)據(jù)依賴的公理系統(tǒng),例： 設(shè)函數(shù)依賴集F={A→C，C→A，B→AC，D→AC，BD→A} 求與F等價(jià)的最小函數(shù)依賴集。 例：

40、設(shè)有函數(shù)依賴集F={B→C，C→AB，A→BC，BC→A} 求與F等價(jià)的最小函數(shù)依賴集。 注意：一個(gè)函數(shù)依賴集的最小集不是惟一的。 例如，F(xiàn)={A→B，B→A，B→C，A→C，C→A} Fm1={A→B，B→C，C→A}， Fm2={A→B，B→A，A→C，C→A}。,4.4 關(guān)系模式的分解,對(duì)于存在數(shù)據(jù)冗余、插入異常、刪除異常的關(guān)系模式，可以通過(guò)對(duì)關(guān)系模式的分解來(lái)解決問(wèn)題。關(guān)系模式分解后會(huì)

41、帶來(lái)兩個(gè)問(wèn)題：(1)查詢時(shí)的連接操作是否會(huì)丟失某些信息或多出某些信息。這引出了無(wú)損連接的概念。(2)分解后的關(guān)系模式是否保持了原來(lái)的函數(shù)依賴。這是保持函數(shù)依賴性的問(wèn)題。 一、等價(jià)模式分解的定義一個(gè)關(guān)系有多種分解方法，如何判斷分解的好與壞呢？例: 關(guān)系模式R(S#,SD,MN)，F(xiàn)={S#?SD, SDMN}分解一：ρ1={R1(S#), R2(SD), R3(MN)} 不好！無(wú)法恢復(fù)R分解二：ρ2={R

42、1(S#, SD), R2(S#, MN)} 不好！丟失SDMN分解三：ρ3={R1(S#, SD), R2(SD, MN)} 好！,4.4 關(guān)系模式的分解,二、無(wú)損連接性與依賴保持性 對(duì)于R中任何一個(gè)關(guān)系r，R分解ρ={R1, R2, …., RK}無(wú)損連接性：r=ΠR1(r) ? ΠR2(r) ? … ? ΠRK(r)保持函數(shù)依賴：F ≡ ΠR1(F)∪ΠR2(F)∪… ΠR

43、K(F)ΠRi(F)={X?Y| X?Y∈F+∧XY?Ri },Ri所含的F+中的函數(shù)依賴,4.4 關(guān)系模式的分解,例: R(A, B, C)，F(xiàn)={A?B, A?C}，分解ρ={AB, AC} 判斷1：r=ΠAB(r) ? ΠAC(r) 是無(wú)損連接分解。 判斷2：F≡ΠAB(F)∪ΠAC(F) = {A?B, A?C}具有函數(shù)依賴保持性。,r,4.4 關(guān)系模式的分解,算法4.3 無(wú)損

44、連接性檢驗(yàn)。 輸入：關(guān)系模式R(A1，A2，…，An)，它的函數(shù)依賴集F，以及 分解ρ={R1，R2，…，Rk}。 輸出：確定ρ是否具有無(wú)損連接性。 方法：(1)構(gòu)造一個(gè)k行n列的表，第i行對(duì)應(yīng)于關(guān)系模式Ri， 第j列對(duì)應(yīng)于屬性Aj。如果Aj∈Ri，則在第i行第j列上放符號(hào)ai，否則放符號(hào)bij。 (2)重復(fù)考察F中的每一個(gè)函數(shù)依賴，并修改表中的元素。 方法如下：取F中一個(gè)X→Y

45、，在X的分量中尋找相同的行， 然后將這些行中Y的分量改為相同的符號(hào)，如果其中有aj， 則將bij改為aj；若其中無(wú)aj，則全部改為bij（i是這些行的行號(hào)最小值）。,4.4 關(guān)系模式的分解,(3)如果發(fā)現(xiàn)表中某一行變成了al，a2，…，an，則分解ρ 具有無(wú)損連接性；如果F中所有函數(shù)依賴都不能再修改 表中的內(nèi)容，且沒(méi)有發(fā)現(xiàn)這樣的行，則分解ρ不具有無(wú)損連接性。 例：設(shè)R，其中U={A，B，C，D，E}，

46、 F={A→C，B→C，C→D，DE→C，CE→A} ρ={R1，R2，R3，R4，R5}， 這里R1=AD，R2=AB，R3=BE， R4=CDE，R5=AE。 判斷分解ρ是否具有無(wú)損連接性。,4.4 關(guān)系模式的分解,定理: 設(shè)ρ=(R1，R2)是R的一個(gè)分解，F(xiàn)是R上的函數(shù) 依賴集，分解ρ具有無(wú)損連接性的充分必要條件是： R1∩R2→(R1-R2)∈F+

47、 或 R1∩R2→(R2-R1)∈F+ 證明： （1）充分性：設(shè)R1∩R2→(R1-R2)，按算法5.2可構(gòu)造出下表。表中省略了a和b的下標(biāo)，這無(wú)關(guān)緊要。,4.4 關(guān)系模式的分解,如果R1∩R2→(R1-R2)在F中，則可將表中第2行位于(R1-R2)列中的所有符號(hào)都改為a，這樣該表中第2行就全是a了，則ρ具有無(wú)損連接性。同理可證R1∩R2→(R2-R1)的情況。 如果R1∩R2→(R1-R2)不在F中，但在F

48、+中，即它可以用公理從 F中推出來(lái)，從而也能推出R1∩R2→Ax, 其中Ax?R1-R2，所以可以將Ax列的第2行改為全a，同樣可以將R1-R2中的其他屬性的第2行也改為a，這樣第2行就變成全a行。所以分解ρ={R1，R2}具有無(wú)損連接性。 同樣可以證明R1∩R2→(R2-R1)的情況。 （2）必要性:設(shè)構(gòu)造的表中有一行全為a，例如第1行全為a，則由函數(shù)依賴定義可知R1∩R2→(R2-R1)；如果是第2行全為a，則 R1

49、∩R2→(R1-R2)。定理證畢。,4.4 關(guān)系模式的分解,例: 下列分解是否具有無(wú)損連接性和函數(shù)依賴保持性。 已知：R(A,B,C) F={A→B，C→B} (1）ρ1={AB，AC} （2）ρ2={AB，BC},4.4 關(guān)系模式的分解,三、模式分解的方法3NF的保持無(wú)損連接及函數(shù)依賴的分解： 設(shè)：R(1)對(duì)Fm中任一X?A，若XA=U則不分解，結(jié)束；(2)若R中Z屬性在Fm中未出現(xiàn)，則

50、所有Z為一個(gè)子模式，令U=U-Z；(3)對(duì)Fm中 X?A1, …., X?An，用合成規(guī)則合成一個(gè)，再對(duì)Fm中每個(gè)X?A，令Ri=XA；(4) R的分解為{R1, R2, …., RK, 碼},4.4 關(guān)系模式的分解,BCNF的保持無(wú)損連接的分解：（1）令ρ={R}；（2）如果ρ中所有關(guān)系模式都是BCNF，則轉(zhuǎn)（4）； （3）如果ρ中有一個(gè)關(guān)系模式Ri不是BCNF， 則Ri中必有X→A∈Fi+(

51、A?X)，且X不是Ri的碼。 設(shè)S1=XA，S2=Ui-A，用分解{S1，S2}代替Ri， 轉(zhuǎn)（2）； （4）分解結(jié)束，輸出ρ。 例：設(shè)R={A,B,C,D}, F={A→C，C→A，B→AC，D→AC，BD→A} （1）將R分解為3NF且具有無(wú)損連接性和依賴保持性。 （2）將R 分解為BCNF且具有無(wú)損連接性。,4.5 規(guī)范化的問(wèn)題,一、規(guī)范化的缺點(diǎn)

52、模式分解會(huì)降低查詢效率；僅基于一個(gè)關(guān)系模式的規(guī)范化。二、反規(guī)范化的設(shè)計(jì)對(duì)特定的應(yīng)用不規(guī)范化，而通過(guò)使用冗余來(lái)改進(jìn)性能。例: 清單(帳號(hào), 支行名, 密碼, 余額)，帳戶(客戶名, 帳號(hào)) 每次訪問(wèn)時(shí)，客戶名都與帳號(hào)、密碼和余額一起顯示。 并不是規(guī)范化程度越高越好；并非越簡(jiǎn)越好。例: 收益(公司號(hào), 年份, 數(shù)量)，若設(shè)計(jì)成：(1)使用多個(gè)關(guān)系 ，每年建一個(gè)表。收益-xx(公司號(hào)，數(shù)量) BCNF 多年、

53、分組統(tǒng)計(jì)不便！ (2)使用一個(gè)關(guān)系：收益(公司號(hào)，收入2000，收入2001，收入2002) BCNF 好不好？,4.5 規(guī)范化的問(wèn)題,三、模式設(shè)計(jì)的原則(1)模式R，分解ρ= {R1, …, Rk}，一般應(yīng)有的特性：是3NF模式集或BCNF模式；無(wú)損分解：r=ΠR1(r) ? ΠR2(r) ? … ? ΠRK(r) 保持函數(shù)依賴：F≡ F1∪F2∪… Fk(2)盡可能使模式保持最好的特性:盡量設(shè)計(jì)成B

54、CNF。若達(dá)不到保持函數(shù)依賴的特點(diǎn)，則需設(shè)計(jì)成3NF，以保證兩個(gè)條件。(3)模式分解和轉(zhuǎn)換的關(guān)鍵是要: “等價(jià)”。原則：表達(dá)性：新模式能表達(dá)原模式。分離性：將產(chǎn)生不好性質(zhì)的屬性分離。少冗余性：選擇非最高的范式、“小”的公共屬性。,少連接屬性,第四章 關(guān)系數(shù)據(jù)理論,1. 函數(shù)依賴關(guān)系2. 關(guān)系模式的規(guī)范化幾種常見(jiàn)范式及其轉(zhuǎn)換3. 阿氏公理及其推理規(guī)則4. XF+的定義及求XF+5. 用函數(shù)依賴或XF+求碼