數(shù)據(jù)庫系統(tǒng)概論課件：規(guī)范化理論總結(jié)(new)

1、數(shù)據(jù)庫模式（結(jié)構(gòu)）可以有很多種，不同人可能設(shè)計不同的數(shù)據(jù)庫模式。給定一個關(guān)系S，如何判斷S是否是一個好的模式？判斷： 是否存在 1）數(shù)據(jù)冗余，2）數(shù)據(jù)不一致，3）插入異常， 4） 刪除異常如果一個模式S不存在上述問題，我們認為是一個好的模式，否則，我們要想辦法將關(guān)系S進行分解，變?yōu)槎鄠€模式S1, S2等，其中要求每個子模式S1,S2都是好的模式。我們不能對于模式每次都主觀的去判斷是否存在數(shù)據(jù)冗余、數(shù)據(jù)不一致、插入異常、刪除異常等，而應(yīng)該通過數(shù)學(xué)上的方法進行判斷。那么問題是：到底是什么造成了上述的問題呢？答案是：不同屬性間的數(shù)據(jù)依賴所導(dǎo)致的。如果在關(guān)系S中，屬性間的數(shù)據(jù)依賴符合某種規(guī)則，則不會產(chǎn)

2、生，或者可以減少上述的問題。這種規(guī)則稱為范式。數(shù)據(jù)依賴數(shù)據(jù)依賴是現(xiàn)實世界事物之間的相互聯(lián)系的一種表達，是屬性固有的語義的體現(xiàn)。在設(shè)計數(shù)據(jù)庫時，設(shè)計人員對需求進行詳細的分析，才能歸納出與客觀事實相符合的數(shù)據(jù)依賴。因此，數(shù)據(jù)依賴是一種語義的表示，不能說數(shù)據(jù)依賴不好，或者好。一般情況下，數(shù)據(jù)依賴是函數(shù)依賴(FD)。例如比如我們要設(shè)計一個學(xué)生成績管理的數(shù)據(jù)庫，我們會分析實際的成績管理系統(tǒng)的情況，發(fā)現(xiàn)：學(xué)生的學(xué)號Xh是唯一的，通過學(xué)號，可以知道學(xué)生的姓名xm、性別xb、班級bj等信息。一個學(xué)生的學(xué)號，就決定了某一個學(xué)生的姓名、性別。因此，我們寫為 Xhxm, xhxb, xhbj。Xhxm，我們說，xm

3、是依賴于xh的，xh決定了xm.這就是一個函數(shù)依賴。比如我們要設(shè)計一個學(xué)生成績管理的數(shù)據(jù)庫，我們會分析實際的成績管理系統(tǒng)的情況，發(fā)現(xiàn)：一個學(xué)生會學(xué)習多門課程(kc)，然后每門課程有個成績(cj)。我們不能寫為kccj，因為同一門課程可能有多個同學(xué)去學(xué)習，這樣寫不符合實際情況。因此，如果考慮到這個因素，就可以得出xh, kc cj。也就是說，cj是依賴于xh和kc這兩個屬性的。給定唯一的xh和唯一的kc,只有一個成績與其對應(yīng)如果考慮到還有重修，則xh,kccj也不對了。因為某個學(xué)生可能在第一學(xué)期學(xué)習了“高等數(shù)學(xué)”，得了30分，第二學(xué)期不得不重修“高等數(shù)學(xué)”，因此，唯一的xh和kc的組合，就有兩個

4、成績與其對應(yīng)了，因此不能說cj是由xh和kc決定的了。在這種情況下，xh,kc,xqcj因此，具體的函數(shù)依賴是要根據(jù)需求和實際情況確定的，反映了各個屬性間的邏輯聯(lián)系又如，某個學(xué)生是屬于一個院系的，沒有學(xué)生可以同時屬于兩個院系。每個院系都只有一個系主任。通過這樣的語義，我們可以推出這兩個依賴：XhdeptNamedeptNamedeptChair函數(shù)依賴FD的形式化定義設(shè)R(U)是一個屬性集U上的關(guān)系模式，X和Y是U的子集。 若對于R(U)的任意一個可能的關(guān)系r，r中不可能存在兩個元組在X上的屬性值相等， 而在Y上的屬性值不等， 則稱 “X函數(shù)確定Y” 或 “Y函數(shù)依賴于X”，記作XY。 X稱為

