第06章 關(guān)系數(shù)據(jù)及其規(guī)范化理論

第6章

關(guān)系數(shù)據(jù)及其規(guī)范化理論數(shù)據(jù)庫設(shè)計(jì)任務(wù)針對給定的應(yīng)用環(huán)境和用戶需求，建立一個(gè)合理的數(shù)據(jù)庫模式，使數(shù)據(jù)庫系統(tǒng)能夠高效地存儲和管理數(shù)據(jù)。指導(dǎo)工具規(guī)范化理論它主要研究的是關(guān)系模式中各屬性之間的依賴關(guān)系及其對關(guān)系模式的影響，探討良好的關(guān)系模式應(yīng)具備的特性，以及使關(guān)系模式達(dá)到良好的方法。6.1問題的提出6.1.1關(guān)系模式中可能存在的問題【例6.1】設(shè)有一個(gè)訂購關(guān)系模式R(訂單編號orderID，訂單日期orderDate，客戶編號custID，送貨地址orderAddress，客戶名稱custName，商品編號pdID，商品名稱pdName，訂購數(shù)量quantity)。orderIDorderDatecustIDorderAddresscustNamepdIDpdNamequantityD2010051616280012010-5-16901北京市朝陽區(qū)聯(lián)盟小區(qū)9號樓里奇11201羽毛球拍10D2010051616280012010-5-16901北京市朝陽區(qū)聯(lián)盟小區(qū)9號樓里奇11203羽毛球40D2010051616280012010-5-16901北京市朝陽區(qū)聯(lián)盟小區(qū)9號樓里奇11206籃球15D2010051716300022010-5-17903上海市虹梅路201號張松林12202羽毛球拍4D2010051716300022010-5-17903上海市虹梅路201號張松林11203羽毛球5D2010060609230032010-6-6905廣州市江南大道中82號賈立委11206籃球10D2010060609230032010-6-6905廣州市江南大道中82號賈立委11209足球10D2010061016280042010-6-10901北京市海淀區(qū)光華路55號里奇12202羽毛球拍10D2010061016280042010-6-10901北京市海淀區(qū)光華路55號里奇11205羽毛球20D2010061016280042010-6-10901北京市海淀區(qū)光華路55號里奇11208籃球10D2010061016280042010-6-10901北京市海淀區(qū)光華路55號里奇11210足球10D2010070109160052010-7-1902北京市北四環(huán)中路35號環(huán)宇11207籃球5D2010070109160052010-7-1902北京市北四環(huán)中路35號環(huán)宇11210足球5R中存在的問題數(shù)據(jù)冗余是指相同數(shù)據(jù)在數(shù)據(jù)庫中多次重復(fù)存儲

