數(shù)據(jù)庫(kù)原理第8章 數(shù)據(jù)庫(kù)設(shè)計(jì)理論 V2.1

1、DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué)數(shù)據(jù)庫(kù)原理及應(yīng)用數(shù)據(jù)庫(kù)原理及應(yīng)用第第8章章 數(shù)據(jù)庫(kù)設(shè)計(jì)理論數(shù)據(jù)庫(kù)設(shè)計(jì)理論電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院鄭莉華鄭莉華 cd_cd_20222022年年5 5月月3 3日星期二日星期二DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué)Click to add TitleClick to add Title1 1 關(guān)系模式設(shè)計(jì)問題關(guān)系模式設(shè)計(jì)問題1 1Click to add TitleClick to add Title2 2 函數(shù)依賴函數(shù)依賴2 2Click to add TitleClick to add T

2、itle2 2 模式分解模式分解3 3Click to add TitleClick to add Title1 1 規(guī)范化規(guī)范化4 4Click to add TitleClick to add Title1 1 * *多值依賴多值依賴5 5Click to add TitleClick to add Title2 2 * *連接依賴連接依賴6 6DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n如何構(gòu)造一個(gè)合適的數(shù)據(jù)模式？如何構(gòu)造一個(gè)合適的數(shù)據(jù)模式？u應(yīng)該構(gòu)造幾個(gè)關(guān)系模式？應(yīng)該構(gòu)造幾個(gè)關(guān)系模式？u每個(gè)關(guān)系應(yīng)該由哪些屬性組成？每個(gè)關(guān)系應(yīng)該由哪些屬性組成？n思考：教務(wù)管理數(shù)據(jù)庫(kù)模

3、式？思考：教務(wù)管理數(shù)據(jù)庫(kù)模式？n數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的工具數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的工具u關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n關(guān)系模式的五元組表示：關(guān)系模式的五元組表示： R(U, D, DOM, F)R(U, D, DOM, F)uR R：關(guān)系名：關(guān)系名uU U：組成該關(guān)系的屬性名集合：組成該關(guān)系的屬性名集合uD D：屬性組：屬性組U U中屬性所來(lái)自的域中屬性所來(lái)自的域uDOMDOM：屬性向域的映象集合：屬性向域的映象集合uF F：屬性間數(shù)據(jù)的依賴關(guān)系集合：屬性間數(shù)據(jù)的依賴關(guān)系集合n關(guān)系模式的簡(jiǎn)化三元組表示：關(guān)系模式的簡(jiǎn)化三元組表示：

4、R R（U, FU, F）n什么是數(shù)據(jù)依賴？什么是數(shù)據(jù)依賴？u是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象u是數(shù)據(jù)內(nèi)在的性質(zhì)是數(shù)據(jù)內(nèi)在的性質(zhì)u是語(yǔ)義的體現(xiàn)是語(yǔ)義的體現(xiàn)DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n關(guān)系模式實(shí)例關(guān)系模式實(shí)例u設(shè)有一個(gè)醫(yī)生與患者之間的就診關(guān)系模式設(shè)有一個(gè)醫(yī)生與患者之間的就診關(guān)系模式R R（DnameDname，DlevelDlevel，DsalDsal，PnamePname，F(xiàn)sumFsum），其屬性分別表示醫(yī)生姓名、醫(yī)生職稱級(jí)），其屬性分別表示醫(yī)生姓名、醫(yī)生職稱級(jí)別、醫(yī)生工資、患者姓名、診治費(fèi)用。別、醫(yī)生工資、患者姓名、診治費(fèi)用。

5、nR R上的語(yǔ)義：上的語(yǔ)義：u假設(shè)醫(yī)生和患者的姓名分別都是唯一的。假設(shè)醫(yī)生和患者的姓名分別都是唯一的。u醫(yī)生與患者之間是多對(duì)多的關(guān)系，即醫(yī)生可以為不同的患者看病醫(yī)生與患者之間是多對(duì)多的關(guān)系，即醫(yī)生可以為不同的患者看病，同時(shí)患者可以選擇不同的醫(yī)生。假設(shè)同一名患者不看相同的醫(yī)，同時(shí)患者可以選擇不同的醫(yī)生。假設(shè)同一名患者不看相同的醫(yī)生，即可以選擇生，即可以選擇DnameDname和和PnamePname作為就診關(guān)系模式作為就診關(guān)系模式R R的主鍵。的主鍵。u一位患者每次就診都有一個(gè)花銷總金額。一位患者每次就診都有一個(gè)花銷總金額。u每位醫(yī)生具有相應(yīng)的職稱級(jí)別。每位醫(yī)生具有相應(yīng)的職稱級(jí)別。u職稱級(jí)別決定

6、了醫(yī)生的工資金額。職稱級(jí)別決定了醫(yī)生的工資金額。DnameDlevelDsalaryPnameFsum羅曉羅曉主任醫(yī)師主任醫(yī)師3200張珍張珍30.00楊勛楊勛副主任醫(yī)師副主任醫(yī)師2800張珍張珍50.00楊勛楊勛副主任醫(yī)師副主任醫(yī)師2800劉景劉景55.00楊勛楊勛副主任醫(yī)師副主任醫(yī)師2800張柳張柳58.00鄧英超鄧英超主治醫(yī)師主治醫(yī)師2400李秀李秀75.00羅曉羅曉主任醫(yī)師主任醫(yī)師3200傅偉相傅偉相35.00DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n可以確定以下函數(shù)依賴：可以確定以下函數(shù)依賴：F = F = Dname,PnameFsumDname,PnameF

7、sum， DnameDlevelDnameDlevel， DlevelDsalDlevelDsal DnamePnameDlevelDsalFsumDATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n就診模式就診模式R R存在的問題（雖然只有存在的問題（雖然只有5 5個(gè)屬性）：個(gè)屬性）：u數(shù)據(jù)冗余：浪費(fèi)存儲(chǔ)空間，引起異常。數(shù)據(jù)冗余：浪費(fèi)存儲(chǔ)空間，引起異常。u操作異常：操作異常：l 更新異常（更新異常（Update Anomalies）。）。l 刪除異常（刪除異常（Delete Anomalies）。）。l 插入異常（插入異常（Insert Anomalies）。）。n因此，就診關(guān)系

8、模式因此，就診關(guān)系模式R R不是一個(gè)好的關(guān)系模式。不是一個(gè)好的關(guān)系模式。DnameDlevelDsalaryPnameFsum羅曉羅曉主任醫(yī)師主任醫(yī)師3200張珍張珍30.00楊勛楊勛副主任醫(yī)師副主任醫(yī)師2800張珍張珍50.00楊勛楊勛副主任醫(yī)師副主任醫(yī)師2800劉景劉景55.00楊勛楊勛副主任醫(yī)師副主任醫(yī)師2800張柳張柳58.00鄧英超鄧英超主治醫(yī)師主治醫(yī)師2400李秀李秀75.00羅曉羅曉主任醫(yī)師主任醫(yī)師3200傅偉相傅偉相35.00DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n消除冗余和異?，F(xiàn)象（模式分解）消除冗余和異常現(xiàn)象（模式分解）uR1R1（DnameDnam

