關(guān)系數(shù)據(jù)庫(kù)基本原理

（3）規(guī)范化理論王傳棟南京郵電大學(xué)計(jì)算機(jī)學(xué)院關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第1頁(yè)2引言關(guān)系DB規(guī)范化設(shè)計(jì)是指面對(duì)一個(gè)現(xiàn)實(shí)問(wèn)題（問(wèn)題域），怎樣選擇一個(gè)比很好關(guān)系模式集合（求解域：DB實(shí)現(xiàn)方案，也稱(chēng)數(shù)據(jù)庫(kù)模式）規(guī)范化設(shè)計(jì)理論，對(duì)關(guān)系數(shù)據(jù)庫(kù)結(jié)構(gòu)設(shè)計(jì)起著主要作用，包括3個(gè)方面內(nèi)容：數(shù)據(jù)依賴(lài)起著關(guān)鍵作用，研究數(shù)據(jù)之間聯(lián)絡(luò)范式（NF）關(guān)系模式標(biāo)準(zhǔn)模式設(shè)計(jì)方法自動(dòng)化設(shè)計(jì)基礎(chǔ)關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第2頁(yè)3關(guān)系模式設(shè)計(jì)問(wèn)題外延和內(nèi)涵外延，與時(shí)間相關(guān)，隨時(shí)間推移不停改變通常指關(guān)系、表或當(dāng)前值內(nèi)涵，與時(shí)間是獨(dú)立，通常指關(guān)系模式，包含2個(gè)方面數(shù)據(jù)定義：關(guān)系、屬性、域定義和說(shuō)明數(shù)據(jù)完整性約束定義靜態(tài)約束，包括到數(shù)據(jù)之間聯(lián)絡(luò)（稱(chēng)為數(shù)據(jù)依賴(lài)，datadependences）、主鍵和值域設(shè)計(jì)動(dòng)態(tài)約束，定義各種操作（插入、刪除、修改）對(duì)關(guān)系值影響關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第3頁(yè)4關(guān)系模式設(shè)計(jì)問(wèn)題冗余和異常問(wèn)題域：學(xué)生選修課程泛關(guān)系模式R（SNO,SNAME,AGE,SEX,NativePlace,CNO,CNAME,Credit, CreditHours,CPNO,TNO,TNAME,TITLE,SEX,DNO,DNAME,Grade）泛關(guān)系關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第4頁(yè)5關(guān)系模式設(shè)計(jì)問(wèn)題冗余和異常數(shù)據(jù)冗余是指同一個(gè)數(shù)據(jù)在系統(tǒng)中屢次重復(fù)出現(xiàn)數(shù)據(jù)冗余引發(fā)操作異常修改異常插入異常刪除異常消除冗余主要方式：分解問(wèn)題什么是最優(yōu)關(guān)系模式？標(biāo)準(zhǔn)是什么？怎樣實(shí)現(xiàn)？關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第5頁(yè)6關(guān)系模式設(shè)計(jì)問(wèn)題冗余和異常求解域數(shù)據(jù)庫(kù)模式數(shù)據(jù)庫(kù)實(shí)例：關(guān)系集合關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第6頁(yè)7關(guān)系模式設(shè)計(jì)問(wèn)題非形式化設(shè)計(jì)準(zhǔn)則準(zhǔn)則1：一事一地設(shè)計(jì)標(biāo)準(zhǔn)關(guān)系模式設(shè)計(jì)應(yīng)盡可能只包含有直接聯(lián)絡(luò)屬性，不要包含有間接聯(lián)絡(luò)屬性也就是：每個(gè)關(guān)系模式應(yīng)只對(duì)應(yīng)于一個(gè)實(shí)體類(lèi)型或一個(gè)聯(lián)絡(luò)類(lèi)型準(zhǔn)則2關(guān)系模式設(shè)計(jì)應(yīng)盡可能使對(duì)應(yīng)關(guān)系中不出現(xiàn)插入、刪除和修改等操作異?，F(xiàn)象假如出現(xiàn)任何異常，則要清楚地加以說(shuō)明，并確保更新數(shù)據(jù)庫(kù)程序正確操作關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第7頁(yè)8關(guān)系模式設(shè)計(jì)問(wèn)題非形式化設(shè)計(jì)準(zhǔn)則準(zhǔn)則3關(guān)系模式設(shè)計(jì)應(yīng)盡可能使對(duì)應(yīng)關(guān)系中防止放置經(jīng)常為空值屬性（允許為NULL屬性盡可能少）準(zhǔn)則4關(guān)系模式設(shè)計(jì)應(yīng)盡可能使關(guān)系等值連接在主鍵和外鍵屬性上進(jìn)行，而且確保連接后不會(huì)生成額外元組關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第8頁(yè)9關(guān)系模式設(shè)計(jì)問(wèn)題符號(hào)要求大寫(xiě)字母“A，B，C，…”表示單個(gè)屬性大寫(xiě)字母“…，U，V，W，X，Y，Z”表示屬性集大寫(xiě)字母R表示關(guān)系模式，小寫(xiě)字母r表示其關(guān)系有時(shí)也用屬性名組合寫(xiě)法表示關(guān)系模式若模式有A、B、C有三個(gè)屬性，就用ABC表示關(guān)系模式屬性集｛A1，…，An｝簡(jiǎn)寫(xiě)為A1…AnX∪Y簡(jiǎn)寫(xiě)為XYX∪｛A｝簡(jiǎn)寫(xiě)為XA或AX關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第9頁(yè)10函數(shù)依賴(lài)（functionaldependency，簡(jiǎn)記為FD）定義關(guān)系模式R(U)，XU，YU，r是R當(dāng)前關(guān)系，函數(shù)依賴(lài)FD是形為X→Y一個(gè)命題：r中任意兩個(gè)元組t和s，都有t[X]＝s[X]蘊(yùn)涵t[Y]＝s[Y]，則稱(chēng)FDX→Y在關(guān)系模式R(U)中成立若X→Y，且Y→X，記作XY，X與Y一一對(duì)應(yīng)（一對(duì)一）了解函數(shù)依賴(lài)是指：一個(gè)或一組屬性值能夠決定其它屬性值屬性值之間聯(lián)絡(luò)（本質(zhì)：實(shí)體完整性）是基于整個(gè)關(guān)系模式，而不是關(guān)系模式特定實(shí)例(或值)X→Y，讀“X函數(shù)決定Y”或“Y函數(shù)依賴(lài)于X”，稱(chēng)X為決定子Y不依賴(lài)于X，記作X→Y/

