數(shù)據(jù)庫(kù)課件第6章關(guān)系數(shù)據(jù)理論.ppt

1、4.關(guān)系模式的規(guī)范化,2.范式的定義和分類,3.關(guān)系模式所屬范式類型的判別,本次課內(nèi)容,1.關(guān)系模式中的函數(shù)依賴,例：學(xué)校數(shù)據(jù)庫(kù)的語(yǔ)義： 一個(gè)系有若干學(xué)生， 一個(gè)學(xué)生只屬于一個(gè)系，學(xué)號(hào)唯一，姓名可能重名； 一個(gè)系只有一名系主任，系名不重復(fù)，系主任可能重名； 一個(gè)學(xué)生可以選修多門課程， 每門課程有若干學(xué)生選修； 每個(gè)學(xué)生所學(xué)的每門課程都有一個(gè)成績(jī)，課程號(hào)唯一，課程名不排除相同情況。,根據(jù)語(yǔ)義，有如下函數(shù)依賴：,學(xué)生(學(xué)號(hào), 姓名, 系名, 系主任, 課程號(hào),課程名, 分?jǐn)?shù)),假設(shè)某個(gè)人根據(jù)上述語(yǔ)義設(shè)計(jì)了如下關(guān)系模式:,學(xué)號(hào)姓名,學(xué)號(hào)系名,系名系主任, (學(xué)號(hào),課程號(hào)) 分?jǐn)?shù),課程號(hào)課程名,學(xué)生(

2、學(xué)號(hào), 姓名, 系名, 系主任, 課程號(hào),課程名, 分?jǐn)?shù)),關(guān)系模式R(U)， U 是R的屬性集合，X、Y、Z是U的子集，X是X的任意真子集。 1.完全函數(shù)依賴：X Y， X Y，則 X Y。,關(guān)系模式R(U)， U 是R的屬性集合，X、Y、Z是U的子集，X是X的任意真子集。 2.部分函數(shù)依賴： X Y，存在一個(gè) X Y， X P Y 。,關(guān)系模式R(U)， U 是R的屬性集合，X、Y、Z是U的子集，X是X的任意真子集。 3.傳遞函數(shù)依賴： XY，YZ，且Y X，Y X，則XZ ,稱Z傳遞函數(shù)依賴于X。,1.范式,范式(Normal Form, NF)：關(guān)系模式的規(guī)范形式。是符合某一種級(jí)別的關(guān)

3、系模式的集合。,規(guī)范化目的：逐漸消除異常,減少冗余。,規(guī)范化方法：一般采用分解的辦法，將低級(jí)別范式向高級(jí)別范式轉(zhuǎn)化，使關(guān)系的語(yǔ)義單純化。,規(guī)范化：將一個(gè)給定的關(guān)系模式轉(zhuǎn)化為某種級(jí)別范式的過(guò)程稱為關(guān)系模式的規(guī)范化過(guò)程，簡(jiǎn)稱規(guī)范化。,2.規(guī)范化,定義：如果一個(gè)關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項(xiàng)，則稱該關(guān)系模式為第一范式關(guān)系模式，記作R1NF。,(1)第一范式（1NF）,以函數(shù)依賴為基礎(chǔ)的范式種類：第一范式、第二范式、第三范式和BCNF范式。,3.以函數(shù)依賴為基礎(chǔ)的范式,非第一范式的關(guān)系轉(zhuǎn)換為1NF關(guān)系：將復(fù)合屬性變?yōu)楹?jiǎn)單屬性即可。,學(xué) 生,學(xué)生(學(xué)號(hào), 姓名, 系名, 系主任, 課程號(hào),課

4、程名, 分?jǐn)?shù)),a.插入情況:若要插入一個(gè)沒(méi)選課的學(xué)生,能插入嗎?,X,結(jié)論:存在插入異常,b.刪除情況:,如某學(xué)生只選了一門課，如果要?jiǎng)h除學(xué)生的該門選課，則會(huì)出現(xiàn)什么后果?,結(jié)論:存在刪除異常,c.冗余情況:,結(jié)論:冗余度大,d.更新情況：如果某學(xué)生要轉(zhuǎn)系,要修改那些數(shù)據(jù)?,可見(jiàn)：滿足1NF是不夠的，它可能出現(xiàn)插入、刪除和更新異常,冗余度也大。 原因:因?yàn)榭赡艽嬖凇安糠趾瘮?shù)依賴”與“傳遞函數(shù)依賴”。,2NF實(shí)質(zhì)：不存在非主屬性“部分函數(shù)依賴”于碼的情況。,定義 若關(guān)系模式R1NF，并且每一個(gè)非主屬性都完全函數(shù)依賴于R的碼，則稱該關(guān)系模式為第二范式關(guān)系模式則記作R2NF,(2)第二范式（2NF