9、e，DlevelDlevel）uR2R2（DlevelDlevel，DsalDsal）uR3R3（DnameDname，PnamePname，F(xiàn)sumFsum） DnameDlevelDsalaryPnameFsum羅曉羅曉主任醫(yī)師主任醫(yī)師3200張珍張珍30.00楊勛楊勛副主任醫(yī)師副主任醫(yī)師2800張珍張珍50.00楊勛楊勛副主任醫(yī)師副主任醫(yī)師2800劉景劉景55.00楊勛楊勛副主任醫(yī)師副主任醫(yī)師2800張柳張柳58.00鄧英超鄧英超主治醫(yī)師主治醫(yī)師2400李秀李秀75.00羅曉羅曉主任醫(yī)師主任醫(yī)師3200傅偉相傅偉相35.00DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué)Cl

10、ick to add TitleClick to add Title1 1 關(guān)系模式設(shè)計(jì)問題關(guān)系模式設(shè)計(jì)問題1 1Click to add TitleClick to add Title2 2 函數(shù)依賴函數(shù)依賴2 2Click to add TitleClick to add Title2 2 模式分解模式分解3 3Click to add TitleClick to add Title1 1 規(guī)范化規(guī)范化4 4Click to add TitleClick to add Title1 1 * *多值依賴多值依賴5 5Click to add TitleClick to add Title2

11、2 * *連接依賴連接依賴6 6DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n什么是數(shù)據(jù)依賴？什么是數(shù)據(jù)依賴？u是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象u是數(shù)據(jù)內(nèi)在的性質(zhì)是數(shù)據(jù)內(nèi)在的性質(zhì)u是語(yǔ)義的體現(xiàn)是語(yǔ)義的體現(xiàn)n數(shù)據(jù)依賴的類型數(shù)據(jù)依賴的類型u函數(shù)依賴（函數(shù)依賴（Functional DependencyFunctional Dependency，簡(jiǎn)記為，簡(jiǎn)記為FDFD）u多值依賴（多值依賴（MultivaluedMultivalued Dependency Dependency，簡(jiǎn)記為，簡(jiǎn)記為MVDMVD）DATABASEUESTC學(xué)以致用學(xué)以致用 用以

12、促學(xué)用以促學(xué) n函數(shù)依賴是指一個(gè)關(guān)系表中屬性（列）之間的聯(lián)系。函數(shù)依賴是指一個(gè)關(guān)系表中屬性（列）之間的聯(lián)系。n函數(shù)依賴關(guān)注一個(gè)屬性或?qū)傩约c另外一個(gè)屬性或?qū)傩院瘮?shù)依賴關(guān)注一個(gè)屬性或?qū)傩约c另外一個(gè)屬性或?qū)傩约g的依賴，亦即兩個(gè)屬性或?qū)傩约g的約束。集之間的依賴，亦即兩個(gè)屬性或?qū)傩约g的約束。n函數(shù)依賴是關(guān)系中屬性之間在語(yǔ)義上的關(guān)聯(lián)特性。函數(shù)依賴是關(guān)系中屬性之間在語(yǔ)義上的關(guān)聯(lián)特性。n數(shù)據(jù)庫(kù)設(shè)計(jì)者根據(jù)對(duì)關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)者根據(jù)對(duì)關(guān)系R R中的屬性的語(yǔ)義理解確定函中的屬性的語(yǔ)義理解確定函數(shù)依賴，確定約束數(shù)依賴，確定約束R R的所有元組的所有元組r r的函數(shù)依賴集，并獲知的函數(shù)依賴集，并獲知屬性間的

13、語(yǔ)義關(guān)聯(lián)。屬性間的語(yǔ)義關(guān)聯(lián)。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n符號(hào)說(shuō)明：符號(hào)說(shuō)明：uR R表示一個(gè)關(guān)系的模式；表示一個(gè)關(guān)系的模式；uU UA1A1，A2A2，AnAn是是R R的所有屬性的集合；的所有屬性的集合；uF F是是R R中函數(shù)依賴的集合；中函數(shù)依賴的集合；ur r是是R R所取的值；所取的值；utXtX 表示元組表示元組t t在屬性在屬性X X上的取值。例如上的取值。例如 tDnametDname = = 楊勛楊勛 n函數(shù)依賴定義函數(shù)依賴定義n函數(shù)依賴圖函數(shù)依賴圖u左部稱為決定因子左部稱為決定因子u右部稱為依賴因子。右部稱為依賴因子。XYY函數(shù)依賴于函數(shù)

14、依賴于X函數(shù)依賴圖函數(shù)依賴圖DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n定義定義n平凡函數(shù)依賴必然成立，它不反映新的語(yǔ)義。平凡函數(shù)依賴必然成立，它不反映新的語(yǔ)義。例如：例如： Dname,PnameDname,Pname PnamePname 。n平常所指的函數(shù)依賴一般都指非平凡函數(shù)依賴。平常所指的函數(shù)依賴一般都指非平凡函數(shù)依賴。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n定義定義n完全函數(shù)依賴用來(lái)表明函數(shù)依賴的決定因子中的最小屬完全函數(shù)依賴用來(lái)表明函數(shù)依賴的決定因子中的最小屬性集。性集。n屬性集屬性集Y Y完全函數(shù)依賴于屬性集完全函數(shù)依賴于屬性集X X

15、，如果滿足下列條件：，如果滿足下列條件：uY Y函數(shù)依賴于函數(shù)依賴于X X。uY Y不函數(shù)依賴于不函數(shù)依賴于X X的任何真子集。的任何真子集。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n舉例舉例DnamePnameDlevelDsalFsumDATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n定義定義n直接依賴直接依賴DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n舉例：舉例： 在就診關(guān)系在就診關(guān)系R R中，存在函數(shù)依賴中，存在函數(shù)依賴DnameDnameDlevelDlevel，DlevelDlevelDsalDsal，所以，所以DnameDn

16、ame DsalDsal。DnamePnameDlevelDsalFsumDATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n函數(shù)依賴中需要解決的問題：從一些已知的函數(shù)依賴函數(shù)依賴中需要解決的問題：從一些已知的函數(shù)依賴去判斷另外一些函數(shù)依賴是否成立。去判斷另外一些函數(shù)依賴是否成立。n例如，如果例如，如果A AB B和和B BC C在某個(gè)關(guān)系中成立，記在某個(gè)關(guān)系中成立，記F= F= A AB B，B BCC，那么，那么A AC C在該關(guān)系中是否成立的問題稱在該關(guān)系中是否成立的問題稱為邏輯蘊(yùn)涵問題，若為邏輯蘊(yùn)涵問題，若A AC C成立，則說(shuō)成立，則說(shuō)F F邏輯蘊(yùn)涵邏輯蘊(yùn)涵A AC C，

