數(shù)據(jù)庫系統(tǒng)原理 課件 第6章 關系規(guī)范化

第6章關系規(guī)范化函數(shù)依賴

函數(shù)依賴/完全依賴/部分依賴/傳遞依賴范式范式第一/第二/第三/BC/第四范式

關系模式規(guī)范化Armstrong公理函數(shù)依賴集閉包屬性集閉包最小函數(shù)依賴集關系模式分解關系模式的分解算法1第6章關系規(guī)范化2問題1：邏輯模型中的關系模式，是否可以使用？

問題2：EBook中的Book、Cust、Press、Buy是否可用如下BInfo替代？BInfo（BNo，BName，Author，EditNo，Price，PPrice，SPrice，CNo，CName，CSex，Birth，Phone，Marry，Photo，Email，PNo，PName，PCode，PAddr，Email，HPage，PDate）分析1：購買圖書的每個客戶，不但需要添加客戶信息、書號和購買日期等必要信息，而且還要重復添加圖書和出版社的全部信息（數(shù)據(jù)冗余）。分析2：如果刪除部分下架的圖書信息，則會把購買這些書的的客戶信息和出版社信息一起刪除，這是絕對不合理的（刪除異常）。顯然：使用Book、Cust、Press和Buy，明顯優(yōu)于使用BInfo！結論：邏輯模型中的關系模式，不能直接使用，需要進行規(guī)范化（本章內容），從而在一定程度上解決數(shù)據(jù)冗余、插入異常、修改異常和刪除異常等方面的問題。思考：從數(shù)據(jù)冗余、插入異常、修改異常和刪除異常等方面，進一步分析單表BInfo的不合理性。6.1函數(shù)依賴函數(shù)依賴完全依賴部分依賴傳遞依賴多值依賴36.1.1函數(shù)依賴4定義6.1設R(U)是屬性集U上的關系模式，X和Y是U的子集。對于R(U)的任意關系的任意元組t1,t2，如果t1[Y]≠t2[Y]，成立t1[X]≠t2[X]（即：不存在t1,t2，使得t1[X]=t2[X]，而t1[Y]≠t2[Y]）。則稱X函數(shù)確定Y（即：X→Y）或Y函數(shù)依賴于X。如果X→Y，并且Y→X，則稱X與Y互相函數(shù)依賴。記為：X←→Y。如果X不函數(shù)確定Y，則記為：XY。提示：對于關系模式R(U)，如果成立X→Y，則對R(U)的任意關系均成立X→Y。例如：在BInfo中，則存在函數(shù)依賴：BNo→BName；BNo→Author；BNo→PNo；BNo→EditNo；BNo→Price但是：BnameAuthor；BNamePNo。6.1.1函數(shù)依賴5如果X→Y，且Y

X，則稱X→Y是平凡函數(shù)依賴。即：集合的任意子集均平凡函數(shù)依賴于自身。亦即：平凡函數(shù)依賴總是成立的。如果X→Y，但Y

X，則稱X→Y是非平凡函數(shù)依賴。說明：若無特殊聲明，則函數(shù)依賴均指非平凡函數(shù)依賴。例如：在BInfo中，存在函數(shù)依賴：

非平凡函數(shù)依賴：(BNo,CNo)→PDate

平凡函數(shù)依賴：(BNo，CNo)→(BNo，CNo)；(BNo，CNo)→BNo；(BNo，CNo)→CNo。說明：(X，Y)→Y簡記為XY→Y；(X，Y)→(X，Y)簡記為XY→XY。函數(shù)依賴集：R(U)的所有函數(shù)依賴的集合。記為：F={函數(shù)依賴}。所以：R(U)可以進一步表示為R(U，F(xiàn))。6.1.1函數(shù)依賴6例6.1BInfo可以表示為：BInfo(U，F(xiàn))U={BNo，CNo，BName，Author，EditNo，Price，PPrice，SPrice，CName，CSex，Birth，Phone，Marry，Photo，Email，PNo，PName，PCode，PAddr，Email，HPage，PDate}F={BNo→（BName，Author，PNo，EditNo，Price，PPrice，SPrice），CNo→（CName，CSex，Birth，Marry，Photo，Email），PNo→（PName，PCode，PAddr，Phone，Email，HPage，

（CNo，BNo）→PDate}6.1.1函數(shù)依賴7例6.2如果R(A，B，C，D，E)存在函數(shù)依賴A→B；A→C；A→D；C→D；BC→E。則R(A，B，C，D，E)可以表示如下：R(U，F(xiàn))U={A,B,C,D,E}F={A→B，A→C，A→D，C→D，BC→E}6.1.2完全依賴和部分依賴8定義6.2在R(U，F(xiàn))中，如果X→Y，且對于X的任何一個真子集X’，都滿足X’Y（即：Y不函數(shù)依賴于X的任意真子集，只依賴于X本身）。則稱Y完全函數(shù)依賴于X，記作XY。定義6.3在R(U，F(xiàn))中，如果X→Y，且Y不完全函數(shù)依賴于X。則稱Y部分函數(shù)依賴于X，記作XY。例如：在BInfo中，由于：BNoPDate，而且CNoPDate。因此：(BNo,CNo)PDate例如：在R(A，B，C，D，E)中，如果F={A→C，AB→D，AB→E，C→E}。則ABC；ABD；ABE。根據(jù)定義6.1和定義6.2，則候選鍵可以進一步描述：在R(U，F(xiàn))中X

