數(shù)據(jù)庫原理與應用關系規(guī)范化理論PPT學習教案

1、會計學1數(shù)據(jù)庫原理與應用數(shù)據(jù)庫原理與應用 關系規(guī)范化理論關系規(guī)范化理論2關系模式 R (UR (U，D D，domdom，I I，F(xiàn)) F) 數(shù)據(jù)依賴：關系中屬性間互相依存、互相制約的關系。 函數(shù)依賴函數(shù)依賴、多值依賴、連接依賴、分層依賴和相互依賴第1頁/共93頁3例：例：U=學號，系部，系主任，課程名稱，成績 F=學號系部，系部 系主任, (學號，課程名稱) 成績系部系部系主任系主任成績成績 學號學號課程名稱課程名稱第2頁/共93頁43常 學號學號系部系部 系系主任主任 課程課程 名稱名稱成成績績02101CSXAAA02101CSXBBB02101CSXCCA02102MAMAAB0210

2、2MAMDDA02103MAMEEC02104ISJEEB02105ISJBBA第3頁/共93頁5一、一、 函數(shù)依賴：函數(shù)依賴： 屬性或?qū)傩越M之間可能存在的依賴性。屬性或?qū)傩越M之間可能存在的依賴性。1、定義 定義定義4.14.1：設R(U)是屬性集U上的關系模式。X，Y是U的子集。若對于R(U)的任意一個可能的關系r，當且僅當r中任意一個給定的X的值，r中存在唯一的Y值與之對應。也就是說，如果X相等，Y也相等，則稱Y函數(shù)依賴與X，或者X函數(shù)確定Y，記作XY。第4頁/共93頁6定義定義4.3：R（U）的屬性子集）的屬性子集X，Y之間的函數(shù)依賴之間的函數(shù)依賴用用X Y表示，它在構成關系表示，它在構

3、成關系R的任意元組的任意元組r上指定上指定了一個約束。這個約束是：如果對于了一個約束。這個約束是：如果對于r中的任何兩個中的任何兩個元組元組t1和和t2有有t1Xt2X，則必須也有，則必須也有t1Yt2Y。 定義定義4.2：設設R(U)是屬性集是屬性集U上的關系模式，上的關系模式，X，Y是是U的子集。若對于的子集。若對于R (U)的任意一個可能的關系的任意一個可能的關系r，r中不可能存在兩個元組在中不可能存在兩個元組在X上的屬性值相等，而在上的屬性值相等，而在Y上的屬性值不等，則稱上的屬性值不等，則稱X函數(shù)確定函數(shù)確定Y或或Y函數(shù)依賴于函數(shù)依賴于X，記作，記作XY。第5頁/共93頁7例：例：U

4、=學號，系部，系主任，課程名稱，成績 F=學號系部，系部 系主任, (學號，課程名稱) 成績注意：函數(shù)依賴不是指關系模式R的某個或某些關系滿足的條件，而是指R的一切關系均要滿足的約束條件第6頁/共93頁8第7頁/共93頁9 第8頁/共93頁10 定義定義4.5 ：完全函數(shù)依賴完全函數(shù)依賴 在在R(U)中，如果中，如果X Y，并且對于，并且對于X的的任何一個真子集任何一個真子集X，都有，都有X Y，則稱，則稱Y對對X完全函數(shù)依賴。記作：完全函數(shù)依賴。記作：FXYPXY第9頁/共93頁11定義定義4.74.7：傳遞函數(shù)依賴傳遞函數(shù)依賴 在在R(U)中，如果中，如果X Y，(Y X )，Y X，Y

5、Z，則稱，則稱Z對對X傳遞函數(shù)依賴。傳遞函數(shù)依賴。第10頁/共93頁12系部系部系主任系主任成績成績 學號學號課程名稱課程名稱第11頁/共93頁13FKU主碼：主碼：若候選碼多于一個，則選定其中的一個為主碼。主屬性：主屬性：包含在任何一個侯選碼中的屬性。非主屬性：非主屬性：不包含在任何碼中的屬性。 全碼：全碼：整個屬性組是碼。定義定義6.6:6.6: 關系模式R中屬性或?qū)傩越MX并非R的碼，但X是另一個關系模式的碼，則稱X是R的外碼外碼。主碼與外碼提供了一個表示關系間聯(lián)系的手段。主碼與外碼提供了一個表示關系間聯(lián)系的手段。第12頁/共93頁14刪除異常、冗余太大、修改復雜 學號學號系部系部 系系主