17、記作記作F F A AC C。n定義定義DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n一個(gè)關(guān)系模式可能有多個(gè)函數(shù)依賴形成函數(shù)依賴集，一個(gè)關(guān)系模式可能有多個(gè)函數(shù)依賴形成函數(shù)依賴集，現(xiàn)在有一個(gè)新的函數(shù)依賴不在函數(shù)依賴集里，但能從現(xiàn)在有一個(gè)新的函數(shù)依賴不在函數(shù)依賴集里，但能從集合里根據(jù)一定的集合里根據(jù)一定的規(guī)則規(guī)則推導(dǎo)出來(lái)，就說(shuō)那個(gè)集合邏輯推導(dǎo)出來(lái)，就說(shuō)那個(gè)集合邏輯蘊(yùn)涵這個(gè)新的函數(shù)依賴。蘊(yùn)涵這個(gè)新的函數(shù)依賴。n舉例舉例n如果一個(gè)函數(shù)依賴能夠由集合中的其他函數(shù)推出，則如果一個(gè)函數(shù)依賴能夠由集合中的其他函數(shù)推出，則該函數(shù)依賴是多余的。該函數(shù)依賴是多余的。DATABASEUESTC學(xué)以致

18、用學(xué)以致用 用以促學(xué)用以促學(xué) n閉包閉包n函數(shù)依賴集的閉包（也成為完備集）定義了由給定函函數(shù)依賴集的閉包（也成為完備集）定義了由給定函數(shù)依賴集所能推導(dǎo)出的所有函數(shù)依賴。數(shù)依賴集所能推導(dǎo)出的所有函數(shù)依賴。n通過通過F F得到得到F F的算法可以由的算法可以由ArmstrongArmstrong公理推導(dǎo)出來(lái)。公理推導(dǎo)出來(lái)。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n無(wú)冗余的函數(shù)依賴集和函數(shù)依賴的完備集（閉包）是無(wú)冗余的函數(shù)依賴集和函數(shù)依賴的完備集（閉包）是好的關(guān)系設(shè)計(jì)。好的關(guān)系設(shè)計(jì)。n根據(jù)已知函數(shù)依賴集，推導(dǎo)其它函數(shù)依賴時(shí)所依據(jù)的根據(jù)已知函數(shù)依賴集，推導(dǎo)其它函數(shù)依賴時(shí)所依據(jù)的規(guī)

19、則稱為推理規(guī)則。規(guī)則稱為推理規(guī)則。n函數(shù)依賴的推理規(guī)則最早出現(xiàn)在函數(shù)依賴的推理規(guī)則最早出現(xiàn)在ArmstrongArmstrong的論文里。的論文里。這些規(guī)則常被稱為這些規(guī)則常被稱為“ArmstrongArmstrong公理公理”。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n設(shè)設(shè)U U是關(guān)系模式是關(guān)系模式R R的屬性集，的屬性集，F(xiàn) F是是R R上成立的只涉及上成立的只涉及U U中屬中屬性的函數(shù)依賴集。性的函數(shù)依賴集。FDFD推理規(guī)則推理規(guī)則n（1 1）自反性（）自反性（ReflexivityReflexivity）n（2 2）增廣性（）增廣性（AugmentationAug

20、mentation）n（3 3）傳遞性（）傳遞性（TransitivityTransitivity）DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) nArmstrongArmstrong公理是公理是正確的（正確的（SoundSound），即如果，即如果X XY Y是從是從F F用推理規(guī)則導(dǎo)出，那么用推理規(guī)則導(dǎo)出，那么X XY Y在在F F中。中。nArmstrongArmstrong公理（公理（FDFD推理規(guī)則推理規(guī)則A1A1，A2A2，A3A3）是）是完備的完備的（CompleteComplete）。n推理規(guī)則的正確

21、性是指推理規(guī)則的正確性是指“從從FDFD集集F F使用推理規(guī)則推出的使用推理規(guī)則推出的FDFD必定在必定在F F+ +中中”，而推理規(guī)則的完備性是指，而推理規(guī)則的完備性是指“F F+ +中的中的FDFD都能從都能從F F集使用推理規(guī)則推出集使用推理規(guī)則推出”。n即正確性保證了推出的所有即正確性保證了推出的所有FDFD都是正確的，完備性保都是正確的，完備性保證了可以推出所有被蘊(yùn)涵的證了可以推出所有被蘊(yùn)涵的FDFD。這些就保證了推導(dǎo)的。這些就保證了推導(dǎo)的有效性和可靠性。有效性和可靠性。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n候選碼與主碼：用函數(shù)依賴定義候選碼與主碼：用函數(shù)依

22、賴定義n包含在任何候選碼中的屬性稱為主屬性（包含在任何候選碼中的屬性稱為主屬性（Prime Prime AttributeAttribute）。不包含在任何候選碼中的屬性稱為非主）。不包含在任何候選碼中的屬性稱為非主屬性（屬性（Non-Key AttributeNon-Key Attribute）。）。n最簡(jiǎn)單的情況，單個(gè)屬性是碼。最極端的情況，整個(gè)最簡(jiǎn)單的情況，單個(gè)屬性是碼。最極端的情況，整個(gè)屬性組是碼，稱為全碼（屬性組是碼，稱為全碼（All-keyAll-key）。）。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n候選碼與主碼的舉例候選碼與主碼的舉例u在關(guān)系模式在關(guān)系模式

23、R R1 1（DnoDno，DlevelDlevel，DsalDsal）中）中DnoDno是碼是碼u在關(guān)系模式在關(guān)系模式R R2 2（DnoDno，PnoPno，F(xiàn)sumFsum）中的屬性組合（）中的屬性組合（DnoDno，PnoPno）是碼。）是碼。u關(guān)系模式關(guān)系模式R R3 3（DnoDno，PnoPno，MnoMno）表示醫(yī)生給患者開具的藥品，假設(shè)一）表示醫(yī)生給患者開具的藥品，假設(shè)一個(gè)醫(yī)生可以給多個(gè)患者看病，一位患者可以選擇不同的醫(yī)生就診，不個(gè)醫(yī)生可以給多個(gè)患者看病，一位患者可以選擇不同的醫(yī)生就診，不同的醫(yī)生可以給患者開具不同的藥品，因此（同的醫(yī)生可以給患者開具不同的藥品，因此（DnoD

24、no，PnoPno，MnoMno）為）為R R3 3的碼，即全碼。的碼，即全碼。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n外碼：用函數(shù)依賴定義外碼：用函數(shù)依賴定義n舉例：舉例：u在關(guān)系模式在關(guān)系模式R R2 2（DnoDno，PnoPno，F(xiàn)sumFsum）中，）中，DnoDno不是碼，不是碼，u但但DnoDno是關(guān)系模式是關(guān)系模式R R1 1（DnoDno，DlevelDlevel，DsalDsal）的碼，）的碼，u則則DnoDno是關(guān)系模式是關(guān)系模式R R2 2的外碼。的外碼。n主碼與外碼提供了一個(gè)表示關(guān)系之間聯(lián)系的手段。如主碼與外碼提供了一個(gè)表示關(guān)系之間聯(lián)系的手段。