U，如果XU，則X是候選鍵。例如：在例6.1中，(BNo,CNo)是BInfo的候選鍵。在例6.2中，AB是R的候選鍵。提示：利用“屬性集的閉包”可以給出“候選鍵”更直觀的解釋。6.1.3傳遞依賴9定義6.4在R(U，F(xiàn))中，如果X→Y，Y→Z，并且YX。則稱Z傳遞函數(shù)依賴于X。記為：XZ。說明：在定義6.4中，X→Y和Y→Z均為非平凡依賴。如果Y→X，則X←→Y，會導致Z直接依賴于X。所以X→Y、Y→Z和Y→X會導致非本質上的傳遞依賴。例如：在BInfo中，成立BnoPName；BnoPCode。6.2范式范式第一范式第二范式第三范式BC范式第四范式106.2.1范式11范式：是滿足系統(tǒng)規(guī)范要求的關系模式的集合。規(guī)范化的關系模式的集合。在實際應用中，邏輯模型中的關系模式一般必須達到系統(tǒng)的規(guī)范要求。根據(jù)不同應用需求，可以把滿足不同規(guī)范要求的關系模式分為：第一范式(FirstNormalForm，1NF)第二范式(2NF)第三范式(3NF)BC范式(BoyceCoddNormalForm，BCNF)第四范式(4NF)第五范式(5NF)。1NF、2NF和3NF是關系規(guī)范化的基本要求。如果關系模式R滿足第n范式，則記為R∈nNF。6.2.1范式12范式之間的關系如下（如圖6.1所示）：1NF2NF3NFBCNF4NF5NF6.2.2第一范式13定義6.5如果R（U，F(xiàn)）的所有屬性都是不可再分的最小數(shù)據(jù)項，則稱R滿足1NF。即：R∈1NF。1NF是關系模式必須滿足的最低要求。即關系數(shù)據(jù)庫系統(tǒng)必須滿足1NF。通常滿足1NF的關系模式，存在較多的冗余數(shù)據(jù)，而且存在插入異常、修改異常和刪除異常等問題，從而會破壞數(shù)據(jù)完整性6.2.3第二范式14定義6.6如果R（U，F(xiàn)）∈1NF，并且R的每一個非主屬性都完全函數(shù)依賴于R的候選鍵，則R∈2NF。2NF的等價描述：對于R（U，F(xiàn)）∈1NF，如果存在非主屬性部分函數(shù)依賴于R的候選鍵，則R∈2NF。例6.3在例1.1的BInfo中，則：判斷BInfo∈2NF？，如果不是，則分解相應的關系模式，使之滿足2NF。（1）預處理：判斷BInfo是否存在計算型屬性。如果存在，則從BInfo中去掉該冗余屬性。例如：如果在BInfo中，存在利潤BProfit屬性，則利潤可以由進價和售價導出。即：BProfit=SPrice-PPrice（2）1NF判斷：分析BInfo的屬性可知，每個屬性均為不可再分的屬性，因此BInfo∈1NF。不難看出，在BInfo的關系中，存在大量的冗余數(shù)據(jù)。6.2.3第二范式15（3）確定候選建在BInfo中，戶號確定客戶的其它屬性；書號確定圖書的其它屬性；社號確定出版社的其它屬性；戶號和書號確定購買日期。BInfo的函數(shù)依賴關系如圖6.2所示。BInfo的候選鍵為(BNo,CNo)；BNo和CNo為主屬性；其它為非主屬性。CNoCNameCSexBirthMarryPhotoEmail

CNoBNoPNamePCodePAddrPhoneEmailHPageBNoBNameAuthorEditNoPNoPricePPriceSPricePDate6.2.3第二范式16（4）2NF分解在BInfo中，由于存在函數(shù)依賴：BNo→(BName，Author，PNo，EditNo，Price，PPrice，SPrice)CNo→（CName，CSex，Birth，Marry，Photo，Email）PNo→（PName，PCode，PAddr，Phone，Email，HPage）則存在非主屬性對候選建的部分函數(shù)依賴：

(BNo,CNo)(BName，Author，PNo，EditNo，Price，PPrice，SPrice)(BNo,CNo)(CName，CSex，Birth，Marry，Photo，Email)(BNo,CNo)(PName，PCode，PAddr，Phone，Email，HPage)不難看出，BInfo中存在三組非主屬性對候選鍵的部分依賴，因此R2NF。因此采用投影分解法，把導致R2NF的部分函數(shù)依賴進行如下分解：6.2.3第二范式17BInfo=Cust∪PressBook∪Buy1）Cust(U1,F1)：U1={CNo，CName，CSex，Birth，Marry，Photo，Email}F1={CNo→（CName，CSex，Birth，Marry，Photo，Email）}2）Buy(U2,F2)：U2={BNo,CNo,PDate}F2={(BNo,CNo)→PDate}3）PressBook(U3,F3)：U3={BNo，BName，Author，EditNo，Price，PPrice，SPrice，PNo，PName，PCode，PAddr，Phone，Email，HPage}F3={BNo→(BName，Author，PNo，EditNo，Price，PPrice，SPrice)，PNo→（PName，PCode，PAddr，Phone，Email，HPage）}不難證明，Cust∈2NF，PressBook∈2NF，Buy∈2NF。6.2.3第二范式BInfo的2NF分解結果18

CNoCNameCSexBirthMarryPhotoEmail

CNoBNoPNamePCodePAddrPhoneEmailHPageBNoBNameAuthorEditNoPNoPricePPriceSPricePDate提示：在進行2NF分解時，一般需要把包含候選鍵的屬性集合及其相應的函數(shù)依賴單獨分解出來，因為它是連接的基本條件例如：(BNo,CNo)PDate，盡管它存在一定的數(shù)據(jù)冗余

