關(guān)系數(shù)據(jù)庫規(guī)范化理論

1、關(guān)系數(shù)據(jù)庫規(guī)范化理論 第四章第四章 關(guān)系數(shù)據(jù)庫的規(guī)范化理論關(guān)系數(shù)據(jù)庫的規(guī)范化理論 關(guān)系數(shù)據(jù)庫規(guī)范化理論 本章內(nèi)容本章內(nèi)容 n1、問題的提出、問題的提出 n2、函數(shù)依賴、函數(shù)依賴 n3、 關(guān)系范式關(guān)系范式 n4、 函數(shù)依賴理論函數(shù)依賴理論 n5、 關(guān)系分解原則關(guān)系分解原則 關(guān)系數(shù)據(jù)庫規(guī)范化理論 4.1 問題的提出問題的提出 學(xué)號學(xué)號姓名姓名年齡年齡性別性別系名系名系主任系主任課程名課程名成績成績 011121王強王強19男男計算機計算機王金喜王金喜操作系統(tǒng)操作系統(tǒng)87 011132李琳李琳18女女信息信息劉成劉成數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)90 020923劉過劉過19男男信息信息劉成劉成C語言語言97 0

2、21206張克張克20男男數(shù)學(xué)數(shù)學(xué)劉國民劉國民高等數(shù)學(xué)高等數(shù)學(xué)88 021511吳雯吳雯18女女計算機計算機王金喜王金喜軟件工程軟件工程76 出現(xiàn)的問題：出現(xiàn)的問題： 1、數(shù)據(jù)冗余、數(shù)據(jù)冗余 2、修改異常、修改異常 3、插入異常、插入異常 4、刪除異常、刪除異常 例：教學(xué)關(guān)系例：教學(xué)關(guān)系S1實例實例 出現(xiàn)問題的原因出現(xiàn)問題的原因： 有太多相互之間相聯(lián)系的屬性保存在了同一個關(guān)系模有太多相互之間相聯(lián)系的屬性保存在了同一個關(guān)系模 式中，這就造成因一種信息被捆綁在其他信息上而產(chǎn)式中，這就造成因一種信息被捆綁在其他信息上而產(chǎn) 生的信息之間相互依附存儲的問題生的信息之間相互依附存儲的問題數(shù)據(jù)依賴數(shù)據(jù)依賴

3、關(guān)系數(shù)據(jù)庫規(guī)范化理論 n解決問題的方法：解決問題的方法：將相互之間有太多依賴關(guān)系的屬性分別存放在不將相互之間有太多依賴關(guān)系的屬性分別存放在不 同的關(guān)系中。同的關(guān)系中。 n分解后的三個關(guān)系分解后的三個關(guān)系 學(xué)號學(xué)號姓名姓名年齡年齡性別性別系名系名 011121王強王強19男男計算機計算機 011132李琳李琳18女女信息信息 020923劉過劉過19男男信息信息 021206張克張克20男男數(shù)學(xué)數(shù)學(xué) 021511吳雯吳雯18女女計算機計算機 系名系名系主任系主任 計算機計算機王金喜王金喜 信息信息劉成劉成 信息信息劉成劉成 數(shù)學(xué)數(shù)學(xué)劉國民劉國民 計算機計算機王金喜王金喜 學(xué)號學(xué)號課程名課程名成績

4、成績 011121操作系統(tǒng)操作系統(tǒng)87 011132數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)90 020923C語言語言97 021206高等數(shù)學(xué)高等數(shù)學(xué)88 021511軟件工程軟件工程76 學(xué)生學(xué)生 S1系系 S2選修選修 S3 關(guān)系數(shù)據(jù)庫規(guī)范化理論 關(guān)系模式的函數(shù)依賴關(guān)系模式的函數(shù)依賴 n4.2.1 函數(shù)依賴的相關(guān)定義函數(shù)依賴的相關(guān)定義 n（1）函數(shù)依賴）函數(shù)依賴 n定義定義 設(shè)一個關(guān)系為設(shè)一個關(guān)系為R（U），），X、Y是屬性集是屬性集U的子集。若對于元組中的子集。若對于元組中X 上的每個值都有上的每個值都有Y上的一個唯一值與之對應(yīng)，上的一個唯一值與之對應(yīng)， 則稱則稱X和和Y具有函數(shù)依賴具有函數(shù)依賴 關(guān)系，并稱