5、）,示例：,學(xué)生(學(xué)號(hào), 姓名, 系, 系主任, 課程號(hào),課程名, 分?jǐn)?shù)),1NF關(guān)系向2NF的轉(zhuǎn)換：消除其中的部分函數(shù)依賴，一般是將一個(gè)關(guān)系模式分解成多個(gè)2NF的關(guān)系模式。即：將部分函數(shù)依賴于碼的非主屬性及其決定屬性移出，另成一關(guān)系，使其滿足2NF。,(1) 學(xué)生信息(學(xué)號(hào), 姓名, 系名, 系主任),(2) 修課 (學(xué)號(hào),課程號(hào),分?jǐn)?shù)),(3) 課程 (課程號(hào),課程名),上述“學(xué)生”關(guān)系模式分解成如下三個(gè)關(guān)系模式:,異常情況分析：,學(xué)生,修課,課程,b.刪除情況：如某學(xué)生只選了一門課，如果要?jiǎng)h除學(xué)生的該門選課，則會(huì)出現(xiàn)什么后果?,a.插入情況:若要插入一個(gè)沒(méi)選課的學(xué)生,能插入嗎?,c.冗余

6、情況:,d.更新情況：如果某學(xué)生要轉(zhuǎn)系,要修改那些數(shù)據(jù)?,能,學(xué)生、系的信息仍可保留,減少了，但仍存在,只需修改一次 但如果要更換系主任，則要修改多條記錄,2NF判斷: 語(yǔ)義:一個(gè)國(guó)家可參加多項(xiàng)比賽,一個(gè)比賽項(xiàng)目有多個(gè)國(guó)家參加,關(guān)系模式如下: 比賽(國(guó)家名稱,參賽項(xiàng)目名稱,項(xiàng)目得分, 總分),2NF關(guān)系可能的異常：仍可能存在插入異常、刪除異常、更新異常和冗余。因?yàn)?，還可能存在非主屬性對(duì)碼的“傳遞函數(shù)依賴”。,3NF的得來(lái)： 3NF是從1NF消除非主屬性對(duì)碼的部分函數(shù)依賴和從2NF消除非主屬性對(duì)碼的傳遞函數(shù)依賴而得到的關(guān)系模式。,定義：若關(guān)系模式R是2NF，而且它的任何一個(gè)“非主屬性”都不傳遞函

7、數(shù)依賴于R的碼，則稱該關(guān)系模式為第三范式關(guān)系模式，記作3NF。,(3)第三范式（3NF）,學(xué)生(學(xué)號(hào), 姓名, 系名, 系主任),示例：,(1) 學(xué)生信息(學(xué)號(hào), 姓名, 系名, 系主任),(2) 修課 (學(xué)號(hào),課程號(hào),分?jǐn)?shù)),(3) 課程 (課程號(hào),課程名),上述三個(gè)關(guān)系模式中，存在非主屬性對(duì)碼的傳遞函數(shù)依賴的關(guān)系模式是：,2NF關(guān)系向3NF的轉(zhuǎn)換：消除傳遞函數(shù)依賴，將2NF關(guān)系分解成多個(gè)3NF關(guān)系模式。,(1) 學(xué)號(hào) (學(xué)號(hào), 姓名, 系名),(2) 系 (系名, 系主任),例題分析: 1、工人(工號(hào),姓名,工種,定額,車間,車間主任) 若有如下函數(shù)依賴:,工號(hào)姓名,工號(hào)工種,工種定額,工