導(dǎo)致的問題：不僅會浪費(fèi)存儲空間，而且可能造成數(shù)據(jù)的不一致性。orderIDorderDatecustIDorderAddresscustNamepdIDpdNamequantityD2010051616280012010-5-16901北京市朝陽區(qū)聯(lián)盟小區(qū)9號樓里奇11201羽毛球拍10D2010051616280012010-5-16901北京市朝陽區(qū)聯(lián)盟小區(qū)9號樓里奇11203羽毛球40D2010051616280012010-5-16901北京市朝陽區(qū)聯(lián)盟小區(qū)9號樓里奇11206籃球15D2010051716300022010-5-17903上海市虹梅路201號張松林12202羽毛球拍4D2010051716300022010-5-17903上海市虹梅路201號張松林11203羽毛球5D2010060609230032010-6-6905廣州市江南大道中82號賈立委11206籃球10D2010060609230032010-6-6905廣州市江南大道中82號賈立委11209足球10D2010061016280042010-6-10901北京市海淀區(qū)光華路55號里奇12202羽毛球拍10D2010061016280042010-6-10901北京市海淀區(qū)光華路55號里奇11205羽毛球20D2010061016280042010-6-10901北京市海淀區(qū)光華路55號里奇11208籃球10D2010061016280042010-6-10901北京市海淀區(qū)光華路55號里奇11210足球10D2010070109160052010-7-1902北京市北四環(huán)中路35號環(huán)宇11207籃球5D2010070109160052010-7-1902北京市北四環(huán)中路35號環(huán)宇11210足球5R中存在的問題(續(xù))更新異常插入異常：希望保存的數(shù)據(jù)無法存入數(shù)據(jù)庫修改異常：潛在的數(shù)據(jù)的不一致性刪除異常：不想刪除的數(shù)據(jù)刪除了orderIDorderDatecustIDorderAddresscustNamepdIDpdNamequantityD2010051616280012010-5-16901北京市朝陽區(qū)聯(lián)盟小區(qū)9號樓里奇11201羽毛球拍10D2010051616280012010-5-16901北京市朝陽區(qū)聯(lián)盟小區(qū)9號樓里奇11203羽毛球40D2010051616280012010-5-16901北京市朝陽區(qū)聯(lián)盟小區(qū)9號樓里奇11206籃球15D2010051716300022010-5-17903上海市虹梅路201號張松林12202羽毛球拍4D2010051716300022010-5-17903上海市虹梅路201號張松林11203羽毛球5D2010060609230032010-6-6905廣州市江南大道中82號賈立委11206籃球10D2010060609230032010-6-6905廣州市江南大道中82號賈立委11209足球10D2010061016280042010-6-10901北京市海淀區(qū)光華路55號里奇12202羽毛球拍10D2010061016280042010-6-10901北京市海淀區(qū)光華路55號里奇11205羽毛球20D2010061016280042010-6-10901北京市海淀區(qū)光華路55號里奇11208籃球10D2010061016280042010-6-10901北京市海淀區(qū)光華路55號里奇11210足球10D2010070109160052010-7-1902北京市北四環(huán)中路35號環(huán)宇11207籃球5D2010070109160052010-7-1902北京市北四環(huán)中路35號環(huán)宇11210足球5結(jié)論訂購關(guān)系模式R不是一個(gè)好的模式?！昂谩钡哪Ｊ剑翰粫l(fā)生插入異常、刪除異常、更新異常，數(shù)據(jù)冗余應(yīng)盡可能少。原因由存在于模式中的某些數(shù)據(jù)依賴引起的6.1.2解決的方法解決方法：通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴，減少數(shù)據(jù)冗余。將例6.1中訂購關(guān)系模式R分解為四個(gè)關(guān)系模式：商品信息Product(pdID,pdName)客戶信息Customer(custID,custName)訂單信息Order(orderID,orderDate,custID,orderAddress)訂單細(xì)節(jié)OrderDetail(orderID,pdID,quantity)6.2函數(shù)依賴數(shù)據(jù)依賴同一關(guān)系中屬性值之間存在相互依賴與相互制約的關(guān)系函數(shù)依賴數(shù)據(jù)依賴中最重要的一種它反映了同一關(guān)系中屬性間一一對應(yīng)的約束6.2.1函數(shù)依賴的基本概念1．函數(shù)依賴定義6.1設(shè)有關(guān)系模式R(U)，U是R的屬性集合，X和Y是U的子集。對于R(U)的任意一個(gè)可能的關(guān)系r，如果r中不存在兩個(gè)元組，它們在X上的屬性值相同，而在Y上的屬性值不同，則稱“X函數(shù)決定Y”或“Y函數(shù)依賴于X”，記做X→Y。函數(shù)依賴不是指關(guān)系模式R的某個(gè)或某些關(guān)系實(shí)例滿足的約束條件，而是指R的所有關(guān)系實(shí)例均要滿足的約束條件。函數(shù)依賴是語義范疇的概念。只能根據(jù)數(shù)據(jù)的語義來確定函數(shù)依賴。數(shù)據(jù)庫設(shè)計(jì)者可以對現(xiàn)實(shí)世界作強(qiáng)制的規(guī)定?！纠?.2】在訂購關(guān)系模式R中，如下函數(shù)依賴成立：orderID→(orderDate,orderAdress)custID→custName(orderID,pdID)→quantity但是pdID→quantity若規(guī)定custName不重，則custName→custID1．函數(shù)依賴(續(xù))當(dāng)X→Y成立時(shí)，則稱X為決定因素(Determinant)，稱Y為依賴因素(Dependent)。當(dāng)Y不函數(shù)依賴于X時(shí)，記為X→Y。如果X→Y，且Y→X，則記其為X←→Y。2．平凡函數(shù)依賴與非平凡函數(shù)依賴定義6.2在關(guān)系模式R(U)中，對于U的子集X和Y，如果X→Y，但Y

X，則稱X→Y是非平凡的函數(shù)依賴若X→Y，但Y

X,則稱X→Y是平凡的函數(shù)依賴【例6.3】在訂購關(guān)系模式R中：orderID→orderID(custID,custName)→custName對于任一關(guān)系模式，平凡函數(shù)依賴都是必然成立的，它不反映新的語義，因此若不特別聲明，我們總是討論非平凡函數(shù)依賴。3．完全函數(shù)依賴與部分函數(shù)依賴定義6.3在關(guān)系模式R(U)中，如果X→Y，并且對于X的任何一個(gè)真子集X’，都有X’Y,則稱Y完全函數(shù)依賴于X，記作XF

Y。

若X→Y，但Y不完全函數(shù)依賴于X，則稱Y部分函數(shù)依賴于X，記作XPY?！纠?.4】在訂購關(guān)系模式R中：(orderID,pdID)P(orderDate,orderAdress)(orderID,pdID)F

quantity

6.傳遞函數(shù)依賴定義6.4在關(guān)系模式R(U)中，如果X→Y，Y→Z，且Y

X，Y→X，則稱Z傳遞函數(shù)依賴于X，記作XT