5、關(guān)系，并稱X函數(shù)決定函數(shù)決定Y，或稱，或稱Y函數(shù)依賴于函數(shù)依賴于X，記作，記作XY，稱，稱X為決定為決定 因素。（同書上的概念因素。（同書上的概念p106) n例例1：設(shè)一個職工關(guān)系為（：設(shè)一個職工關(guān)系為（職工號職工號，姓名，性別，年齡，職稱），姓名，性別，年齡，職稱） 職工號職工號為決該函數(shù)依賴的決定因素為決該函數(shù)依賴的決定因素 例例2： U=（學(xué)號，姓名，性別，班級，系，課程號，成績）（學(xué)號，姓名，性別，班級，系，課程號，成績） 則其函數(shù)依賴情況是：則其函數(shù)依賴情況是： F學(xué)號學(xué)號姓名，學(xué)號姓名，學(xué)號性別，學(xué)號性別，學(xué)號班級，學(xué)號班級，學(xué)號系，班級系，班級系，系， （學(xué)號，課程號）（學(xué)號，

6、課程號）成績成績 注意：幾點說明注意：幾點說明 關(guān)系數(shù)據(jù)庫規(guī)范化理論 4.2.2 函數(shù)依賴的類型函數(shù)依賴的類型 n（1）平凡函數(shù)依賴與非平凡函數(shù)依賴）平凡函數(shù)依賴與非平凡函數(shù)依賴 n定義定義4.3 對于函數(shù)依賴對于函數(shù)依賴XY,如果滿足如果滿足 ，則稱，則稱 此函數(shù)依賴為非平凡函數(shù)依賴，此函數(shù)依賴為非平凡函數(shù)依賴， 否則稱之為平凡函數(shù)否則稱之為平凡函數(shù) 依賴。依賴。 n例如：例如：學(xué)號學(xué)號姓名，學(xué)號姓名，學(xué)號性別，（學(xué)號，課程號）性別，（學(xué)號，課程號）成績成績 等都是非平凡函數(shù)依賴。等都是非平凡函數(shù)依賴。 n例如：例如： （學(xué)號，課程號）（學(xué)號，課程號）學(xué)號，（學(xué)號，課程號）學(xué)號，（學(xué)號，課程

7、號）課程號課程號 是平凡函數(shù)依賴是平凡函數(shù)依賴 n對于任一關(guān)系模式，平凡函數(shù)依賴必然是成立的。對于任一關(guān)系模式，平凡函數(shù)依賴必然是成立的。 n通常討論的都是非平凡函數(shù)依賴。通常討論的都是非平凡函數(shù)依賴。 YX YX 關(guān)系數(shù)據(jù)庫規(guī)范化理論 n（2）完全函數(shù)依賴與部分函數(shù)依賴）完全函數(shù)依賴與部分函數(shù)依賴 n定義定義4.4 對于函數(shù)依賴對于函數(shù)依賴XY，若，若Y函數(shù)依賴于函數(shù)依賴于X，但不依賴于，但不依賴于X的任的任 意一個真子集意一個真子集 ，則稱，則稱Y完全函數(shù)依賴于完全函數(shù)依賴于X。記作：。記作： n n例：（學(xué)號，課程號）例：（學(xué)號，課程號） 成績成績 n定義定義4.4 若若Y函數(shù)依賴于函數(shù)