8、號(hào)車間,車間車間主任,2.比賽(球隊(duì),比賽場(chǎng)次,得分) 函數(shù)依賴情況: 3.假設(shè)一個(gè)帳號(hào)一天只能取一次款,那么關(guān)系模式: 取款(日期,帳號(hào),取款金額,取款身份證號(hào)),其中的函數(shù)依賴有：,3NF異常示例： 每一教師只教一門課,每門課有若干教師,某一學(xué)生選定了某門課，就對(duì)應(yīng)一個(gè)固定的教師。,(學(xué)號(hào),課程號(hào))教師號(hào), (學(xué)號(hào),教師號(hào))課程號(hào), 教師號(hào)課程號(hào),STC (學(xué)號(hào), 教師號(hào), 課程號(hào)),STC,(學(xué)號(hào),課程號(hào))教師號(hào), (學(xué)號(hào),教師號(hào))課程號(hào), 教師號(hào)課程號(hào),STC,(學(xué)號(hào),課程號(hào))教師號(hào), (學(xué)號(hào),教師號(hào))課程號(hào), 教師號(hào)課程號(hào),a.插入異常分析：插入尚未選課的學(xué)生時(shí)，能否插入?或 插入沒(méi)

9、有學(xué)生選課的課程時(shí)，能否插入? 都不能,STC,(學(xué)號(hào),課程號(hào))教師號(hào), (學(xué)號(hào),教師號(hào))課程號(hào), 教師號(hào)課程號(hào),b.刪除異常分析：如選修某課程的學(xué)生全畢業(yè)，刪除學(xué)生則會(huì)刪除課程的信息。,STC,(學(xué)號(hào),課程號(hào))教師號(hào), (學(xué)號(hào),教師號(hào))課程號(hào), 教師號(hào)課程號(hào),c.冗余：每個(gè)選修某課程的學(xué)生均帶有教師的信息，故冗余。,STC,(學(xué)號(hào),課程號(hào))教師號(hào), (學(xué)號(hào),教師號(hào))課程號(hào), 教師號(hào)課程號(hào),d.更新異常：如教師所教的課程變更了,則修改某門課程對(duì)應(yīng)的教師信息，則要修改多行。,可見(jiàn)：3NF關(guān)系可能的異常仍可能存在插入異常、刪除異常、更新異常和冗余。因?yàn)?，還可能存在“主屬性”“部分函數(shù)依賴”于碼。,

10、定義：若關(guān)系模式R是1NF，如果對(duì)于R的每個(gè)函數(shù)依賴XY，X必為候選碼，則R為BCNF范式（Boyce-Codd Normal Form, BCNF）。,每個(gè)BCNF范式具有的三個(gè)性質(zhì)： a. 所有非主屬性都完全函數(shù)依賴于每個(gè)候選碼； b. 所有主屬性都完全函數(shù)依賴于每個(gè)不包含它的候選 碼； c. 沒(méi)有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。,提出：由Boyce和Codd提出，故稱BCNF范式。亦被認(rèn)為是增強(qiáng)的第三范式，有時(shí)也歸入第三范式。,(4)BCNF范式,說(shuō)明：,由于BCNF的每一個(gè)非平凡函數(shù)依賴的決定因素必為候選碼，故不會(huì)出現(xiàn)3NF中決定因素可能不是候選碼的情況。 3NF不一定是BC

11、NF，而B(niǎo)CNF一定是3NF。 不過(guò)，屬于3NF而非BCNF的關(guān)系模式不多，即使有，對(duì)數(shù)據(jù)庫(kù)設(shè)計(jì)者來(lái)說(shuō)，所引起的更新異常也不太重要。,3NF和BCNF常常都是數(shù)據(jù)庫(kù)設(shè)計(jì)者所追求的關(guān)系范式。有些文獻(xiàn)有時(shí)統(tǒng)稱它們?yōu)榈谌妒?，只要不引起誤解。 如果一個(gè)關(guān)系數(shù)據(jù)庫(kù)的所有關(guān)系模式都屬于BCNF，那么，在函數(shù)依賴范疇內(nèi)，它已達(dá)到了最高的規(guī)范化程度(但不是最完美的范式)，在一定程度上已消除了插入和刪除的異常。,3NF關(guān)系向BCNF的轉(zhuǎn)換：消除那些決定因素不是候選碼的函數(shù)依賴，即可將3NF關(guān)系分解成多個(gè)BCNF關(guān)系模式。,ST (學(xué)號(hào),教師號(hào)),示例：,TC (教師號(hào),課程號(hào)),關(guān)系模式STC (學(xué)號(hào), 教師

12、號(hào), 課程號(hào)) 可分解為下列兩個(gè)關(guān)系模式：,范式級(jí)別與異常問(wèn)題之關(guān)系：一般，級(jí)別越低，出現(xiàn)異 地常的程度越高, 范式不一定越高就越好,設(shè)計(jì)中一般達(dá)到3NF或BCNF即可。,范式之間存在的關(guān)系：,關(guān)系模式中的范式：1NF、2NF、3NF、BCNF、4NF和5NF。,6.2.7 多值依賴與第四范式（4NF）,例: 學(xué)校中某一門課程由多個(gè)教師講授，他們使用相同的一套參考書。每個(gè)教師可講授多門課,每種參考書可以供多門課使用。 關(guān)系模式Teaching(課程,教師,參考書),表6.3,用二維表表示Teaching,TeachingBCNF: Teaching具有唯一候選碼(課程,教師,參考書)， 即全碼