6、任主任 課程課程 名稱名稱成成績績99101CSXAAA99101CSXBBB99101CSXCCA99102MAMAAB99102MAMDDA99103MAMEEC99104ISJEEB99105ISJBBA第13頁/共93頁15系部系部系主任系主任成績成績 學號學號課程名稱課程名稱第14頁/共93頁16成績成績系部系部系主任系主任 學號，系部，系主任 學號學號 學號學號課程名稱課程名稱 學號，課程名稱，成績第15頁/共93頁17即：若R 3NF，且每一個非主屬性既不部分依賴于碼也不傳遞依賴于碼。系部系部系主任系主任 學號學號若若R 2NF，且每一個非主屬性，且每一個非主屬性不傳遞依賴于碼，

7、則不傳遞依賴于碼，則R 3NF。第16頁/共93頁18編號編號成員成員負責人負責人項目名稱項目名稱任務情況任務情況職務職務第17頁/共93頁19任務（編號，成員，任務情況）項目（編號，項目名稱，負責人，職務）編號編號成員成員任務情況任務情況編號編號負責人負責人項目名項目名稱稱職務職務任務任務項目項目第18頁/共93頁20編號編號成成 員員任務情況任務情況任務任務編號編號負責人負責人項目名項目名稱稱項目項目負責人負責人職務職務負責人職務第19頁/共93頁21第20頁/共93頁22學號課程號學號課程號姓名成績先修課程課程名系主任系部宿舍年齡班級分析函數(shù)依賴關系：判斷：屬于1NF第21頁/共93頁2

8、3成績學號+課程號姓名系部宿舍年齡班級學號系主任系部先修課程課程名課程號第22頁/共93頁24設有關系模式設有關系模式R（A，B，C，D），其），其數(shù)據(jù)依賴集：數(shù)據(jù)依賴集：F（A，B）C，CD，則關系模式，則關系模式R的規(guī)范化程度最的規(guī)范化程度最高達到（高達到（ ）。）。 第23頁/共93頁25BCNF(擴充的擴充的3NF)定義：定義：關系模式R(U，F(xiàn)) 1NF。若 XY且Y X時X必含有碼，則R(U，F(xiàn)) BCNF。即：關系模式R(U，F(xiàn)) 中，若每一個決定因素都包含碼，則R(U，F(xiàn)) BCNF。第24頁/共93頁26所有非主屬性對每一個碼都是完所有非主屬性對每一個碼都是完全函數(shù)依賴。全函

9、數(shù)依賴。所有主屬性對每一個不包含它的所有主屬性對每一個不包含它的碼也是完全函數(shù)依賴。碼也是完全函數(shù)依賴。沒有任何屬性完全函數(shù)依賴于非沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。碼的任何一組屬性。一個滿足一個滿足BCNF BCNF 的關系模式有的關系模式有: :第25頁/共93頁27第26頁/共93頁28第27頁/共93頁29消除非主屬性對碼的部分函數(shù)依賴消除非主屬性對碼的部分函數(shù)依賴消除非主屬性對碼的傳遞函數(shù)依賴消除非主屬性對碼的傳遞函數(shù)依賴消除主屬性對碼的部分和傳遞函數(shù)依賴消除主屬性對碼的部分和傳遞函數(shù)依賴1NF1NF2NF2NF3NF3NFBCNFBCNF消除消除決定決定因素因素非碼非碼

10、的非的非平凡平凡函數(shù)函數(shù)依賴依賴第28頁/共93頁30(1) R（X,Y,Z） FXY Z(2) R（X,Y,Z） FY Z, XZ Y(3) R（X,Y,Z） FY Z, Y X ,X YZ第29頁/共93頁31假設某旅館業(yè)務規(guī)定，每個賬單對應一個顧客，賬單的發(fā)票號假設某旅館業(yè)務規(guī)定，每個賬單對應一個顧客，賬單的發(fā)票號是惟一的，賬單中包含一個顧客姓名、到達日期和顧客每日的是惟一的，賬單中包含一個顧客姓名、到達日期和顧客每日的消費明細，賬單的格式如圖所示消費明細，賬單的格式如圖所示:試回答下列問題：試回答下列問題：(1)找出找出R的候選鍵。的候選鍵。(2)判斷判斷R最高可達到第幾范式，為什么最

11、高可達到第幾范式，為什么?第30頁/共93頁32配件管理關系模式配件管理關系模式 WPE（WNO，PNO，ENO，QNT）分別表）分別表倉庫號，配件號，職工號，數(shù)量。有以下條件倉庫號，配件號，職工號，數(shù)量。有以下條件 a.一個倉庫有多個職工。一個倉庫有多個職工。 b.一個職工僅在一個倉庫工作。一個職工僅在一個倉庫工作。 c.每個倉庫里一種型號的配件由專人負責，但一個人可以管理每個倉庫里一種型號的配件由專人負責，但一個人可以管理幾種配件。幾種配件。 d.同一種型號的配件可以分放在幾個倉庫中同一種型號的配件可以分放在幾個倉庫中,一個倉庫可以存放一個倉庫可以存放多種型號的配件多種型號的配件 。請問：