8、依賴于X，但并非完全依賴于，但并非完全依賴于X，則稱，則稱 Y部分函數(shù)依賴于部分函數(shù)依賴于X，或稱，或稱Y函數(shù)依賴于函數(shù)依賴于X的某個真子集。的某個真子集。 n記作：記作： n例：（學(xué)號，課程號）例：（學(xué)號，課程號）姓名姓名 n（學(xué)號，課程號）（學(xué)號，課程號） 姓名，而對于每個學(xué)生都有唯一的學(xué)號值，所姓名，而對于每個學(xué)生都有唯一的學(xué)號值，所 以以 學(xué)號學(xué)號姓名。因此（學(xué)號，課程號）姓名。因此（學(xué)號，課程號） 姓名姓名 是部分函數(shù)依賴。是部分函數(shù)依賴。 X X F XY P XY P F 關(guān)系數(shù)據(jù)庫規(guī)范化理論 n（3）傳遞函數(shù)依賴）傳遞函數(shù)依賴 n定義定義4.5 如果如果XY，（，（ ），），

9、， YZ，則稱，則稱Z 傳遞依賴于傳遞依賴于X。記作：記作： n例：學(xué)號例：學(xué)號班級，班級班級，班級系，學(xué)號系，學(xué)號 系系 n例：有以下班級關(guān)系：例：有以下班級關(guān)系： n班級（班級（班號班號，專業(yè)名，系名，人數(shù)，入學(xué)年份），專業(yè)名，系名，人數(shù)，入學(xué)年份） n其中，主碼是班號。其中，主碼是班號。 n經(jīng)分析，有：班號經(jīng)分析，有：班號專業(yè)名，班號專業(yè)名，班號人數(shù)，班號人數(shù)，班號入入 學(xué)年份，專業(yè)名學(xué)年份，專業(yè)名系名。系名。 n又因為：班號又因為：班號專業(yè)名，專業(yè)名專業(yè)名，專業(yè)名 班號，專業(yè)名班號，專業(yè)名 系名，所以有：班號系名，所以有：班號 系名。系名。 Y X Y X T XZ T T 關(guān)系數(shù)據(jù)庫

10、規(guī)范化理論 F KU 4.2.3 關(guān)鍵字的相關(guān)定義關(guān)鍵字的相關(guān)定義 n1、關(guān)鍵字、關(guān)鍵字 n定義：在關(guān)系模式R（U）中，若 ， 且滿足 ，則稱K為R的候選鍵或候 選關(guān)鍵字。 n2、候選關(guān)鍵字、主關(guān)鍵字、候選關(guān)鍵字、主關(guān)鍵字 n3、主屬性、非主屬性、主屬性集、非主、主屬性、非主屬性、主屬性集、非主 屬性集屬性集 K U 關(guān)系數(shù)據(jù)庫規(guī)范化理論 4.2.4 函數(shù)依賴的推理規(guī)則 n1、函數(shù)依賴的邏輯蘊涵 n2、Armstrong 公理系統(tǒng) n3、函數(shù)依賴推理規(guī)則的完備性 n4、閉包的計算 關(guān)系數(shù)據(jù)庫規(guī)范化理論 n4.2 函數(shù)依賴理論函數(shù)依賴理論 n一個關(guān)系模式可能存在很多個函數(shù)依賴，它們構(gòu)一個關(guān)系模式

11、可能存在很多個函數(shù)依賴，它們構(gòu) 成了該關(guān)系模式的函數(shù)依賴集。成了該關(guān)系模式的函數(shù)依賴集。 n該集合是很大的該集合是很大的,如果僅依靠語義分析的方法去找如果僅依靠語義分析的方法去找 出一個關(guān)系模式的所有函數(shù)依賴是一件很不出一個關(guān)系模式的所有函數(shù)依賴是一件很不 容易容易 的事情，實際上也沒有必要。的事情，實際上也沒有必要。 n1,邏輯蘊涵：用推理的方法，從一個已知的函數(shù)依邏輯蘊涵：用推理的方法，從一個已知的函數(shù)依 賴集去推導(dǎo)出另一個函數(shù)依賴集，這樣兩個函數(shù)賴集去推導(dǎo)出另一個函數(shù)依賴集，這樣兩個函數(shù) 依賴集之間的互為因果關(guān)系稱之為邏輯蘊涵。依賴集之間的互為因果關(guān)系稱之為邏輯蘊涵。 n因此，我們給出一