13、 Teaching模式中存在的問(wèn)題 (1)數(shù)據(jù)冗余度大：有多少名任課教師，參考書就要存儲(chǔ)多少次,Teaching,(2)插入操作復(fù)雜：當(dāng)某一課程增加一名任課教師時(shí)，該課程有多少本參照書，就必須插入多少個(gè)元組 例如物理課增加一名教師劉關(guān)，需要插入三個(gè)元組： （物理，劉關(guān)，普通物理學(xué)） （物理，劉關(guān)，光學(xué)原理） （物理，劉關(guān)，物理習(xí)題集）,Teaching,t,s,v,w,(3) 刪除操作復(fù)雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個(gè)元組 (4) 修改操作復(fù)雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個(gè)元組 產(chǎn)生原因 存在多值依賴,一、多值依賴,定義5.1

14、0 設(shè)R(U)是一個(gè)屬性集U上的一個(gè)關(guān)系模式， X、 Y和Z是U的子集，并且ZUXY，多值依賴 XY成立當(dāng)且僅當(dāng)對(duì)R的任一關(guān)系r，r在（X，Z）上的每個(gè)值對(duì)應(yīng)一組Y的值，這組值僅僅決定于X值而與Z值無(wú)關(guān) 例 Teaching（課程,教師,參考書） 對(duì)于課程(X)和參考書(Z)的每一個(gè)值，教師(Y)有一組值與之對(duì)應(yīng)，這組值與參考書(Z)無(wú)關(guān)，只與課程(X)有關(guān),在R（U）的任一關(guān)系r中，如果存在元組t，s 使得tX=sX，那么就必然存在元組 w，v r，（w，v可以與s，t相同），使得wX=vX=tX，而wY=tY，wZ=sZ，vY=sY，vZ=tZ（即交換s，t元組的Y值所得的兩個(gè)新元組必在r

15、中），則Y多值依賴于X，記為XY。 這里，X，Y是U的子集，Z=U-X-Y。 t x y1 z2 s x y2 z1 w x y1 z1 v x y2 z2,平凡多值依賴和非平凡的多值依賴 若XY，而Z，則稱 XY為平凡的多值依賴 否則稱XY為非平凡的多值依賴,多值依賴的性質(zhì),（1）多值依賴具有對(duì)稱性 若XY，則XZ，其中ZUXY 多值依賴的對(duì)稱性可以用完全二分圖直觀地表示出來(lái)。 （2）多值依賴具有傳遞性 若XY，YZ， 則XZ -Y,多值依賴的對(duì)稱性,多值依賴的對(duì)稱性,（3）函數(shù)依賴是多值依賴的特殊情況。 若XY，則XY。 （4）若XY，XZ，則XY Z(或表示為YZ)。 （5）若XY，XZ

16、，則XYZ。 （6）若XY，XZ，則XY-Z，XZ -Y。,多值依賴與函數(shù)依賴的區(qū)別,(1) 有效性 多值依賴的有效性與屬性集的范圍有關(guān) 若XY在U上成立，則在W（X Y W U）上一定成立；反之則不然，即XY在W（W U）上成立，在U上并不一定成立 多值依賴的定義中不僅涉及屬性組 X和 Y，而且涉及U中其余屬性Z。 一般地，在R（U）上若有XY在W（W U）上成立，則稱XY為R（U）的嵌入型多值依賴,只要在R（U）的任何一個(gè)關(guān)系r中，元組在X和Y上的值滿足函數(shù)依賴定義， 則函數(shù)依賴XY在任何屬性集W（X Y W U）上成立。,(2) 若函數(shù)依賴XY在R（U）上成立，則對(duì)于任何Y Y均有XY

