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

關(guān)系數(shù)據(jù)理論第一頁，共一百一十頁，2022年，8月28日教學(xué)目的：①關(guān)系模式的異常問題②函數(shù)依賴③Armstrong公理④閉包及其計(jì)算算法⑤最小依賴集和候選碼的求解方法⑥1NF,2NF,3NF和BCNF的概念⑦模式分解的等價(jià)標(biāo)準(zhǔn)重點(diǎn)難點(diǎn)：①Armstrong公理系統(tǒng)②最小依賴集和候選碼的求解方法③如何將模式分解為1NF,2NF,3NF和BCNF教學(xué)方法：多媒體教學(xué)教學(xué)課時(shí)：10節(jié)理論課+2節(jié)習(xí)題課第二頁，共一百一十頁，2022年，8月28日目錄6.1問題的提出6.2規(guī)范化6.3函數(shù)依賴的公理系統(tǒng)6.4模式的分解第三頁，共一百一十頁，2022年，8月28日6.1問題的提出 針對(duì)一個(gè)具體的問題，應(yīng)該如何構(gòu)造一個(gè)適合于它的數(shù)據(jù)模式？即應(yīng)該構(gòu)造幾個(gè)關(guān)系模式？每個(gè)關(guān)系模式由哪些屬性組成呢？這就是數(shù)據(jù)庫設(shè)計(jì)的問題。 對(duì)于一個(gè)信息系統(tǒng)來說，如果所設(shè)計(jì)的數(shù)據(jù)庫均具有良好的、合理的范式級(jí)別，那么系統(tǒng)的正確性將自動(dòng)得到某種保證。第四頁，共一百一十頁，2022年，8月28日如：對(duì)于學(xué)生和課程的關(guān)系模式，屬性集：U={sno、dept、dean、cno、grade}關(guān)系模式包含的語義：(1)一個(gè)系有多名學(xué)生，但一個(gè)學(xué)生只屬于一個(gè)系(2)一個(gè)系只有一名正系主任(3)一個(gè)學(xué)生可以選修多門課程，一門課程有多名學(xué)生選修根據(jù)語義，得到屬性之間有某種關(guān)系，即屬性值之間的相互依賴又相互制約的關(guān)系，稱它為數(shù)據(jù)依賴。數(shù)據(jù)依賴分為：函數(shù)依賴和多值依賴。1、數(shù)據(jù)依賴一個(gè)關(guān)系模式描述為：R(U,D,dom,F)，F(xiàn)是屬性組U上的一組數(shù)據(jù)依賴。第五頁，共一百一十頁，2022年，8月28日假如有下關(guān)系模式：學(xué)生表D(Sno,Sname,Sdept,Sage,Cno,Cname,Credit,Grade)

在數(shù)據(jù)庫中的D表模式信息如圖表：Sno(5)Sname(10)Sdept(10)Sage(2)Cno(5)Cname(20)Credit(2)Grade(2)0001張三計(jì)算機(jī)17c101數(shù)據(jù)結(jié)構(gòu)4900001張三計(jì)算機(jī)17c102網(wǎng)絡(luò)安全3880001張三計(jì)算機(jī)17c103軟件工程4780001張三計(jì)算機(jī)17c105數(shù)值分析2800001張三計(jì)算機(jī)17c110編譯原理3860002李四物理19c103軟件工程4820002李四物理19c105數(shù)值分析2800003王五計(jì)算機(jī)17c107C語言475此關(guān)系的關(guān)鍵字：sno+cno2、什么是不好的關(guān)系模式？第六頁，共一百一十頁，2022年，8月28日此表包含了哪些信息呢？①一個(gè)學(xué)生可以選多門課程②一門課程可以被多名學(xué)生選修③一個(gè)學(xué)生選修一門課程的成績?cè)趯?shí)際應(yīng)用中，此關(guān)系會(huì)不會(huì)出現(xiàn)問題呢？可能出現(xiàn)些什么問題？第七頁，共一百一十頁，2022年，8月28日第一類問題是數(shù)據(jù)冗余太大，這表現(xiàn)在：總字節(jié)數(shù)=(5+10+10+2+5+20+2+2)*8=448B

關(guān)于學(xué)生張三的sname、sdept和Sage在關(guān)系中出現(xiàn)了五次。這樣，一方面浪費(fèi)存儲(chǔ)空間，另一方面系統(tǒng)要付出很大的代價(jià)來維護(hù)數(shù)據(jù)庫的完整性。第二類問題是更新出現(xiàn)異常，這表現(xiàn)在：（1）修改異常：如果把張三同學(xué)的sdept改為“數(shù)學(xué)”，那么它要修改5次，在維護(hù)D表時(shí)不夠小心的話，可能我只修改了四次，漏掉了一個(gè)，那么張三同學(xué)的sdept的值就有兩個(gè)（計(jì)算機(jī)，數(shù)學(xué)），這樣造成數(shù)據(jù)不一致。第八頁，共一百一十頁，2022年，8月28日(2)插入異常：此表的主關(guān)鍵字是(sno,cno),那么這兩個(gè)字段不能為空。在這個(gè)數(shù)據(jù)表中，如果我們要插入一門課程的信息，但此課程本學(xué)期不開設(shè)，故無學(xué)生選讀，這樣就無法將這門課程的信息存入到數(shù)據(jù)表中，這就使表在功能上產(chǎn)生了極不正常的現(xiàn)象。如果在Sno和Sname兩屬性上定義了非空約束，上述元組的插入就是非法操作。（該插入的數(shù)據(jù)不能插入。）

(3)刪除異常：如果在這個(gè)數(shù)據(jù)表中0003的王五同學(xué)因病退學(xué)，因而有關(guān)他的元組在數(shù)據(jù)表中就被刪除，但遺憾的是在王五的有關(guān)情況刪除時(shí)，連課程“C語言”的有關(guān)信息也同時(shí)被刪除了(因?yàn)樵谶@個(gè)數(shù)據(jù)表中，只有在王五這個(gè)元組中記載有“C語言”課程的有關(guān)信息)，并且在整個(gè)數(shù)據(jù)表中再也找不到有關(guān)課程“C語言”的有關(guān)信息了。這就叫做：“城門失火，殃及池魚”。這也是數(shù)據(jù)表中的一種極其不正常的現(xiàn)象，這種現(xiàn)象就叫刪除異常。（不該被刪除的數(shù)據(jù)被刪除。）第九頁，共一百一十頁，2022年，8月28日問題的分析 這兩類現(xiàn)象的根本原因在于關(guān)系的結(jié)構(gòu)。一個(gè)關(guān)系可以有一個(gè)或者多個(gè)候選鍵，其中一個(gè)可以選為主鍵。主鍵的值唯一確定其他屬性的值，它是各個(gè)元組之間區(qū)別的標(biāo)識(shí)，也是一個(gè)元組存在的標(biāo)識(shí)。這些候選鍵的值不能重復(fù)出現(xiàn)，也不能全部或者部分設(shè)為空值。本來這些候選鍵都可以作為獨(dú)立的關(guān)系存在，而現(xiàn)在卻不得不依附于其他關(guān)系而存在。這就是關(guān)系結(jié)構(gòu)帶來的限制，它不能正確反映現(xiàn)實(shí)世界的真實(shí)情況。如果在構(gòu)造關(guān)系模式的時(shí)候，不從語義上研究和考慮到屬性間的這種關(guān)聯(lián)，而簡單地將有關(guān)系和無關(guān)系的、關(guān)系密切的和關(guān)系松散的屬性都隨意編排在一起，就必然發(fā)生某種沖突，引起某些“排它”現(xiàn)象出現(xiàn)，即冗余度水平較高，更新產(chǎn)生異常。解決問題的根本方法就是將關(guān)系模式進(jìn)行分解，也就是進(jìn)行關(guān)系的規(guī)范化。第十頁，共一百一十頁，2022年，8月28日6.2規(guī)范化關(guān)系數(shù)據(jù)庫中關(guān)系規(guī)范化問題在1970年Codd提出關(guān)系模型時(shí)同時(shí)被提出來。關(guān)系模式必須是規(guī)范化的，規(guī)范化的最基本要求是關(guān)系的每個(gè)分量必須是不可再分的數(shù)據(jù)項(xiàng)。但是，并不是所有滿足基本要求的關(guān)系模式就是一個(gè)好的關(guān)系模式，一個(gè)好的關(guān)系模式必須能很好的反映現(xiàn)實(shí)世界。為了說明一個(gè)好的關(guān)系模式如何能真實(shí)的反映現(xiàn)實(shí)世界，必須首先要研究關(guān)系模式中屬性之間的數(shù)據(jù)依賴關(guān)系。第十一頁，共一百一十頁，2022年，8月28日snocnogradesdeptdean1、函數(shù)依賴FD(FunctionalDependency)給定一個(gè)屬性的值，另一個(gè)屬性的值也會(huì)唯一的確定了。這種關(guān)系像數(shù)學(xué)中的函數(shù)。因此稱之為函數(shù)依賴。如前例：學(xué)生(sno，sdept、dean、cno、grade)規(guī)定：一個(gè)學(xué)生只能屬于一個(gè)系，一個(gè)系只能有一個(gè)系主任，每個(gè)學(xué)生每學(xué)一門課程只有一個(gè)成績。即：sno的值一經(jīng)確定后sdept的值也隨之唯一地確定了，此時(shí)即稱sno函數(shù)決定sdept或稱sdept函數(shù)依賴于sno，它可用下面符號(hào)表示：