12、個函數(shù)依賴集閉包的定義。因此，我們給出一個函數(shù)依賴集閉包的定義。 關(guān)系數(shù)據(jù)庫規(guī)范化理論 n定義：所有被一個已知函數(shù)依賴集（定義：所有被一個已知函數(shù)依賴集（F） 邏輯蘊涵的那些函數(shù)依賴的集合稱為邏輯蘊涵的那些函數(shù)依賴的集合稱為F的的 閉包。閉包。 nP109 n如何由一個已知函數(shù)依賴集找出它的閉如何由一個已知函數(shù)依賴集找出它的閉 包呢？包呢？1974年，年，Armstrong提出了用提出了用 推理方法計算閉包的一套規(guī)則，具體包推理方法計算閉包的一套規(guī)則，具體包 括三個推理規(guī)則和三條推論，及一定的括三個推理規(guī)則和三條推論，及一定的 算法。算法。 關(guān)系數(shù)據(jù)庫規(guī)范化理論 n函數(shù)依賴的一些常用規(guī)則：函數(shù)

13、依賴的一些常用規(guī)則： n自反性：自反性： n增廣性增廣性 n傳遞性傳遞性 n合并規(guī)則合并規(guī)則 n分解規(guī)則分解規(guī)則 n偽傳遞性偽傳遞性 P109p110 關(guān)系數(shù)據(jù)庫規(guī)范化理論 n實際上計算推導(dǎo)出函數(shù)依賴集的閉包是實際上計算推導(dǎo)出函數(shù)依賴集的閉包是 一件非常繁瑣復(fù)雜的事情，所以引入的一件非常繁瑣復(fù)雜的事情，所以引入的 屬性集閉包的概念。屬性集閉包的概念。 關(guān)系數(shù)據(jù)庫規(guī)范化理論 定義定義4.9 設(shè)設(shè)F是屬性集合是屬性集合U上的一個函數(shù)依賴集，上的一個函數(shù)依賴集， X U，稱，稱 為屬性集為屬性集X關(guān)于關(guān)于F的閉包。的閉包。 P110 引理引理 設(shè)設(shè)F是屬性集是屬性集U上的函數(shù)依賴集，上的函數(shù)依賴集，

14、X，Y是是U的的 子集，則子集，則XY能由能由F根據(jù)根據(jù)Armstrong公理導(dǎo)出的充公理導(dǎo)出的充 分必要條件是分必要條件是 。 ArmstrongFAXU,A|AX F 公理導(dǎo)出根據(jù)能由 XY 關(guān)系數(shù)據(jù)庫規(guī)范化理論 n求屬性集X關(guān)于函數(shù)依賴集F的閉包的算 法 nP111 關(guān)系數(shù)據(jù)庫規(guī)范化理論 函數(shù)依賴集的等價與覆蓋 每個函數(shù)依賴集至少存在一個最小依賴集， 但并不唯一。 最小函數(shù)依賴集的定義 最小函數(shù)依賴集的計算方法 函數(shù)依賴集極小化的作用 關(guān)系數(shù)據(jù)庫規(guī)范化理論 n定理定理4.7 4.7 每個函數(shù)依賴集每個函數(shù)依賴集F F都有最小覆蓋。都有最小覆蓋。 n定義：設(shè)一個關(guān)系為定義：設(shè)一個關(guān)系為R（

15、U），），X 和和Y為為U的子集，若的子集，若X Y，并且為完全非平凡函數(shù)依賴，同時，并且為完全非平凡函數(shù)依賴，同時Y為單屬性，為單屬性， 則稱則稱X Y為為R的最小函數(shù)依賴。由的最小函數(shù)依賴。由R中所有最小函數(shù)中所有最小函數(shù) 依賴構(gòu)成依賴構(gòu)成R的最小函數(shù)依賴集，其中不含有冗余的傳的最小函數(shù)依賴集，其中不含有冗余的傳 遞函數(shù)依賴。遞函數(shù)依賴。 n最小函數(shù)依賴集的計算方法最小函數(shù)依賴集的計算方法 P113 關(guān)系數(shù)據(jù)庫規(guī)范化理論 n最小函數(shù)依賴集的計算方法： n1、 F Fmin min中任一函數(shù)依賴的右部都是單個屬性， 故先把F中的函數(shù)依賴的右部化為單屬性的形 式。 n2、 F Fmin min