5、這個函數(shù)依賴的決定屬性集(Determinant)。 X到Y(jié)是單射的。一個X屬性上的值，在Y屬性上只能有一個值和其對應(yīng)。 Y=f(x)41 537函數(shù)依賴和屬性關(guān)系設(shè)屬性集X,Y以及存在關(guān)系模式R如果X和Y是“1-1”的關(guān)系（如學(xué)校和校長），則存在函數(shù)依賴XY和YX, 即XY如果X和Y之間是“m-1”的關(guān)系(如學(xué)號和課程），則存在函數(shù)依賴XY如果X和Y之間是”m-n”關(guān)系（如學(xué)生和課程），則X和Y之間不存在函數(shù)依賴有了函數(shù)依賴可以做什么？如果我們找到了給定模式S上的所有的函數(shù)依賴：可以確定這個模式的鍵是什么（超鍵、候選鍵）可以判斷這個模式是否是“好”的模式，即是否符合某個范式可以判斷某個元組是

6、否滿足這些FD的約束，進行完整性的檢查現(xiàn)在的問題就變?yōu)榱耍喝绾握业絊上的所有的函數(shù)依賴？因為有些依賴是可以由別的依賴推導(dǎo)出來的例如： XhdeptName 以及 DeptNameDeptChair， 就蘊含了 xh DeptChair如果F是給定的S的函數(shù)依賴，則F+，即F的閉包，就包含了S上的所有的函數(shù)依賴因此，問題變?yōu)槿绾胃鶕?jù)F求F+,即根據(jù)給定的一些函數(shù)依賴，求出S上的所有的函數(shù)依賴。F+求法根據(jù)阿姆斯特朗公理：自反、傳遞、增廣if , then if , then if , and , then 具體算法： F + = F重復(fù)對于F+中的每個函數(shù)依賴f 對f實施自反和增廣律。 將獲得的

7、新的函數(shù)依賴加入到F+中。對于F+中的一對函數(shù)依賴 f1和 f2 如果 f1 和 f2 能夠通過傳遞律結(jié)合則將新的函數(shù)依賴加入到F+中。直到 F + 不再增加F的閉包計算是NP問題 F=X Y,Y Z, F+計算是NP完全問題， 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, YZ YZ, XYZ Z,X XY, XY XY, XZ XY, XYZ XY, X XZ, XY YZ