25、如上述關(guān)系模式上述關(guān)系模式R R1 1和和R R2 2的聯(lián)系就是通過的聯(lián)系就是通過DnoDno來(lái)體現(xiàn)的。來(lái)體現(xiàn)的。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n判斷能否從已知的判斷能否從已知的FDFD集推導(dǎo)出集推導(dǎo)出FD FD X XY Y，那么可先求出，那么可先求出F F的閉包的閉包F F+ +，然后再看，然后再看X XY Y是否在中是否在中F F+ +。n但是從但是從F F求求F F+ +是一個(gè)是一個(gè)NPNP完全問題（指數(shù)級(jí)的時(shí)間復(fù)雜度完全問題（指數(shù)級(jí)的時(shí)間復(fù)雜度）。下面引入屬性集閉包概念，將使該問題化為多項(xiàng)）

26、。下面引入屬性集閉包概念，將使該問題化為多項(xiàng)式級(jí)的時(shí)間復(fù)雜度問題。式級(jí)的時(shí)間復(fù)雜度問題。n屬性集閉包的定義屬性集閉包的定義n定理定理DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n從屬性集從屬性集X X求求X X并不太難，花費(fèi)的時(shí)間與并不太難，花費(fèi)的時(shí)間與F F中的中的FDFD數(shù)目數(shù)目成正比，是一個(gè)多項(xiàng)式級(jí)時(shí)間復(fù)雜度的問題。成正比，是一個(gè)多項(xiàng)式級(jí)時(shí)間復(fù)雜度的問題。n求屬性集閉包的算法求屬性集閉包的算法n舉例舉例DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n函數(shù)依賴集等價(jià)：函數(shù)依賴集等價(jià)： F F = =G Gn設(shè)設(shè)F F是屬性集是屬性集U U上的函數(shù)依賴集，如

27、果上的函數(shù)依賴集，如果F Fminmin是是F F的一個(gè)最小的一個(gè)最小依賴集，那么依賴集，那么F Fminmin應(yīng)滿足下列應(yīng)滿足下列4 4個(gè)條件：個(gè)條件：DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n求最小函數(shù)依賴集的算法求最小函數(shù)依賴集的算法n舉例舉例n每個(gè)每個(gè)FDFD至少存在一個(gè)至少存在一個(gè)F Fminmin ，但不一定唯一。，但不一定唯一。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué)Click to add TitleClick to add Title1 1 關(guān)系模式設(shè)計(jì)問題關(guān)系模式設(shè)計(jì)問題1 1Click to add TitleClick to a

28、dd Title2 2 函數(shù)依賴函數(shù)依賴2 2Click to add TitleClick to add Title2 2 模式分解模式分解3 3Click to add TitleClick to add Title1 1 規(guī)范化規(guī)范化4 4Click to add TitleClick to add Title1 1 * *多值依賴多值依賴5 5Click to add TitleClick to add Title2 2 * *連接依賴連接依賴6 6DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n由函數(shù)依賴可以引起的更新異常問題，同樣，多值依由函數(shù)依賴可以引起的更新異常

29、問題，同樣，多值依賴和連接依賴也會(huì)引起類似的問題。解決這些問題的賴和連接依賴也會(huì)引起類似的問題。解決這些問題的途徑就是按照途徑就是按照“一事一地一事一地”的原則，對(duì)關(guān)系模式進(jìn)行的原則，對(duì)關(guān)系模式進(jìn)行分解，使之表達(dá)的語(yǔ)義概念單純化。分解，使之表達(dá)的語(yǔ)義概念單純化。n關(guān)系模式關(guān)系模式R R的分解就是用兩個(gè)或兩個(gè)以上關(guān)系來(lái)替換的分解就是用兩個(gè)或兩個(gè)以上關(guān)系來(lái)替換R R，分解后的關(guān)系模式的屬性集都是，分解后的關(guān)系模式的屬性集都是R R中屬性的子集，其中屬性的子集，其并集與并集與R R的屬性集相同。的屬性集相同。n模式分解幫助消除不良設(shè)計(jì)中的一些問題，如冗余、模式分解幫助消除不良設(shè)計(jì)中的一些問題，如冗余

30、、不一致或異常。不一致或異常。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n模式分解的定義模式分解的定義n模式分解的問題模式分解的問題DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n一個(gè)關(guān)系表被分解成兩個(gè)或兩個(gè)以上的小表，通過連一個(gè)關(guān)系表被分解成兩個(gè)或兩個(gè)以上的小表，通過連接被分解后的小表可以獲得原始表的內(nèi)容，則稱為無(wú)接被分解后的小表可以獲得原始表的內(nèi)容，則稱為無(wú)損連接分解。損連接分解。n例如：將例如：將R R（X X，Y Y，Z Z）分解成）分解成R R1 1（X X，Y Y）和）和R R2 2（X X，Z Z），如果，如果X X是是R R1 1和和R R2

31、 2的共同屬性或?qū)傩约?，且存在函?shù)依的共同屬性或?qū)傩约掖嬖诤瘮?shù)依賴集賴集F F=X XY Y，X XZ Z ，則該分解是無(wú)損的。，則該分解是無(wú)損的。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) u無(wú)損中的損是指信息丟失。如果一個(gè)分解不是無(wú)損分解，無(wú)損中的損是指信息丟失。如果一個(gè)分解不是無(wú)損分解， 則所得結(jié)則所得結(jié)果的元組數(shù)總比原來(lái)的多（增加了噪聲，但把原來(lái)的信息丟失了）。果的元組數(shù)總比原來(lái)的多（增加了噪聲，但把原來(lái)的信息丟失了）。所謂所謂“有損有損”就損在出現(xiàn)多余的元組上。就損在出現(xiàn)多余的元組上。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n無(wú)損分解測(cè)試算

32、法無(wú)損分解測(cè)試算法追逐法（追逐法（ChaseChase）DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) nChaseChase是一個(gè)普遍的算法，無(wú)論一個(gè)關(guān)系模式分解為多是一個(gè)普遍的算法，無(wú)論一個(gè)關(guān)系模式分解為多少個(gè)關(guān)系模式，都可以用此算法進(jìn)行檢驗(yàn)。少個(gè)關(guān)系模式，都可以用此算法進(jìn)行檢驗(yàn)。n如果一個(gè)關(guān)系模式一分為二，可以簡(jiǎn)化檢驗(yàn)。如果一個(gè)關(guān)系模式一分為二，可以簡(jiǎn)化檢驗(yàn)。n例如例如DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n所有的模式分解必須是無(wú)損的。所有的模式分解必須是無(wú)損的。n無(wú)損連接分解總是關(guān)于特定函數(shù)依賴集無(wú)損連接分解總是關(guān)于特定函數(shù)依賴集F F定義的。定義