16、中不存在冗余的FD（即不存在這樣的 FD：X X A A，使得，使得 F F XXAA與與F F等價；故消去等價；故消去 冗余的冗余的FD。 n3、消去左邊冗余的屬性：對對F F中的任一函數(shù)依中的任一函數(shù)依 賴賴X X A A，若，若Z Z X X，則，則(F(F XXA)A) ZZAA與與F F 不等價。不等價。 n每一個函數(shù)依賴集至少存在一個最小函數(shù)依賴每一個函數(shù)依賴集至少存在一個最小函數(shù)依賴 集，但并不一定唯一。集，但并不一定唯一。 關(guān)系數(shù)據(jù)庫規(guī)范化理論 4.3 關(guān)系范式關(guān)系范式 n分解前后模式的好壞，是用什么標準來衡量呢？分解前后模式的好壞，是用什么標準來衡量呢？ n 關(guān)系模式的規(guī)范化

17、標準（范式）關(guān)系模式的規(guī)范化標準（范式） n關(guān)系規(guī)范化的條件可以分為幾級，每一級稱為一個范關(guān)系規(guī)范化的條件可以分為幾級，每一級稱為一個范 式，記為式，記為XNF。 nNF（Normal Form），范式），范式即關(guān)系模式滿足的即關(guān)系模式滿足的 條件。條件。 n范式的概念范式的概念 關(guān)系數(shù)據(jù)庫規(guī)范化理論 4.3.1 范式的定義及規(guī)范化范式的定義及規(guī)范化 n1、第一范式（、第一范式（1NF） n定義：如果一個關(guān)系模式定義：如果一個關(guān)系模式R的每個屬性的值都是不可再的每個屬性的值都是不可再 分的基本數(shù)據(jù)項，則稱分的基本數(shù)據(jù)項，則稱R屬于第一范式。屬于第一范式。 n2、第二范式（、第二范式（2NF）

18、n定義：如果一個關(guān)系模式定義：如果一個關(guān)系模式R屬于屬于1NF，且它的任一非主，且它的任一非主 屬性都完全函數(shù)依賴于任一候選關(guān)鍵字，則稱屬性都完全函數(shù)依賴于任一候選關(guān)鍵字，則稱R滿足第滿足第 二范式。二范式。 n2NF不允許關(guān)系模式中的非主屬性部分函數(shù)依賴于關(guān)鍵字。不允許關(guān)系模式中的非主屬性部分函數(shù)依賴于關(guān)鍵字。 n例：書例：書P122 n分析可知：部分依賴必然帶來數(shù)據(jù)冗余和操作異常。分析可知：部分依賴必然帶來數(shù)據(jù)冗余和操作異常。 n如何消除部分依賴，使一個只滿足如何消除部分依賴，使一個只滿足1NF的關(guān)系模式變?yōu)閷儆诘年P(guān)系模式變?yōu)閷儆?NF的的 關(guān)系模式？關(guān)系模式？ 關(guān)系數(shù)據(jù)庫規(guī)范化理論 n通

19、過模式分解，使任一非主屬性都完全函數(shù)依賴于它通過模式分解，使任一非主屬性都完全函數(shù)依賴于它 的任一候選關(guān)鍵字。的任一候選關(guān)鍵字。 n對于一個關(guān)系對于一個關(guān)系R（U），假定），假定W、X、Y、Z是是U的互不的互不 相交的屬性子集，其中（相交的屬性子集，其中（W、X）是主碼，且）是主碼，且X Y， （W，X）Z，Z中不包含依賴于中不包含依賴于X的屬性，則把的屬性，則把R （U）分解為兩個關(guān)系）分解為兩個關(guān)系R1（X，Y）和）和R2（W，X，Z） 后就取消了后就取消了Y對（對（W，X）的部分依賴。）的部分依賴。 F 關(guān)系數(shù)據(jù)庫規(guī)范化理論 n3、第三范式（、第三范式（3NF） n定義：如果一個關(guān)系模式