sno→sdept同樣，我們還可以有：sdept→dean(sno，cno)→grade其函數(shù)依賴圖為：6.2.1函數(shù)依賴第十二頁，共一百一十頁，2022年，8月28日定義6.1：設(shè)有關(guān)系模式R(U)，屬性集合U={A1,A2,…,An}，X，Y是U的子集，設(shè)u,v是關(guān)系r中的任意兩個(gè)元組，若有u[X]=v[X]，就有u[Y]=v[Y](即r中不可能存在兩個(gè)元組在X上的屬性值相等，而在Y上的屬性值不等。換句話說，對(duì)于任一個(gè)關(guān)系R中的任一元組在X中的屬性值確定后則在Y中的屬性值必確定)，則稱Y函數(shù)依賴于X或稱X函數(shù)決定Y,并記作X→Y，而其中X稱為決定因素，Y稱為依賴因素。

例如：在關(guān)系D中，各屬性間的函數(shù)依賴集合為：

F={sno→sname,sno→sdept,sno→sage,cno→cname，cno→credit,cno+sno→grade}第十三頁，共一百一十頁，2022年，8月28日課堂練習(xí)：設(shè)有一個(gè)關(guān)系模式R(A,B,C,D)，在關(guān)系R中，屬性值間有這樣的聯(lián)系：A值與B值有一對(duì)多聯(lián)系，即每個(gè)A值有多個(gè)B值與之聯(lián)系，而每個(gè)B值只有一個(gè)A值與之聯(lián)系；C值與D值是一對(duì)一聯(lián)系，即每個(gè)C值只有一個(gè)D值與之聯(lián)系，每個(gè)D值只有一個(gè)C值與之聯(lián)系。試寫出相應(yīng)的函數(shù)依賴。B→AD→C，C→D第十四頁，共一百一十頁，2022年，8月28日函數(shù)依賴與屬性關(guān)系：屬性之間有3種關(guān)系，但并不是每一種關(guān)系中都存在函數(shù)依賴。設(shè)有屬性集X、Y以及關(guān)系模式R：如果X和Y之間是“1：1”關(guān)系(學(xué)校和校長)，則存在函數(shù)依賴：

X→Y和Y→X如果X和Y之間是“m：1”關(guān)系(學(xué)生和班長)，則存在函數(shù)依賴：

X→Y如果X和Y之間是“m：n”關(guān)系(學(xué)生和課程)，則X和Y之間不存在函數(shù)依賴。第十五頁，共一百一十頁，2022年，8月28日注意：①不是R的某個(gè)關(guān)系，而是R的一切關(guān)系，任意抽取兩個(gè)元組②函數(shù)依賴與碼有關(guān)，而函數(shù)依賴和碼都是由語義決定的，是由數(shù)據(jù)庫開發(fā)人員，根據(jù)用戶模型和事務(wù)規(guī)則人為確定的。所以數(shù)據(jù)依賴屬于語義范疇，不能用數(shù)學(xué)方法去證明。第十六頁，共一百一十頁，2022年，8月28日2、平凡函數(shù)依賴與非平凡函數(shù)依賴設(shè)函數(shù)依賴關(guān)系X→Y，若滿足YX，則稱此函數(shù)依賴是非平凡的函數(shù)依賴。在本章中若無特殊聲明，凡提到函數(shù)依賴時(shí)總認(rèn)為指的是非平凡的函數(shù)依賴。設(shè)函數(shù)依賴關(guān)系X→Y，若滿足YX，則稱此函數(shù)依賴是平凡的函數(shù)依賴。若X→Y，Y→X，稱為X←→Y第十七頁，共一百一十頁，2022年，8月28日這里引入一種完全函數(shù)依賴的概念，這個(gè)概念為真正的函數(shù)依賴打下基礎(chǔ)。例如在D中我們有Sno→Sdept，因而我們同樣也會(huì)有：

(Sno，Sname)→Sdept(Sno，Sage)→Sdept比較這三種函數(shù)依賴后我們會(huì)發(fā)現(xiàn)，實(shí)際上真正起作用的函數(shù)依賴是：

Sno→Sdept

而其他兩種函數(shù)依賴都是由它派生而成的，即是說在函數(shù)依賴中真正起作用的是Sno，而不是Snane或Sage等。這樣，我們?cè)谘芯亢瘮?shù)依賴時(shí)要區(qū)別這兩種不同類型的函數(shù)依賴，前一種叫完全函數(shù)依賴，而后一種叫不完全函數(shù)依賴(部分函數(shù)依賴)。3、完全函數(shù)依賴與部分函數(shù)依賴第十八頁，共一百一十頁，2022年，8月28日定義6.2：R(U)中如有X，YU，滿足X→Y，且對(duì)任何X的真子集X’，都有X’→Y不成立，則稱Y完全函數(shù)依賴于X，并記作：

XY

在R(U)中如有X，YU，滿足X→Y，對(duì)任何X的真子集X’，都有X’→Y成立，則稱Y部分依賴于X，或稱Y函數(shù)依賴于X的某個(gè)真子集，記作：

XY

由上所述可知，Sdept完全函數(shù)依賴于Sno，但Sdept不完全函數(shù)依賴于(Sno，Sname)，亦即有：

SnoSdept(Sno，Sname)Sdept(Sno，Sage)SdeptFPFPP第十九頁，共一百一十頁，2022年，8月28日在函數(shù)依賴中還要區(qū)別直接函數(shù)依賴與間接函數(shù)依賴這兩個(gè)不同的概念，例如Sno→Sdept中Sdept是直接函數(shù)依賴于Sno，但如果在屬性中有系主任dean(假如每個(gè)系有唯一的一個(gè)系主任)，則有：Sdept→dean，從而由Sno→Sdept及Sdept→dean可得到：

Sno→dean

在這個(gè)函數(shù)依賴中，dean并不直接函數(shù)依賴于Sno，而是經(jīng)過中間屬性Sdept傳遞而依賴于Sno，亦即是dean直接依賴于Sdept(Sdept不依賴于Dean)，而Sdept又直接依賴于Sno，從而構(gòu)成了dean依賴于Sno。這種函數(shù)依賴關(guān)系，是一種間接依賴關(guān)系，或叫傳遞依賴關(guān)系。我們可以對(duì)它定義如下。定義6.3：在R(U)中如有X，Y，ZU且滿足：

X→Y，(YX)Y/X，Y→Z

則稱Z傳遞函數(shù)依賴于X，否則，稱為非傳遞函數(shù)依賴。記為：XZT4、傳遞函數(shù)依賴第二十頁，共一百一十頁，2022年，8月28日定義6.4：設(shè)K為R<U,F>中的屬性或?qū)傩越M合，若KU且滿足KU,則K為R的候選碼。若候選碼多于一個(gè)，則選定其中的一個(gè)為主碼。在最簡單的情況下，候選碼只包含一個(gè)屬性。包含在任何一個(gè)候選碼中的屬性，叫做主屬性。不包含在任何碼中的屬性稱為非主屬性或非碼屬性。所有的屬性的組合構(gòu)成候選碼，這時(shí)稱為全碼。F例：有關(guān)系CSZ(city，st，zip)，其中有三個(gè)屬性：城市city，街道st，郵政編碼zip。其函數(shù)依賴關(guān)系為：F={(city,st)→zip，zip→city}解：在這個(gè)關(guān)系模式中，有兩個(gè)候選碼(city，st)和(st，zip)。所以city，st，zip都是主屬性。6.2.2碼(鍵)第二十一頁，共一百一十頁，2022年，8月28日6.3函數(shù)依賴的公理系統(tǒng)1、邏輯蘊(yùn)涵定義6.11：設(shè)F是關(guān)系模式R的函數(shù)依賴集合，由F出發(fā)可以證明其他某些函數(shù)依賴也成立，我們稱這些函數(shù)依賴被F邏輯蘊(yùn)涵。如：F={A→B，B→C}，從這個(gè)函數(shù)依賴集中可以推出A→C，所以說函數(shù)依賴集F邏輯蘊(yùn)涵函數(shù)依賴A→C。