17、成立 多值依賴XY若在R(U)上成立，不能斷言對(duì)于任何Y Y有XY 成立,二、第四范式（4NF）,定義5.10 關(guān)系模式R1NF，如果對(duì)于R的每個(gè)非平凡多值依賴XY（Y X），X都含有候選碼，則R4NF。 （XY） 如果R 4NF， 則R BCNF 不允許有非平凡且非函數(shù)依賴的多值依賴 允許的是函數(shù)依賴（是非平凡多值依賴）,例：關(guān)系模式:Teaching(課程,教師,參考書) 4NF 存在非平凡的多值依賴課程教師，且課程不是候選碼 用投影分解法把Teaching分解為如下兩個(gè)關(guān)系模式： CT(課程,教師) 4NF CB(課程,參考書) 4NF 課程教師，課程參考書 是平凡多值依賴,三、關(guān)系模式

18、的規(guī)范化 1.規(guī)范化步驟,規(guī)范化的實(shí)質(zhì)：概念的單一化。即：一個(gè)關(guān)系只描述一個(gè)概念、一個(gè)實(shí)體或?qū)嶓w間的一種聯(lián)系，若多于一個(gè)概念就應(yīng)將其它概念分離出去。,規(guī)范化基本步驟：,問(wèn)題提出：在關(guān)系模式的規(guī)范化處理過(guò)程中，不僅要知道一個(gè)給定的函數(shù)依賴集合，還要知道由給定的函數(shù)依賴集合所蘊(yùn)涵（或推導(dǎo)出）的所有函數(shù)依賴的集合。為此，需要一個(gè)有效而完備的公理系統(tǒng)，Armstrong公理系統(tǒng)即是這樣的一個(gè)系統(tǒng)。,2.Armstrong公理系統(tǒng),蘊(yùn)含定義：設(shè)F是R上的函數(shù)依賴集合， XY是R的一個(gè)函數(shù)依賴 。如果R的任何一個(gè)關(guān)系實(shí)例r, XY都成立，則稱F邏輯蘊(yùn)含(Imply) XY。,Armstrong公理：為從已

19、知的函數(shù)依賴推導(dǎo)出其他的函數(shù)依賴，Armstrong提出了一套推理規(guī)則，稱為Armstrong公理(Armstrongs Axioms)。,(2) 增廣律(Augmentation) ：若XY，ZU，則XZYZ。,(1) 自反律(Reflexivity) ：若YXU，則XY。,(3) 傳遞律(Transitivity) ：若XY和YZ，則XZ。,定理.6.1：Armstrong公理是正確的，即：如F成立，則由F根據(jù)Armstrong公理所推導(dǎo)的函數(shù)依賴總是成立的。,公理包含如下三條推理規(guī)則：,根據(jù)上述三條推理規(guī)則可以得到下面有用的三條推理規(guī)則：,(2) 偽傳遞規(guī)則(Pseudo Transit

20、ivity)：如果XY，YWZ，則XWZ。,(1) 合并規(guī)則(Union)：如果XY，XZ，則XYZ。,(3) 分解規(guī)則(Decomposition)：如果XY，ZY，則XZ。 或：如XYZ，則XY，XZ。,根據(jù)合并規(guī)則和分解規(guī)則，可得如下： 引理6.1: XA1 A2Ak成立的充分必要條件是XAi成立(i=l,2,k)。 定義6.12:函數(shù)依賴集F的閉包：在關(guān)系模式R中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作F的閉包，記為F+。 定義6.13: 屬性集X關(guān)于函數(shù)依賴集F的閉包：設(shè)F為屬性集U上的一組函數(shù)依賴，X U，XF+ = A|XA能由F根據(jù)Armstrong公理導(dǎo)出，XF+稱為屬性集X關(guān)于函

21、數(shù)依賴集F 的閉包。 引理6.2：設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y U，XY能由F 根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y XF+。,閉包的用途：將判定XY是否能由F根據(jù)Armstrong公理導(dǎo)出的問(wèn)題，就轉(zhuǎn)化為求出XF+ ，判定Y是否為XF+的子集的問(wèn)題。 Armstrong公理系統(tǒng)的有效性與完備性 有效性(正確性)：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出的每個(gè)函數(shù)依賴一定在F+中。 完備性：F+中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來(lái)。,求屬性集X(XU)關(guān)于U上函數(shù)依賴集F 的閉包XF+的算法： 輸入：X，F(xiàn) 輸出：XF+ 令X (0) =