20、定義：如果一個關(guān)系模式R屬于屬于1NF，且每一個非主，且每一個非主 屬性不傳遞依賴于任一候選關(guān)鍵字，則稱屬性不傳遞依賴于任一候選關(guān)鍵字，則稱R滿足第三滿足第三 范式。范式。 n消除關(guān)系的傳遞函數(shù)依賴也是通過關(guān)系分解的方法來實現(xiàn)的。消除關(guān)系的傳遞函數(shù)依賴也是通過關(guān)系分解的方法來實現(xiàn)的。 n設(shè)一個關(guān)系設(shè)一個關(guān)系R（U），假定），假定X、Y、Z 、W是是U的互不相交的屬性的互不相交的屬性 子集，其中子集，其中 X是主碼，是主碼，YZ是直接函數(shù)依賴（也可能包含部分函是直接函數(shù)依賴（也可能包含部分函 數(shù)依賴），數(shù)依賴）， XZ 是傳遞函數(shù)依賴，則把是傳遞函數(shù)依賴，則把 R（U）分解為兩個關(guān)）分解為兩個關(guān)

21、 系系R1（Y，Z）和）和R2（X，Y，W），其中），其中Y是是R1的主碼，的主碼，R2的的 外碼，這樣就消除了外碼，這樣就消除了Z對對X的傳遞依賴。的傳遞依賴。 關(guān)系數(shù)據(jù)庫規(guī)范化理論 n4、Boyce-Codd范式（范式（BCNF） n定義：設(shè)有關(guān)系模式定義：設(shè)有關(guān)系模式R及其函數(shù)依賴集及其函數(shù)依賴集F，X和和A是是R的的 屬性集會，且屬性集會，且 。如果只要。如果只要R滿足滿足X A，X就必就必 包含包含R的一個候選關(guān)鍵字，則稱的一個候選關(guān)鍵字，則稱R滿足滿足BCNF。 n或：若一個關(guān)系為或：若一個關(guān)系為R（U），它是滿足），它是滿足1NF的，當?shù)模擱中中 不存在任何屬性對候選碼的傳遞函

22、數(shù)依賴時，則稱不存在任何屬性對候選碼的傳遞函數(shù)依賴時，則稱R 是符合是符合BCNF的。的。 n或：若或：若R中的所有屬性都完全直接依賴于候選碼，或中的所有屬性都完全直接依賴于候選碼，或 說說R的所有函數(shù)依賴的決定因素都是候選碼。的所有函數(shù)依賴的決定因素都是候選碼。 n沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。 A X 關(guān)系數(shù)據(jù)庫規(guī)范化理論 n定理定理 如果一個關(guān)系模式如果一個關(guān)系模式R BCNF，則它必滿足，則它必滿足3NF。 反之，不一定成立。反之，不一定成立。 n3NF和和BCNF是在函數(shù)依賴的條件下對模式分解所能達是在函數(shù)依賴的條件下對模

23、式分解所能達 到的分離程度的測度。到的分離程度的測度。 n一個模式中的關(guān)系模式如果都屬于一個模式中的關(guān)系模式如果都屬于BCNF，那么在函，那么在函 數(shù)依賴范疇內(nèi)，它已實現(xiàn)了徹底的分離，已消除了插數(shù)依賴范疇內(nèi)，它已實現(xiàn)了徹底的分離，已消除了插 入和刪除的異常。入和刪除的異常。 n3NF的的“不徹底不徹底”性表現(xiàn)在可能存在主屬性對碼的部性表現(xiàn)在可能存在主屬性對碼的部 分依賴和傳遞依賴。分依賴和傳遞依賴。 關(guān)系數(shù)據(jù)庫規(guī)范化理論 n4.3.2 關(guān)系規(guī)范化小結(jié)關(guān)系規(guī)范化小結(jié) n規(guī)范化的基本思想是逐步消除數(shù)據(jù)依賴中不適規(guī)范化的基本思想是逐步消除數(shù)據(jù)依賴中不適 合的部分，使各關(guān)系模式達到某種程度的合的部分，