8、, XZ XZ, XYZ YZX YZ, XY XZ, XZ XY, XYZ XZ,X ZYZ, XY XYZ, XZ XYZ, XYZ XYZ 把求F的閉包的問題，轉(zhuǎn)換為求屬性集的閉包因為求F+計算量大，所以人們通過間接的途徑，去求屬性集的閉包。設(shè)F為屬性集U上的一組函數(shù)依賴，X U， XF+ = A|XA能由F 根據(jù)Armstrong公理導(dǎo)出，XF+稱為屬性集X關(guān)于函數(shù)依賴集F 的閉包例如要判斷S上的某個函數(shù)依賴XY是否成立，我們可以首先根據(jù)給定的那些函數(shù)依賴，計算F+，然后判斷XY是否屬于里面（NP問題）也可以，計算屬性X的閉包X+，然后判斷Y是否屬于X+(多項式問題）求屬性集的閉包的算

9、法 result := a; while (result發(fā)生變化) dofor each in F dobeginif result then result := result end例子設(shè)U=A, B, C, D, E, IF=AD, ABE, BIE, CDI, EC問AEEI是否成立？求解方法：1. 根據(jù)阿姆斯特朗公理，去嘗試2.求(AE)+1. result = AE2. result = AEDC 根據(jù)AD, EC3. result = AEDCI 根據(jù)CDI4. 由于F中沒有用過的函數(shù)依賴左邊的屬性已經(jīng)沒有AEDCI的子集，所以計算結(jié)束。(AE)+=ACDEI由于EI 屬于 (AE

10、)+, 根據(jù)閉包的定義，有AEEI成立。有了屬性集的閉包可以判斷那些屬性是鍵如果某個屬性集X的閉包包含了所有的屬性，則X為S上的超鍵如果沒有X的子集的閉包包含了所有的屬性，則X為S上的候選鍵判斷函數(shù)依賴XY是否成立計算X的閉包即可函數(shù)依賴的等價和覆蓋給定一個關(guān)系模式S上的兩個函數(shù)依賴集F和G,如果F+=G+，則兩者是等價的。例如： A B, B C, A CD 和 A B, B C, A D 是等價的既然同一個關(guān)系模式上的函數(shù)依賴集合有很多個，那么是否存在一個最小的依賴集合呢？通過最小的函數(shù)依賴集合，可以用最簡單的形式表示出關(guān)系模式S上的函數(shù)依賴最小依賴集如果函數(shù)依賴集F滿足下列條件，則稱F為

11、一個極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。 (1) F中任一函數(shù)依賴的右部僅含有一個屬性。 (2) F中不存在這樣的函數(shù)依賴XA，使得F與F-XA等價。（保證F中不存在多余的依賴） (3) F中不存在這樣的函數(shù)依賴XA， X有真 子集Z使得F-XAZA與F等價。 （保證每個函數(shù)依賴的左邊沒有多余的屬性）求最小依賴的算法(1)根據(jù)分解規(guī)則，使得F中每一個依賴的右部屬性單一化(2)去掉各個依賴左邊的多余屬性。一個一個檢查F中左邊是非單屬性的依賴。例如XYA，現(xiàn)在要判斷Y是否是多余的，即以XA替代XYA后，是否等價？那么只要在F中，求X+，如果X+包含了A，則Y是多余的；否則Y不是多余屬性。依

12、次判斷其它屬性即可以消除各依賴左邊多余屬性。（3）去掉多余的依賴。從第一個依賴開始，從F去掉這個依賴（假設(shè)為XY），然后在剩余的依賴中求X+，看X+是否包含Y。如果包含，則XY是多余依賴，刪除。否則，不能去除。依次做下去，檢查所有的依賴。例子設(shè)F=ABC, CA, BCD, ACDB, DEG, BEC, CGBD, CEAG求與其等價的最小依賴將依賴右邊屬性單一化：F1= ABC, CA, BCD, ACDB, DE, DG, BEC, CGB, CGD, CEA, CEGF1= ABC, CA, BCD, ACDB, DE, DG, BEC, CGB, CGD, CEA, CEG(2)在F

13、1中，去掉依賴左邊多余的屬性。例如，我們檢查ABC中，B是否是多余屬性，由于A+=空集，所以B不是多余屬性，同樣，B+也為空，所以A也不是多余屬性。對于CEA，由于存在CA，所以C+包含A，所以E是多余的。對于ACDB,由于(CD)+=ABCDEG，所以A是多余的，刪除這些多余的屬性后，有：F2= ABC, CA, BCD, CDB, DE, DG, BEC, CGB, CGD, CA, CEG刪除重復(fù)的依賴，有F2= ABC, CA, BCD,CDB, DE, DG, BEC, CGB, CGD, CEGF2= ABC, CA, BCD,CDB DE, DG, BEC, CGB, CGD,

14、CEG（3）在F2中刪除多余的依賴。例如，對于CGB，由于（CG)+=ABCDEG，所以CGB是多余的，刪除。依次判斷，最后的結(jié)果是：F3=ABC, CA, BC D,CDB, DE, DG, BEC, CGD, CEG然后.有了這些理論的基礎(chǔ)，我們可以來判斷模式S是否屬于某些范式:1NF, 2NF, 3NF, 4NF, BCNF名詞定義平凡函數(shù)依賴與非平凡函數(shù)依賴完全函數(shù)依賴與部分函數(shù)依賴傳遞函數(shù)依賴碼(1) 平凡函數(shù)依賴與非平凡函數(shù)依賴在關(guān)系模式R(U)中，對于U的子集X和Y，如果XY，但Y X，則稱XY是非平凡的函數(shù)依賴若XY，但Y X, 則稱XY是平凡的函數(shù)依賴例：在關(guān)系SC(Sno,

15、 Cno, Grade)中， 非平凡函數(shù)依賴： (Sno, Cno) Grade 平凡函數(shù)依賴： (Sno, Cno) Sno (Sno, Cno) Cno(2) 完全函數(shù)依賴與部分函數(shù)依賴在關(guān)系模式R(U)中，如果XY，并且對于X的任何一個真子集X，都有 X Y, 則稱Y完全函數(shù)依賴于X，記作X Y。 若XY，但Y不完全函數(shù)依賴于X，則稱Y部分函數(shù)依賴于X，記作X P Y。 例: 在關(guān)系SC(Sno, Cno, Grade)中， 由于：Sno Grade，Cno Grade， 因此：(Sno, Cno) Grade (3)傳遞函數(shù)依賴 在關(guān)系模式R(U)中，如果XY，YZ，且Y X，YX，則