1974年首先提出了函數(shù)依賴的公理系統(tǒng)，稱為Armstrong公理(Armstrong’saxioms)。對(duì)于一組已知的函數(shù)依賴，利用該公理可導(dǎo)出所邏輯蘊(yùn)函的函數(shù)依賴，從而確定一個(gè)關(guān)系模式中的碼。第二十二頁，共一百一十頁，2022年，8月28日2、Armstrong公理公理如下：設(shè)U為屬性集總體，X，Y，Z，W均是U的子集，F(xiàn)是U上的一組函數(shù)依賴,于是有關(guān)系模式R〈U,F〉。對(duì)R〈U,F〉且有：

A1：若YXU,則X→Y為F所蘊(yùn)涵(自反律)。

A2：若X→Y為F所蘊(yùn)含,且ZU,則XZ→YZ為F所蘊(yùn)涵(增廣律)。

A3：若X→Y及Y→Z為F所蘊(yùn)含,則X→Z為F所蘊(yùn)涵(傳遞律)。根據(jù)Armstrong公理可以得到下面另三條很有用的推論:

推論1：由X→Y,X→Z,有X→YZ（合并律）。推論2：由X→Y,WY→Z,有XW→Z（偽傳遞律）。推論3：由X→ZY,有X→Y及X→Z成立（分解律）。第二十三頁，共一百一十頁，2022年，8月28日4、算法6.1屬性集閉包的計(jì)算。

原則上講，對(duì)于一個(gè)關(guān)系模式R(U,F)，根據(jù)已知的函數(shù)依賴F，反復(fù)使用前面的規(guī)則，可以計(jì)算函數(shù)依賴集合F的閉包F+。但是，利用推理規(guī)則求出其全部的函數(shù)依賴F+是非常困難的，而且也沒有必要。因此，可以計(jì)算閉包的子集，即選擇一個(gè)屬性子集，判斷該屬性子集能函數(shù)決定哪些屬性，這就是利用屬性集閉包的概念。

(1)定義：設(shè)F為屬性集U上的一組函數(shù)依賴，XU，即X是U的一個(gè)子集。在函數(shù)依賴集合F下，被X函數(shù)決定的所有屬性為F+下屬性集X的閉包，記作X+，記X+={A|X→A}。

(2)計(jì)算屬性集閉包X+的算法如下：輸入：X，F(xiàn)

輸出：X+3、函數(shù)依賴集合F的閉包F+

定義6.13：由F所邏輯蘊(yùn)涵的所有的函數(shù)依賴的集合，稱為F的閉包，記為F+

第二十四頁，共一百一十頁，2022年，8月28日迭代算法的步驟： ①選取X+的初始值為X，即X+＝{X}； ②計(jì)算X+，X+＝{XZ}，其中Z要滿足如下條件：

YX+，且F中存在一函數(shù)依賴Y→Z，就把Z并到X+中。實(shí)際上就是以X+中的屬性子集作為函數(shù)依賴的決定因素，在F中搜索函數(shù)依賴集，找到函數(shù)依賴的被決定屬性Z放到X+中。 ③判斷：如果X+沒有變化？或X+等于U？則X+就是所求的結(jié)果，算法終止。否則轉(zhuǎn)②。 因?yàn)閁是有窮的，所以上述迭代過程經(jīng)過有限步驟之后就會(huì)終止。第二十五頁，共一百一十頁，2022年，8月28日例：已知關(guān)系模式R(U，F(xiàn))，其中U={A,B,C,D,E},F={AB→C,B→D,C→E,EC→B,AC→B},求(AB)+

。解：①令(AB)+={AB}②在F中找出左邊是AB子集的函數(shù)依賴，其結(jié)果是：AB→C,B→D,所以(AB)+={(AB)+∪CD}={ABCD}，③在F中找出左邊是ABCD子集的函數(shù)依賴，其結(jié)果是：C→E,AC→B，得到(AB)+={(AB+∪BE)}={ABCDE}④判斷(AB)+={ABCDE}=U，算法結(jié)束。由于(AB)+有變化但不等于U，所以繼續(xù)迭代。由計(jì)算結(jié)果可知，(AB)可以決定屬性集合U={A,B,C,D,E}，所以，(AB)是一個(gè)候選碼。但不是唯一的候選碼。第二十六頁，共一百一十頁，2022年，8月28日課堂練習(xí)：設(shè)有關(guān)系模式R(U,F),其中U={A,B,C,D,E,I},F={A→D,AB→E,BI→E,CD→I,E→C},計(jì)算(AE)+

結(jié)果為：(AE)+=ACDEI第二十七頁，共一百一十頁，2022年，8月28日5、Armstong公理系統(tǒng)的完備性和有效性有效性是指：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個(gè)函數(shù)依賴一定在F所邏輯蘊(yùn)涵的函數(shù)依賴。也就是說只要使用F中的依賴為真，則用公理推出的函數(shù)依賴也為真。完備性是指：F所邏輯蘊(yùn)涵的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來。也就是說F+中的所有函數(shù)依賴都能用公理推出。實(shí)質(zhì)上：Armstrong公理是正確和完備的。第二十八頁，共一百一十頁，2022年，8月28日6、求函數(shù)依賴的最小集定義6.15：對(duì)于給定的函數(shù)依賴F，當(dāng)滿足下列條件時(shí)，稱為F的最小依賴集，記作FM。FM的每個(gè)依賴的右邊都是單個(gè)屬性。對(duì)于FM中的任何一個(gè)X→A和X的真子集Z，(FM-{X→A})∪{Z→A}與FM都不等價(jià)。(保證了FM中每個(gè)函數(shù)依賴的左邊沒有多余的屬性)對(duì)于FM中的任何一個(gè)函數(shù)依賴X→A，F(xiàn)M-{X→A}與FM都不等價(jià)。(保證了在FM中不存在多余的函數(shù)依賴)定理：每個(gè)函數(shù)依賴集與它的最小依賴集FM等價(jià)。第二十九頁，共一百一十頁，2022年，8月28日輸入：一個(gè)函數(shù)依賴集F輸出：F的一個(gè)等價(jià)最小依賴集G方法：(1)應(yīng)用分解規(guī)則，使F中每一個(gè)依賴的右邊屬性單一化。(2)去掉各依賴左邊多余的屬性。具體做法是；一個(gè)一個(gè)地檢查F中左邊是非單屬性的依賴，例如XY→A?，F(xiàn)在要判斷Y是否多余的，即以X→A代替XY→A是否等價(jià)。只要在F中求X+，若X+包含A，則Y是多余的屬性；否則Y不是多余的屬性。依次判斷其他屬性即可消除各依賴左邊的多余屬性。(3)去掉多余的依賴。具體做法是：從第一個(gè)依賴開始，從F中去掉它(假設(shè)該依賴是X→Y)，然后在剩下的依賴中求X+，看X+是否包含Y，若是，則可以去掉X→Y；若不包含Y，則不能去掉。第三十頁，共一百一十頁，2022年，8月28日例：設(shè)有依賴集：F={AB→C，C→A，BC→D，ACD→B，D→EG，BE→C，CG→BD，CE→AG}，計(jì)算其等價(jià)的最小依賴集。解：(1)將依賴右邊屬性單一化，結(jié)果為：F1={AB→C，C→A，BC→D，ACD→B，D→E，D→G，BE→C，CG→B，CG→D，CE→A，CE→G}

(2)在F1中去掉左邊多余的屬性。Ⅰ、對(duì)于ACD→B，由于(CD)+=ABCDEG，則A是多余的，所以結(jié)果為：F2={AB→C，C→A，BC→D，CD→B，D→E，D→G，BE→C，CG→B，CG→D，CE→G}Ⅱ、對(duì)于CE→A，由于C→A，則E是多余的

(3)在F2中去掉多余的依賴。對(duì)于CD→B，在剩下的函數(shù)依賴中，由于(CD)+=CDAEGB，所以CD→B是多余的，則Fm={AB→C，C→A，BC→D，D→E，D→G，BE→C，CG→B，CG→D，CE→G}或者對(duì)于CG→B，由于(CG)+=ABCDEG，所以CG→B是多余的，則Fm={AB→C，C→A，BC→D，CD→B，D→E，D→G，BE→C，CG→D，CE→G}總結(jié)：求得的最小依賴集并不是唯一的。第三十一頁，共一百一十頁，2022年，8月28日課堂練習(xí)：設(shè)有關(guān)系模式，其中U={E，F(xiàn)，G，H}，F(xiàn)={E→G，G→E，F(xiàn)→EG，H→EG，F(xiàn)H→E}，計(jì)算其等價(jià)的最小依賴集。結(jié)果為：Fm={E→G，G→E，F(xiàn)→G，H→G}

或者：Fm={E→G，G→E，F(xiàn)→G，H→E}

或者：Fm={E→G，G→E，F(xiàn)→E，H→G}