Z。如果Y→X，即X←→Y，則Z直接依賴于X?！纠?.5】在訂購關(guān)系模式R中：orderID→custID，custID→orderID，custID→custName，orderID

T

custName弱數(shù)據(jù)依賴是產(chǎn)生數(shù)據(jù)冗余的原因之一6.2.2函數(shù)依賴的推理規(guī)則邏輯蘊(yùn)含定義6.5設(shè)有關(guān)系模式R(U,F)，X和Y是屬性集合U的兩個(gè)子集，如果對于R中每個(gè)滿足F的關(guān)系r也滿足X→Y，則稱F邏輯蘊(yùn)含X→Y?！纠?.6】在訂購關(guān)系模式R中：orderID→(orderDate,orderAdress)蘊(yùn)含下面兩個(gè)函數(shù)依賴：orderID→orderDate,orderID→orderAdress6.2.2函數(shù)依賴的推理規(guī)則(續(xù))

函數(shù)依賴集的閉包定義6.6設(shè)F是函數(shù)依賴集合，被F邏輯蘊(yùn)含的函數(shù)依賴的全體構(gòu)成的集合，稱為函數(shù)依賴集F的閉包，記為F＋。Armstrong公理系統(tǒng)1974年，W.W.Armstrong提出的一套推理規(guī)則用于推導(dǎo)函數(shù)依賴的邏輯蘊(yùn)涵關(guān)系已證明其有效性和完備性1．Armstrong公理系統(tǒng)3條基本公理自反律：如果Y

X

U，則X→Y在R上成立。增廣律：如果X→Y在R上成立，且ZU，則XZ→YZ。傳遞律：如果X→Y和Y→Z在R上成立，則X→Z在R上也成立。2．幾條有用的推理規(guī)則合并性規(guī)則：若X→Y，X→Z，則X→YZ。分解性規(guī)則：若X→Y，Z

Y，則X→Z。偽傳遞性規(guī)則：若X→Y，WY→Z，則WX→Z復(fù)合性規(guī)則：若X→Y，W→Z，則WX→YZ通用一致性規(guī)則：若X→Y，W→Z，則X(W-Y)→YZ

【例6.7】給定關(guān)系模式R(U,F)，X、Y為U的子集，F(xiàn)={X→Y}，則F+={X→

，X→X，X→Y，X→XY，Y→

，Y→Y，XY→

，XY→X，XY→Y，XY→XY}基數(shù)=10【例6.8】給定關(guān)系模式R(U,F)，X、Y、Z為U的子集，F(xiàn)={X→Y,Y→Z}，則依據(jù)上述關(guān)于函數(shù)依賴集閉包計(jì)算公式，可以得到F＋由43個(gè)函數(shù)依賴組成。屬性集的閉包定義6.7設(shè)F為屬性集U上的一組函數(shù)依賴，X

U，XF+={A|X→A能由F根據(jù)Armstrong公理導(dǎo)出}，XF+稱為屬性集X關(guān)于函數(shù)依賴集F的閉包，可簡記為X+。關(guān)于閉包的引理引理6.1設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y

U，X→Y能由F根據(jù)Armstrong公理推導(dǎo)出，即X→Y∈F+的充分必要條件是Y

X+。用途將判定X→Y是否能由F根據(jù)Armstrong公理導(dǎo)出的問題，轉(zhuǎn)化為求出X+

、判定Y是否為X+的子集的問題。算法6.1算法6.1求屬性集X關(guān)于函數(shù)依賴F的屬性閉包X+。輸入：關(guān)系模式R的全部屬性集U，U的子集X，U上的函數(shù)依賴集F。輸出：X關(guān)于F的屬性閉包X+。步驟：設(shè)i=0，1，2，…。(1)初始化：i=0，X(i)=X(0)=X。(2)求屬性集A。A是這樣的屬性：在F中尋找尚未用過的左邊是X(i)子集的函數(shù)依賴Y(i)