12、關系模式請問：關系模式WPE最高可達幾范式？最高可達幾范式？1 ENO WNO2 WNO,PNO ENO3 WNO, PNO QNT候選碼1 (WNO， PNO)為候選碼2 因為ENO，PNO WNO 所以（ ENO，PNO ）為候選碼第31頁/共93頁33例：關系模式R(U，F(xiàn))其中U(A，B，C，D，E，F(xiàn)，G) F(AB，CD，ABE，F(xiàn)G)問：F是否邏輯蘊含AE第32頁/共93頁34自反律、增廣律、傳遞律是最基本的自反律、增廣律、傳遞律是最基本的Armstrong公理。公理。第33頁/共93頁35。由自反律、增廣律、傳遞律可以導出下面三條推理規(guī)則。由自反律、增廣律、傳遞律可以導出下面三

13、條推理規(guī)則。第34頁/共93頁36例：關系模式R(U，F(xiàn))其中U(A，B，C，D，E，F(xiàn)，G) F(AB，CD，ABE，F(xiàn)G)問：F是否邏輯蘊含AE解：解： AB （已知） AAB （增廣率） ABE （已知） AE （傳遞率）第35頁/共93頁37第36頁/共93頁38定義定義 4.174.17 第37頁/共93頁39若X=A，AB，BC （已知）AC （傳遞律）AA （自反律） XF+=A，B，C若X=B，BB BC XF+=B，C若X=C，CC XF+=C第38頁/共93頁40定理定理 4.2：第39頁/共93頁41(6)若否，則i=i+1，返回第(2)步。算法算法 4.1：第40頁/共

14、93頁42找出左部為A，B或AB的函數(shù)依賴第41頁/共93頁43第42頁/共93頁44第43頁/共93頁45F+=G+的充分必要條件是F G+且G F+第44頁/共93頁46A BCF與G等價第45頁/共93頁47第46頁/共93頁48結(jié)論：結(jié)論： F與 F 等價 F是最小覆蓋，F(xiàn)不是。第47頁/共93頁49i。賴左部是否有冗余屬性賴左部是否有冗余屬性第48頁/共93頁50X(1)=BC X(2)=ABC =X+因為因為A屬于屬于X+ 所以所以BA冗余。冗余?？疾炜疾霣C：令令X=B 求求X+ = ？X(0)=B X(1)=B=X+因為因為C不屬于不屬于X+ 所以所以BC不冗余。不冗余。第49

15、頁/共93頁51F=AB，BA，BC，AC，CAF m=AB，BA，AC，CA思思考考F2=AB，BC，CA第50頁/共93頁52第51頁/共93頁53第52頁/共93頁54n 模式分解等價性的三個判定準則模式分解等價性的三個判定準則 n分解的無損連接性和函數(shù)依賴保持性分解的無損連接性和函數(shù)依賴保持性 n模式分解的算法模式分解的算法第53頁/共93頁55T#TDDHT#TDDHT1T2T3T4D1D1D2D3AAAABBCC 設一關系模式R(T#，TD，DH)，其中T#表示教師編號，TD表示教師所屬系部，DH表示系主任名。假定每位教師只能在一個系任教，每個系只有一位系主任。第54頁/共93頁5

16、6第55頁/共93頁57分解分解 1：T#T1T2T3T4R1R2TDD1D2D3R3DHAABBCC問題：T1是哪一個系的教師？無法回答。R1，R2，R3也無法恢復到原來的R。第56頁/共93頁58分解分解 2：T#T1T2T3T4R1TDD1D1D2D3T#T1T2T3T4R2DHAAAABBCC此時，R1，R2的分解是可恢復的，但仍然存在操作異常。原因：TDDH 在R1，R2中沒有體現(xiàn)。第57頁/共93頁59分解分解 3：T#T1T2T3T4R1TDD1D1D2D3TDR2DHD1D2D3AABBCC此時，R1，R2的分解是可恢復的，并且消除了操作異常。第58頁/共93頁60第59頁/共