或者：Fm={E→G，G→E，F(xiàn)→E，H→E}第三十二頁，共一百一十頁，2022年，8月28日補(bǔ)充：候選碼求解理論和算法對(duì)于給定的關(guān)系R(A1,A2,…An)和函數(shù)依賴集F，可將其屬性分為4類：L類：僅出現(xiàn)在F的函數(shù)依賴左邊的屬性R類：僅出現(xiàn)在F的函數(shù)依賴右邊的屬性N類：在F的函數(shù)依賴左右邊均未出現(xiàn)的屬性LR類：在F的函數(shù)依賴左右邊均出現(xiàn)的屬性第三十三頁，共一百一十頁，2022年，8月28日1、快速求解候選碼的一個(gè)充分條件定理1：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集F，若X(X∈R)是L類屬性，則X是R的任一候選碼成員。推論：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集F，若X(X∈R)是L類屬性，且X+包含了R的全部屬性，則X必是R的唯一候選碼。例：設(shè)有關(guān)系模式R(A,B,C,D)，其函數(shù)依賴集F={D→B，B→D，AD→B，AC→D}，求R的所有候選碼。解：考察F發(fā)現(xiàn)，A、C兩屬性是L類屬性，由上面定理1可知，A、C必是R的候選碼的成員。又因?yàn)?AC)+=ABCD，所以AC必是R的唯一候選碼。第三十四頁，共一百一十頁，2022年，8月28日定理2：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集F，若X(X∈R)是R類屬性，則X不在任何候選碼中。定理3：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集F，若X(X∈R)是N類屬性，則X必包含在R的任一候選碼中。例：設(shè)有關(guān)系模式R(A,B,C,D,E,P)，其函數(shù)依賴集F={A→D，E→D，D→B，BC→D，DC→A}，求R的所有候選碼。解：考察F發(fā)現(xiàn)，C、E兩屬性是L類屬性，由上面定理1可知，C、E必是R的候選碼的成員；P是N類屬性，由上面的定理3可知，P也是R的候選碼的成員。又因?yàn)?CEP)+=ABCDEP，所以CEP必是R的唯一候選碼。定理4：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集F，若X(X∈R)是N類和L類組成的屬性集，且X+包含了R的全部屬性，則X必是R的唯一候選碼。第三十五頁，共一百一十頁，2022年，8月28日2、左邊是單屬性的函數(shù)依賴集的候選碼成員的圖論判定方法定義1：一個(gè)函數(shù)依賴圖G是一個(gè)有序二元組(R,F)，記做G=(R,F)，簡稱依賴圖。其中：(1)R=(A1,A2,…,An)是一個(gè)有限非空集，Ai(I=1,2,…,n)是G的結(jié)點(diǎn)，它們表示對(duì)應(yīng)關(guān)系模式R的屬性全集。(2)F是G的邊集，其元素是G的一條有向線段(即邊)，每條邊(Ai，Aj)表示一個(gè)函數(shù)依賴Ai→Aj，F(xiàn)是R的單屬性最小依賴集。第三十六頁，共一百一十頁，2022年，8月28日定義2：在一個(gè)函數(shù)依賴圖中有下列術(shù)語：(1)引出線/引入線：(2)原始點(diǎn)：只有引出線而無引入線的結(jié)點(diǎn)。它表示L類屬性。(3)終結(jié)點(diǎn)：只有引入線而無引出線的結(jié)點(diǎn)。它表示R類屬性。(4)途中點(diǎn)：既有引出線又有引入線的結(jié)點(diǎn)。它表示LR類屬性。(5)孤立點(diǎn)：即無引出線而無引入線的結(jié)點(diǎn)。它表示N類屬性。(6)關(guān)鍵點(diǎn)：原始點(diǎn)和孤立點(diǎn)的統(tǒng)稱。(7)關(guān)鍵屬性：關(guān)鍵點(diǎn)對(duì)應(yīng)的屬性。(8)獨(dú)立回路：不能被其他結(jié)點(diǎn)到達(dá)的回路。第三十七頁，共一百一十頁，2022年，8月28日定理5：一個(gè)關(guān)系模式R的函數(shù)依賴圖G中若存在關(guān)鍵結(jié)點(diǎn)，則關(guān)鍵結(jié)點(diǎn)對(duì)應(yīng)的屬性必在R的任何候選碼中，而所有的終結(jié)點(diǎn)必不在R的任何候選碼中。定理6：屬性集X是R的唯一候選碼的充要條件是X為能到達(dá)G中任一結(jié)點(diǎn)的關(guān)鍵屬性集。推論：在單屬性情況下，R具有唯一候選碼的充要條件是G中不存在獨(dú)立回路。定理7：設(shè)Y是途中點(diǎn)，則Y必在某個(gè)候選碼中的充要條件是Y為某一獨(dú)立回路中的結(jié)點(diǎn)。第三十八頁，共一百一十頁，2022年，8月28日定理8：設(shè)F為單屬性依賴集。R的關(guān)鍵屬性集X不能到達(dá)G中的某個(gè)結(jié)點(diǎn)，G中存在K(k>=1)個(gè)獨(dú)立回路r1,r2,…rk，各回路的結(jié)點(diǎn)集分別為：AA1={A11，A12，…A1n1}AA2={A21，A22，…A2n2}……AAk={Ak1，Ak2，…Aknn}其中Aij(I=1,2,…,k，j=1,2,…,n)都是R的屬性，則：(1)R的候選碼必不唯一(2)R的每個(gè)候選碼均由兩部分組成關(guān)鍵屬性集X(X可以為空)K個(gè)獨(dú)立回路中，每個(gè)獨(dú)立回路任選一個(gè)點(diǎn)作為候選碼的成員，候選碼的集合Y是AA1，

AA2，…，

AKk(3)候選碼的個(gè)數(shù)等于各回路中結(jié)點(diǎn)個(gè)數(shù)的乘積(4)每個(gè)候選碼所含屬性個(gè)數(shù)是一個(gè)常數(shù)，它等于關(guān)鍵屬性個(gè)數(shù)|X|＋獨(dú)立回路個(gè)數(shù)，即N=|X|+K第三十九頁，共一百一十頁，2022年，8月28日例：設(shè)有關(guān)系模式R(O,B,I,S,Q,D)，其函數(shù)依賴集F={S→D，D→S，I→B，B→I，B→O，O→B}，求R的所有候選碼。解：(1)FM=F={S→D，D→S，I→B，B→I，B→O，O→B}(2)構(gòu)造函數(shù)依賴圖，如右圖所示：sDIBQO(3)關(guān)鍵屬性集：{Q}(4)共有2條回路，SD，IBO，所以候選碼個(gè)數(shù)是2*3=6，每個(gè)候選碼的屬性個(gè)數(shù)是1+2=3。所以R的候選碼不唯一，所有候選碼為：QSI，QDI，QSB，QDB，QSO，QDO第四十頁，共一百一十頁，2022年，8月28日例：設(shè)有關(guān)系模式R(X,Y,Z,W)，其函數(shù)依賴集F={W→Y，Y→W，X→WY，Z→WY，XZ→W}，求R的所有候選碼。解：(1)FM={W→Y，Y→W，X→Y，Z→W}(2)構(gòu)造函數(shù)依賴圖，如右圖所示：WYZX(3)關(guān)鍵屬性集：{X，Z}(4)無獨(dú)立回路所以，R只有唯一候選碼XZ第四十一頁，共一百一十頁，2022年，8月28日3、多屬性依賴集候選碼求解法★★算法：多屬性依賴集候選碼求解法輸入：關(guān)系模式R及其函數(shù)依賴集F輸出：R的所有候選碼方法：(1)將R的所有屬性分為L、R、N、LR四類，并令X代表L、N類，Y代表LR類。(2)求X+，若X+包含了R的全部屬性，則X即為R的唯一候選碼，轉(zhuǎn)(5)；否則，轉(zhuǎn)(3)(3)在Y中取一屬性A，求(XA)+。若它包含了R的全部屬性，那么XA為其中一個(gè)候選碼，然后轉(zhuǎn)(4)；否則，調(diào)換一屬性反復(fù)進(jìn)行這一過程，直到試完所有Y中的屬性。(4)如果已找出所有候選碼，則轉(zhuǎn)(5)；否則在Y中依次取兩個(gè)、三個(gè)、…，求它們的屬性閉包，直到其閉包包含了R的所有屬性。(5)停止，輸出。第四十二頁，共一百一十頁，2022年，8月28日例：關(guān)系模式CSZ(CITY，ST，ZIP)，其中城市CITY，街道ST，郵政編碼ZIP。屬性的函數(shù)依賴集：F={(CITY,ST)ZIP，ZIPCITY}，試找出CSZ的候選碼。解：候選碼為(ST，ZIP)和(ST，CITY)(1)因?yàn)镾T是L類屬性，所以ST是候選碼的成員之一。CITY和ZIP是LR類。