33、的。n模式分解能消除數(shù)據(jù)冗余和操作異?，F(xiàn)象。模式分解能消除數(shù)據(jù)冗余和操作異?，F(xiàn)象。n但是分解以后，檢索操作需要做笛卡爾積或連接操作但是分解以后，檢索操作需要做笛卡爾積或連接操作，這將付出時(shí)間代價(jià)。，這將付出時(shí)間代價(jià)。n一般認(rèn)為，為了消除冗余和異?，F(xiàn)象，對(duì)模式進(jìn)行分一般認(rèn)為，為了消除冗余和異常現(xiàn)象，對(duì)模式進(jìn)行分解是值得的。解是值得的。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n模式分解的另一個(gè)特性是分解的過程中能否保持函數(shù)模式分解的另一個(gè)特性是分解的過程中能否保持函數(shù)依賴集，如果不能保持函數(shù)依賴，那么數(shù)據(jù)的語(yǔ)義就依賴集，如果不能保持函數(shù)依賴，那么數(shù)據(jù)的語(yǔ)義就會(huì)出現(xiàn)混亂。會(huì)出現(xiàn)

34、混亂。n模式分解要保持函數(shù)依賴，因?yàn)楹瘮?shù)依賴集模式分解要保持函數(shù)依賴，因?yàn)楹瘮?shù)依賴集F F中的每一中的每一個(gè)函數(shù)依賴都代表數(shù)據(jù)庫(kù)的一個(gè)約束。個(gè)函數(shù)依賴都代表數(shù)據(jù)庫(kù)的一個(gè)約束。n如果某個(gè)分解能保持函數(shù)依賴集，那么在數(shù)據(jù)輸入或如果某個(gè)分解能保持函數(shù)依賴集，那么在數(shù)據(jù)輸入或更新時(shí)，只要每個(gè)關(guān)系模式本身的函數(shù)依賴約束被滿更新時(shí)，只要每個(gè)關(guān)系模式本身的函數(shù)依賴約束被滿足，就可以確保整個(gè)數(shù)據(jù)庫(kù)中的語(yǔ)義完整性不被破壞足，就可以確保整個(gè)數(shù)據(jù)庫(kù)中的語(yǔ)義完整性不被破壞。顯然這是一種良好的特性。顯然這是一種良好的特性。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n定義定義n舉例：舉例：u設(shè)醫(yī)生關(guān)系

35、模式設(shè)醫(yī)生關(guān)系模式R R（DnoDno，DlevelDlevel，DsalDsal）。假設(shè)每個(gè)醫(yī)生只有一個(gè)職）。假設(shè)每個(gè)醫(yī)生只有一個(gè)職稱級(jí)別，每個(gè)職稱級(jí)別只有一個(gè)工資數(shù)目。那么稱級(jí)別，每個(gè)職稱級(jí)別只有一個(gè)工資數(shù)目。那么R R上函數(shù)依賴集上函數(shù)依賴集F F=DnoDnoDlevelDlevel，DlevelDlevelDsalDsal 。u如果將如果將R R分解成分解成=RR1 1(Dno,Dlevel)(Dno,Dlevel)，R R2 2(Dno,Dsal)(Dno,Dsal)，可以驗(yàn)證這個(gè)，可以驗(yàn)證這個(gè)分解是無(wú)損分解。分解是無(wú)損分解。uR R1 1上的函數(shù)依賴是上的函數(shù)依賴是F F1 1=

36、DnoDnoDlevelDlevel ，R R2 2上的函數(shù)依賴是上的函數(shù)依賴是F F2 2=DnoDnoDsalDsal 。但是從這兩個(gè)函數(shù)依賴推導(dǎo)不出在。但是從這兩個(gè)函數(shù)依賴推導(dǎo)不出在R R上成立的函數(shù)上成立的函數(shù)依賴依賴DnoDnoDsalDsal。因此分解。因此分解把函數(shù)依賴把函數(shù)依賴DnoDnoDsalDsal丟失了，即丟失了，即不保不保持持F F。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n關(guān)系模式分解的兩個(gè)特性實(shí)際上涉及兩個(gè)數(shù)據(jù)庫(kù)模式的等關(guān)系模式分解的兩個(gè)特性實(shí)際上涉及兩個(gè)數(shù)據(jù)庫(kù)模式的等價(jià)問題，這種等價(jià)包括價(jià)問題，這種等價(jià)包括數(shù)據(jù)等價(jià)數(shù)據(jù)等價(jià)和和依賴等價(jià)依賴等

37、價(jià)兩個(gè)方面。兩個(gè)方面。n數(shù)據(jù)等價(jià)是指兩個(gè)數(shù)據(jù)庫(kù)實(shí)例應(yīng)表示同樣的信息內(nèi)容，用數(shù)據(jù)等價(jià)是指兩個(gè)數(shù)據(jù)庫(kù)實(shí)例應(yīng)表示同樣的信息內(nèi)容，用“無(wú)損分解無(wú)損分解”衡量。如果是無(wú)損分解，那么對(duì)關(guān)系反復(fù)的衡量。如果是無(wú)損分解，那么對(duì)關(guān)系反復(fù)的投影和連接都不會(huì)丟失信息。投影和連接都不會(huì)丟失信息。n依賴等價(jià)是指兩個(gè)數(shù)據(jù)庫(kù)模式應(yīng)有相同的依賴集閉包。在依賴等價(jià)是指兩個(gè)數(shù)據(jù)庫(kù)模式應(yīng)有相同的依賴集閉包。在依賴集閉包相等情況下，數(shù)據(jù)的語(yǔ)義是不會(huì)出錯(cuò)的。依賴集閉包相等情況下，數(shù)據(jù)的語(yǔ)義是不會(huì)出錯(cuò)的。n違反數(shù)據(jù)等價(jià)或依賴等價(jià)的分解很難說(shuō)是一個(gè)很好的設(shè)計(jì)違反數(shù)據(jù)等價(jià)或依賴等價(jià)的分解很難說(shuō)是一個(gè)很好的設(shè)計(jì)模式。模式。n但是要同時(shí)達(dá)到無(wú)損

38、分解和保持函數(shù)依賴的分解也不是一但是要同時(shí)達(dá)到無(wú)損分解和保持函數(shù)依賴的分解也不是一件容易的事情，需要認(rèn)真對(duì)待。件容易的事情，需要認(rèn)真對(duì)待。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n舉例分析舉例分析DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué)Click to add TitleClick to add Title1 1 關(guān)系模式設(shè)計(jì)問題關(guān)系模式設(shè)計(jì)問題1 1Click to add TitleClick to add Title2 2 函數(shù)依賴函數(shù)依賴2 2Click to add TitleClick to add Title2 2 模式分解模式分解3 3