6.2.3第二范式19例6.4R(U,F)：U={A,B,C,D,E}；F={AD→E,A→B,B→C}。判斷R(U,F)∈2NF？，如果不是，則分解R(U,F)，使之滿足2NF。（1）確定候選建根據(jù)F不難看出，R(U,F)的候選建為AD。A和D為主屬性；B，C和E為非主屬性。（2）判斷是否存在部分函數(shù)依賴因為：A→B,B→C，所以：ADB和ADC。即：B和C均部分函數(shù)依賴于AD。因此：R(U,F)2NF。R(U,F)的2NF分解結果如下：R1(U1,F1)=({A,D,E},{AD→E})R2(U2,F2)=({A,B,C},{A→B,B→C})不難證明，R1(U1,F1)∈2NF，R2(U2,F2)∈2NF。6.2.3第二范式20提示：2NF雖然在一定程度上解決了插入異常、修改異常、刪除異常和冗余數(shù)據(jù)等問題，但2NF一般也不是最理想的關系模式，仍然會破壞數(shù)據(jù)完整性。結論：解決不滿足2NF的方法是分解關系模式，消除所有非主屬性對候選鍵的部分函數(shù)依賴關系。即：對于R∈1NF，只要存在一個非主屬性部分函數(shù)依賴于R的候選鍵，則R2NF。6.2.4第三范式定義6.7如果R（U，F(xiàn)）∈2NF，且R的每個非主屬性都不傳遞函數(shù)依賴于R的候選鍵，則R∈3NF。顯然，如果R∈3NF，則R的每個非主屬性，既不部分函數(shù)依賴于候選鍵，也不傳遞函數(shù)依賴于候選鍵。即：如果R∈3NF，則R∈2NF。例6.5在例6.3中，則：判斷BInfo∈3NF？，如果不是，則分解相應的關系模式，使之滿足3NF。分析：在例6.3中，顯然成立：Cust(U1,F1)∈3NF，Buy(U2,F2)∈3NF。那么：PressBook(U3,F3)∈3NF？（1）確定候選建根據(jù)F3不難看出，PressBook的候選建為BNo。BNo為主屬性；其他屬性為非主屬性。216.2.4第三范式（2）3NF分解在F3中，因為存在如下函數(shù)依賴：BNo→(BName，Author，PNo，EditNo，Price，PPrice，SPrice)PNo→（PName，PCode，PAddr，Phone，Email，HPage）所以：非主屬性PName，PCode，PAddr，Phone，Email和HPage均傳遞依賴于候選鍵BNo，即：BNo（PName，PCode，PAddr，Phone，Email，HPage）所以：PressBook(U3,F3)3NF。因此：采用投影分解法，把導致PressBook3NF的傳遞函數(shù)依賴進行分解。226.2.4第三范式PressBook的3NF分解結果如下：PressBook=Press∪Book1）Book(U4,F4)：U4={BNo，BName，Author，PNo，EditNo，Price，PPrice，SPrice}F4={BNo→(BName，Author，PNo，EditNo，Price，PPrice，SPrice)}2）Press(U5,F5)：U5={PNo，PName，PCode，PAddr，Phone，Email，HPage}F5={PNo→（PName，PCode，PAddr，Phone，Email，HPage）}不難證明，Book(U4,F4)∈3NF，Press(U5,F5)∈3NF。236.2.4第三范式PressBook的3NF分解如圖6.4所示。24

CNoCNameCSexBirthMarryPhotoEmail

CNoBNoPNamePCodePAddrPhoneEmailHPageBNoBNameAuthorEditNoPNoPricePPriceSPricePDate

提示：在進行3NF分解時，一般需要把中間起傳遞作用的屬性集合同時分配到分解前后的關系模式中。因為它是連接的基本條件，盡管它存在一定的數(shù)據(jù)冗余。例如：BNo→PNo，PNo→（PName，PCode，PAddr，Phone，Email，HPage），所以把PNo同時分配到Book和Press中。BInfo的最終3NF分解結果Cust(U1,F1)：U1={CNo，CName，CSex，Birth，Marry，Photo，Email}F1={CNo→（CName，CSex，Birth，Marry，Photo，Email）}Buy(U2,F2)：U2={BNo,CNo,PDate}F2={(BNo,CNo)→PDate}Book(U4,F4)：U4={BNo，BName，Author，PNo，EditNo，Price，PPrice，SPrice}F4={BNo→(BName，Author，PNo，EditNo，Price，PPrice，SPrice)}Press(U5,F5)：U5={PNo，PName，PCode，PAddr，Phone，Email，HPage}F5={PNo→（PName，PCode，PAddr，Phone，Email，HPage）}

思考：分析BInfo的分解過程與EBook的“E-R圖向關系模式轉換過程”的區(qū)別。256.2.4第三范式例6.6在例6.4的R(U,F)中，請判斷R(U,F)∈3NF？如果不是，則分解相應的關系模式，使之滿足3NF。對于R(U,F)的2NF分解結果，則顯然成立R1(U1,F1)∈3NF。那么：R2(U2,F2)∈3NF？由于在F2中存在：A→B,B→C，所以非主屬性C傳遞依賴于候選鍵A，即：AC。所以：R2(U2,F2)3NF。因此采用投影分解法，把導致3NF的傳遞函數(shù)依賴進行分解如下：R2=R21∪R221）R21(U21,F21)：U21={A,B}；F21={A→B}2）R22(U22,F22)：U22={B,C}；F22={B→C}不難證明：R21(U21,F21)∈3NF，R22(U22,F22)∈3NF。266.2.4第三范式如果R（U，F(xiàn)）∈1NF，并且R的每個非主屬性都不傳遞函數(shù)依賴于R的候選鍵，則R不一定滿足3NF。反例如下：例6.7關系模式BuyTest(U,F)如下（如圖6.5所示）：U={BNo,BName,CNo,CName,PDate}F={BNo→BName,CNo→CName,(BNo,CNo)→PDate}則：BuyTest(U,F)3NF。276.2.4第三范式根據(jù)BuyTest(U,F)的F不難看出，(BNo,CNo)是BuyTest(U,F)的唯一候選鍵，而且非主屬性BName和CName均部分函數(shù)依賴于候選鍵(BNo,CNo)，因此BuyTest(U,F)2NF，又因為2NF

3NF，從而BuyTest(U,F)3NF。但是：BuyTest(U,F)∈1NF，并且根據(jù)傳遞函數(shù)依賴的定義，BuyTest(U,F)的每一個非主屬性都不傳遞函數(shù)依賴于候選鍵(BNo,CNo)。28

CNameCNoBNoBNamePDate