22、X，i=0。 求B，B = A |(V)(W)(VWFV X (i) AW)。 X (i+1) =BX (i) 。 判斷X (i+1) = X (i)嗎? 若相等或X (i) =U , 則X (i)就是XF+ , 算法終止；否則i=i+1，返回第2步。,例1已知關(guān)系模式R，其中U=A,B,C,D,E，F(xiàn)=ABC,BD,CE,ECB,ACB，求(AB)F+。 設(shè)X (0) =AB ； 計(jì)算X (1) : 逐一的掃描F集合中各個(gè)函數(shù)依賴，找左部為A、B或AB的函數(shù)依賴，有ABC，BD， 于是X (1) =ABCD=ABCD。 因?yàn)閄 (0) X (1) ，所以再找出左部為ABCD子集的那些函數(shù)依賴

23、，又得到CE，ACB， 于是X (2) =X (1) BE=ABCDE。 因?yàn)閄 (2) =U，算法終止。 所以(AB)F+ =ABCDE。,根據(jù)閉包可以求關(guān)系模式的候選碼：如已知關(guān)系模式R(ABCDEG)上FD集F=DG,CA,CDE,AB， S(ABCD)上FD集F=BC, ACB，利用閉包概念可以分別求它們的候選碼。 (D)F+, (C)F+, (CD)F+, (A)F+ (B)F+, (AC)F+,函數(shù)依賴集的等價(jià) 定義：若G+=F+，則函數(shù)依賴集F覆蓋G(F是G的覆蓋或G是F的覆蓋)，或F與G等價(jià)。 充要條件：F+ =G+ 的充分必要條件是F G+ 和G F+。 證: 必要性顯然，只

24、證充分性。 若FG+ ，則XF+ XG+ 。 任取XYF+ ， 則有YXF+ XG+ ， 所以XY(G+)+= G+。即F+ G+。 同理可證G+ F+ ，所以F+ =G+。 判斷方法：要判定F G+，只須逐一對(duì)F中的函數(shù)依賴XY，考察Y是否屬于XG+就行了。,最小依賴集：如果函數(shù)依賴集F滿足下列條件，則稱F為一個(gè)極小函數(shù)依賴集，亦稱為最小依賴集或最小覆蓋。 F中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性。 F中不存在這樣的函數(shù)依賴XA，使得F與FXA等價(jià)。 F中不存在這樣的函數(shù)依賴XA，X有真子集Z使得FXAZA與F等價(jià)。,例:設(shè)關(guān)系模式S中，U= Sno,Sdept,Mname,Cno,Grade

25、， 設(shè)F=SnoSdept,SdeptMname，(Sno,Cno)Grade ， F=SnoSdept,SnoMname,SdeptMname, (Sno,Cno)Grade ，(Sno,Sdept)Sdept，則F是最小覆蓋，而F 不是。 因?yàn)椋?FSnoMname與F等價(jià)； F(Sno, Sdept)Sdept也與F等價(jià)； F(Sno, Sdept)SdeptSnoSdept也與F等價(jià) 。,求F最小依賴集Fm的過(guò)程 使每一函數(shù)依賴右邊單屬性化：逐一檢查F中各函數(shù)依賴FDi：XY，若Y=A1A2Ak，則以 XAj |j=1,2,k 取代XY。 去掉多余的函數(shù)依賴：逐一檢查F中各函數(shù)依賴FD

26、i：XA，令G=FXA，若AXG+，則從F中去掉此函數(shù)依賴。因F與G =FXA等價(jià)的充要條件是AXG+，故F變換前后等價(jià)。 去掉每一函數(shù)依賴左邊多余的屬性：逐一取出F中各函數(shù)依賴FDi：XA，設(shè)X=B1B2Bm，逐一考查Bi (i=l,2,m)，若A (X-Bi )F+ ，則以X-Bi 取代X。 由于F與FXAZA等價(jià)的充要條件是AZF+，其中Z=X Bi ，故F變換前后等價(jià)。 最后剩下的F就是最小依賴集Fm 。,例:F=AB,BA,BC,AC,CA，則Fm1、Fm2都是F的最小依賴集： Fm1=AB,BC,CA Fm2=AB,BA,AC,CA F的最小依賴集Fm不一定是唯一的，它與對(duì)各函數(shù)依