(2)(ST)+沒有包含CSZ的所有屬性，所以ST不是唯一候選碼。

(3)(ST，ZIP)+包含CSZ的所有屬性，所以(ST,ZIP)是一個(gè)候選碼。

(4)(ST，CITY)+也包含CSZ的所有屬性，所以(ST,CITY)是一個(gè)候選碼。第四十三頁，共一百一十頁，2022年，8月28日例：設(shè)有關(guān)系模式R(A,B,C,D,E)，其函數(shù)依賴集F={A→BC，CD→E，B→D，E→A}，求R的所有候選碼。解：(1)Fm={A→B，A→C，CD→E，B→D，E→A}(2)A，B，C，D，E五個(gè)屬性在F中各個(gè)函數(shù)依賴的右邊和左邊都出現(xiàn)了，所以候選碼中可能包含A，B，C，D，E。(4)除去A，E兩個(gè)候選碼，在B，C，D中查找兩個(gè)屬性的候選碼

(BC)+=ABCDE，即BC→U，所以BC是一個(gè)候選碼

(BD)+=BD，即BC→U，所以BD不是一個(gè)候選碼

(CD)+=ABCDE，即CD→U，所以CD是一個(gè)候選碼(3)A+=ABCDE，即A→U，所以A是一個(gè)候選碼

B+，C+，D+→U，所以B，C，D不是候選碼

E+=ABCDE，即E→U，所以也E是一個(gè)候選碼候選碼有：A，E，BC，CD第四十四頁，共一百一十頁，2022年，8月28日課堂練習(xí)：1、設(shè)有關(guān)系模式，其中U={A，B，C，D，E，P，H，G}，F(xiàn)={AB→CE，A→C，GP→B，EP→A，CDE→P，HB→P，D→HG，ABC→PG}，計(jì)算其等價(jià)的最小依賴集。Fm={AB→E，A→C，GP→B，EP→A，CDE→P，HB→P，D→H，D→G，ABC→P，ABC→G}2、設(shè)有關(guān)系模式R(A,B,C,D,E,P)，其函數(shù)依賴集F={A→B，C→P，E→A，CE→D}，求R的所有候選碼。候選碼為：CE3、設(shè)有關(guān)系模式R(S,D,I,B,O,Q)，其函數(shù)依賴集F={S→D，I→B，B→O，O→Q，Q→I}，求R的所有候選碼。候選碼為：SI，SB，SQ，SO第四十五頁，共一百一十頁，2022年，8月28日6.2.3-6.2.6范式一、規(guī)范化和范式 關(guān)系模式設(shè)計(jì)的不好，會(huì)引起插入、刪除、更新異常。在70年代，諸多專家和學(xué)者，各自研究了發(fā)生異常的類型及防止異常的方法，使得設(shè)計(jì)關(guān)系的準(zhǔn)則得到了改進(jìn)。這些用以防止異常發(fā)生的準(zhǔn)則(技術(shù))叫做規(guī)范化。規(guī)范化的關(guān)系模式被稱為范式。范式是更符合某些規(guī)則的關(guān)系模式。關(guān)系規(guī)范化可按屬性間不同的依賴程度分為第一范式、第二范式、第三范式、Boyce-Codd范式以及第四范式。人們對(duì)規(guī)范化的認(rèn)識(shí)是有一個(gè)過程的，在1970年時(shí)已發(fā)現(xiàn)屬性間的函數(shù)依賴關(guān)系，從而定義了與函數(shù)依賴關(guān)系有關(guān)的第一、第二、第三范式；1974年Codd和Boyce共同提出BCNF范式。在1976~1978年間，F(xiàn)agin，Delobe以及Zanjolo發(fā)現(xiàn)了多值依賴關(guān)系，從而定義了與多值依賴有關(guān)的第四范式。以后又有人提出了5NF。第四十六頁，共一百一十頁，2022年，8月28日二、規(guī)范化的方法——分解 研究產(chǎn)生異常的原因發(fā)現(xiàn)：如果一個(gè)關(guān)系模式中包含兩個(gè)或多個(gè)不同問題的事實(shí)，如：學(xué)生(sno，sdept、dean、cno、grade)

。增加一行時(shí)，必須增加關(guān)于兩個(gè)或多個(gè)主題的數(shù)據(jù)，刪除一行時(shí)，也必須刪除關(guān)于兩個(gè)或多個(gè)主題的數(shù)據(jù)。因此，將關(guān)系規(guī)范化，就是讓每個(gè)關(guān)系只有一個(gè)主題，如果某個(gè)關(guān)系模式有多于一個(gè)的主題，就把他們分解成多個(gè)關(guān)系(二維表)，就像我們寫文章，一個(gè)自然段中只有一個(gè)中心內(nèi)容。第四十七頁，共一百一十頁，2022年，8月28日三、范式級(jí)別

1NF2NF3NFBCNF4NF5NF其規(guī)范化的條件按上述次序越來越強(qiáng)。范式概念可以理解為符合某一種級(jí)別的關(guān)系模式的集合，關(guān)系模式R為第幾范式可以寫成RxNF。把低級(jí)范式的關(guān)系模式，通過分解轉(zhuǎn)換為高一級(jí)范式的關(guān)系模式的集合，這個(gè)過程稱為關(guān)系模式的規(guī)范化設(shè)計(jì)。第四十八頁，共一百一十頁，2022年，8月28日第一范式(1NF)第一范式（1NF）：規(guī)定關(guān)系的每一個(gè)分量必須是一個(gè)不可分的數(shù)據(jù)項(xiàng)。關(guān)系數(shù)據(jù)模型要求所有的關(guān)系模式必須滿足第一范式的要求。這是對(duì)關(guān)系模式最起碼的規(guī)范化要求。第四十九頁，共一百一十頁，2022年，8月28日非第一范式的例子如果關(guān)系模式僅僅滿足第一范式的條件是不夠的，可能會(huì)存在數(shù)據(jù)冗余和操作異常。為了消除這些數(shù)據(jù)冗余和操作異常，需要進(jìn)行關(guān)系模式的規(guī)范化。轉(zhuǎn)換為第一范式姓名單位辦公電話住宅電話手機(jī)號(hào)碼姓名單位聯(lián)系電話辦公電話住宅電話手機(jī)號(hào)碼第五十頁，共一百一十頁，2022年，8月28日第二范式(2NF)定義6.6：如果關(guān)系模式R滿足第一范式，且它的任何一個(gè)非主屬性都完全函數(shù)依賴于任一個(gè)候選碼，則R滿足第二范式（簡記為R2NF）。第五十一頁，共一百一十頁，2022年，8月28日例：學(xué)生表D(Sno,Sname,Sdept,Sage,Cno,Cname,Credit,Grade)是1NF但不是2NF的關(guān)系模式Sno(5)Sname(10)Sdept(10)Sage(2)Cno(5)Cname(20)Credit(2)Grade(2)0001張三計(jì)算機(jī)17c101數(shù)據(jù)結(jié)構(gòu)4900001張三計(jì)算機(jī)17c102網(wǎng)絡(luò)安全3880001張三計(jì)算機(jī)17c103軟件工程4780001張三計(jì)算機(jī)17c105數(shù)值分析2800001張三計(jì)算機(jī)17c110編譯原理3860002李四物理19c103軟件工程4820002李四物理19c105數(shù)值分析2800003王五計(jì)算機(jī)17c107C語言475第五十二頁，共一百一十頁，2022年，8月28日在關(guān)系模式D中，非主屬性Sname，sdept，sage對(duì)碼是部分函數(shù)依賴。D屬于1NF，但不屬于2NF。則D表的函數(shù)依賴如下：sno→sname，sno→sdept，sno→sageCno→Cname，cno→credit(Sno,Cno)→Grade候選碼是(Sno，Cno)，其函數(shù)依賴圖為：SnoCnoGradecreditCnamesdeptsagesname第五十三頁，共一百一十頁，2022年，8月28日根據(jù)第二范式的定義，為消除部分函數(shù)依賴，將D關(guān)系模式分解為s、c和sc這3個(gè)關(guān)系模式：sc(Sno，Cno，Grade)

函數(shù)依賴是：(Sno，Cno)→GradeS(sno,sname,sdept,sage)

函數(shù)依賴是：sno→sname，sno→sdept，sno→sageC(Cno，Cname，credit)