16、稱Z傳遞函數(shù)依賴于X。注: 如果YX， 即XY，則Z直接依賴于X。例: 在關(guān)系Std(Sno, Sdept, Mname)中，有：Sno Sdept，Sdept Mname Mname傳遞函數(shù)依賴于Sno(4) 碼 設(shè)K為關(guān)系模式R中的屬性或?qū)傩越M合。若K U，則K稱為R的一個侯選碼（Candidate Key）。若關(guān)系模式R有多個候選碼，則選定其中的一個做為主碼（Primary key）。主屬性與非主屬性候選鍵中包括的那些屬性被稱為主屬性。例如， SC(Sno, Cno, Grade)中， (SNO，CNo)是候選鍵，所以，SNO是主屬性，CNo也是主屬性ALL KEY范式見中文ppt各種范

17、式之間存在聯(lián)系：某一關(guān)系模式R為第n范式，可簡記為RnNF。1nf: 原子性當且僅當R中的每一個屬性A的值域只包含原子項，即不可分割的項目。2Nf:消除了部分函數(shù)依賴例如，在模式(學(xué)號，課程代碼，成績，班級代碼）這樣的模式中，（學(xué)號、課程代碼）是主鍵，因此（學(xué)號，課程代碼）決定了班級代碼，但是，同時又有學(xué)號決定了班級代碼，因此，（學(xué)號，課程代碼）決定班級代碼是一個部分函數(shù)依賴，或者說，班級代碼是部分依賴于（學(xué)號、課程代碼）的。（因為只要xh就可以決定bjdm了，而現(xiàn)在多了一個kcdm,所以是部分依賴），這個模式就不是2nfR屬于第二范式，當且僅當R是1NF,并且每個非主屬性完全函數(shù)依賴于主關(guān)鍵

18、字。3NF:消除了傳遞依賴沒有AB, BC這樣的依賴R屬于第三范式，當且僅當R是2nf，并且每個非主屬性都不傳遞依賴于主關(guān)鍵字。4NF:消除了多值依賴BCNF：消除了碼中的傳遞依賴和部分依賴判斷時，只要判斷函數(shù)依賴集合F中，所有依賴的左部是否包含了R的候選碼就可以了。即AB這樣形式的依賴，A必須包含了R中的某一個候選碼（因為候選碼有多個）。例如，關(guān)系模式(學(xué)生，教師，課程）中，假設(shè)1個教師上1門課程，每門課有多個教師（例如，數(shù)據(jù)庫這門課程，06軟工陳越上，06計算機李老師上），1個學(xué)生選定某門課，就對應(yīng)一個固定的教師（例如張三選擇了06軟工的數(shù)據(jù)庫，則就只會由陳越來上了），根據(jù)這個語義，有如下

19、的函數(shù)依賴 (學(xué)生、課程） 老師，（學(xué)生，老師）課程， 老師課程。因此，（老師、學(xué)生）（學(xué)生、課程）都是候選關(guān)鍵字，而由于老師課程中，左邊只是老師，沒有包含候選關(guān)鍵字，所以這個模式不是BCNF。候選關(guān)鍵字的求法在函數(shù)依賴集F中，如果有函數(shù)依賴XA， X只出現(xiàn)在F的左邊，則X必定是R中任意候選關(guān)鍵字的成員對于在F中沒有出現(xiàn)的屬性，必定是R的候選關(guān)鍵字的成員。在函數(shù)依賴集F中，如果有函數(shù)依賴XA， A只出現(xiàn)在F的右邊，則A必定不是R中任意候選關(guān)鍵字的成員關(guān)系模式分解關(guān)系模式分解無損連接性對模式進行分解后，在原有模式下的關(guān)系可以通過分解之后的模式進行自然連接恢復(fù)出來如何判斷？P189要求F是最小覆蓋

20、構(gòu)建二維表格根據(jù)依賴修改二維表格判斷例如，有關(guān)系模式R(C,T,H,R,S,G F=CSG,CT，THR, HRC, HSR分解為R1(C,S,G), R2(C,T), R3(T,H,R), R4(H,R,C), R5(H,S,R)是否是無損分解？解：（1）首先F已經(jīng)是最小依賴了 （2）構(gòu)建二維表格，行是分解出的模式構(gòu)成的屬性，列是所有屬性集合。R1(C,S,G), R2(C,T), R3(T,H,R), R4(H,R,C), R5(H,S,R)RiCTHRSGCSG（由R1得出)CT （由R2)THR （由R3)HRC （由R4)HSR （由R5)如何判斷無損連接？（3）修改表格，從第一行到

