數(shù)據(jù)庫系統(tǒng)概論(六)

1、第六章 關(guān)系數(shù)據(jù)理論問題：給出一組數(shù)據(jù)，如何構(gòu)造一個(gè)適合于 它們的數(shù)據(jù)模型？ 6.1 數(shù)據(jù)依賴（理論核心） 6.2 規(guī)范化 6.3 關(guān)系框架的分解 8/13/202216.1 數(shù)據(jù)依賴關(guān)系模型的形式化定義（規(guī)范化理論的背景）數(shù)據(jù)依賴 函數(shù)依賴（FD）8/13/20222關(guān)系模型的形式化定義1、關(guān)系模型的五元組定義：R R 關(guān)系名，U 屬性組，D 域，DOM 映射（屬性與域之間的聯(lián)系），F(xiàn) 數(shù)據(jù)依賴（屬性與屬性之間的聯(lián)系）2、關(guān)系模型的三元組定義：R 當(dāng)且僅當(dāng) U 上的一個(gè)關(guān)系 r 滿足 F 時(shí)，r 稱為關(guān)系模式R的一個(gè)關(guān)系。8/13/20223數(shù)據(jù)依賴1、定義 數(shù)據(jù)依賴是通過一個(gè)關(guān)系中屬性間值

2、的相等與否體現(xiàn)出來的數(shù)據(jù)間的相互關(guān)系，它是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象。2、種類 函數(shù)依賴 數(shù)據(jù)依賴 多值依賴 連接依賴8/13/20224函數(shù)依賴的定義 設(shè)R(U)是屬性集U上的關(guān)系模式。X，Y是U的子集。對于R(U)的任意一個(gè)可能的關(guān)系r，如果r中不存在兩個(gè)元組，它們在X上的屬性值相等，而在Y上的屬性值不等，則稱“X函數(shù)確定Y”或“Y函數(shù)依賴于X”，記作XY。 X稱為這個(gè)函數(shù)依賴的決定屬性集。學(xué)號姓名學(xué)號年齡學(xué)號性別學(xué)號籍貫具體關(guān)系的函數(shù)依賴關(guān)系框架的函數(shù)依賴8/13/20225完全依賴 在R(U)中，如果XY，并且對于X的任何一個(gè)真子集X都有XY，則稱Y對X完全依賴，記作X Y。 部分依

3、賴 若XY但Y不完全依賴于X，則稱Y對X部分函數(shù)依賴，記作X Y。 傳遞依賴 在R(U)中，如果XY，YZ，且YX，ZY，YX，則稱Z對X傳遞依賴。記作X Z。 fp函數(shù)依賴的種類傳遞SC ( SNO , CNO , SD , Grade )8/13/20226課堂練習(xí)已知關(guān)系模式SLC（S#，SD，SL，C#，G）， 學(xué)號 系 住址 課程號 成績規(guī)定每個(gè)系的學(xué)生只住一個(gè)地方，寫出關(guān)系模式中的所有函數(shù)依賴。S#SD， SDSL， S# SL，(S#,C#)G，(S#,C#)SD，(S#,C#)SLfpp傳遞8/13/20227公理F1（自反性）：若XY，則 XY 或 XX。F2（增廣性）：若X

4、Y，則 XZYZ 或 XZY。F3（傳遞性）：若XY，YZ，則 XZ。推理規(guī)則F4（偽增性）：若XY，WZ，則 XWYZ。F5（偽傳性）：若 XY，YWZ，則 XWZ。F6（合成性）：若 XY，XZ，則 XYZ。F7（分解性）：若 XYZ，則 XY，XZ。 FD公理及推理規(guī)則8/13/20228課堂練習(xí)1、已知關(guān)系框架R（A，B，C，D，E，P）及其上的函數(shù)依賴集合F= AB，CP，EA，CED ，則R的候選碼是（ ）。AC BC CE CD2、給定關(guān)系框架R（A，B，C，D ，E）及其上的函數(shù)依賴集合F= CDA，BC，DE ，則R的候選碼是（ ）。CD BC BD AE3、設(shè)關(guān)系框架R上的