函數(shù)依賴是：(Cno→Cname,Cno→credit)sc、S和C都消除了非主屬性對(duì)碼的部分函數(shù)依賴，因此都屬于2NF。第五十四頁，共一百一十頁，2022年，8月28日Sno(5)Sname(10)Sdept(10)Sage(2)0001張三計(jì)算機(jī)170002李四物理190003王五計(jì)算機(jī)17Sno(5)Cno(5)Grade(2)0001c101900001c102880001c103780001c105800001c110860002c103820002c105800003c10775關(guān)系s關(guān)系scCno(5)Cname(20)Credit(2)c101數(shù)據(jù)結(jié)構(gòu)4c102網(wǎng)絡(luò)安全3c103軟件工程4c105數(shù)值分析2c107C語言4c110編譯原理3關(guān)系c是否存在冗余？盡管增加了字段，但字節(jié)數(shù)減少=(5+10+10+2)*3+(5+5+2)*8+(5+20+2)*6=339是否存在更新異?，F(xiàn)象？第五十五頁，共一百一十頁，2022年，8月28日練習(xí)：設(shè)有關(guān)系模式如下：T(Sno，Cno，Cname，Tname，room，Grade)若每門課只由一位教師講授但一個(gè)教師可以講授多門課程，每位教師只在一個(gè)教室中講課。SnoCnoGradeCnameTnameroomS1C178數(shù)據(jù)庫李美麗1234S1C289C語言李美麗1234S2C186數(shù)據(jù)庫李美麗1234S2C296C語言李美麗1234S3C246C語言李美麗1234S3C381英語李剛3422第五十六頁，共一百一十頁，2022年，8月28日SnoCnoGradeTnameroomCname在關(guān)系模式T中，非主屬性Cname，Tname，room對(duì)碼是部分函數(shù)依賴，并存在傳遞函數(shù)依賴Cno→Tname，Tname→room。T屬于1NF，但不屬于2NF。則T表的函數(shù)依賴如下：

(Sno,Cno)→GradeCno→CnameCno→TnameTname→room候選碼是(Sno，Cno)第五十七頁，共一百一十頁，2022年，8月28日根據(jù)第二范式的定義，為消除部分函數(shù)依賴，將T關(guān)系模式分解為T1和C這2個(gè)關(guān)系模式：T1(Sno，Cno，Grade)

函數(shù)依賴是：(Sno，Cno)→GradeC(Cno，Cname，Tname，room)

函數(shù)依賴是:(Cno→Cname,Cno→Tname,Tname→room)T1和C都消除了非主屬性對(duì)碼的部分函數(shù)依賴，因此都屬于2NF。第五十八頁，共一百一十頁，2022年，8月28日CnoCnameTnameroomC1數(shù)據(jù)庫李美麗1234C2C語言李美麗1234C3英語李剛3422SnoCnoGradeS1C178S1C289S2C186S2C296S3C246S3C381關(guān)系T1關(guān)系C第五十九頁，共一百一十頁，2022年，8月28日一個(gè)關(guān)系模式僅僅滿足2NF仍是不夠的，如在關(guān)系模式C(Cno，Cname，Tname，room)中，仍存在著插入、刪除和修改異常問題：

--新來的教師，還沒有分配授課之前，教師的姓名及教室編號(hào)都不能加到關(guān)系中；

--如果要修改教室編號(hào)，必須修改與教師授課相對(duì)應(yīng)的所有元組中的教室編號(hào)，因?yàn)橐晃唤處熆赡軙?huì)教多門課。

--如果要?jiǎng)h除c3這門課程，則殃及李剛老師的教師編號(hào)也被刪除。存在上述這些問題的原因是關(guān)系模式C中存在非主屬性對(duì)碼的傳遞函數(shù)依賴，所以要把關(guān)系模式C向第三范式轉(zhuǎn)化，除去非主屬性對(duì)碼的傳遞函數(shù)依賴。第六十頁，共一百一十頁，2022年，8月28日第三范式(3NF)

定義6.7如果關(guān)系模式R滿足2NF，并且它的任何一個(gè)非主屬性都不傳遞函數(shù)依賴于任何候選碼，則稱R是第三范式3NF,記作R3NF。第六十一頁，共一百一十頁，2022年，8月28日在上一例題中，關(guān)系模式：C(Cno，Cname，Tname，room)其中存在非主屬性room對(duì)碼的傳遞函數(shù)依賴，即：Cno→Tname，Tname→room，因此C不屬于3NF。分解方法：將起傳遞作用的函數(shù)關(guān)系中的主屬性(決定方)和非主屬性取出單獨(dú)構(gòu)成一個(gè)關(guān)系模式，再將它的決定方和關(guān)系式中余下的屬性加上主碼，構(gòu)成另一個(gè)關(guān)系模式。所以，將C分解為：C1(Cno,Cname,Tname)F={Cno→Tname,Cno→Cname}L(Tname，room)F={Tname→ROOM}則關(guān)系模式C1和L中都沒有非主屬性對(duì)碼的傳遞函數(shù)依賴，因此都屬于3NF。第六十二頁，共一百一十頁，2022年，8月28日至此，關(guān)系模式T分解為下列3個(gè)屬于3NF的一組關(guān)系模式：

T1(Sno,Cno,Grade)C1(Cno,Cname,Tname)L(Tname,room)如下一張幻燈片和關(guān)系模式T相比，這些關(guān)系模式是對(duì)現(xiàn)實(shí)世界更加精確的描述。把這3個(gè)關(guān)系進(jìn)行連接，總能重構(gòu)初始的關(guān)系。第六十三頁，共一百一十頁，2022年，8月28日CnoCnameTnameC1數(shù)據(jù)庫李美麗C2C語言李美麗C3英語李剛SnoCnoGradeS1C178S1C289S2C186S2C296S3C246S3C381關(guān)系T1關(guān)系C1Tnameroom李美麗1234李剛3422關(guān)系L第六十四頁，共一百一十頁，2022年，8月28日第三范式還有問題嗎？？？例：關(guān)系模式STJ(S學(xué)生，T教師，J課程)，其包含的語義是：每位教師只教一門課程；每門課有若干個(gè)教師，某一學(xué)生選定某門課，就對(duì)應(yīng)一個(gè)固定的老師。根據(jù)語義存在的函數(shù)依賴？F={T→J，SJ→T，ST→J}此關(guān)系的碼是：ST或SJ該關(guān)系屬于第幾范式？該關(guān)系有沒有部分函數(shù)依賴和傳遞函數(shù)依賴呢？？結(jié)論：STJ模式，因?yàn)闆]有非主屬性的部分函數(shù)依賴和傳遞函數(shù)依賴，所以∈3NFSTJS4王建華數(shù)據(jù)結(jié)構(gòu)(計(jì)算機(jī))S2趙穎數(shù)據(jù)結(jié)構(gòu)(電子)S3趙穎數(shù)據(jù)結(jié)構(gòu)(電子)S1陳訊C語言程序設(shè)計(jì)S2陳訊C語言程序設(shè)計(jì)第六十五頁，共一百一十頁，2022年，8月28日在這個(gè)表中，仍然存在著數(shù)據(jù)冗余、插入異常、刪除異常。數(shù)據(jù)冗余：若選趙穎老師課的有30人，則要重復(fù)30次趙穎和數(shù)據(jù)結(jié)構(gòu)。插入異常：有一個(gè)新老師開設(shè)了一門新的課程，在沒有學(xué)生選課的情況下，是不能插入的。刪除異常：刪除s4學(xué)生時(shí)，也刪除了王建華老師所教授的計(jì)算機(jī)專業(yè)的數(shù)據(jù)結(jié)構(gòu)課程。修改復(fù)雜：課程改名，則所有選修的學(xué)生所在元組都要修改。第六十六頁，共一百一十頁，2022年，8月28日Boyce的新發(fā)現(xiàn)：已經(jīng)屬于第三范式的關(guān)系模式仍會(huì)出現(xiàn)數(shù)據(jù)冗余、插入異常、刪除異常等問題。原因是：T→J，但T不是碼。第六十七頁，共一百一十頁，2022年，8月28日BCNF范式

BCNF(BoyceCoddNormalForm)是由Boyce和Codd提出的，通常認(rèn)為是3NF的修正，有時(shí)也稱為擴(kuò)充的第三范式。定義6.8關(guān)系模式R1NF，若對(duì)于R中的每個(gè)函數(shù)依賴XY，且YX時(shí)，X必含有候選碼，則RBCNF。也就是說，關(guān)系模式R中，若R的每一個(gè)決定因素都包含候選碼，則RBCNF。第六十八頁，共一百一十頁，2022年，8月28日所以，一個(gè)滿足BCNF的關(guān)系模式，應(yīng)具有如下性質(zhì)：每個(gè)非主屬性對(duì)每個(gè)碼都是完全函數(shù)依賴和非傳遞函數(shù)依賴；所有主屬性對(duì)每個(gè)不包含它的碼也是完全函數(shù)依賴；沒有任何屬性完全函數(shù)依賴于非碼。若RBCNF，則R3NF。若R3NF，則R不一定屬于BCNF。由第三范式規(guī)范化成BCNF的方法仍然是投影分解：