39、Click to add TitleClick to add Title1 1 規(guī)范化規(guī)范化4 4Click to add TitleClick to add Title1 1 * *多值依賴多值依賴5 5Click to add TitleClick to add Title2 2 * *連接依賴連接依賴6 6DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n范式（范式（Normal FormaNormal Forma，NFNF）是一種關(guān)系的狀態(tài)，也是衡）是一種關(guān)系的狀態(tài)，也是衡量關(guān)系模式好壞的標(biāo)準(zhǔn)。量關(guān)系模式好壞的標(biāo)準(zhǔn)。n范式的種類（范式的種類（ 1NF 1NF，2NF2NF

40、，3NF3NF，BCNF BCNF ）與數(shù)據(jù)依賴有著）與數(shù)據(jù)依賴有著直接的聯(lián)系。在關(guān)系模式中存在函數(shù)依賴時(shí)就有可能存直接的聯(lián)系。在關(guān)系模式中存在函數(shù)依賴時(shí)就有可能存在數(shù)據(jù)冗余，引出數(shù)據(jù)操作異?，F(xiàn)象。在數(shù)據(jù)冗余，引出數(shù)據(jù)操作異?，F(xiàn)象。n例如：就診關(guān)系模式例如：就診關(guān)系模式R R（DnameDname，DlevelDlevel，DsalDsal，PnamePname，F(xiàn)sumFsum）不是一個(gè)好的設(shè)計(jì)，因?yàn)榇嬖谌哂嘈畔ⅲㄖ貜?fù)存）不是一個(gè)好的設(shè)計(jì)，因?yàn)榇嬖谌哂嘈畔ⅲㄖ貜?fù)存儲(chǔ)的職稱和工資）。數(shù)據(jù)冗余不僅浪費(fèi)存儲(chǔ)空間，而且儲(chǔ)的職稱和工資）。數(shù)據(jù)冗余不僅浪費(fèi)存儲(chǔ)空間，而且會(huì)使數(shù)據(jù)庫(kù)難以保持?jǐn)?shù)據(jù)的一致性。會(huì)

41、使數(shù)據(jù)庫(kù)難以保持?jǐn)?shù)據(jù)的一致性。n范式可以用于確保數(shù)據(jù)庫(kù)模式中沒有各種類型的異常和范式可以用于確保數(shù)據(jù)庫(kù)模式中沒有各種類型的異常和不一致性。為了確定一個(gè)特定關(guān)系是否符合范式要求，不一致性。為了確定一個(gè)特定關(guān)系是否符合范式要求，需要需要檢查關(guān)系中屬性間的函數(shù)依賴檢查關(guān)系中屬性間的函數(shù)依賴，而不是檢查關(guān)系中而不是檢查關(guān)系中的當(dāng)前實(shí)例的當(dāng)前實(shí)例。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n一個(gè)規(guī)范化的模式有最小的數(shù)據(jù)冗余，它要求除了與元一個(gè)規(guī)范化的模式有最小的數(shù)據(jù)冗余，它要求除了與元組進(jìn)行連接的組進(jìn)行連接的外鍵外鍵（在另一個(gè)關(guān)系中是主鍵的屬性組）（在另一個(gè)關(guān)系中是主鍵的屬性組）之外

42、，數(shù)據(jù)庫(kù)實(shí)例中的其他屬性的值都不能被復(fù)制。之外，數(shù)據(jù)庫(kù)實(shí)例中的其他屬性的值都不能被復(fù)制。n規(guī)范化主要作為驗(yàn)證和改進(jìn)邏輯數(shù)據(jù)庫(kù)設(shè)計(jì)的工具，使規(guī)范化主要作為驗(yàn)證和改進(jìn)邏輯數(shù)據(jù)庫(kù)設(shè)計(jì)的工具，使得邏輯設(shè)計(jì)能夠得邏輯設(shè)計(jì)能夠滿足特定約束滿足特定約束并并避免不必要的數(shù)據(jù)重復(fù)避免不必要的數(shù)據(jù)重復(fù)。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n定義：在關(guān)系模式定義：在關(guān)系模式R R的每個(gè)關(guān)系的每個(gè)關(guān)系r r中，如果每個(gè)屬性中，如果每個(gè)屬性值都是不可再分的原子值，那么稱值都是不可再分的原子值，那么稱R R是第一范式（是第一范式（1NF1NF）的模式。）的模式。n1NF1NF不允許每個(gè)元組的每個(gè)

43、屬性對(duì)應(yīng)一組值、一行值不允許每個(gè)元組的每個(gè)屬性對(duì)應(yīng)一組值、一行值或兩個(gè)值的組合。簡(jiǎn)單地說(shuō)，或兩個(gè)值的組合。簡(jiǎn)單地說(shuō)，1NF1NF中不允許出現(xiàn)中不允許出現(xiàn)“表表中有表中有表”的現(xiàn)象。的現(xiàn)象。n1NF1NF是關(guān)系模式應(yīng)具有的最起碼的條件。滿足是關(guān)系模式應(yīng)具有的最起碼的條件。滿足1NF1NF的的關(guān)系稱為規(guī)范化的關(guān)系；否則稱為非規(guī)范化的關(guān)系關(guān)系稱為規(guī)范化的關(guān)系；否則稱為非規(guī)范化的關(guān)系。關(guān)系數(shù)據(jù)庫(kù)研究的關(guān)系都是規(guī)范化的關(guān)系。關(guān)系數(shù)據(jù)庫(kù)研究的關(guān)系都是規(guī)范化的關(guān)系。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n例如，就診關(guān)系模式例如，就診關(guān)系模式R R（DnoDno，PnoPno，Dlev

44、elDlevel，DsalDsal，F(xiàn)sum)Fsum)中每個(gè)屬性都不可再分，因此中每個(gè)屬性都不可再分，因此R R滿足滿足1NF1NF。n但在醫(yī)生關(guān)系模式但在醫(yī)生關(guān)系模式D D（DnoDno，DnameDname，DresumeDresume）中，）中，如果如果DresumeDresume包括工作單位和工作時(shí)間兩列信息，在包括工作單位和工作時(shí)間兩列信息，在某個(gè)醫(yī)生可能曾經(jīng)工作過多個(gè)單位而出現(xiàn)多值，則某個(gè)醫(yī)生可能曾經(jīng)工作過多個(gè)單位而出現(xiàn)多值，則D D不滿足不滿足1NF1NF。將。將D D修改為修改為D1D1（DnoDno，DnameDname，DorganiseDorganise，DdateDd