X(i)，并且在F中有Y(i)→Z(i)，則A=Z(1)∪Z(2)∪…∪Z(i)。(3)X(i+1)=X(i)∪A。(4)判斷以下條件之一是否成立，若有條件成立，則轉(zhuǎn)向(5)；否則，i=i+1，轉(zhuǎn)向(2)。①X(i+1)=X(i)；②X(i)中已包含了R的全部屬性；③在F中的每個(gè)函數(shù)依賴的右邊屬性中已沒有X(i)中未出現(xiàn)過的屬性；④在F中未用過的函數(shù)依賴的左邊屬性已沒有X(i)的子集。(5)輸出X(i+1)，即為X+?！纠?.9】設(shè)有關(guān)系模式R(U,F)，其中U=ABCDE，F(xiàn)={AB→C，B→D，C→E，E→C，A→C}，計(jì)算(BC)+。計(jì)算過程：(1)設(shè)X(0)=BC。(2)在F中找出尚未用過的左邊是BC子集的函數(shù)依賴：B→D，C→E。(3)X(1)=X(0)∪D∪E=BCDE。(4)很明顯，X(1)≠X(0)。(5)在F中找出尚未用過的左邊是BCDE子集的函數(shù)依賴E→C。(6)X(2)=X(1)∪C=BCDE。(7)X(2)=X(1)，算法結(jié)束。(8)(BC)+=BCDE?！纠?.10】設(shè)有關(guān)系模式R(U,F)，其中U=ABCDEI，F(xiàn)={A→D，AB→C，BI→C，DE→I，C→E}，求(AC)+。計(jì)算過程：(1)令X={AC}，則X(0)=AC。(2)在F中找出未用過的左邊是AC子集的函數(shù)依賴A→D，C→E。(3)X(1)=X(0)∪D∪E=ACDE。(4)很明顯，X(1)≠X(0)。(5)在F中找未用過的左邊是ACDE子集的函數(shù)依賴DE→I。(6)X(2)=X(1)∪I=ACDEI。(7)雖然X(2)≠X(1)，但是F中未用過的函數(shù)依賴的左邊屬性已沒有X(2)的子集，算法結(jié)束。(8)(AC)+=X(2)=ACDEI。6.2.3碼的函數(shù)依賴表示超碼定義6.8設(shè)K為關(guān)系模式R(U,F)中的屬性或?qū)傩约?。若K→U，則K稱為R的一個(gè)超碼。侯選碼定義6.9設(shè)K為關(guān)系模式R(U,F)中的屬性或?qū)傩约?。若KFU，則K稱為R的一個(gè)侯選碼。主碼若關(guān)系模式R有多個(gè)候選碼，則選定其中的一個(gè)做為主碼。碼的函數(shù)依賴表示（續(xù)）主屬性和非主屬性組成候選碼的屬性稱為主屬性，不參加任何候選碼的屬性稱為非主屬性。單碼和全碼單個(gè)屬性是碼，稱為單碼；整個(gè)屬性組都是碼，稱為全碼。外碼定義6.10關(guān)系模式R中屬性或?qū)傩越MX并非R的碼，但X是另一個(gè)關(guān)系模式的碼，則稱X是R的外碼，也稱外部碼。6.2.4最小函數(shù)依賴集1．函數(shù)依賴集的覆蓋與等價(jià)定義6.11設(shè)F和G是關(guān)系模式R上的兩個(gè)函數(shù)依賴集，如果所有為F所蘊(yùn)含的函數(shù)依賴都為G所蘊(yùn)含，即F

+是G

+的子集：F

+

G

+，則稱G是F的覆蓋。定義6.12如果G是F的函數(shù)覆蓋，同時(shí)F又是G的函數(shù)覆蓋，即F+=G+，則稱F和G是相互等價(jià)的函數(shù)依賴集。引理6.2F+=G+的充分必要條件是，F(xiàn)

G

+且G

F

+。2．最小函數(shù)依賴集定義6.13對于一個(gè)函數(shù)依賴集F，稱函數(shù)依賴集Fmin為F的最小函數(shù)依賴集，當(dāng)且僅當(dāng)Fmin滿足下述條件：Fmin與F等價(jià)，=F+。Fmin中每個(gè)函數(shù)依賴X→Y的依賴因素Y只含有一個(gè)屬性。Fmin中每個(gè)函數(shù)依賴X→Y的決定因素X沒有冗余，即只要?jiǎng)h除X中任何一個(gè)屬性就會改變Fmin的閉包。這樣的函數(shù)依賴稱為是左邊不可約的函數(shù)依賴。Fmin中每個(gè)函數(shù)依賴都不是冗余的，即刪除Fmin中任何一個(gè)函數(shù)依賴，F(xiàn)min就將變?yōu)榱硪粋€(gè)不等價(jià)于Fmin的集合。可以證明，對任何一個(gè)函數(shù)依賴集都存在一個(gè)與其等價(jià)的最小依賴集。3．求最小函數(shù)依賴集的算法算法6.2計(jì)算F的最小函數(shù)依賴集Fmin。輸入：一個(gè)函數(shù)依賴集F。輸出：F的一個(gè)等價(jià)的最小函數(shù)依賴集Fmin。步驟：(1)函數(shù)依賴的右部單屬性化。利用分解性規(guī)則，使F中的任何一個(gè)函數(shù)依賴的右部僅含有一個(gè)屬性。(2)去掉多余的函數(shù)依賴。逐一地檢查F中的每一個(gè)函數(shù)依賴X→A，令G=F-{X→A}，求X關(guān)于函數(shù)依賴集G的閉包X

+，若A

X

+，則從F中去掉X→A，即F=F-{X→A}。(3)去掉各函數(shù)依賴左部多余的屬性。逐一地檢查左部非單個(gè)屬性的函數(shù)依賴XY→A，求X關(guān)于函數(shù)依賴集F的閉包X