21、最后一行，如果列的屬性Aj包含在分解模式中，則將對應(yīng)的單元格填寫aj,如果不包括，則填寫bij,這里i是行號，j是列號。RiCTHRSGCSGa1b12b13b14a5a6CTa1a2b23b24b25b26THRb31a2a3a4b35b36HRCa1b42a3a4b45b46HSRb51b52a3a4a5b56（4）根據(jù)依賴集合F修改表格。逐一檢查F中的每一個函數(shù)依賴，修改表中的元素。方法：取得F中的一個函數(shù)依賴XY，在X的分量中找到相同的行，然后將這些行中的Y分量改為相同的符號，如果其中有aj,則將bij全部改為aj,如果沒有，則將對應(yīng)的分量都改為最小的行號對應(yīng)的bij.從F中提取所有的

22、依賴進行如上的操作過程稱為1次掃描要掃描多次，直到最后一次掃描后，表格不發(fā)生變化為止。如果在掃描過程中，有1行的值是a1,a2,a3an則說明是無損分解。如果掃描結(jié)束，還沒有1行滿足這個條件，則說明不是無損分解。第一次掃描：CSG由于在表格中，沒有兩行中C和S分量的值相同的，所以這個依賴無需改變表格。RiCTHRSGCSGa1b12b13b14a5a6CTa1a2b23b24b25b26THRb31a2a3a4b35b36HRCa1b42a3a4b45b46HSRb51b52a3a4a5b56第一次掃描： CT顯然，在表格中的第1、2，4行中，C屬性列的值都是a1，所以此時，要更改T列，由于第

23、2行的T列的值是a2,所以將第1行中的T列的屬性值b12更改為a2，將第4行中的b42改為a2RiCTHRSGCSGa1a2b13b14a5a6CTa1a2b23b24b25b26THRb31a2a3a4b35b36HRCa1a2a3a4b45b46HSRb51b52a3a4a5b56RiCTHRSGCSGa1b12b13b14a5a6CTa1a2b23b24b25b26THRb31a2a3a4b35b36HRCa1b42a3a4b45b46HSRb51b52a3a4a5b56第一次掃描： THR顯然，第3，4行在屬性TH列上相同，所以更改表格的第3，4行上的R列的值，由于值已經(jīng)是a4，所以就

24、不用改了。RiCTHRSGCSGa1a2b13b14a5a6CTa1a2b23b24b25b26THRb31a2a3a4b35b36HRCa1a2a3a4b45b46HSRb51b52a3a4a5b56RiCTHRSGCSGa1a2b13b14a5a6CTa1a2b23b24b25b26THRb31a2a3a4b35b36HRCa1a2a3a4b45b46HSRb51b52a3a4a5b56第一次掃描： HRCRiCTHRSGCSGa1a2b13b14a5a6CTa1a2b23b24b25b26THRb31a2a3a4b35b36HRCa1a2a3a4b45b46HSRb51b52a3a4a5b56RiCTHRSGCSGa1a2b13b14a5a6CTa1a2b23b24b25b26THRa1