ST(S,T)TJ(T,J)S4王建華S2趙穎S3趙穎S1陳訊S2陳訊王建華數(shù)據(jù)結(jié)構(gòu)(計(jì)算機(jī))趙穎數(shù)據(jù)結(jié)構(gòu)(電子)陳訊C語言程序設(shè)計(jì)前面所說的問題是否得到緩解呢？第六十九頁，共一百一十頁，2022年，8月28日例：一個(gè)是3NF但不是BCNF的關(guān)系模式CSZ

關(guān)系模式CSZ(CITY，ST，ZIP)，其中城市CITY，街道ST，郵政編碼ZIP。屬性的函數(shù)依賴集：F={(CITY,ST)ZIP，ZIPCITY}候選碼：(CITY,ST)或(ST,ZIP)CITY，ST，ZIP都是主屬性，該關(guān)系模式?jīng)]有非主屬性。 關(guān)系模式CSZ3NF。但是，關(guān)系模式CSZBCNF，因?yàn)楹瘮?shù)依賴ZIPCITY的決定因素ZIP不是碼。對(duì)于不是BCNF的關(guān)系模式，仍然存在不合適的地方。例如：當(dāng)城市已經(jīng)設(shè)置，并確定郵政編碼，但還沒有建立街道，則該城市和郵政編碼的信息就不能加入到數(shù)據(jù)庫中。非BCNF的關(guān)系模式可以通過分解成為BCNF。若將關(guān)系模式CSZ分解為兩個(gè)關(guān)系模式：Z_C(ZIP，CITY)和S_Z(ST，ZIP),它們就都是BCNF的關(guān)系模式了。第七十頁，共一百一十頁，2022年，8月28日6.2.7多值依賴前面所講完全是函數(shù)依賴的范疇內(nèi)討論關(guān)系模式問題。如果僅考慮函數(shù)依賴這一種數(shù)據(jù)依賴，屬于BCNF的關(guān)系模式就已經(jīng)很完美了。但如果考慮其他數(shù)據(jù)依賴，例如多值依賴，屬于BCNF的關(guān)系模式仍存在問題，不能算作是一個(gè)完美的關(guān)系模式。例：設(shè)學(xué)校中某一門課程由多個(gè)教師講授，他們使用相同的一套參考書。每個(gè)教師可以講授多門課程，每種參考書可以供多門課程使用。用一個(gè)非規(guī)范化的關(guān)系來表示課程c、教師t、參考書b之間的關(guān)系。課程c教師t參考書b物理李勇普通物理學(xué)光學(xué)原理物理習(xí)題集王軍數(shù)學(xué)張平數(shù)學(xué)分析微分方程李勇第七十一頁，共一百一十頁，2022年，8月28日課程c教師t參考書b物理李勇普通物理學(xué)物理李勇光學(xué)原理物理李勇物理習(xí)題集物理王軍普通物理學(xué)物理王軍光學(xué)原理物理王軍物理習(xí)題集數(shù)學(xué)張平數(shù)學(xué)分析數(shù)學(xué)張平微分方程數(shù)學(xué)李勇數(shù)學(xué)分析數(shù)學(xué)李勇微分方程轉(zhuǎn)換分析：關(guān)系模式Teaching(c,t,b)的碼為(c,t,b)，即為全碼。因而Teaching∈BCNF。但存在一些問題：數(shù)據(jù)冗余度大：每一門課程的參考書是固定的，但Teaching關(guān)系中，有多少名任課教師，參考書就要存儲(chǔ)多少次，造成大量的數(shù)據(jù)冗余。插入煩：當(dāng)某一門課程增加一名任課教師時(shí)，該課程有多少本參考書，就必須插入多少個(gè)元組。刪除煩：某一門課程要去掉一本參考書，該課程有多少名教師，就必須刪除多少個(gè)元組。修改煩：某一門課程要修改一本參考書，該課程有多少名教師，就必須修改多少個(gè)元組。第七十二頁，共一百一十頁，2022年，8月28日造成這些問題的原因是：在這個(gè)關(guān)系模式中，對(duì)于一門課程，有一組屬于本課程的參考書，無論這門課程是由哪個(gè)教師來教授都是選擇這幾本參考書。所以，每本參考書由課程決定，而與該課程的教師無關(guān)。即b與t彼此無關(guān)，卻因?yàn)閏而摻在一起，這就是參考書多值依賴于課程。多值依賴MVD(MultivaluedDependency)：對(duì)于一個(gè)屬性值，另一個(gè)屬性值有多個(gè)值與其對(duì)應(yīng)。而且多值屬性之間無關(guān)。定義6.9：有關(guān)系模式R(U)，其中X、Y、Z是U的子集，并且Z=U-X-Y，關(guān)系模式R(U)中，當(dāng)且僅當(dāng)滿足下列性質(zhì)：對(duì)R(U)的任一關(guān)系r，給定一對(duì)(x,z)的值，就有一組y的值與之相對(duì)應(yīng)，而且這組y的值只依賴于x的值，而與z的值無關(guān)。則稱Y多值依賴于X，記作X→→Y第七十三頁，共一百一十頁，2022年，8月28日第四范式定義6.10關(guān)系模式R1NF，若對(duì)于R中的每個(gè)非平凡多值依賴XY，且YX時(shí)，X必含有候選碼，則R4NF。第七十四頁，共一百一十頁，2022年，8月28日課程c教師t物理李勇物理王軍數(shù)學(xué)張平數(shù)學(xué)李勇課程c參考書b物理普通物理學(xué)物理光學(xué)原理物理物理習(xí)題集數(shù)學(xué)數(shù)學(xué)分析數(shù)學(xué)微分方程關(guān)系ct關(guān)系cb通過投影分解法可以消除非平凡的多值依賴，得到符合4NF的兩個(gè)關(guān)系：如此，上述問題得到緩解：（1）參考書只需要在CB關(guān)系中存儲(chǔ)一次——降低冗余（2）當(dāng)某一課程增加一名任課教師時(shí)，只需要在CT中增加一元組——降低增加的復(fù)雜性（3）當(dāng)某一門課程要去掉一本參考書時(shí)，只需要在CB中刪除一元組——降低刪除的復(fù)雜性第七十五頁，共一百一十頁，2022年，8月28日關(guān)于范式的辨證思考：范式揭示了一個(gè)關(guān)系框架中，各屬性之間不同類型，不同層次的依賴關(guān)系。對(duì)于一個(gè)信息系統(tǒng)來說，如果所設(shè)計(jì)的數(shù)據(jù)庫，均有良好的、合理的范式級(jí)別，那么，系統(tǒng)的正確性將自動(dòng)得到某種保證。規(guī)范化準(zhǔn)則是經(jīng)過周密思考的，它作為設(shè)計(jì)數(shù)據(jù)庫過程中的非常有用的輔助工具，直到數(shù)據(jù)庫的邏輯設(shè)計(jì)。但它不像數(shù)學(xué)中嚴(yán)密的定理證明和運(yùn)用，決不是萬靈的妙藥。需要設(shè)計(jì)者具體情況具體對(duì)待。關(guān)于范式的級(jí)別問題，不是級(jí)別越高，數(shù)據(jù)庫模式越好。有時(shí)，有極其正當(dāng)?shù)睦碛?，不將?guī)范化進(jìn)行到底，要根據(jù)實(shí)際應(yīng)用情況，決定達(dá)到第幾范式，一般情況下，達(dá)到3NF就可以了。第七十六頁，共一百一十頁，2022年，8月28日模式設(shè)計(jì)示例例1：訂購的關(guān)系模式：訂購（客戶名，住址，聯(lián)系電話，書號(hào)，書名，作者，出版社，社址）該關(guān)系模式的函數(shù)依賴集：F={客戶名→住址，客戶名→聯(lián)系電話，書號(hào)→書名，書號(hào)→作者，書號(hào)→出版社，出版社→社址}訂購關(guān)系的候選碼是(客戶名，書號(hào))。函數(shù)依賴圖如下：客戶名書號(hào)住址聯(lián)系電話書名作者出版社社址第一步：該模式屬于1NF，滿足的條件是元組的每個(gè)分量必須是不可分的數(shù)據(jù)項(xiàng)，但存在部分函數(shù)依賴和傳遞函數(shù)依賴。是一個(gè)不好的關(guān)系模式。第七十七頁，共一百一十頁，2022年，8月28日第二步：修改設(shè)計(jì)使其滿足2NF訂購關(guān)系不屬于2NF，因?yàn)榇嬖诜侵鲗傩詫?duì)碼的部分函數(shù)依賴，如：客戶名→住址，客戶名→聯(lián)系電話，書號(hào)→書名，書號(hào)→作者，書號(hào)→出版社。將訂購關(guān)系進(jìn)行分解，消除部分函數(shù)依賴，得到三個(gè)關(guān)系模式符合2NF要求：客戶(客戶名，住址，聯(lián)系電話)圖書(書號(hào)，書名，作者，出版社，社址)訂購(客戶名，書號(hào))在圖書關(guān)系中，仍然存在數(shù)據(jù)冗余，以及插入和刪除異常。第七十八頁，共一百一十頁，2022年，8月28日第三步：修改設(shè)計(jì)使其滿足3NF圖書關(guān)系不屬于3NF，因?yàn)榇嬖诜侵鲗傩詫?duì)碼的傳遞函數(shù)依賴，如：書號(hào)→出版社→社址，消除傳遞函數(shù)依賴，將圖書分解如下：圖書（書號(hào)，書名，作者，出版社）出版社（出版社，社址）至此，關(guān)系模式訂購分解為4個(gè)3NF的關(guān)系模式：客戶(客戶名，住址，聯(lián)系電話)圖書(書號(hào)，書名，作者，出版社)訂購(客戶名，書號(hào))出版社（出版社，社址）第七十九頁，共一百一十頁，2022年，8月28日第四步：修改設(shè)計(jì)使其滿足BCNF關(guān)系模式訂購分解為4個(gè)3NF的關(guān)系模式，實(shí)際上也滿足BCNF。例如：關(guān)系模式客戶(客戶名，住址，聯(lián)系電話)只有一個(gè)碼“客戶名”，沒有任何非主屬性對(duì)碼有部分和傳遞函數(shù)依賴，所以客戶∈3NF。同時(shí)，客戶中客戶名是唯一的決定因素，因此客戶∈BCNF第八十頁，共一百一十頁，2022年，8月28日例題：設(shè)有如下所示的關(guān)系R課程名教師名教師地址C1張三D1C2李四D1C3王五D2C4李四D1它是第幾范式？為什么？(2)是否存在數(shù)據(jù)冗余及各種異?，F(xiàn)象？若存在，則說明是在什么情況下發(fā)生？(3)將它分解為高一級(jí)范式，分解后的關(guān)系如何解決分解前可能存在的各種異常問題。第八十一頁，共一百一十頁，2022年，8月28日解:(1)它是2NF。因?yàn)镽的候選碼為課程名，而“課程名→教師名”成立，“教師名→課程名”不成立。又“教師名→教師地址”，所以課程名教師地址，即存在非主屬性教師地址對(duì)候選碼課程名的傳遞函數(shù)依賴，因此R不是3NF。這里面不存在非主屬性對(duì)候選碼的的部分函數(shù)依賴，所以R是2NF。