+，若A

X

+，則以X→A代替F中的XY→A，即F=F-{XY→A}∪{X→A}。(4)最終得到的函數(shù)依賴集F即為最小函數(shù)依賴集Fmin?！纠?.11】設(shè)有關(guān)系模式R(U,F)，其中U=ABC，F(xiàn)={A→BC,B→C,AB→C}，求F的最小函數(shù)依賴集Fmin。求解過程：(1)函數(shù)依賴的右部單屬性化。F={A→B,A→C,B→C,AB→C}【例6.11】(續(xù))求解過程：(2)去掉多余的函數(shù)依賴。檢查A→B：令G={A→C,B→C,AB→C}，A關(guān)于函數(shù)依賴集G的閉包A+=AC，B

A+，A→B不是冗余的。檢查A→C：令G={A→B,B→C,AB→C}，A關(guān)于函數(shù)依賴集G的閉包A+=ABC，C

A+，A→C是冗余的，從F中去掉，則F={A→B,B→C,AB→C}。檢查B→C：令G={A→B,AB→C}，B關(guān)于函數(shù)依賴集G的閉包B+=B，C

B+，B→C不是冗余的。檢查AB→C：令G={A→B,B→C}，AB關(guān)于函數(shù)依賴集G的閉包(AB)+=ABC，C

(AB)+，AB→C是冗余的，從F中去掉，則F={A→B,B→C}?！纠?.11】(續(xù))求解過程：(3)去掉各函數(shù)依賴左部多余的屬性。F中的函數(shù)依賴左部均為單屬性，不存在冗余的屬性。

因此F的最小函數(shù)依賴集Fmin={A→B,B→C}?！纠?.12】設(shè)有關(guān)系模式R(U,F)，其中U=ABC，F(xiàn)={AB→C,A→B,B→A}，求F的最小函數(shù)依賴集Fmin。求解過程：(1)F中所有函數(shù)依賴右部已經(jīng)是單屬性。(2)F中沒有冗余的函數(shù)依賴，判斷過程略。(3)去掉各函數(shù)依賴左部多余的屬性。考察AB→C，對于AB的真子集A：A→C成立嗎？A關(guān)于F的閉包A+=ABC，C

A+，則說明A→C成立，B是多余的，F(xiàn)={A→C,A→B,B→A}即為Fmin={A→C,A→B,B→A}?！纠?.12】（續(xù)）如果改變考察順序，先來判定B→C?。B關(guān)于F的閉包B+=ABC，C

B+，則說明B→C成立，A是多余的，F(xiàn)={B→C,A→B,B→A}，由此得到另一個(gè)最小函數(shù)依賴集Fmin={B→C,A→B,B→A}。最小函數(shù)依賴集不是唯一的。不同的處理順序，可能會得到不同的最小函數(shù)依賴集。練習(xí)已知關(guān)系模式R(U,F),U={A,B,C,D,E,G}F={A→BE，CB→D，E→CG}

求關(guān)系R的候選碼？請驗(yàn)證，關(guān)系R是否滿足函數(shù)依賴C→DH？為什么？

CDHSC1D1H1S1C1D1H2S1C1D1H1S2C2D2H2S3關(guān)系模式R(A,B,C,D,E),F={A→BC,CD→E,B→D,E→A},確定侯選碼求Fmin6.3規(guī)范化規(guī)范化的關(guān)系其分量都是不可分的數(shù)據(jù)項(xiàng)最基本的條件規(guī)范化程度可以有6個(gè)不同的級別6種范式：第一范式、第二范式、第三范式、BC范式、第四范式和第五范式。各種范式之間存在聯(lián)系：1NF

2NF

3NF

BCNF

4NF

5NF通常把某一關(guān)系模式R為第n范式簡記為R

nNF。規(guī)范化的概念一個(gè)低一級范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個(gè)高一級范式的關(guān)系模式集合，這種過程就叫關(guān)系模式的規(guī)范化6.3.1范式1．第一范式(1NF)定義6.14如果關(guān)系模式R中每個(gè)屬性值都是一個(gè)不可分解的數(shù)據(jù)項(xiàng)，則稱該關(guān)系模式滿足第一范式，簡稱1NF，記為R

1NF。第一范式是對關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫模式不能稱為關(guān)系數(shù)據(jù)庫。例：非規(guī)范化關(guān)系職工編號職工姓名家庭電話電話1電話220100101張三8723123513967889013……………………部門編號部門名稱職工姓名01辦公室張三……02財(cái)務(wù)處李四……0NF->1NF的方法:

縱橫延伸職工編號職工姓名電話1電話220100101張三8723123513967889013……………………部門編號部門名稱職工姓名01辦公室張三………02財(cái)務(wù)處李四………【例6.1】訂購關(guān)系模式RR的碼（orderID,pdID），R