關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第10頁(yè)11函數(shù)依賴(lài)（functionaldependency，簡(jiǎn)記為FD）示例1）關(guān)系R中FDA→B關(guān)系S中FDA→B2）關(guān)系模式R（ABCD），屬性值間含有聯(lián)絡(luò)：A值與B值有一對(duì)多聯(lián)絡(luò)FDB→A；A→BC值與D值有一對(duì)一聯(lián)絡(luò)FD

C→D，D→C；DC/

/

關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第11頁(yè)12函數(shù)依賴(lài)（functionaldependency，簡(jiǎn)記為FD）示例3）R（SNO,SNAME,AGE,SEX,NativePlace,CNO,CNAME,Credit, CreditHours,CPNO,TNO,TNAME,TITLE,SEX,DNO,DNAME,Grade）SNO→SNAME，SNO→(AGE,SEX)CNO→CNAME(SNO,CNO)→GRADE，(SNO,CNO)→UCNO→TNO，TNO→CNOAGE→SNO，SEX→AGE等/

/

/

關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第12頁(yè)13FD和關(guān)鍵碼聯(lián)絡(luò)定義關(guān)系模式R（U），假設(shè)X1

X，XU若X→U在R上成立，則稱(chēng)X是R一個(gè)超鍵若X→U在R上成立， 但對(duì)于X1→U不成立（X1→U），則稱(chēng)X是R上一個(gè)候選鍵/

關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第13頁(yè)14FD和關(guān)鍵碼聯(lián)絡(luò)示例R（SNO,SNAME,AGE,SEX,NativePlace,CNO,CNAME,Credit, CreditHours,CPNO,TNO,TNAME,TITLE,SEX,DNO,DNAME,Grade）(SNO,CNO)是唯一候選鍵，因?yàn)?SNO,CNO)→U怎樣確定關(guān)系候選鍵？包含(SNO,CNO)屬性組合就是超鍵，但不是候選鍵，如(SNO,CNO,AGE)(SNO,SNAME,CNO,CNAME)∵能→U，但……關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第14頁(yè)15FD和關(guān)鍵碼聯(lián)絡(luò)邏輯蘊(yùn)含設(shè)F是在關(guān)系模式R上成立FD集合，X→Y是一個(gè)FD。假如對(duì)于R每個(gè)滿(mǎn)足F關(guān)系r也滿(mǎn)足X→Y，那么稱(chēng)F邏輯蘊(yùn)涵X→Y，記為F?X→Y。示例：F=｛A→B，B→C｝?