(2)存在。當(dāng)刪除某門課程時(shí)會(huì)刪除不該刪除的教師的有關(guān)信息。

(3)分解為高一級(jí)范式如下所示：T課程名教師名C1張三C2李四C3王五C4李四教師名教師地址張三D1李四D2王五D3R1R2分解后，若刪除課程數(shù)據(jù)時(shí)，僅對(duì)關(guān)系R1操作，教師地址信息在關(guān)系R2中還是保留著,不會(huì)丟失教師方面的信息。第八十二頁，共一百一十頁，2022年，8月28日例3：指出下列關(guān)系模式是第幾范式？并說明理由。(1)R(X,Y,Z)F={XY→Z}(2)R(X,Y,Z)F={Y→Z，XZ→Y}(3)R(X,Y,Z)F={Y→Z，Y→X，X→YZ}(4)R(X,Y,Z)F={X→Y，X→Z}(5)R(W,X,Y,Z)F={X→Z，WX→Y}解:(1)候選碼為XY，所以R∈BCNF(2)候選碼為XY和XZ，x,y,z都是主屬性，所以R∈3NF，又因?yàn)閅→Z，Y不是碼，所以R不屬于BCNF(3)FM={Y→Z，Y→X，X→Y,X→Z}，候選碼為X和Y，不存在部分函數(shù)依賴和傳遞函數(shù)依賴，并且函數(shù)依賴的左邊都是碼，所以R∈BCNF(4)候選碼為X，所以R∈BCNF(5)候選碼為WX，因?yàn)閄→Z，存在部分函數(shù)依賴，所以R∈1NF第八十三頁，共一百一十頁，2022年，8月28日學(xué)號(hào)姓名班級(jí)專業(yè)9901001陳小蕾計(jì)算機(jī)9901班計(jì)算機(jī)應(yīng)用專業(yè)9901002李泉勇計(jì)算機(jī)9901班計(jì)算機(jī)應(yīng)用專業(yè)9901003張小芳計(jì)算機(jī)9901班計(jì)算機(jī)應(yīng)用專業(yè)9903003于小波建筑9902班建筑設(shè)計(jì)專業(yè)9903002李群建筑9902班建筑設(shè)計(jì)專業(yè)9905056高明服裝9901班服裝設(shè)計(jì)專業(yè)練習(xí)：設(shè)有如下學(xué)生關(guān)系(1)學(xué)生關(guān)系屬于第幾范式？為什么(2)將關(guān)系規(guī)范化到3NF。第八十四頁，共一百一十頁，2022年，8月28日解:(1)它屬于第2范式,因?yàn)榉侵鲗傩远际峭耆瘮?shù)依賴于候選建學(xué)號(hào)，但上表中存在傳遞函數(shù)依賴，即“專業(yè)”傳遞函數(shù)依賴于“學(xué)號(hào)”，不是3NF。

(2)規(guī)范化到3NF如下：學(xué)號(hào)姓名班級(jí)9901001陳小蕾計(jì)算機(jī)9901班9901002李泉勇計(jì)算機(jī)9901班9901003張小芳計(jì)算機(jī)9901班9903003于小波建筑9902班9903002李群建筑9902班9905056高明服裝9901班班級(jí)專業(yè)計(jì)算機(jī)9901班計(jì)算機(jī)應(yīng)用專業(yè)建筑9902班建筑設(shè)計(jì)專業(yè)服裝9901班服裝設(shè)計(jì)專業(yè)學(xué)生表班級(jí)專業(yè)表第八十五頁，共一百一十頁，2022年，8月28日消除非主屬性對(duì)碼的部分函數(shù)依賴消除非主屬性對(duì)碼的傳遞函數(shù)依賴消除主屬性對(duì)碼的部分和傳遞函數(shù)依賴1NF2NF3NFBCNF關(guān)系模式的規(guī)范化，是通過對(duì)關(guān)系模式的分解實(shí)現(xiàn)的。分解的實(shí)質(zhì)：“一事一表”，讓一個(gè)關(guān)系只描述一個(gè)實(shí)體或聯(lián)系，使關(guān)系單一化，以利于處理簡單化。小結(jié)第八十六頁，共一百一十頁，2022年，8月28日 規(guī)范化過程就是把一個(gè)關(guān)系模式分解為若干個(gè)關(guān)系模式，而且這種分解應(yīng)該是可逆的。所謂可逆，是要求模式的分解是沒有信息丟失，并保證分解后產(chǎn)生的關(guān)系模式集合和原來的關(guān)系模式等價(jià)。 如何對(duì)關(guān)系模式進(jìn)行分解才能保證沒有信息丟失呢？ 對(duì)于同一個(gè)關(guān)系模式可能有多種分解方案。下面的例子給出三種分解方案，如何判斷哪種分解方案更好呢？6.4關(guān)系模式的分解第八十七頁，共一百一十頁，2022年，8月28日三種分解方案(模式分解不唯一)例：關(guān)系模式S(Sno,sdept,dean)。何D2s3何D2s2羅D1s1deanSdeptSnoF={Sno→sdept，sdept→dean}S1是哪個(gè)系的學(xué)生？何是哪個(gè)系的系主任呢？D1的系主任是誰呢？做連接snosdeptdeans1d1羅s1d1何s1d2羅s1d2何…………聯(lián)接后問題沒有得到解決，原因是沒有保持函數(shù)依賴。第一種分解：SnoS1S2S3Sdeptd1d2dean羅何∈3NF第八十八頁，共一百一十頁，2022年，8月28日snosdeptdeanS1D1羅S2D2何S3D2何做自然連接分解后可以恢復(fù)原關(guān)系，但數(shù)據(jù)冗余問題沒有得到解決，問題是丟失了函數(shù)依賴sdept→dean。D1的系主任是誰呢？何是哪個(gè)系的系主任呢？關(guān)系模式S(Sno,sdept,dean)，F(xiàn)={Sno→sdept，sdept→dean}第二種分解：SnosdeptS1d1S2d2S3d2SnodeanS1羅S2何S3何∈3NF第八十九頁，共一百一十頁，2022年，8月28日snosdeptdeanS1D1羅S2D2何S3D2何做自然連接問題得到了徹底解決，即不丟失信息，也減少了冗余。關(guān)系模式S(Sno,sdept,dean)，F(xiàn)