1NFR存在數(shù)據(jù)冗余、更新異常（插入異常、刪除異常、修改異常）的問題R不是一個(gè)好的關(guān)系模式。orderIDorderDatecustIDorderAddresscustNamepdIDpdNamequantityD2010051616280012010-5-16901北京市朝陽區(qū)聯(lián)盟小區(qū)9號樓里奇11201羽毛球拍10D2010051616280012010-5-16901北京市朝陽區(qū)聯(lián)盟小區(qū)9號樓里奇11203羽毛球40D2010051616280012010-5-16901北京市朝陽區(qū)聯(lián)盟小區(qū)9號樓里奇11206籃球15D2010051716300022010-5-17903上海市虹梅路201號張松林12202羽毛球拍4D2010051716300022010-5-17903上海市虹梅路201號張松林11203羽毛球5D2010060609230032010-6-6905廣州市江南大道中82號賈立委11206籃球10D2010060609230032010-6-6905廣州市江南大道中82號賈立委11209足球10D2010061016280042010-6-10901北京市海淀區(qū)光華路55號里奇12202羽毛球拍10D2010061016280042010-6-10901北京市海淀區(qū)光華路55號里奇11205羽毛球20D2010061016280042010-6-10901北京市海淀區(qū)光華路55號里奇11208籃球10D2010061016280042010-6-10901北京市海淀區(qū)光華路55號里奇11210足球10D2010070109160052010-7-1902北京市北四環(huán)中路35號環(huán)宇11207籃球5D2010070109160052010-7-1902北京市北四環(huán)中路35號環(huán)宇11210足球52．第二范式(2NF)定義6.15如果一個(gè)關(guān)系模式R

1NF，且它的所有非主屬性都完全函數(shù)依賴于R的碼，則R

2NF。分析:訂購關(guān)系模式RR的函數(shù)依賴圖R2NF

R存在問題的原因：存在orderDate、orderAddress、pdName等屬性對碼的部分函數(shù)依賴分析（續(xù)）解決方法：投影分解product(pdID,pdName)order_cust(orderID,orderDate,custID,custName,orderAddress)orderDetail(orderID,pdID,quantity)分析（續(xù)）Product的函數(shù)依賴圖

2NForder_cust的函數(shù)依賴圖

2NForderDetail的函數(shù)依賴圖

2NForderIDpdIDquantitypdIDpdNameorderIDorderDatecustIDorderAddresscustName分析（續(xù)）order_cust存在的問題：數(shù)據(jù)冗余更新異常（插入異常、刪除異常、修改異常）屬于2NF的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式。orderIDorderDatecustIDorderAddresscustName3．第三范式(3NF)定義6.16如果一個(gè)關(guān)系模式R∈2NF，且所有非主屬性都不傳遞函數(shù)依賴于碼，則R∈3NF。分析:order_custorder_cust2NF3NForder_cust存在問題的原因custName傳遞函數(shù)依賴于orderID。orderIDorderDatecustIDorderAddresscustName分析:order_cust（續(xù)）解決方法：投影分解Customer(custID,custName)Orders(orderID,orderDate,custID,orderAddress)orderIDorderDatecustIDorderAddresscustName分析:order_cust（續(xù)）Customer的函數(shù)依賴圖

3NF

Orders的函數(shù)依賴圖

3NF

orderIDorderDatecustIDorderAddresscustIDcustName分析關(guān)系模式STC

3NF的關(guān)系模式就一定是好的關(guān)系模式？關(guān)系模式STC(學(xué)生學(xué)號Sno,教師編號Tno,課程課號Cno,成績Grade)每個(gè)教師只教一門課，但一門課可由幾個(gè)教師講授。存在如下函數(shù)依賴：(Sno,Cno)→Tno(Sno,Cno)→Grade(Sno,Tno)→Cno(Sno,Tno)→GradeTno→CnoSTC的候選碼：（SNO，CNO）和（SNO，TNO）分析關(guān)系模式STC(續(xù))關(guān)系模式STC(學(xué)生學(xué)號Sno,教師編號Tno,課程課號Cno,成績Grade)STC3NFSTC存在的問題：數(shù)據(jù)冗余更新異常（插入異常、刪除異常、修改異常）屬于3NF的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式。SnoCnoTnoSTC的函數(shù)依賴圖GradeSnoTnoCnoGrade6.BCNF范式(BCNF)定義6.17關(guān)系模式R

1NF，對任何非平凡的函數(shù)依賴X→Y，X均包含碼，則R