6.2.4第三范式思考：如果R（U，F(xiàn)）無非主屬性，則R∈3NF？提示：3NF雖然在一定程度上解決了插入異常、修改異常、刪除異常和冗余數(shù)據(jù)等問題，但3NF一般也不是最理想的關系模式，仍然會破壞數(shù)據(jù)完整性。結論：解決不滿足3NF的方法是分解關系模式，消除所有非主屬性對候選鍵的部分函數(shù)依賴關系和傳遞函數(shù)依賴關系。即：對于R∈1NF，只要存在一個非主屬性部分函數(shù)依賴于R的候選鍵，或者存在一個非主屬性傳遞函數(shù)依賴于R的候選鍵，則R3NF。296.2.5BC范式定義6.8對于R（U，F(xiàn)）∈1NF的任意非平凡函數(shù)依賴X→Y，如果X必含有候選鍵，則R∈BCNF。根據(jù)定義6.8不難證明：如果R∈BCNF，則R的所有屬性（主屬性+非主屬性）均完全函數(shù)依賴于R的候選鍵，且均不傳遞依賴于R的候選鍵。即：BCNF在3NF的基礎上，進一步消除了主屬性對候選鍵的部分函數(shù)依賴和傳遞函數(shù)依賴。BCNF的等價描述：如果R(U,F)∈1NF，則R的每個屬性既不部分，也不傳遞函數(shù)依賴于R的候選鍵。不難證明，以下結論成立：（1）如果R∈BCNF，則R∈3NF；如果R∈3NF，則R不一定滿足BCNF。（2）如果R∈3NF，且R只有一個候選鍵，則R∈BCNF。（3）如果R的候選鍵為全鍵，則R∈BCNF。306.2.5BC范式例6.8如果R(A,B,C,D)∈1NF的函數(shù)依賴集為F={AB→D,D→C}，則RBCNF。因為：R的唯一候選鍵為AB，對于F中的函數(shù)依賴D→C，D不包含候選鍵，所以R(A,B,C,D)BCNF。R的BCNF分解結果：R=R1∪R2R1(U1,F1)=({A,B,D},{AB→D})R2(U2,F2)=({D,C},{D→C})顯然：R1(U1,F1)∈BCNF，R2(U2,F2)∈BCNF。思考：R(A,B,C,D)∈3NF？說明原因。316.2.5BC范式例6.9如果R(A,B,C)∈1NF的函數(shù)依賴集為F={AB→C,BC→A}，則R∈BCNF。因為：R的候選鍵為AB和BC，由于R(A,B,C)的每個非平凡函數(shù)依賴均包含候選鍵，根據(jù)定義6.8可知，R(A,B,C)∈BCNF。例6.10如果R(A,B,C)∈1NF的函數(shù)依賴集為F={AB→C,AC→B,B→C}，則RBCNF。因為：R的候選鍵為AB和AC，對于F中的函數(shù)依賴B→C，B不包含候選鍵，所以：R(A,B,C)BCNF。R的BCNF分解結果：R=R1∪R2R1(U1,F1)=({A,B},

)R2(U2,F2)=({B,C},{B→C})顯然：R1(U1,F1)∈BCNF，R2(U2,F2)∈BCNF。

思考：R(A,B,C)是否滿足3NF？說明原因。326.2.5BC范式例6.11如果R(A,B,C)∈1NF的函數(shù)依賴集為空集（F=

），則R∈BCNF。因為：F=

，所以A,B,C之間不存在任何函數(shù)依賴關系。所以：R的候選鍵為ABC（即：全鍵）。因此，R(A,B,C)∈BCNF。結論：解決不滿足BCNF的方法是分解關系模式，消除所有屬性對候選鍵的部分函數(shù)依賴關系和傳遞函數(shù)依賴關系。即：對于R∈1NF，只要存在一個屬性部分函數(shù)依賴于R的候選鍵；或者存在一個屬性傳遞函數(shù)依賴于R的候選鍵；或者存在一個函數(shù)依賴，其決定屬性集不包含R的候選鍵，則RBCNF。在函數(shù)依賴的范疇內，BCNF達到了范式規(guī)范化的最高級別，實現(xiàn)了函數(shù)依賴的“徹底分離”，已經(jīng)“基本上”解決了插入異常、修改異常和刪除異常等問題。思考：滿足BCNF的關系模式R存在冗余數(shù)據(jù)嗎？插入、修改和刪除是否出現(xiàn)異常？R是最理想的關系模式嗎？R存在多值依賴嗎？336.2.6第四范式定義6.9對于關系模式R(U，F(xiàn))，X和Y是U的子集，且Z＝U－X－Y。如果R的關系中存在元組s1=(x,y1,z1)和s2=(x,y2,z2)，則R的關系中一定存在元組t1=(x,y2,z1)和t2=(x,y1,z2)，則稱Y多值依賴于X，記為X→→Y。其中：x,yi,zi（i=1，2）分別為元組在X,Y,Z上的分量值。在定義6.9中，通過分析s1,s2與t1,t2的特征，不難發(fā)現(xiàn)t1,t2是交換s1,s2的Y分量值后所得到的兩個元組，而且s1,s2與t1,t2的X,Z的分量值保持不變。多值依賴的等價定義：定義6.10對于關系模式R(U，F(xiàn))，X和Y是U的子集，且Z＝U－X－Y。如果R的關系在(X，Z)上的每個值所對應的一組Y值，只取決于X值而與Z值無關，則稱Y多值依賴于X。346.2.6第四范式對于定義6.9和定義6.10的分析：對于定義6.9中的四個元組，假設s1,s2,t1,t2這四個元組組成的關系為S，則S在(X，Z)上的值x,z1(或x,z2)所對應的一組Y值{y1,y2}，只決定于X值x(即：x→(y1,y2)),而與Z值z1(或z2)無關。即：s1=(x,y1,z1)和t1=(x,y2,z1)在(X，Z)上的值x,z1，所對應的Y值為{y1,y2}，只取決于X值x，而與Z值z1無關。亦即：s2=(x,y2,z2)和t2=(x,y1,z2)在(X，Z)上的值x,z2，所對應的Y值仍然為{y1,y2}，只取決于X值x，而與Z值z2無關。約定：若X→→Y，而Z＝