45、ate），則），則D1D1就滿足了就滿足了1NF1NF。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n如果關(guān)系模式中存在部分函數(shù)依賴，那么它就不是一如果關(guān)系模式中存在部分函數(shù)依賴，那么它就不是一個(gè)好的關(guān)系模式，因?yàn)樗芸赡艹霈F(xiàn)數(shù)據(jù)冗余和操作個(gè)好的關(guān)系模式，因?yàn)樗芸赡艹霈F(xiàn)數(shù)據(jù)冗余和操作異?，F(xiàn)象。因此，需要對(duì)這樣的關(guān)系模式進(jìn)行分解，異常現(xiàn)象。因此，需要對(duì)這樣的關(guān)系模式進(jìn)行分解，以排除局部函數(shù)依賴，使模式達(dá)到以排除局部函數(shù)依賴，使模式達(dá)到2NF2NF的標(biāo)準(zhǔn)。的標(biāo)準(zhǔn)。n2NF2NF定義：定義： 如果關(guān)系模式如果關(guān)系模式R R1NF1NF，且每個(gè)，且每個(gè)非主屬性非主屬性（不是組成候選

46、碼的屬性）不是組成候選碼的屬性）完全函數(shù)依賴完全函數(shù)依賴于候選碼，那于候選碼，那么稱么稱R R屬于屬于2NF2NF的模式。的模式。n2NF2NF是基于完全函數(shù)依賴的，只有在主鍵是復(fù)合屬性是基于完全函數(shù)依賴的，只有在主鍵是復(fù)合屬性下才可能不符合下才可能不符合2NF2NF。n2NF2NF是通往更高范式的中間步驟，它消除了是通往更高范式的中間步驟，它消除了1NF1NF存在的存在的部分問題。部分問題。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n2NF2NF舉例舉例u設(shè)有關(guān)系模式設(shè)有關(guān)系模式R R（DnoDno，PnoPno，DlevelDlevel，DsalDsal，F(xiàn)sum)Fs

47、um)的屬性分別表的屬性分別表示醫(yī)生編號(hào)、患者編號(hào)、醫(yī)生職稱級(jí)別、醫(yī)生工資和診療費(fèi)用。示醫(yī)生編號(hào)、患者編號(hào)、醫(yī)生職稱級(jí)別、醫(yī)生工資和診療費(fèi)用。（DnoDno，PnoPno）是）是R R的候選碼。的候選碼。u如果如果R R上有兩個(gè)上有兩個(gè)FDFD：（：（DnoDno，PnoPno）（DlevelDlevel，DsalDsal）和）和DnoDno（DlevelDlevel，DsalDsal），因此前面一個(gè)），因此前面一個(gè)FDFD是局部依賴，所以是局部依賴，所以R R不是不是2NF2NF。此時(shí)此時(shí)R R會(huì)出現(xiàn)冗余和異常。例如，某個(gè)醫(yī)生為會(huì)出現(xiàn)冗余和異常。例如，某個(gè)醫(yī)生為N N個(gè)病人看病，則在個(gè)病人看

48、病，則在關(guān)系中會(huì)出現(xiàn)關(guān)系中會(huì)出現(xiàn)N N個(gè)元組，而醫(yī)生的職稱級(jí)別和工資就會(huì)重復(fù)個(gè)元組，而醫(yī)生的職稱級(jí)別和工資就會(huì)重復(fù)N N次。次。u如果將如果將R R分解為分解為R R1 1（DnoDno，DlevelDlevel，DsalDsal）和）和R R2 2（DnoDno，PnoPno，F(xiàn)sumFsum）后，局部依賴（）后，局部依賴（DnoDno，PnoPno）（DlevelDlevel，DsalDsal）就消失了，）就消失了，R R1 1和和R R2 2都是都是2NF2NF了。了。DnamePnameDlevelDsalFsumDATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n2NF2

49、NF分解算法：將關(guān)系模式分解算法：將關(guān)系模式R R分解成分解成2NF2NF模式子集模式子集u設(shè)有關(guān)系模式設(shè)有關(guān)系模式R(U)R(U)，主鍵是，主鍵是W W，R R上還存在函數(shù)依賴上還存在函數(shù)依賴X XZ Z，其中，其中Z Z是是非主屬性和非主屬性和X WX W，則，則W WZ Z就是一個(gè)局部依賴。此時(shí)應(yīng)該把就是一個(gè)局部依賴。此時(shí)應(yīng)該把R R分解分解成兩個(gè)模式：成兩個(gè)模式：u R R1 1（XZXZ），主鍵是），主鍵是X X；u R R2 2（U-ZU-Z），主鍵仍為），主鍵仍為W W，外鍵是，外鍵是X X（參考（參考R R1 1）。）。u利用外鍵和主鍵的連接可以從利用外鍵和主鍵的連接可以從R

50、R1 1和和R R2 2重新得到重新得到R R。u如果如果R R1 1和和R R2 2還不是還不是2NF2NF，則重復(fù)上述過程，一直到數(shù)據(jù)庫(kù)模式中每，則重復(fù)上述過程，一直到數(shù)據(jù)庫(kù)模式中每一個(gè)關(guān)系模式都是一個(gè)關(guān)系模式都是2NF2NF為止。為止。n例如例如uR R（DnoDno，PnoPno，DlevelDlevel，DsalDsal，F(xiàn)sum)Fsum)中，存在中，存在FDFD：（：（DnoDno，PnoPno）（DlevelDlevel，DsalDsal）和）和DnoDno（DlevelDlevel，DsalDsal）u分解為：分解為：R R1 1（DnoDno，DlevelDlevel，Ds

51、alDsal）和）和R R2 2（DnoDno，PnoPno，F(xiàn)sumFsum）DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n定義：如果關(guān)系模式定義：如果關(guān)系模式R R1NF1NF，且每個(gè)，且每個(gè)非主屬性非主屬性都都不傳不傳遞依賴遞依賴于于R R的候選碼，那么稱的候選碼，那么稱R R屬于屬于3NF3NF的模式。的模式。n在在3NF3NF中，關(guān)系模式是由主鍵和一組相互獨(dú)立的非主中，關(guān)系模式是由主鍵和一組相互獨(dú)立的非主屬性組成的，它滿足兩個(gè)條件：屬性組成的，它滿足兩個(gè)條件：u（1 1）R R中的非主屬性相互獨(dú)立；中的非主屬性相互獨(dú)立；u（2 2）R R中的非主屬性函數(shù)依賴于主鍵。

52、中的非主屬性函數(shù)依賴于主鍵。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n3NF3NF舉例：舉例：uR R2 2（DnoDno，PnoPno，F(xiàn)sumFsum）是）是2NF2NF模式，而且也是模式，而且也是3NF3NF模式。模式。u但是但是R R1 1（DnoDno，DlevelDlevel，DsalDsal）是）是2NF2NF模式，但不一定是模式，但不一定是3NF3NF。因?yàn)?。因?yàn)槿绻绻鸕 R1 1中存在函數(shù)依賴中存在函數(shù)依賴DnoDnoDlevelDlevel和和DlevelDlevelDsalDsal，那么，那么DnoDnoDsalDsal就是一個(gè)傳遞依賴，即就是一個(gè)