27、賴FDi及XA中X各屬性的處理順序有關(guān)。,例：學(xué)生(學(xué)號(hào), 姓名, 系名, 系主任, 課程號(hào),課程名, 分?jǐn)?shù)),F=學(xué)號(hào)姓名,課程號(hào)課程名,系名系主任, 學(xué)號(hào)系主任，學(xué)號(hào)系名, (學(xué)號(hào),課程號(hào)) 分?jǐn)?shù),1、使每一函數(shù)依賴右邊單屬性化： 逐一檢查F中各函數(shù)依賴FDi：XY，若Y=A1A2Ak，則以 XAj |j=1,2,k 取代XY。 2、去掉多余的函數(shù)依賴： 去掉：學(xué)號(hào)姓名 G1=課程號(hào)課程名,系名系主任,學(xué)號(hào)系主任 學(xué)號(hào)系名, (學(xué)號(hào),課程號(hào)) 分?jǐn)?shù)， 求（學(xué)號(hào)）G1+ ，檢查“姓名”是否屬于該閉包。如果是則去掉該函數(shù)依賴。同理檢查其他四個(gè)函數(shù)依賴。,去掉：課程號(hào)課程名 G2=學(xué)號(hào)姓名，系名

28、系主任,學(xué)號(hào)系主任 學(xué)號(hào)系名, (學(xué)號(hào),課程號(hào)) 分?jǐn)?shù) 去掉：系名系主任 G3=學(xué)號(hào)姓名，課程號(hào)課程名， 學(xué)號(hào)系名, 學(xué)號(hào)系主任,(學(xué)號(hào),課程號(hào)) 分?jǐn)?shù) 去掉：學(xué)號(hào)系主任 G4=學(xué)號(hào)姓名，課程號(hào)課程名，學(xué)號(hào)系名， 系名系主任, (學(xué)號(hào),課程號(hào)) 分?jǐn)?shù) 因?qū)W號(hào)在G4上的閉包包含系主任， 所以函數(shù)依賴學(xué)號(hào)系主任可以去掉。 去掉：學(xué)號(hào)系名 G5=學(xué)號(hào)姓名，課程號(hào)課程名，系名系主任, (學(xué)號(hào),課程號(hào)) 分?jǐn)?shù),去掉： (學(xué)號(hào),課程號(hào)) 分?jǐn)?shù) G6=學(xué)號(hào)姓名，課程號(hào)課程名，系名系主任, 學(xué)號(hào)系名。 G7=學(xué)號(hào)姓名，課程號(hào)課程名，系名系主任, 學(xué)號(hào)系名， (學(xué)號(hào),課程號(hào)) 分?jǐn)?shù) 3、去掉每一函數(shù)依賴左邊多余

29、的屬性 (學(xué)號(hào),課程號(hào)) 分?jǐn)?shù)，分別檢查“學(xué)號(hào)”、“課程號(hào)”在G7上的閉包是否包含“分?jǐn)?shù)”，由于不包含，所以 G7為最小函數(shù)依賴集,6.4 模式的分解 把低一級(jí)的關(guān)系模式分解為若干個(gè)高一級(jí)的關(guān)系模式的方法并不是唯一的 只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)，分解方法才有意義 1.分解具有無(wú)損連接性 2.分解要保持函數(shù)依賴 3.分解既要保持函數(shù)依賴，又要具有無(wú)損連接性,定義: 關(guān)系模式R的一個(gè)分解： = R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，F(xiàn)i 為 F在 Ui 上的投影 定義: 函數(shù)依賴集合XY | XY F+XY Ui 的一個(gè)覆蓋 Fi 叫作 F 在屬性 Ui 上的

30、投影,示例：關(guān)系模式SDL(Sno,Sdept,Mname) F=Sno Sdept, Sdept Mname 對(duì)關(guān)系模式SDL(Sno,Sdept,Mname)分解 第一種分解：R1(Sno), R2(Sdept), R3(Mname) 第二種分解：R1(Sno,Sdept), R2(Sno，Mname) 第三種分解：R1(Sno,Sdept), R2(Sdept, Mname),關(guān)系模式R的一個(gè)分解 = R1，R2， ，Rn 若R與R1、R2、Rn自然連接的結(jié)果相等，則稱關(guān)系 模式R的這個(gè)分解具有無(wú)損連接性（Lossless join） 具有無(wú)損連接性的分解保證不丟失信息 無(wú)損連接性不一定