，則X→→Y稱為平凡多值依賴；否則為非平凡多值依賴。356.2.6第四范式例6.12對于關系模式：配送（書庫，職工，圖書），要求每個書庫有多個職工和多種圖書，同時要求每個職工管理所在書庫的圖書（如表6.1所示）。36書庫職工圖書庫1張磊高等數(shù)學庫1張磊圖像分析庫1張磊Java語言庫1李麗高等數(shù)學庫1李麗圖像分析庫1李麗Java語言庫2王娟數(shù)據(jù)結構庫2王娟軟件工程庫2孫亮數(shù)據(jù)結構庫2孫亮軟件工程6.2.6第四范式（1）根據(jù)定義6.9判斷配送的多值依賴設X={書庫}，Y={職工}，Z={圖書}，對于配送關系中的元組：s1=（庫1，張磊，高等數(shù)學）和s2=（庫1，李麗，圖像分析），則：t1=（庫1，李麗，高等數(shù)學）和t2=（庫1，張磊，圖像分析）也在配送關系中。因此，職工多值依賴于書庫。（2）根據(jù)定義6.10判斷配送的多值依賴設X={書庫}，Y={職工}，Z={圖書}，則配送在(X，Z)上的值：（庫1,高等數(shù)學)、或（庫1,圖像分析)、或（庫1,Java語言）所對應的一組Y值{張磊,李麗}，只取決于X值：庫1(即：庫1→(張磊,李麗)),而與Z值高等數(shù)學、或圖像分析、或Java語言無關。因此，職工多值依賴于書庫。

思考：分析圖書對書庫的多值依賴關系。376.2.6第四范式因為配送中存在多值依賴，從而導致表6.1中存在大量的冗余數(shù)據(jù)、插入/修改/刪除數(shù)據(jù)復雜等問題。多值依賴的基本性質：（1）如果X→→Y，則X→→Z，其中Z＝U－X－Y（對稱性）。（2）如果X→→Y，Y→→Z，則X→→Z–Y（傳遞性）。（3）如果X→Y，則X→→Y（函數(shù)依賴是多值依賴的特例）。（4）如果X→→Y，X→→Z，則X→→Y∪Z。（5）如果X→→Y，X→→Z，則X→→Y∩Z。（6）如果X→→Y，X→→Z，則X→→Y-Z，X→→Z-Y。（7）如果X→→Y在U上成立，則在W（X∪Y

W

U）上一定成立；反之不真。（8）如果X→→Y，且Z

Y，則X→→Z不一定成立。386.2.6第四范式定義6.11如果R(U,F)∈1NF的每個非平凡多值依賴X→→Y（Y

X），X都含有候選鍵，則R∈4NF。顯然，如果R∈4NF，則R∈BCNF。根據(jù)定義6.11不難證明，4NF不允許存在非平凡且非函數(shù)依賴的多值依賴。例如：在例6.12中，配送（書庫，職工，圖書）的候選鍵是全鍵，則配送∈BCNF，但是，配送不滿足4NF，因為配送存在多值依賴：書庫→→管理員；書庫→→圖書。采用投影分解法，配送的4NF分解結果：配送1（書庫，管理員)，配送2（書庫，圖書)。396.2.6第四范式結論：解決不滿足4NF的方法是分解關系模式，消除所有非平凡且非函數(shù)依賴的多值依賴。即：對于R∈1NF，只要存在一個多值依賴X→→Y，但是X不包含R的候選鍵,則R4NF。在多值依賴的范疇內，4NF達到了范式規(guī)范化的最高級別，并“基本上”解決了數(shù)據(jù)冗余、插入異常、修改異常和刪除異常等問題。但是4NF仍然存在一定的問題。因此需要使用連接依賴，使關系模式達到更高級的范式5NF。即：對于R∈4NF，如果消除關系模式中的連接依賴，則R∈5NF。連接依賴和5NF的有關內容，請參閱相關文獻。40關系模式的規(guī)范化過程41BCNF4NF3NF5NF2NF1NF消除連接依賴消除非平凡且非函數(shù)依賴的多值依賴

消除主屬性對候選鍵的部分和傳遞函數(shù)依賴消除非主屬性對候選鍵的傳遞函數(shù)依賴