17、93頁614.4.2 4.4.2 無損連接和函數(shù)依賴保持無損連接和函數(shù)依賴保持一、分解的無損連接性：一、分解的無損連接性： 如果一個關系模式分解后，可以通過自然如果一個關系模式分解后，可以通過自然連接恢復原模式的信息，這一特性稱為分解連接恢復原模式的信息，這一特性稱為分解的無損連接性。的無損連接性。第60頁/共93頁62Tij=aj， 如果如果AjRibij， 如果如果AjRi1) 構造一個n列k行的二維表T。=R1(U1,F1),Rk(Uk,Fk)是R(U,F)的一個分解，U=A1,An，F(xiàn)=FD1,FD2,FDp。算法算法 4.34.3 判定分解的無損連接性判定分解的無損連接性第61頁/共

18、93頁63第62頁/共93頁64例：例：已知 R(U，F(xiàn)) U=A，B，C，D，E，F(xiàn)，F(xiàn)=ABC, CD，AF，DE，DF R的一個分解為 ： =R1(A，B，C)，R2(C，D)，R3(D，E，F(xiàn)) 判斷是否具有無損連接性。第63頁/共93頁65ABCDEFa1b21b31a2b22b32a3a3b33b14a4a4b15b25a5b16b26a6第一步：建第一步：建T=R1(A，B，C) R2(C，D) R3(D，E，F(xiàn))Tij=aj， 如果如果AjRibij， 如果如果AjRi第64頁/共93頁66a4a5a5ABCDEFa1b21b31a2b22b32a3a3b33a4a4a5a6b

19、14b16b15b25b26a6a6由于沒有相同的分量，所以表不改變第65頁/共93頁67 1 T# TD DH a1 b12 b13 b21 a2 b23 b31 b32 a3具有無損連接性具有無損連接性 2T# TD DH a1 a2 b13 a1 b22 a3 3 T# TD DH a1 a2 b13 b21 a2 a3具有無損連接性具有無損連接性第66頁/共93頁68 設有關系模式R(B,O,I,S,Q,D)，其函數(shù)依賴集為： F=SD,IB,ISQ,BO,如果將R分解為R1=SD,R2=IB,R3=ISQ,R4=BO,這樣的分解是否具有無損連接性？第67頁/共93頁69BOISQDS

20、Db11b12b13a4b15a6IBa1b22a3b24b25b26ISQb31b32a3a4a5b36BOa1a2b43b44b45b46第68頁/共93頁70BOISQDSDa4a6IBa1a3ISQa1a2a3a4a5a6BOa1a2F=SD,IB,ISQ,BO第69頁/共93頁71 設設=R1，R2是關系模式是關系模式R的一個分解，的一個分解，F(xiàn)是是R的一個函數(shù)依賴集，則對于的一個函數(shù)依賴集，則對于F，具有具有連接不失真性的充分必要條件是：連接不失真性的充分必要條件是： R1R2R1-R2F+ 或或 R1R2R2-R1F+。定理定理4.4:4.4: 第70頁/共93頁72( )RiF

21、( )ZF第71頁/共93頁73i=1k(Fi)i=1k(Fi)+第72頁/共93頁74第73頁/共93頁75第74頁/共93頁76 設有R（U，F(xiàn)），其中， U=A，B，C，D，F(xiàn)，F(xiàn)= AC， BC，CD， DFC， CFA ，R的一個分解為：R1=AB，R2=AD，R3=AF，R4=BF，R5=CDF，判斷該分解是否具有函數(shù)依賴保持性。 第75頁/共93頁77算法算法4.54.5： 結(jié)果為結(jié)果為3 3NFNF的依賴保持分解算法的依賴保持分解算法 如果如果R R中有某些屬性與中有某些屬性與F F的最小覆蓋中的每個依賴的左邊和的最小覆蓋中的每個依賴的左邊和右邊都無關，原則上可由這些屬性構成一

22、個關系模式，并從右邊都無關，原則上可由這些屬性構成一個關系模式，并從R R中將它們消除；否則，中將它們消除；否則， 如果如果FF中有一個依賴涉及到中有一個依賴涉及到R R的所有屬性，則輸出的所有屬性，則輸出R R；否否則，則， 輸出一個分解輸出一個分解 ，它由模式，它由模式XAXA組成，其中組成，其中XA XA F 。但。但當當XA1XA1，XA2XA2，XAn XAn 均屬于均屬于FF時，則用模式時，則用模式XA1 XA1 A2AnA2An代替代替XAiXAi（i=1i=1，2 2，n n）。）。第76頁/共93頁78舉舉 例例第77頁/共93頁79舉舉 例例 1 求求F的最小覆蓋的最小覆蓋