53、傳遞依賴，即R R1 1不是不是3NF3NF模式。模式。u此時(shí)此時(shí)R R1 1的關(guān)系也會(huì)出現(xiàn)冗余和異常。例如，的關(guān)系也會(huì)出現(xiàn)冗余和異常。例如，R R2 2中存在中存在M M個(gè)職稱同為個(gè)職稱同為主任級(jí)別的醫(yī)生，則主任級(jí)別的醫(yī)生，則R R1 1中需要重復(fù)存儲(chǔ)中需要重復(fù)存儲(chǔ)M M個(gè)相同的工資數(shù)目。個(gè)相同的工資數(shù)目。u如果將如果將R R1 1分解為分解為R R1111（DnoDno，DlevelDlevel）和）和R R1212（DlevelDlevel，DsalDsal）后，）后，DnoDnoDsalDsal就不會(huì)出現(xiàn)在就不會(huì)出現(xiàn)在R R1111和和R R1212中，因此中，因此R R1111和和R

54、 R1212都是都是3NF3NF的模式。的模式。DnamePnameDlevelDsalFsumDATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n3NF3NF分解算法：分解算法： 將關(guān)系模式將關(guān)系模式R R分解為分解為3NF3NF模式集。模式集。u設(shè)關(guān)系模式設(shè)關(guān)系模式R R（U U），主鍵是），主鍵是W W，R R上還存在上還存在FD XFD XZ Z，其中，其中Z Z是非主屬是非主屬性，性， 且且X X不是候選鍵，這樣不是候選鍵，這樣W WZ Z就是一個(gè)傳遞依賴。此時(shí)應(yīng)把就是一個(gè)傳遞依賴。此時(shí)應(yīng)把R R分解成兩個(gè)模式：分解成兩個(gè)模式：u R R1 1（XZXZ），主鍵是），主鍵

55、是X X；u R R2 2（U -Z U -Z ），主鍵仍是），主鍵仍是W W，外鍵是，外鍵是X X（參考（參考R R1 1）。）。u利用外鍵和主鍵相匹配機(jī)制，利用外鍵和主鍵相匹配機(jī)制，R R1 1和和R R2 2通過連接可以重新得到通過連接可以重新得到R R。u如果如果R R1 1和和R R2 2還不是還不是3NF3NF，則重復(fù)上述過程，一直到數(shù)據(jù)庫(kù)模式中每，則重復(fù)上述過程，一直到數(shù)據(jù)庫(kù)模式中每一個(gè)關(guān)系模式都是一個(gè)關(guān)系模式都是3NF3NF為止。為止。n例如：例如：uR R1 1（DnoDno，DlevelDlevel，DsalDsal）上存在）上存在DnoDnoDlevelDlevel和和D

56、levelDlevelDsalDsal，則，則DnoDno DsalDsal為傳遞函數(shù)依賴為傳遞函數(shù)依賴u分解為：分解為：R R1111（DnoDno，DlevelDlevel）和）和R R1212（DlevelDlevel，DsalDsal）ZX DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n定理：如果定理：如果R R是是3NF3NF模式，那么模式，那么R R也是也是2NF2NF模式。模式。n局部依賴和傳遞依賴是關(guān)系模式產(chǎn)生數(shù)據(jù)冗余和異常局部依賴和傳遞依賴是關(guān)系模式產(chǎn)生數(shù)據(jù)冗余和異常的兩個(gè)重要原因。的兩個(gè)重要原因。n由于由于3NF3NF模式中不存在非主屬性對(duì)候選鍵的局部依賴

57、模式中不存在非主屬性對(duì)候選鍵的局部依賴和傳遞依賴，因此和傳遞依賴，因此3NF3NF消除了很大一部分存儲(chǔ)異常，消除了很大一部分存儲(chǔ)異常，具有較好的性能。具有較好的性能。n而對(duì)于非而對(duì)于非1NF1NF、1NF1NF和和2NF2NF的關(guān)系模式，由于它們的性的關(guān)系模式，由于它們的性能較差，通常不宜作為數(shù)據(jù)庫(kù)模式，需要將這些關(guān)系能較差，通常不宜作為數(shù)據(jù)庫(kù)模式，需要將這些關(guān)系模式變換為模式變換為3NF3NF或更高級(jí)的范式。這種變換過程稱為或更高級(jí)的范式。這種變換過程稱為“關(guān)系的規(guī)范化處理關(guān)系的規(guī)范化處理”。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n在在3NF3NF模式中，并未排除主屬

58、性對(duì)候選鍵的傳遞依賴模式中，并未排除主屬性對(duì)候選鍵的傳遞依賴，因此有必要提出更高一級(jí)的范式。，因此有必要提出更高一級(jí)的范式。nBCBC范式（范式（Boyce-Codd Normal FormBoyce-Codd Normal Form，BCNFBCNF），由），由BoyceBoyce與與CoddCodd提出的，比上述的提出的，比上述的3NF3NF又進(jìn)了一步，通常又進(jìn)了一步，通常認(rèn)為認(rèn)為BCNFBCNF是修正的第三范式，有時(shí)也稱為擴(kuò)充的第三是修正的第三范式，有時(shí)也稱為擴(kuò)充的第三范式。范式。n3NF3NF定義：如果關(guān)系模式定義：如果關(guān)系模式R R1NF1NF，且每個(gè)屬性都不傳，且每個(gè)屬性都不傳遞依

59、賴于遞依賴于R R的候選碼，那么稱的候選碼，那么稱R R是是BCNFBCNF的模式。的模式。DATABASEUESTC學(xué)以致用學(xué)以致用 用以促學(xué)用以促學(xué) n由由BCNFBCNF的定義可以得到以下結(jié)論，一個(gè)滿足的定義可以得到以下結(jié)論，一個(gè)滿足BCNFBCNF的關(guān)的關(guān)系模式有：系模式有：u所有非主屬性對(duì)每一個(gè)碼都是完全函數(shù)依賴。所有非主屬性對(duì)每一個(gè)碼都是完全函數(shù)依賴。u所有的主屬性對(duì)每一個(gè)不包含它的碼，也是完全函數(shù)依賴。所有的主屬性對(duì)每一個(gè)不包含它的碼，也是完全函數(shù)依賴。u沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。DATABASEUESTC學(xué)以致用

60、學(xué)以致用 用以促學(xué)用以促學(xué) n舉例舉例u關(guān)系模式關(guān)系模式R R（BnoBno，BnameBname，AuthorAuthor）的屬性分別表示書號(hào)、書名和）的屬性分別表示書號(hào)、書名和作者名。假如每個(gè)書號(hào)只有一個(gè)書名，但不同的書號(hào)可以有相同的作者名。假如每個(gè)書號(hào)只有一個(gè)書名，但不同的書號(hào)可以有相同的書名；每本書可以有多個(gè)作者合寫，但每個(gè)作者參與編著的書名應(yīng)書名；每本書可以有多個(gè)作者合寫，但每個(gè)作者參與編著的書名應(yīng)該互不相同。該互不相同。uR R上的上的FDFD如下：如下：BnoBnoBnameBname和（和（BnameBname，AuthorAuthor）BnoBnou因此因此R R的關(guān)鍵碼是（