A→CFD閉包設(shè)F是FD集，被F邏輯蘊(yùn)涵全部FD集合，稱(chēng)為FD集F閉包，記為F+，即F+=｛X→Y｜記為F?X→Y｝屬性集閉包設(shè)R(U,F)，XU，則屬性集X相對(duì)于F閉包： X

=｛屬性A｜F+

?X→A｝，是一個(gè)使用規(guī)則從F推出，全部形如滿(mǎn)足X→A屬性A集合+F關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第15頁(yè)16FD和關(guān)鍵碼聯(lián)絡(luò)屬性集閉包算法，R（U，F(xiàn)），XU，求X+F關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第16頁(yè)17FD和關(guān)鍵碼聯(lián)絡(luò)示例：R(A,B,C,D,E),F={AB→C,B→D,C→E,EC→B,AC→B

} 求(AB)1）X(0)=X=AB;搜索F,得到AB→C,B→D； X(1)=AB∪C∪D=ABCD2）X(1)X(0);搜索F,得到C→E,AC→B； X(2)=ABCD∪E∪B=ABCDE3）X(2)X(1);搜索F,得到EC→B； X(3)=ABCDE∪B=ABCDE4）X(3)=X(2);結(jié)束，(AB)=ABCDE+F+F關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第17頁(yè)18FD和關(guān)鍵碼聯(lián)絡(luò)應(yīng)用AB→E能否從F中推出？ ∵(AB)=ABCDE，∴YESR(A,B,C,D,E)，(AB)是候選鍵嗎？ ∵(AB)=ABCDE，∴YESR（U,F），求候選鍵方法：若屬性A僅在FD右部，則它一定不包含在任何候選鍵中若屬性A僅在FD左部，則它一定包含在某個(gè)候選鍵中若屬性A既在FD右部又在FD左部，則它可能包含在某個(gè)候選鍵中在上述基礎(chǔ)上求屬性閉包+F+F關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第18頁(yè)19FD和關(guān)鍵碼聯(lián)絡(luò)應(yīng)用R（C,T,H,R,S,G） F={C→T,HR→C,HT→R,CS→G,HS→R} 求其候選鍵求解<HS｜H｜S>+{C｜T｜R}∵(HS)=CTHRSG，∴HS是候選鍵H，S不是候選鍵HSC，HSR，HST，HSCT，HSCR，HSTR，HSCTR不是候選鍵+F關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第19頁(yè)20關(guān)系模式范式引子1）規(guī)范化←使關(guān)系模式滿(mǎn)足某種條件處理過(guò)程2）范式NF（NormalForm）←關(guān)系模式滿(mǎn)足條件3）有6級(jí)范式，級(jí)別越高，條件越嚴(yán)格1NF2NF3NF√→BCNF√4NF5NF在模式設(shè)計(jì)中，處理數(shù)據(jù)之間函數(shù)依賴(lài)問(wèn)題多值依賴(lài)連接依賴(lài)，理論研究關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第20頁(yè)21關(guān)系模式范式第一范式（1NF）定義假如關(guān)系模式R每個(gè)關(guān)系r屬性值都是不可分原子值，則稱(chēng)R是第一范式（firstnormalform，簡(jiǎn)記為1NF）模式備注滿(mǎn)足1NF關(guān)系稱(chēng)為規(guī)范化關(guān)系，不然稱(chēng)為非規(guī)范化關(guān)系關(guān)系數(shù)據(jù)庫(kù)研究關(guān)系都是規(guī)范化關(guān)系1NF是關(guān)系模式應(yīng)具備最起碼條件若關(guān)系模式有多值屬性，須轉(zhuǎn)化為多個(gè)單值屬性或弱實(shí)體關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第21頁(yè)22關(guān)系模式范式第一范式（1NF）示例泛關(guān)系模式R（SNO,SNAME,AGE,SEX,NativePlace,CNO,CNAME,Credit, CreditHours,CPNO,TNO,TNAME,TITLE,SEX,DNO,DNAME,Grade）問(wèn)題分析數(shù)據(jù)冗余、更新異常？一事一地標(biāo)準(zhǔn)？(SNO,CNO)是候選鍵，(SNO,CNO)→U(SNO,CNO)→Grade；(SNO,CNO)→{U–Grade}關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第22頁(yè)23關(guān)系模式范式第一范式（1NF）示例泛關(guān)系模式R（SNO,SNAME,AGE,SEX,NativePlace,CNO,CNAME,Credit, CreditHours,CPNO,TNO,TNAME,TITLE,SEX,DNO,DNAME,Grade）問(wèn)題簡(jiǎn)化：S（SNO,SNAME,AGE,SEX,NativePlace）C（CNO,CNAME,Credit,CreditHours,CPNO）T（TNO,TNAME,TITLE,SEX）D（DNO,DNAME）SCTD（SNO,CNO,TNO,DNO,Grade）//問(wèn)題依舊關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第23頁(yè)24關(guān)系模式范式第一范式（1NF）示例泛關(guān)系模式R（SNO,SNAME,AGE,SEX,NativePlace,CNO,CNAME,Credit, CreditHours,CPNO,TNO,TNAME,TITLE,SEX,DNO,DNAME,Grade）問(wèn)題簡(jiǎn)化：SCTD（SNO,CNO,TNO,DNO,Grade）//問(wèn)題依舊(SNO,CNO)是候選鍵，(SNO,CNO)→{TNO,DNO,Grade}(SNO,CNO)→Grade；語(yǔ)義上是完整、正確(SNO,CNO)→{TNO,DNO}CNO→{TNO,DNO}是問(wèn)題所在非主屬性對(duì)候選鍵局部函數(shù)依賴(lài)關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第24頁(yè)25關(guān)系模式范式第二范式（2NF）定義對(duì)于FDW→A，若存在X?W，有X→A成立則稱(chēng)W→A是局部依賴(lài)（A局部依賴(lài)于W）不然稱(chēng)W→A是完全依賴(lài)完全依賴(lài)也稱(chēng)為“左部不可約依賴(lài)”定義：主屬性與非主屬性若A是關(guān)系模式R候選鍵中屬性則稱(chēng)A是R主屬性不然稱(chēng)A是R非主屬性關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第25頁(yè)26關(guān)系模式范式第二范式（2NF）定義若關(guān)系模式R是1NF，且每個(gè)非主屬性都完全函數(shù)依賴(lài)于候選鍵，那么稱(chēng)R是第二范式（2NF）模式假如數(shù)據(jù)庫(kù)模式中每個(gè)關(guān)系模式都是2NF，則稱(chēng)數(shù)據(jù)庫(kù)模式為2NF數(shù)據(jù)庫(kù)模式了解滿(mǎn)足1NF關(guān)系模式，消除了“非主屬性對(duì)候選鍵局部依賴(lài)”，則會(huì)滿(mǎn)足2NF消除方法：關(guān)系模式分解關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第26頁(yè)27關(guān)系模式范式第二范式（2NF）分解成2NF模式集算法設(shè)關(guān)系模式R(U)，主鍵是W，X?W；Z是非主屬性集若存在FDX→Z，則W→Z是一個(gè)局部依賴(lài)；此時(shí)應(yīng)把R分解成兩個(gè)模式R1（XZ），主鍵是XR2（Y）其中Y=U–Z主鍵是W，外鍵是X（參考R1）若R1和R2仍不是2NF，則重復(fù)上述過(guò)程，直到分解后每一個(gè)關(guān)系模式都是2NF為止關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第27頁(yè)28關(guān)系模式范式第二范式（2NF）示例SCTD（SNO,CNO,TNO,DNO,Grade）(SNO,CNO)是候選鍵(SNO,CNO)→{TNO,DNO}，∵CNO→{TNO,DNO}∴是非主屬性對(duì)候選鍵局部依賴(lài)分解關(guān)系模式，得到SC（SNO,CNO,Grade），滿(mǎn)足2NFCTD（CNO,TNO,DNO），滿(mǎn)足2NF 但仍有問(wèn)題：CNO→DNO CNO→DNO是非主屬性對(duì)候選鍵傳遞函數(shù)依賴(lài)關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第28頁(yè)29關(guān)系模式范式第二范式（2NF）舉一反三1）關(guān)系模式滿(mǎn)足1NF，但不一定滿(mǎn)足2NF2）關(guān)系模式滿(mǎn)足2NF，則一定滿(mǎn)足1NF3）關(guān)系模式不滿(mǎn)足2NF，則一定存在“非主屬性對(duì)候選鍵局部依賴(lài)”4）關(guān)系模式滿(mǎn)足2NF，屬性一定是原子，不可再分關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第29頁(yè)30關(guān)系模式范式第三范式（3NF）定義假如X→Y，Y→A， 且Y→X和A∈Y， 那么稱(chēng)X→A是傳遞依賴(lài)（A傳遞依賴(lài)于X）定義假如關(guān)系模式R是1NF，且每個(gè)非主屬性都不傳遞依賴(lài)于R候選鍵，那么稱(chēng)R是第三范式（3NF）模式假如數(shù)據(jù)庫(kù)模式中每個(gè)關(guān)系模式都是3NF，則稱(chēng)其為3NF數(shù)據(jù)庫(kù)模式/