5、函數(shù)依賴集合F= BD，CAE ，則利用FD公理和規(guī)則可推出（ ）。CBB EAD DAB ABAD4、已知關(guān)系模式r（a，b，c，d，e）及其上的函數(shù)相關(guān)性集合fad，bc ，ea ，該關(guān)系模式的候選關(guān)鍵字是（ ） 。 A.ab B. be C.cd D. de8/13/202296.2 規(guī)范化 【目的】通過研究關(guān)系之間的等價(jià)問題，找出一些方法來指導(dǎo)我們定義數(shù)據(jù)庫的邏輯結(jié)構(gòu)，使其具有好的性能（冗余小、數(shù)據(jù)完整性好、操作方便）。 關(guān)系模型評價(jià) 范式 規(guī)范化小結(jié)8/13/202210關(guān)系模型評價(jià)存在的問題(1) 冗余度高(2) 修改困難(3) 插入異常(4) 刪除異常問題的原因 關(guān)系中存在多余

6、的數(shù)據(jù)依賴， 不規(guī)范。OF240ZHOU90C1S4OF347WANG56C4S3OF235LIU70C2S3OF240ZHOU75C1S3OF240ZHOU90C1S2OF347WANG87C4S1OF235LIU85C3S1OF235LIU90C2S1OF240ZHOU90C1S1OFFICETAGETNAMEGRADEC-NOS-NOSCT關(guān)系8/13/202211解決問題的辦法將關(guān)系規(guī)范化關(guān)系規(guī)范化定義通常將結(jié)構(gòu)較簡單的關(guān)系取代結(jié)構(gòu)較復(fù)雜的關(guān)系的過程稱為關(guān)系的規(guī)范化。8/13/202212范式范式表示符合某一種級別的關(guān)系模式的集合。 R為第幾范式寫成RxNF。范式的概念是由Codd給出

7、的，并在19711972年提出了1NF、2NF、3NF的概念，1974年Codd和Boyce又共同提出了BCNF的概念，1976年Fagin又提出了4NF，后來又有人提出了5NF。對于各種范式之間的聯(lián)系是： 5NF 4NF BCNF 3NF 2NF 1NF。一個(gè)低一級范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個(gè)高一級范式的關(guān)系模式的集合，這種過程就叫規(guī)范化。8/13/202213關(guān)系的屬性是原子的（不可分的），這樣的關(guān)系模式就屬于1NF。 1NF示例： R（S_NO，C_NO，GRADE，TNAME，TAGE，OFFICE）; F = (S_NO,C_NO)GRADE, C_NOTNAME,T

8、NAMETAGE,TNAMEOFFICE ;則R1NF8/13/2022148/13/2022152NF若R1NF，且每個(gè)非主屬性完全函數(shù)依賴于關(guān)鍵字，則R2NF。示例： R（S_NO，C_NO，GRADE，TNAME，TAGE，OFFICE）; F = (S_NO,C_NO)GRADE, C_NOTNAME, TNAMETAGE, TNAMEOFFICE ;請問R2NF？分解： SC（S_NO，C_NO，GRADE） CTO（C_NO，TNAME，TAGE，OFFICE） FSC = (S_NO,C_NO)GRADE FCTO = C_NOTNAME, TNAMETAGE, TNAMEOFF

9、ICE ;8/13/2022163NF若R2NF，且R的每個(gè)非主屬性都不傳遞依賴于關(guān)鍵字，則R3NF。示例： SC（S_NO，C_NO，GRADE） CTO（C_NO，TNAME，TAGE，OFFICE） FSC = (S_NO,C_NO)GRADE FCTO = C_NOTNAME, TNAMETAGE, TNAMEOFFICE 請問SC3NF？CTO3NF？分解： SC（S_NO，C_NO，GRADE）FSC = (S_NO,C_NO)GRADE CT（C_NO，TNAME）FCT = C_NOTNAME TO（TNAME，TAGE，OFFICE）FTO=TNAMETAGE,TNAMEOF