31、能解決插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問(wèn)題 算法 6.2 判別一個(gè)分解的無(wú)損連接性 P189,例設(shè)有關(guān)系模式Student(U,F)，其中U=Sno,Sdept,Sloc,Cno,Grade，F(xiàn)=SnoSdept, SdeptSloc,(Sno,Cno)Grade，顯然Student1NF，它存在冗余度大、插入異常、刪除異常、更新異常問(wèn)題。 根據(jù)給定的函數(shù)依賴集F，求出其最小集為F=F。 采用投影方法，將關(guān)系模式Student分解為三個(gè)關(guān)系模式： SCG(U1,F1)、SD(U2,F2)、DL(U3,F3)，其中： U1=Sno,Cno,Grade, F1=(Sno,Cno)Grade

32、, U2=Sno,Sdept , F2=SnoSdept, U3=Sdept,Sloc, F3=SdeptSloc 考察該分解是否具有無(wú)損連接性：具有。,定義6.19 保持函數(shù)依賴 P190 示例1：對(duì)關(guān)系模式SDL(Sno,Sdept,Sloc)保持函數(shù)依賴的分解 示例2：對(duì)關(guān)系模式R(A,B,C,D)，F(xiàn)=ABC,CA,CD，=ACD,BC，判斷分解是否保持函數(shù)依賴。(否?) 示例3：對(duì)關(guān)系模式R(ABCD)，F(xiàn)=ABC,CAD，=ABC,AD，判斷分解是否保持函數(shù)依賴。(是?),模式分解的算法 關(guān)于模式分解的幾個(gè)重要事實(shí) 若要求分解保持函數(shù)依賴，則模式分離總可以達(dá)到3NF，但不一定能達(dá)到

33、BCNF。 若要求分解既保持函數(shù)依賴，又具有無(wú)損連接性，則模式分離總可以達(dá)到3NF，但不一定能達(dá)到BCNF。 若要求分解具有無(wú)損連接性，則模式一定可達(dá)到4NF。 如果一個(gè)分解具有無(wú)損連接性，則它能夠保證不丟失信息。 如果一個(gè)分解保持函數(shù)依賴，則分解前后兩個(gè)模式的函數(shù)依賴集的閉包是等價(jià)的。 分解具有無(wú)損連接性和分解保持函數(shù)依賴是兩個(gè)互相獨(dú)立的標(biāo)準(zhǔn)。具有無(wú)損連接性的分解不一定能夠保持函數(shù)依賴。同樣，保持函數(shù)依賴的分解也不一定具有無(wú)損連接性。,算法6.3(合成法): R轉(zhuǎn)換為3NF的保持函數(shù)依賴的分解。P191 求F的最小集F。 若F中有一函數(shù)依賴XA，且XA=U，則輸出=R。 若R中某些屬性與F中

34、所有函數(shù)依賴的左右部均無(wú)關(guān)，則將它們構(gòu)成關(guān)系模式，并從R中將它們分離出去。 對(duì)于F中的每一個(gè)XiAi,都構(gòu)成一個(gè)關(guān)系模式Ri=XiAi。 分解結(jié)束，輸出。 例設(shè)有關(guān)系模式Student，其中： U=Sno,Sdept,Sloc,Cno,Grade， F= SnoSdept, SdeptSloc,(Sno,Cno)Grade， 則Student保持函數(shù)依賴的一個(gè)分解為： =SCG(Sno,Cno,Grade) ,SD(Sno,Sdept), DL(Sdept,Sloc),算法6.4 : R轉(zhuǎn)換為3NF既有無(wú)損連接又保持函數(shù)依賴的分解。 例設(shè)有關(guān)系模式Student，其中： U=Sno,Sdept,Sloc,Cno,Grade， F=SnoSdept, SdeptSloc,(Sno,Cno)Grade， 則Student保持函數(shù)依賴的一個(gè)分解為： =SCG(Sno,Cno,Grade) ,SD(Sno,Sdept), DL(Sdept,Sloc) 它具有無(wú)損連接性。,算法6.5 :R轉(zhuǎn)換為BCNF的無(wú)損連接分解。 1.令=R。 2.若中所有模式都是BCNF，分解結(jié)束，輸出 。 3.若