BCNF。若R∈BCNF所有非主屬性都完全函數(shù)依賴于每個(gè)候選碼。所有主屬性都完全函數(shù)依賴于每個(gè)不包含它的候選碼。沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。若R∈BCNF，則R∈3NF；反之不成立。分析關(guān)系模式STCSTC3NFSTCBCNFF={(Sno,Cno)→Tno，(Sno,Cno)→Grade，(Sno,Tno)→Cno，(Sno,Tno)→Grade，Tno→Cno}STC存在問題的原因：主屬性CNO對不包含它的碼（Sno,Tno）間存在不良函數(shù)依賴SnoCnoTnoSTC的函數(shù)依賴圖GradeSnoTnoCnoGrade分析關(guān)系模式STC（續(xù)）解決方法：投影分解方法1：SC(Sno,Cno,Grade)TC(Tno,Cno)方法2：ST(Sno,Tno,Grade)TC(Tno,Cno)SnoCnoTnoSTC的函數(shù)依賴圖GradeSnoTnoCnoGrade3NF與BCNF的關(guān)系與區(qū)別如果關(guān)系模式R∈BCNF，必定有R∈3NF如果R∈3NF，且R只有一個(gè)候選碼，則R必屬于BCNF。3NF和BCNF是在函數(shù)依賴的條件下對模式分解所能達(dá)到的分離程度的測度。一個(gè)模式中的關(guān)系模式如果都屬于BCNF，那么在函數(shù)依賴范疇內(nèi)，它已實(shí)現(xiàn)了徹底的分離，已消除了插入和刪除的異常。3NF的“不徹底”性表現(xiàn)在可能存在主屬性對碼的部分依賴和傳遞依賴。練習(xí)題指明下列關(guān)系模式最高屬于第幾范式.R(X,Y,Z)F={XY→Z}R(X,Y,Z)F={Y→Z,XZ→Y}R(X,Y,Z)F={Y→Z,Y→X,X→YZ}R(X,Y,Z)F={X→Y,X→Z}R(W,X,Y,Z)F={X→Z,WX→Y}6.3.2模式分解把低一級的關(guān)系模式分解為若干個(gè)高一級的關(guān)系模式的方法不是唯一的只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)，分解方法才有意義模式分解的定義定義6.18設(shè)有關(guān)系模式R(U)，取定U的一個(gè)子集的集合{U1,U2,

…,Uk}，使得U=U1∪U2

∪…∪Uk，如果用一個(gè)關(guān)系模式的集合ρ={R1(U1)，R2(U2)，…，Rn(Uk)}代替R(U)，就稱ρ是關(guān)系模式R(U)的一個(gè)分解。

關(guān)系模式分解時(shí)一般應(yīng)遵循的原則

關(guān)系模式進(jìn)行無損連接分解。

保持原來模型的函數(shù)依賴關(guān)系?！纠?.13】給定關(guān)系R(部門名稱，主任姓名，主任電話)，R上成立的函數(shù)依賴集F={部門名稱→主任姓名，主任姓名→主任電話}。部門名稱主任姓名主任電話人事處張?zhí)靹?wù)處李樹衛(wèi)處袁曉勤集團(tuán)劉例6.13】分解方法一R1(部門名稱)R2(主任姓名)R3(主任電話)這種方法既不符合無損連接，也沒有保持函數(shù)依賴。R1R2R3部門名稱主任姓名主任電話人事處張?zhí)靹?wù)處李樹衛(wèi)處袁曉勤集團(tuán)劉例6.13】分解方法二R1(部門名稱，主任姓名)R2(主任姓名，主任電話)這種方法既既符合無損連接，也保持了函數(shù)依賴。

R1R2部門名稱主任姓名主任姓名主任電話人事處張?zhí)旆綇執(zhí)靹?wù)處李樹軍李樹衛(wèi)處袁曉寧袁曉勤集團(tuán)劉朋劉例6.13】分解方法三R1(部門名稱，主任姓名)R2(部門名稱，主任電話)這種方法雖然符合無損連接，但沒有保持函數(shù)依賴

R1R2部門名稱主任姓名部門名稱主任電話人事處張?zhí)旆饺耸聞?wù)處李樹軍財(cái)務(wù)衛(wèi)處袁曉寧保衛(wèi)勤集團(tuán)劉朋后勤集例6.13】分解方法四R1(部門名稱，主任電話)R2(主任姓名，主任電話)這種方法雖然符合無損連接，但沒有保持函數(shù)依賴

R1R2部門名稱主任電話主任姓名主任電話人事天務(wù)樹衛(wèi)曉勤集例6.13】

綜上所述第一種分解方法是錯(cuò)誤的分解方法第二種分解方法是最好的分解方法第三種和第四種分解方法都不是好的分解方法。1．無損分解定義6.19設(shè)R是一個(gè)關(guān)系模式，F(xiàn)是R上的一個(gè)依賴集，R分解為關(guān)系模式的集合

={R1(U1),R2(U2),…,Rk(Uk)}。如果對于R中滿足F的每一個(gè)關(guān)系r，都有則稱分解

是滿足函數(shù)依賴集F的無損連接分解或無損分解。算法6.3