10、FICE8/13/202217BCNFR1NF，若XY且YX時(shí)X必含有關(guān)鍵字，則RBCNF。一個(gè)滿足BCNF的關(guān)系框架R：所有非主屬性對每一候選關(guān)鍵字都是完全依賴；所有主屬性對每一不包含它的候選關(guān)鍵字也是完全依賴；沒有任何屬性完全依賴于非候選關(guān)鍵字的任何一組屬性。消除了主屬性對候選關(guān)鍵字的部分依賴和傳遞依賴。 S-NONAMEC-NOGRADES1WANGC190S1WANGC290S1WANGC385S2LIC190S3CHENC175S3CHENC270分析：此關(guān)系有兩個(gè)候選關(guān)鍵字(S-NO,C-NO)(NAME,C-NO)而S-NONAME因此RBCNF8/13/202218規(guī)范化小結(jié)1

11、、規(guī)范化的基本思想 逐步消除數(shù)據(jù)依賴中不合適的部分，使模式中的各關(guān)系模式達(dá)到某種程度的“分離”，即“一事一地”的模式設(shè)計(jì)原則。讓一個(gè)關(guān)系描述一個(gè)概念、一個(gè)實(shí)體或者實(shí)體間的一種聯(lián)系。若多于一個(gè)概念就把它分離出去。 所謂規(guī)范化實(shí)質(zhì)上是概念的單一化。2、規(guī)范化的過程 關(guān)系模式的規(guī)范化的過程是通過對關(guān)系模式的分解來實(shí)現(xiàn)的。 8/13/202219非規(guī)范化關(guān)系 消除所有非平坦的數(shù)據(jù)結(jié)構(gòu) 消除非主屬性對關(guān)鍵字的部分函數(shù)依賴 消除非主屬性對關(guān)鍵字的傳遞函數(shù)依賴 消除主屬性對關(guān)鍵字的部分和傳遞函數(shù)依賴 1NF 2NF 3NF BCNF 8/13/202220課堂練習(xí)1、給定關(guān)系r如圖所示， r 最高是（ ）的

12、。 1NF 2NF 3NF BCNF 2、設(shè)有關(guān)系框架R（A，B，C，D）及其上的函數(shù)依賴集合F=AB，AC，DA，那么該關(guān)系框架R最高是（ ）的。1NF 2NF 3NF BCNFABCb5bd5ba4ce2c8/13/202221課堂練習(xí)3、設(shè)學(xué)生關(guān)系s（sno，sname，ssex，sage，sdpart）的主鍵為sno，學(xué)生選課關(guān)系sc（sno，cno，score）的主鍵為sno和cno，則關(guān)系r（sno，cno，ssex，sage，sdpart，score）的主鍵為sno和cno，其滿足（ ）。 a. 1nf b.2nf c. 3nf d. bcnf 8/13/2022226.3 關(guān)系

13、框架的分解 R（S_NO,C_NO,GRADE,TNAME,TAGE,OFFICE）F = (S_NO,C_NO)GRADE, C_NOTNAME, TNAMETAGE, TNAMEOFFICE 1=SC, CT, TO SC（S_NO,C_NO,GRADE）, CT（C_NO,TNAME）, TO（TNAME,TAGE,OFFICE）2=SC,GT,CO； SC（S_NO,C_NO,GRADE）, GT（GRADE, TNAME）， CO（C_NO,TAGE,OFFICE）3=SC,GTO； SC（S_NO,C_NO,GRADE）, GTO（GRADE, TNAME,TAGE,OFFICE）

14、 無損分解的定義 關(guān)系框架分解準(zhǔn)則 無損分解的判別算法8/13/202223一、無損分解的定義=R1，Rk是R的一個(gè)分解，若對R的任何一個(gè)關(guān)系r均有r = Ri(r)成立，則稱分解具有無損連接性。簡稱為無損分解。i=1k8/13/202224二、關(guān)系框架分解準(zhǔn)則分解既要“保持函數(shù)依賴”，又要是“無損分解”。已知關(guān)系 R 分解一：1= R1 , R2, R3 R1 R2 R3后元組增加了，有損；丟失函數(shù)依賴。分解二：2= R1 , R2 R1 R2無損，但丟失了函數(shù)依賴，存在插入、刪除異常。分解三：3= R1 , R2 R1 R2無損且保持函數(shù)依賴。8/13/202225三、無損分解的判別算法輸