消除非主屬性對候選鍵的部分函數(shù)依賴6.3關系模式規(guī)范化規(guī)范化：分解低級關系模式使其轉換為高級關系模式的過程(范式分解Armstrong公理函數(shù)依賴集閉包屬性集閉包最小函數(shù)依賴集關系模式分解關系模式的分解算法426.3.1Armstrong公理43Armstrong公理作為關系模式規(guī)范化的核心，可以解決如下問題：（1）計算函數(shù)依賴的閉包

。（2）確定關系模式的候選鍵。（3）計算屬性集合的閉包

。（4）計算最小函數(shù)依賴集Fmin。定義6.12對于關系模式R(U,F)∈1NF，如果在R(U,F)下X→Y，則稱函數(shù)依賴集F邏輯蘊涵X→Y（F蘊涵X→Y）。記為：FX→Y。提示：如果FX→Y，則X→Y可能屬于F，也可能不屬于F。例如：對于R(U,F)，U={A,B,C}，F(xiàn)={A→B,B→C}，則FA→B，F(xiàn)B→C，F(xiàn)A→C；其中A→B∈F，B→C∈F，但是A→CF。6.3.1Armstrong公理44Armstrong公理是由W.W.Armstrong于1974提出的，具體內容如下：Armstrong公理

關系模式R(U,F)∈1NF，如果W，X，Y，Z

U，則成立：（1）自反律：如果Y

X，則X→Y。（2）增廣律：如果X→Y，則XZ→YZ。（3）傳遞律：如果X→Y，Y→Z，則X→Z。Armstrong公理的推廣規(guī)則：（1）合并律：如果X→Y，X→Z，則X→YZ。（2）分解律：如果X→YZ，則X→Y，X→Z。（3）偽傳遞：如果X→Y，YW→Z，則有XW→Z。根據(jù)分解律和合并律，不難證明，推論6.1和推論6.2成立。推論6.lX→A1A2…Ak當且僅當X→Ai(i=l,2,…,k)。推論6.2Armstrong公理是封閉的。6.3.2函數(shù)依賴集閉包45定義6.13函數(shù)依賴集閉包是指在關系模式R(U,F)中，F(xiàn)所邏輯蘊含的所有函數(shù)依賴的集合。記為：

顯然成立：={X→Y|

FX→Y}。例6.13對于R（X，Y，Z）∈1NF，如果F={X→Y,Y→Z}，計算根據(jù)定義6.12和定義6.13，則不難導出

中的所有43個函數(shù)依賴。即：{X→

,X→X,X→Y,X→Z,X→XY,X→XZ,X→YZ,X→XYZ,Y→

,Y→Y,Y→Z,Y→YZ,

Z→

,Z→Z,

XY→

,XY→X,XY→Y,XY→Z,XY→XY,XY→YZ,XY→XZ,XY→XYZ,XZ→

,XZ→X,XZ→Y,XZ→Z,XZ→XY,XZ→XZ,XZ→XY,XZ→XYZ,YZ→

,YZ→Y,YZ→Z,YZ→YZ,

XYZ→

,XYZ→X,XYZ→Y,XYZ→Z,XYZ→XY,XYZ→YZ,XYZ→XZ,XYZ→XYZ,

→

}

6.3.2函數(shù)依賴集閉包46根據(jù)上述例題不難看出，

中包含了大量的平凡依賴；而且計算

是一個NP-Hard問題（Non-PolynomialHardProblem，非多項式時間困難問題）

的計算復雜度：O(2n)。6.3.3屬性集閉包47定義6.14U中屬性集X的閉包是指在R(U,F)中,X在F下按照Armstrong公理導出的所有屬性的集合。記為：顯然成立：={A|FX→A}；而且

例6.14對于R（X，Y，Z）∈1NF，如果F={X→Y,Y→Z}，計算根據(jù)定義6.14，由于X→Y，則=XY；又因為Y→Z，則=XYZ。根據(jù)例6.14不難發(fā)現(xiàn)，利用Armstrong公理，計算“屬性集閉包”變得比較容易。如果把計算

轉換為計算

，將使計算

變得比較方便。推論6.3解決了該問題。推論6.3X→Y∈

當且僅當Y判定：X→Y∈

？，轉化為：計算=？和判定Y？定義6.15對于R(U,F)，如果XU，且=U，則X是候選鍵。6.3.3屬性集閉包48屬性集閉包可以解決如下問題：（1）判斷候選鍵判斷屬性集X為候選鍵的方法：先計算

，再判斷=U？如果成立，則X是候選鍵，否則不是。（2）判斷函數(shù)依賴是否成立判斷函數(shù)依賴X→Y，在R(U,F)下成立的方法：先計算

，再判斷

，

？如果成立，則X→Y∈

，否則不成立。（3）計算

利用

生成

的方法：對于每一個ZU，先計算

，再對

任意S，輸出Z→S。6.3.3屬性集閉包49算法6.l對于R(U,F)∈1NF，如果XU，計算

的步驟：（1）i=1，X(i)=X（2）計算B={W|FV→W∧

VX(i)}（3）X(i+1)=B∪X(i)（4）判斷X(i+1)=X(i)？如果相等或X(i+1)=U，則=X(i+1)，結束；否則i←i+l，轉向（2）。計算

的算法復雜度：O(|U|-|X|)。因為1≤|X(i)|＜|X(i+1)|≤|U|。6.3.3屬性集閉包50例6.15對于R(U,F)∈1NF，U={A,B,C,D,E}，F(xiàn)={AB→C,B→D,C→E,EC→B,AC→B}。計算=？（1）i=1，X(1)=AB（2）

VX(1)，計算Y={W|FV→W∧

VX(1)}；即：

計算：{W|FA→W}=？，{W|FB→W}=？，{W|FAB→W}=？。方法：依次掃描F的函數(shù)依賴，計算X(1)的子集分別為A，B，AB的函數(shù)依賴所導出的新屬性。即：A→

，B→D，AB→C，所以，Y=CD。（3）X(2)=Y∪X(1)=ABCD。（4）判斷X(2)=X(1)？因為X(2)≠X(1)，且X(2)≠U，所以X(1)

X(2)，轉向（2），繼續(xù)計算X(1)=ABCD的子集導出的新屬性，即：AB→C，B→D，C→E，AC→B；所以，Y=E。（5）X(2)=Y∪X(1)=E∪X(1)=ABCDE。（6）因為X(2)=U，結束。6.3.3屬性集閉包51算法6.l可以簡化如下（如圖6.7所示）：（1）=X。（2）如果

存在Y，而且Y→A

F，則=∪A。（3）判斷

是否改變，如果不改變，則輸出

，結束；否則轉向（2）。Y新

A6.3.3屬性集閉包52例6.16對于R∈1NF，U={A,B,C,D}，F(xiàn)={A→B,BC→D}，計算

、

、

和

（1）=AA，A→B

F，=∪B=AB。（2）=B。（3）=C。（4）=AC（如圖6.8所示）A，A→B

F，=∪B=ABC；BC，BC→D

F，=∪D=ABCD。

AC

A→B

BC→DABCDACB6.3.4最小函數(shù)依賴集53定義6.16對于函數(shù)依賴集F和G，如果=，則稱F和G互相覆蓋（或者F和G等價。記為：F≡G。定義6.17函數(shù)依賴集F稱為最小函數(shù)依賴集（記為：Fmin），如果F滿足：（1）函數(shù)依賴的右部均為單屬性。（2）不含冗余函數(shù)依賴。即：不存在X→A，使得F≡F-{X→A}。（3）函數(shù)依賴的左部均無冗余屬性。即：不存在X→A，對于

ZX，滿足：F≡(F-{X→A})∪{Z→A}。例如：對于R(U,F)，U={A,B,C,D}，F(xiàn)={A→B,A→C,B→C,C→D}，則A→C是冗余函數(shù)依賴，所以Fmin={A→B,B→C,C→D}。再如：對于R(U,F)，U={A,B,C,D}，F(xiàn)={A→B,BC→D,B→D}，則BC→D中的屬性C是冗余屬性，所以Fmin={A→B,B→D}。如何判斷F覆蓋G或者G覆蓋F？定理6.1幫助解決了這個問題。6.3.4最小函數(shù)依賴集54定理6.1對于函數(shù)依賴集F和G，則：=當且僅當

∧證明：必要性：因為

，所以G，且F充分性：因為

∧

，所以=（1）根據(jù)

，證明

只需證明任意X→Y，則X→Y因為

，所以又因為X→Y，所以Y

進而X→Y。即：

（2）根據(jù)

，證明

。同理可證。如果需要判斷F覆蓋G（即：

），則只須依次判斷G的函數(shù)依賴X→Y，是否成立

？給出了判斷兩個函數(shù)依賴集等價的可行性算法。6.3.4最小函數(shù)依賴集55算法6.2計算Fmin=？（1）分解X→Y1Y2…Yn的右側屬性為單屬性。即：對X→Y1Y2…YnF，則X→Y1，X→Y2，…，X→Yn。（2）消除X=X1…Xi…Xn→Y左側屬性的冗余屬性Xi。即：如果Y，則消除屬性Xi。（3）消除冗余函數(shù)依賴X→Y。即：如果Y，則消除X→Y。思考：Fmin是否唯一？不難看出：如果F≡G，則可以利用Fmin替代G（或Gmin替代F）。6.3.4最小函數(shù)依賴集56例6.17對于R(U,F)，U={A,B,C,D,E}，F(xiàn)={A→D，E→D，D→B，BC→D，DC→A，B→AD}，計算Fmin=？分析：（1）依次分解函數(shù)依賴的右側屬性為單屬性。即：F={A→D，E→D，D→B，BC→D，DC→A，B→A，B→D}（2）依次消除函數(shù)依賴左側屬性的冗余屬性。即：1）BC→D中C冗余。因為D，所以消除C。因此F={A→D，E→D，D→B，B→D，DC→A，B→A}。2）DC→A中C冗余。因為A，所以消除C。因此F={A→D，E→D，D→B，B→D，D→A，B→A}。6.3.4最小函數(shù)依賴集57（3）依次消除冗余函數(shù)依賴。即：B→D冗余。因為D，所以消除B→D。則F={A→D，E→D，D→B，D→A，B→A}。同樣，D→A冗余，則F={A→D，E→D，D→B，B→A}。所以Fmin={A→D，E→D，D→B，B→A}思考：在例6.17中，是否存在等價的Fmin。6.3.4最小函數(shù)依賴集58F的最小依賴集不一定是唯一的

例：F={A→B，B→A，B→C，A→C，C→A}

6.3.5關系模式分解59等價分解：分解后的關系模式，既要保持信息不能丟失，又要保持函數(shù)依賴不能改變。保連接分解：如果分解后的關系模式，通過連接所生成的新關系模式，與原始關系模式等價。這種連接稱為“無損連接”。保依賴分解：如果分解后的關系模式，函數(shù)依賴集的閉包，與原始關系模式的閉包等價不難看出：保連接分解可以保持關系模式分解后不丟失數(shù)據(jù)信息；保依賴分解可以保持關系模式分解后不破壞數(shù)據(jù)完整性。即：保連接保信息；保依賴保完整。關系模式的常用分解：（1）關系模式的保連接分解。（2）關系模式的保依賴分解。（3）關系模式的既保連接，又保依賴分解。關系模式的理想分解。6.3.5關系模式分解60定義6.18對于R(U,F)，V

U，則{X→Y|X→Y∧XY

V}的一個覆蓋G稱為F在V上的投影。例6.18對于R(U,F)，U={A,B,C,D}，F(xiàn)={A→B，B→C，C→D},V={A,B,C}，則AB

V，A→B；BC

V，B→C。F在V上的投影：G={A→B，B→C}。

定義6.19對于R(U,F)，U=U1∪U2∪…∪Un，且任意不同的Ui和Uj均不相互包含，則R{R1(U1,F1)，…，Rn(Un,Fn)}稱為R(U,F)的一個分解。其中：Fi為F在Ui上的投影（i=1，2，…，n）。

例6.19對于R(U,F)，U={A,B,C,D}，F(xiàn)={A→B，B→C，C→D},則R{R1(U1,F1)，R2(U2,F2)}為R(U,F)的一個分解。其中：U1={A,B,C}，F(xiàn)1={A→B，B→C}。U2={A,B,D}，F(xiàn)2={A→B，B→D}。6.3.5關系模式分解61定義6.20假設R{R1(U1,F1)，R2(U2,F2)，…，Rn(Un,Fn)}是R(U,F)的一個分解，如果R1(U1,F1)，R2(U2,F2)，…，Rn(Un,Fn)的連接與R(U,F)等價，即：則

R稱為R的保連接分解。

6.3.5關系模式分解62例6.20對于PBook(U,F)，U={BNo,PNo,PBoss}，F(xiàn)={BNo→PNo，PNo→PBoss}，PBook對應的關系如表6.2所示，則如下分解保連接嗎？（1）R

1={B1({BNo},

)，P1({PNo},

)，S1(PBoss,

)}（2）R2={B2({BNo,PNo},{BNo→PNo})，P2({PNo,PBoss},{PNo→PBoss})}（3）R

3={B3({BNo,PNo},{BNo→PNo})，P3({BNo,PBoss},{BNo→PBoss})}（4）R

4={B4({BNo,PBoss},{BNo→PBoss})，P4({PNo,PBoss},{PNo→PBoss})}

6.3.5關系模式分解63表6.2PBook書號BNo社號PNo社長Pboss（可以重名）ISBN978-7-04-040664-1ISBN978-7-04劉軍ISBN978-7-302-33894-9ISBN978-7-302劉軍ISBN978-7-5612-2591-2ISBN978-7-5612吳廣ISBN978-7-5612-2123-1ISBN978-7-5612吳廣ISBN978-7-5178-0167-2ISBN978-7-81140白亮ISBN978-7-81140-582-8ISBN978-7-81140白亮6.3.5關系模式分解64根據(jù)F可知，PBook(U,F)2NF。（1）R

1={B1,P1,S1}不保連接。因為：B1,P1,S1僅包含書號、社號和社長自身的基本信息，已經(jīng)丟失了所有的函數(shù)依賴關系，所以PBook已經(jīng)無法通過B1,P1,S1的連接進行恢復。如果使用笛卡兒積，則生成6*4*3=72個元組的新關系，與PBook不符。（2）R

2={B2,P2}保連接。因為：B2,P2對應的關系如表6.3和表6.4所示。顯然PBook=B2P2。6.3.5關系模式分解65表6.3B2BNoPNoISBN978-7-04-040664-1ISBN978-7-04ISBN978-7-302-33894-9ISBN978-7-302ISBN978-7-5612-2591-2ISBN978-7-5612ISBN978-7-5612-2123-1ISBN978-7-5612ISBN978-7-5178-0167-2ISBN978-7-81140ISBN978-7-81140-582-8ISBN978-7-81140PNoPBossISBN978-7-04劉軍ISBN978-7-302劉軍ISBN978-7-5612吳廣ISBN978-7-81140白亮表6.4P26.3.5關系模式分解66（3）R

3={B3,P3}保連接。因為：B3和P3對應的關系如6.3和表6.5所示。顯然PBook=B3P3

。6.3.5關系模式分解67表6.3B3BNoPNoISBN978-7-04-040664-1ISBN978-7-04ISBN978-7-302-33894-9ISBN978-7-302ISBN978-7-5612-2591-2ISBN978-7-5612ISBN978-7-5612-2123-1ISBN978-7-5612ISBN978-7-5178-0167-2ISBN978-7-81140ISBN978-7-81140-582-8ISBN978-7-81140表6.5P3BNoPBossISBN978-7-04-040664-1劉軍ISBN978-7-302-33894-9劉軍ISBN978-7-5612-2591-2吳廣ISBN978-7-5612-2123-1吳廣ISBN978-7-5178-0167-2白亮ISBN978-7-81140-582-8白亮6.3.5關系模式分解68（4）R4={B4,P4}不保連接。因為：B4,P4,對應的關系如6.6和表6.4所示。所以：B4P4的對應的關系如6.7所示。6.3.5關系模式分解69表6.6B4表6.4P4BNoPBoosISBN978-7-04-040664-1劉軍ISBN978-7-302-33894-9劉軍ISBN978-7-5612-2591-2吳廣ISBN978-7-5612-2123-1吳廣ISBN978-7-5178-0167-2白亮ISBN978-7-81140-582-8白亮BNoPBoosISBN978-7-04-040664-1劉軍ISBN978-7-302-33894-9劉軍ISBN978-7-5612-2591-2吳廣ISBN978-7-5612-2123-1吳廣ISBN978-7-5178-0167-2白亮ISBN978-7-81140-582-8白亮6.3.5關系模式分解70表6.7B4與P4的自然連接BnoPNoPBossISBN978-7-04-040664-1ISBN978-7-04劉軍ISBN978-7-04-040664-1ISBN978-7-302劉軍ISBN978-7-302-33894-9ISBN978-7-04劉軍ISBN978-7-302-33894-9ISBN978-7-302劉軍ISBN978-7-5612-2591-2ISBN978-7-5612吳廣ISBN978-7-5612-2123-1ISBN978-7-5612吳廣ISBN978-7-5178-0167-2ISBN978-7-81140白亮ISBN978-7-81140-582-8ISBN978-7-81140白亮6.3.5關系模式分解71綜上所述：在使用分解后的關系模式再現(xiàn)原始關系模式時，使用笛卡兒積會增加很多沒有意義的元組（一般不用）；使用條件連接對于特殊應用比較有效（不建議經(jīng)常使用）；使用自然連接是最有效的方法（建議經(jīng)常使用）。6.3.5關系模式分解72定義6.21R{R1(U1,F1)，R2(U2,F2)，…，Rn(Un,Fn)}是R(U,F)的一個分解，如果(F1∪F2∪…∪Fn)≡F，即：則R

稱為R的保依賴分解。6.3.5關系模式分解73例6.21對于例6.20中的分解，判斷其保依賴性。（1）R

1={B1,P1,S1}不保連接，不保依賴。因為在B1({BNo},

)，P1({PNo},

)，S1(PBoss,

)中,FB1∪FP1∪FS1=

。所以

≠(FB1∪FP1∪FS1)。（2）R

2={B2,P2}保連接，保依賴。理想的分解。因為在B2({BNo,PNo},{BNo→PNo})，P2({PNo,PBoss},{PNo→PBoss})中，F(xiàn)B2∪FP2={BNo→PNo,PNo→PBoss}。所以=(FB2∪FP2)。6.3.5關系模式分解74例6.21對于例6.20中的分解，判斷其保依賴性。（3）R

3={B3,P3}保連接，不保依賴。因為在B3({BNo,PNo},{BNo→PNo})，P3({BNo,PBoss}，{BNo→PBoss})中，F(xiàn)B3∪FP3={BNo→PNo,BNo→PBoss}。所以

≠(FB3∪FP3)，顯然丟失PNo→PBoss。（4）R

4={B4,P4}不保連接，不保依賴。因在B4({BNo,PBoss},{BNo→PBoss})，P4({PNo,PBoss},{PNo→PBoss})中，F(xiàn)B4∪FP4={BNo→PBoss,PNo→PBoss}。所以

≠(FB4∪FP4)，顯然丟失BNo→PNo。思考1：舉例說明不保連接保依賴分解。思考2：分析保連接和保依賴的關系？6.3.6關系模式的分解算法75根據(jù)關系模式分解的基本理論，常用的分解算法如下：（1）模式分解的保連接算法。（2）模式分解的保依賴算法。（3）3NF分解的保依賴算法。（4）3NF分解的既保連接性又保依賴算法。（5）BCNF分解的保連接算法。（6）4NF分解的保連接算法。6.3.6關系模式的分解算法76算法6.3模式分解的保連接算法。如果R{R1(U1,F1)，R2(U2,F2)，…，Rn(Un,Fn)}是R(U,F)的一個分解，U={A1,A2,…,Am}，F(xiàn)min={FD1,FD2,…,FDt}，則R的保連接分解如下：（1）構造狀態(tài)表T(n,m)。建立一張n行m列的狀態(tài)表T(n,m)，每行對應分解后的一個Ri(Ui,Fi)，每列對應R(U,F)的一個屬性，則T的第i行第j列T(i,j)的填寫方法：如果第i個Ri(Ui,Fi)的Ui包含R(U,F)的第j個Aj，則T(i,j)=aj；否則T(i,j)=bij。（2）利用R(U,Fmin)的FDi修正T。依次使用R(U,Fmin)的函數(shù)依賴FDi（不妨設為：X→Y）修正T，如果T在X分量上的值不等，則不需要修正，轉向下