算法6.3判別一個(gè)分解的無損連接性輸入：(1)關(guān)系模式R(U)，其中U={A1,A2,…,An}。(2)R(U)上成立的函數(shù)依賴集F。(3)R(U)的一個(gè)分解

={R1(U1),R2(U2),…,Rk(Uk)}，而U=U1∪U2∪…∪Uk。輸出：

相對于F是否無損分解。算法6.3（續(xù)）計(jì)算步驟：(1)構(gòu)造一個(gè)k行n列的表格，每列對應(yīng)一個(gè)屬性Aj(j=1,2,…,n)，每行對應(yīng)一個(gè)模式Ri(Ui)(i=1,2,…,k)的屬性集合。如果Aj在Ui中，那么在表格的第i行第j列處添上記號aj，否則添上記號bij。(2)重復(fù)檢查F的每一個(gè)函數(shù)依賴，并且修改表格中的元素，直到表格出現(xiàn)全a行或者表格不再發(fā)生變化為止。取F中函數(shù)依賴X→Y，如果表格總有兩行在X上分量相等，在Y分量上不相等，則修改Y分量的值，使這兩行在Y分量上相等，實(shí)際修改分為兩種情況：①如果Y分量中有一個(gè)是aj，另一個(gè)也修改成aj。②如果Y分量中沒有aj，就用標(biāo)號較小的那個(gè)bij替換另一個(gè)符號。(3)修改結(jié)束后的表格中有一行全是a，即a1,a2,…,an，則相對于F是無損分解，否則不是無損分解?！纠?.14】設(shè)有關(guān)系模式R(U,F)，其中U={A,B,C,D,E}，F(xiàn)={A→C,B→C,C→D,DE→C,

CE→A}。R(U,F)的一個(gè)模式分解={R1(A,D),R2(A,B),R3(B,E),R4(C,D,E),R5(A,E)}。試判斷是否為無損分解。求解過程：F={A→C,B→C,C→D,DE→C,

CE→A}由于表格中出現(xiàn)了全a行，因此關(guān)系模式R(U)的分解

是無損分解。ABCDE{A,D}a1b12b13a4b15{A,B}a1a2b23b24b25{B,E}b31a2b33b34a5{C,D,E}b41b42a3a4a5{A,E}a1b52b53b54a5b13b13b13a4a4a4a3a3a1a1定理6.1定理6.1關(guān)系模式R(U,F)分解為關(guān)系模式R1(U1,F1),R2(U2,F2)是具有無損連接性的分解的充分必要條件是(U1∩U2→U1-U2)F+，或者(U2∩U1→U2-U1)

F+。【例6.15】設(shè)有關(guān)系模式R(U,F)，U=ABCD，F(xiàn)={A→B，B→C，D→B}，若將R分解成{ACD，BD}，試判斷該分解是否是無損分解。求解過程：U1=ACD，U2=BD，U2∩U1=D，U2-U1=B，顯然D→B成立，因此該分解是無損分解。2．保持函數(shù)依賴設(shè)有關(guān)系模式R(U,F)，F(xiàn)是屬性集U上的函數(shù)依賴集，Z是U的一個(gè)子集，F(xiàn)在Z上的一個(gè)投影用

Z(F)表示，定義為

Z(F)={X→Y|(X→Y)

F+，XY

Z，且Y?X}。定義6.20設(shè)有關(guān)系模式R(U)的一個(gè)分解

={R1(U1),R2(U2),…,Rn(Uk)}，F(xiàn)是R(U)上的函數(shù)依賴集，如果F

+=，則稱分解

保持函數(shù)依賴集F，簡稱保持函數(shù)依賴。【例6.16】設(shè)有關(guān)系模式R(U,F)，其中U=ABCD，F(xiàn)={A→B，B→C，C→D，D→A}。R(U)的一個(gè)模式分解

={R1(U1),R2(U2),R3(U3)}，其中U1=AB，U2=BC，U3=CD。試判定

是否具有保持函數(shù)依賴性。求解過程如下。(1)由題意可知：={A→B,B→A}，={B→C,C→B}，

={C→D,D→C}令G=={A→B,B→A,B→C,C→B,C→D,D→C}求解過程(續(xù))(2)逐一檢查F中的每個(gè)函數(shù)依賴X→Y，X→Y

G+是否成立：A→B

G，B→C

G，C→D

G因此 A→B

G+，B→C

G+，C→D

G+D關(guān)于函數(shù)依賴集G的閉包D+=ABCD，A

D+，因此D→A

G+，因此，成立。求解過程(續(xù))(3)逐一檢查G中的每個(gè)函數(shù)依賴X→Y，X→是否成立：A→B

F，B→C

F，C→D

F，因此

A→B

F+，B→C

F+，C→D

F+。B、C、D關(guān)于函數(shù)依賴集G的閉包

B+=C+=D+=ABCD，A

B+，B

C+，C

D+，因此B→A

G+，C→B

G+，D→C

G+，因此，G

F