/

關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第30頁(yè)31關(guān)系模式范式第三范式（3NF）定義設(shè)F是關(guān)系模式RFD集，若對(duì)F中每個(gè)非平凡FDX→Y，都有X是R超鍵或者，Y每個(gè)屬性都是主屬性則稱(chēng)R是3NF模式了解若非平凡FDX→Y中Y是主屬性，則X→Y不違反3NF條件若Y是非主屬性，且X不包含超鍵，則必存在著關(guān)鍵碼W使W→X，則W→Y是一個(gè)傳遞依賴(lài)，即R不是3NF模式滿(mǎn)足2NF關(guān)系模式，消除了“非主屬性對(duì)候選鍵傳遞依賴(lài)”，則會(huì)滿(mǎn)足3NF；消除方法：關(guān)系模式分解關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第31頁(yè)32關(guān)系模式范式第三范式（3NF）分解成3NF模式集算法設(shè)關(guān)系模式R(U)，主鍵是W；Z是非主屬性，ZX，X不是候選鍵若存在FDX→Z，則W→Z是一個(gè)傳遞依賴(lài)；此時(shí)應(yīng)把R分解成兩個(gè)模式R1（XZ），主鍵是XR2（Y）其中Y=U–Z主鍵是W，外鍵是X（參考R1）若R1和R2仍不是3NF，重復(fù)分解過(guò)程，直到每一個(gè)關(guān)系模式都是3NF為止/