23、FmBC AE, AF , FG， CD2 條件（條件（1）不滿足）不滿足 3 條件（條件（2）不滿足）不滿足 4 根據(jù)條件（根據(jù)條件（3）輸出）輸出 =BCAE,AF,FG,CD第78頁/共93頁80算法算法4.64.6： 結(jié)果為結(jié)果為3 3NFNF的依賴保持和連接不失真分解的依賴保持和連接不失真分解 設是由結(jié)果為設是由結(jié)果為3NF3NF的依賴保持分解算法得到的的依賴保持分解算法得到的3NF3NF分解，分解，X X為為R R的一個候選關鍵字，則的一個候選關鍵字，則=X=X是是R R的一的一個分解，且中的所有關系模式均滿足個分解，且中的所有關系模式均滿足3NF3NF，同時，既，同時，既具有連接

24、不失真性，又具有依賴保持性。具有連接不失真性，又具有依賴保持性。第79頁/共93頁81 對于給定的關系對于給定的關系R R（A1A1，A2A2，AnAn）和函數(shù)）和函數(shù)依賴集依賴集F F，可將其屬性分為，可將其屬性分為4 4類：類：n L L類類 僅出現(xiàn)在僅出現(xiàn)在F F的函數(shù)依賴左部的屬性的函數(shù)依賴左部的屬性n R R類類 僅出現(xiàn)在僅出現(xiàn)在F F的函數(shù)依賴右部的屬性的函數(shù)依賴右部的屬性n N N類類 在在F F的函數(shù)依賴左右兩邊均未出現(xiàn)的屬的函數(shù)依賴左右兩邊均未出現(xiàn)的屬性性n LRLR類類 在在F F的函數(shù)依賴左右兩邊均出現(xiàn)的屬性的函數(shù)依賴左右兩邊均出現(xiàn)的屬性第80頁/共93頁82定理定理1

25、對于給定的關系對于給定的關系模式模式R R及其函數(shù)依賴及其函數(shù)依賴集集F F，若，若X X（XRXR）是）是L L類屬性，則類屬性，則X X必是必是R R的候選碼的成員。的候選碼的成員。定理定理3 對于給定的關系模式對于給定的關系模式R R及其函數(shù)依賴集及其函數(shù)依賴集F F，若，若X X（XRXR）是）是R R類屬性，則類屬性，則X X不在任何候選碼中。不在任何候選碼中。定理定理2 對于給定的關系模對于給定的關系模式式R R及其函數(shù)依賴集及其函數(shù)依賴集F F，若若X X（XRXR）是）是NN類屬類屬性，則性，則X X必是必是R R的候選碼的候選碼的成員。的成員。第81頁/共93頁83候選碼求解

26、推論候選碼求解推論 對于給定的關系模式對于給定的關系模式R R及其函數(shù)依賴集及其函數(shù)依賴集F F，若若X X（XRXR）是）是R R的的L L類或類或N N類屬性組成的屬性集，類屬性組成的屬性集，且且X X包含了包含了R R的全部屬性，則的全部屬性，則X X是是R R的唯一候選的唯一候選碼。碼。第82頁/共93頁84設有關系模式R（A，B，C，D，E，P），R的函數(shù)依賴集為：FAD,ED,DB,BC D,DC A,求R的候選碼。舉例舉例：因為因為 CC，E E是是L L類屬性，類屬性，P P是是N N類屬性，所以類屬性，所以CEPCEP包含在所有候選碼中；包含在所有候選碼中；因為因為 （CEP

27、CEP）ABCDEPABCDEP；所以所以 CEPCEP是是R R的唯一候選碼。的唯一候選碼。第83頁/共93頁85舉舉 例例第84頁/共93頁86 1 求求F的最小覆蓋的最小覆蓋FmBC AE, AF , FG， CD2 R的滿足的滿足3NF且函數(shù)依賴保持的分且函數(shù)依賴保持的分解為：解為： =BCAE,AF,FG,CD 3 R的候選碼為：的候選碼為：BC 4 R的滿足的滿足3NF且函數(shù)依賴保持和無且函數(shù)依賴保持和無損連接的分解為：損連接的分解為： =BCAE,AF,FG,CD第85頁/共93頁87舉舉 例例第86頁/共93頁88第一步：求最小函數(shù)依賴集第一步：求最小函數(shù)依賴集FmFm=C B,E D,D B,B D,DC A第二步：求基于第二步：求基于3NF的函數(shù)依賴保持的分解的函數(shù)依賴保持的分解=CB,ED,DB,DCA第三步：求候選碼第三步：求候選碼XX=CEP第四步第四步:求基于求基于3NF的函數(shù)依賴保持和連接不失真的分解的函數(shù)依賴保持和連接不失