15、入： 關(guān)系框架R(A1,A2,Ak)， 函數(shù)依賴集合F， R的一個(gè)分解 = R1 ，Rn。輸出：是否為無損分解。示例： R（S_NO,C_NO,GRADE,TNAME,TAGE,OFFICE）; F = (S_NO,C_NO)GRADE, C_NOTNAME, TNAMETAGE, TNAMEOFFICE ; 1= SC, CT, TO； SC（S_NO,C_NO,GRADE）, CT（C_NO,TNAME）, TO（TNAME,TAGE,OFFICE）。8/13/202226構(gòu)造一個(gè)n行k列的表，其中第i行對應(yīng)于子框架Ri，第j列對應(yīng)于R的屬性Aj，這種表稱為R表，表中的第i行第j列處的元素

16、應(yīng)這樣填入：如果Aj是子框架Ri的屬性，則在第i行第j列處填上符號aj，否則填上符號bij。RnTijRiR1AkAjA1RS_NO C_NO GRADE TNAME TAGE OFFIGE SC CT TO 1的初始R表 a1 a2 a3 b14 b15 b16 b21 a2 b23a4 b25 b26 b31 b32 b33a4 a5 a68/13/202227填好R表后，根據(jù)F中的函數(shù)依賴對它進(jìn)行修改：取F中的某一函數(shù)依賴XY，在表中尋找對應(yīng)于X中所有屬性的分量相同的行，然后將這些行對應(yīng)于Y中所有屬性的分量也都改為一致。對F中的所有函數(shù)依賴重復(fù)執(zhí)行第二步，直至無新的修改為止。修改1的初始

17、R表S_NO C_NO GRADE TNAME TAGE OFFIGE SC a1 a2 a3 b14 b15 b16 CT b21 a2 b23a4 b25 b26 TO b31 b32 b33a4 a5 a6F = (S_NO,C_NO)GRADE, C_NOTNAME, TNAMETAGE, TNAMEOFFICE ; a4 a5 a5 a6 a68/13/202228若R表中某一行的結(jié)果為a1a2 ak，則分解是無損分解；否則不是無損分解。S_NO C_NO GRADE TNAME TAGE OFFIGE SC a1 a2 a3 a4 a5 a6 CT b21 a2 b23a4 a5

18、a6 TO b31 b32 b33a4 a5 a6判斷：修改后第一行是全a, 因此1是無損分解。8/13/202229課堂練習(xí)R（S_NO,C_NO,GRADE,TNAME,TAGE,OFFICE）;F = (S_NO,C_NO)GRADE, C_NOTNAME, TNAMETAGE, TNAMEOFFICE ;2=SC,GT,CO；SC（S_NO,C_NO,GRADE）, GT（GRADE, TNAME），CO（C_NO,TAGE,OFFICE）S_NO C_NO GRADE TNAME TAGE OFFIGE SC a1 a2 a3 b14 b15 b16 GT b21 b22 a3 a4

19、 b25 b26 CO b31 a2 b33 b34 a5 a6 2的初始R表8/13/202230思考題1、設(shè)有關(guān)系模式w（c，p，s，g，t，r），其數(shù)據(jù)依賴集：d= cp，（s，c）g，（t，r）c，（t，p）r，（t，s）r ，若將關(guān)系模式w分解為三個(gè)關(guān)系模式w1（c，p），w2（s，c，g），w2（s，t，r，c），則w1的規(guī)范化程序最高達(dá)到（ ） 。 A. 1NF B.2NF C. 3NF D. BCNF 8/13/202231思考題1、舉例說明關(guān)系框架上的函數(shù)依賴與具體關(guān)系的函數(shù)依賴的區(qū)別。2、試述如何將一個(gè)非規(guī)范化的關(guān)系轉(zhuǎn)換成一組符合BCNF的關(guān)系的集合。 3、現(xiàn)有如下關(guān)系模式：R( A，