關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第32頁(yè)33關(guān)系模式范式第三范式（3NF）示例SCTD（SNO,CNO,TNO,DNO,Grade）分解關(guān)系模式，得到SC（SNO,CNO,Grade）CTD（CNO,TNO,DNO）CTD（CNO,TNO,DNO）CNO是候選鍵，CNO→DNO非主屬性傳遞依賴(lài)于候選鍵分解關(guān)系關(guān)系模式，得到CT（CNO,TNO）TD（TNO,DNO）關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第33頁(yè)34關(guān)系模式范式第三范式（3NF）定理假如R是3NF模式，那么R也是2NF模式了解滿(mǎn)足3NF，一定滿(mǎn)足2NF，也一定滿(mǎn)足1NF1NF→2NF：消除了“非主屬性對(duì)候選鍵局部依賴(lài)”2NF→3NF：消除了“非主屬性對(duì)候選鍵傳遞依賴(lài)”若關(guān)系模式R中沒(méi)有非主屬性，則滿(mǎn)足3NF局部依賴(lài)和傳遞依賴(lài)是模式產(chǎn)生冗余和異常主要原因因?yàn)?NF模式中不存在非主屬性對(duì)候選鍵局部依賴(lài)和傳遞依賴(lài)，所以消除了很大一部分存放異常，含有很好性能關(guān)系數(shù)據(jù)庫(kù)基本原理規(guī)范化理論第34頁(yè)35關(guān)系模式范式BC范式（BCNF）問(wèn)題滿(mǎn)足3NF數(shù)據(jù)庫(kù)模式，消除了非主屬性對(duì)候選鍵局部依賴(lài)和傳遞依賴(lài)但，并未排除主屬性對(duì)候選 鍵依賴(lài)問(wèn)題定義假如關(guān)系模式R是1NF， 且每