6第6章-關(guān)系數(shù)據(jù)庫模式設(shè)計(jì)PPT優(yōu)秀課件

1、 關(guān)系數(shù)據(jù)庫模式關(guān)系數(shù)據(jù)庫模式 ？ 圖1.14 數(shù)據(jù)庫系統(tǒng)的體系結(jié)構(gòu) 用戶用戶A1A1用戶用戶A1A1 局部邏輯結(jié)構(gòu)局部邏輯結(jié)構(gòu) 概念級概念級DBDB 全局邏輯結(jié)構(gòu)全局邏輯結(jié)構(gòu) 存儲級存儲級DB 存儲組織結(jié)構(gòu)存儲組織結(jié)構(gòu) DBMS OS 用戶級用戶級DB 用戶用戶A1A1用戶用戶A1A1 學(xué)生關(guān)系（學(xué)號，姓名，性別，出生年月，籍貫，專業(yè)代碼，班級）學(xué)生關(guān)系（學(xué)號，姓名，性別，出生年月，籍貫，專業(yè)代碼，班級） 專業(yè)關(guān)系（專業(yè)代碼，專業(yè)名稱）專業(yè)關(guān)系（專業(yè)代碼，專業(yè)名稱） 課程關(guān)系（課程號，課程名，學(xué)時數(shù)）課程關(guān)系（課程號，課程名，學(xué)時數(shù)） 設(shè)置關(guān)系（專業(yè)代碼，課程代碼）設(shè)置關(guān)系（專業(yè)代碼，課程代

2、碼） 學(xué)習(xí)關(guān)系（學(xué)號，課程號，分?jǐn)?shù)）學(xué)習(xí)關(guān)系（學(xué)號，課程號，分?jǐn)?shù)） 教師關(guān)系（教工號，教員姓名，教員性別，教員出生年月，教研室，電話）教師關(guān)系（教工號，教員姓名，教員性別，教員出生年月，教研室，電話） 講授關(guān)系（教工號，課程號）講授關(guān)系（教工號，課程號） 關(guān)系數(shù)據(jù)庫模式：關(guān)系數(shù)據(jù)庫模式： 關(guān)系數(shù)據(jù)庫的模式設(shè)計(jì)問題，是數(shù)據(jù)庫應(yīng)用關(guān)系數(shù)據(jù)庫的模式設(shè)計(jì)問題，是數(shù)據(jù)庫應(yīng)用 系統(tǒng)設(shè)計(jì)中的核心問題之一。系統(tǒng)設(shè)計(jì)中的核心問題之一。 本章中，支撐關(guān)系數(shù)據(jù)庫模式設(shè)計(jì)的函數(shù)依本章中，支撐關(guān)系數(shù)據(jù)庫模式設(shè)計(jì)的函數(shù)依 賴和規(guī)范化理論，是關(guān)系數(shù)據(jù)庫設(shè)計(jì)的重要理論賴和規(guī)范化理論，是關(guān)系數(shù)據(jù)庫設(shè)計(jì)的重要理論 基礎(chǔ)，也是本課

3、程學(xué)習(xí)的主要難點(diǎn)內(nèi)容。基礎(chǔ)，也是本課程學(xué)習(xí)的主要難點(diǎn)內(nèi)容。 Question 關(guān)系數(shù)據(jù)庫模式的設(shè)計(jì)有哪幾種方法呢？關(guān)系數(shù)據(jù)庫模式的設(shè)計(jì)有哪幾種方法呢？ 1 1、E-RE-R模型方法：畫出反映用戶組織中相互關(guān)模型方法：畫出反映用戶組織中相互關(guān) 聯(lián)的數(shù)據(jù)及其之間聯(lián)系的聯(lián)的數(shù)據(jù)及其之間聯(lián)系的E-RE-R圖，再將圖，再將E-RE-R模型轉(zhuǎn)換模型轉(zhuǎn)換 成關(guān)系模型對應(yīng)的關(guān)系模式。成關(guān)系模型對應(yīng)的關(guān)系模式。 2 2、屬性表方法：收集、整理和歸納用戶組織、屬性表方法：收集、整理和歸納用戶組織 進(jìn)行信息管理的各種表格，然后把每個表格轉(zhuǎn)換成進(jìn)行信息管理的各種表格，然后把每個表格轉(zhuǎn)換成 一個關(guān)系模式。一個關(guān)系模式。

4、 由表由表6.1可直接得到如下關(guān)系模式：可直接得到如下關(guān)系模式： 學(xué)生學(xué)籍關(guān)系（學(xué)號，姓名，性別，出生年月，學(xué)生學(xué)籍關(guān)系（學(xué)號，姓名，性別，出生年月， 籍貫，班級，所屬專業(yè)）籍貫，班級，所屬專業(yè)） 考試成績關(guān)系（學(xué)號，姓名，課程編號，課程名稱，考試成績關(guān)系（學(xué)號，姓名，課程編號，課程名稱， 成績，所屬專業(yè)）成績，所屬專業(yè)） 教員信息關(guān)系（教員編號，教員名稱，性別，教員信息關(guān)系（教員編號，教員名稱，性別， 出生年月，職稱，教研室名稱）出生年月，職稱，教研室名稱） 由表由表6.1可直接得到如下關(guān)系模式：可直接得到如下關(guān)系模式： 學(xué)生學(xué)籍關(guān)系（學(xué)號，姓名，性別，出生年月，學(xué)生學(xué)籍關(guān)系（學(xué)號，姓名，性

5、別，出生年月， 籍貫，班級，所屬專業(yè)）籍貫，班級，所屬專業(yè)） 考試成績關(guān)系（學(xué)號，姓名，課程編號，課程名稱，考試成績關(guān)系（學(xué)號，姓名，課程編號，課程名稱， 成績，所屬專業(yè)）成績，所屬專業(yè)） 教員信息關(guān)系（教員編號，教員名稱，性別，教員信息關(guān)系（教員編號，教員名稱，性別， 出生年月，職稱，教研室名稱）出生年月，職稱，教研室名稱） 至少存在有至少存在有2種種 由一些屬性值決定教研室名由一些屬性值決定教研室名 稱屬性值的數(shù)據(jù)依賴關(guān)系。稱屬性值的數(shù)據(jù)依賴關(guān)系。 ),(FDOMDUR ( (教工號教工號, ,姓名姓名, ,職稱職稱, ,教研室，教研室， 課程號課程號, ,課程名課程名, ,學(xué)時學(xué)時) )

6、 數(shù)據(jù)之間存在著一定的數(shù)據(jù)依賴關(guān)系，其實(shí)質(zhì)即數(shù)據(jù)之間存在著一定的數(shù)據(jù)依賴關(guān)系，其實(shí)質(zhì)即 是函數(shù)依賴。是函數(shù)依賴。 進(jìn)行關(guān)系模式分解。進(jìn)行關(guān)系模式分解。 教員任課教員任課( (教工號教工號, ,姓名姓名, ,職稱職稱, ,教研室，課程號教研室，課程號, ,課程名課程名, ,學(xué)時學(xué)時) ) 定義定義6.16.1 設(shè)有關(guān)系模式設(shè)有關(guān)系模式R(AR(A1 1,A,A2 2, ,A,An n) )和屬性集和屬性集 U=AU=A1 1,A,A2 2, ,A,An n 的子集的子集X X、Y Y。如果對于任一具體關(guān)。如果對于任一具體關(guān) 系系r r的任何兩個元組的任何兩個元組u u和和v v，只要，只要uX=

7、vXuX=vX，就有，就有 uY=vYuY=vY，則稱，則稱X X函數(shù)地決定函數(shù)地決定Y Y，或，或Y Y函數(shù)依賴函數(shù)依賴X X，記，記 為為X XY Y。 例如：例如： 由上面的定義和例子說明：由上面的定義和例子說明： 函數(shù)依賴描述了每個關(guān)系中主鍵屬性與非主函數(shù)依賴描述了每個關(guān)系中主鍵屬性與非主 鍵屬性之間的關(guān)系。對于關(guān)系鍵屬性之間的關(guān)系。對于關(guān)系和和 XYXY來說，屬性子集來說，屬性子集X X中包括，且僅僅包括了關(guān)中包括，且僅僅包括了關(guān) 系系R R的主鍵屬性，且對于關(guān)系的任何屬性子集的主鍵屬性，且對于關(guān)系的任何屬性子集Y Y， 一定成立一定成立XYXY。 對于對于XYXY，可能存在，可能存

8、在Y Y X X、 兩兩 種情況。種情況。 YX 若有若有X XY Y，且，且 ，稱，稱X XY Y為非平凡函為非平凡函 數(shù)依賴數(shù)依賴; ; 若有若有X XY Y，且，且Y Y X X，稱，稱X XY Y為平凡函數(shù)依賴。為平凡函數(shù)依賴。 YX 若若X XY Y，則稱，則稱X X為決定因素。為決定因素。 若若Y Y不依賴于不依賴于X X，則記作，則記作X Y X Y 。 若同時有若同時有X XY Y和和Y YX X成立，則記為成立，則記為X YX Y。 S S（S#S#，SNAMESNAME，SSEXSSEX，SBIRTHINSBIRTHIN，PLACEOFB, SCODE#PLACEOFB,

9、SCODE#，CLASSCLASS， SNOSNAMESNOSNAME，SSEXSSEX，SBIRTHINSBIRTHIN，PLACEOFB, SCODEPLACEOFB, SCODE，CLASSCLASS） SSSS（SCODE#SCODE#，SSNAMESSNAME，SCODE#SSNAMESCODE#SSNAME） C C（C#C#，CNAMECNAME，CLASSH CLASSH ，C#CNAMEC#CNAME，CLASSH CLASSH ） CSCS（SCODE#SCODE#，C#C#，SCODE#, C# SCODE#, C#SCODE#, C# SCODE#, C#） SCSC（

10、S#S#，C#C#，GRADE GRADE ， S# S#，C# GRADE C# GRADE ） T T（T#T#，TNAMETNAME，TSEXTSEX，TBIRTHINTBIRTHIN，TITLEOFTITLEOF，TRSECTIONTRSECTION，TELTEL， TNOTNAMETNOTNAME，TSEXTSEX，TBIRTHINTBIRTHIN，TITLEOFTITLEOF，TRSECTIONTRSECTION，TELTEL） TEACHTEACH（ T# T#，C#C#， T# T#，C# T#C# T#，C#C#） 定義定義5.25.2 設(shè)有關(guān)系模式設(shè)有關(guān)系模式R(UR(U，

11、F)F)，X X、Y Y是屬性是屬性 集集U=AU=A1 1,A,A2 2, ,A,An n 的子集，如果從的子集，如果從 中的函數(shù)依賴中的函數(shù)依賴 能夠推導(dǎo)出能夠推導(dǎo)出X XY Y，則稱，則稱F F邏輯蘊(yùn)涵邏輯蘊(yùn)涵X XY Y，或稱，或稱X XY Y 是是F F的邏輯蘊(yùn)涵。的邏輯蘊(yùn)涵。 所有被所有被F F邏輯蘊(yùn)涵的函數(shù)依賴組成的依賴集稱為邏輯蘊(yùn)涵的函數(shù)依賴組成的依賴集稱為 F F的閉包，記為的閉包，記為F F+ +。 F F+ +中的元素是函數(shù)依賴；中的元素是函數(shù)依賴； 如果能計(jì)算出如果能計(jì)算出F F+ +，就可以很方便地判斷，就可以很方便地判斷 某個函數(shù)依賴是否被某個函數(shù)依賴是否被F F+

12、 +邏輯蘊(yùn)涵。邏輯蘊(yùn)涵。 F 舉例：舉例： 能夠唯一地標(biāo)識一個關(guān)系中不同元組的一個能夠唯一地標(biāo)識一個關(guān)系中不同元組的一個 屬性集合；屬性集合； 該屬性集中不含有多余的屬性。該屬性集中不含有多余的屬性。 設(shè)有關(guān)系模式設(shè)有關(guān)系模式R(AR(A 1 1 ,A,A 2 2 , ,A,A n n ) )和屬性集和屬性集 U=AU=A1 1,A,A2 2, ,A,An n 的子集的子集X X、Y Y，F(xiàn) F是是R R的的函數(shù)依賴集。的的函數(shù)依賴集。 如果：如果： XA XA1 1A A2 2A An n屬于屬于F F+ +； 不存在不存在X X的真子集的真子集X X，使，使X XAA1 1A A2 2A

13、An nFF+ +， 則稱則稱X X是是R R的一個候選鍵。的一個候選鍵。 舉例舉例 在課程關(guān)系在課程關(guān)系 中，有中，有 依賴集依賴集 F=C# F=C# CNAMECNAME，CLASSHCLASSH ，判斷候選鍵。，判斷候選鍵。 因?yàn)橐驗(yàn)?F F中的唯一的函數(shù)依賴的決定因素中的唯一的函數(shù)依賴的決定因素C#C#已已 經(jīng)是單個屬性了，所以經(jīng)是單個屬性了，所以C#C#是唯一的候選建。當(dāng)然是唯一的候選建。當(dāng)然 也就是主鍵了。也就是主鍵了。 由前述內(nèi)容可知，對于關(guān)系模式由前述內(nèi)容可知，對于關(guān)系模式 來說，關(guān)來說，關(guān) 系的主鍵實(shí)質(zhì)上是由其依賴集系的主鍵實(shí)質(zhì)上是由其依賴集 中的函數(shù)依賴的決定中的函數(shù)依賴

14、的決定 因素確定的。因素確定的。 ),(FUR F ),(FUR F FXYXY F F F 作用作用：用于從給定的函數(shù)依賴集中推導(dǎo)出被用于從給定的函數(shù)依賴集中推導(dǎo)出被 其蘊(yùn)涵的函數(shù)依賴。其蘊(yùn)涵的函數(shù)依賴。 條件：條件： 合并規(guī)則合并規(guī)則：若若X XY Y且且X XZ Z，則，則X XYZYZ 分解規(guī)則分解規(guī)則：若若X XY Y，且，且Z Z Y Y，則，則X XZ Z 偽傳遞規(guī)則偽傳遞規(guī)則：若若X XY Y且且WYWYZ Z，則，則WXWXZ Z 1 1、合并規(guī)則：、合并規(guī)則：若若X XY Y且且X XZ Z，則，則X XYZYZ 證明：證明： 由條件由條件XYXY，并增廣律可得，并增廣律可

15、得XXYXXY。 由條件由條件XZXZ，并增廣律可得，并增廣律可得XYYZXYYZ。 利用傳遞律，由利用傳遞律，由XXYXXY和和XYYZXYYZ，可得，可得 XYZXYZ。 2 2、分解規(guī)則、分解規(guī)則：若若X XY Y，且，且Z Z Y Y，則，則X XZ Z 證明：證明： 已知有已知有XYXY。 由條件由條件Z Z Y Y，并自反律可得，并自反律可得YZYZ。 利用傳遞律，由利用傳遞律，由XYXY和和YZYZ，可得，可得ZZZZ。 3 3、偽傳遞規(guī)則、偽傳遞規(guī)則：若若X XY Y且且WYWYZ Z，則，則WXWXZ Z 證明：證明： 由條件由條件XYXY，并增廣律可得，并增廣律可得WXWY

16、WXWY。 利用傳遞律，和已知條件利用傳遞律，和已知條件WYZWYZ，可得，可得 WXZWXZ。 對于關(guān)系模式對于關(guān)系模式(CITY(CITY，STST，ZIP)ZIP)，依賴集，依賴集 候選鍵為候選鍵為CITYCITY，STST和和 STST，ZIPZIP。證明有。證明有: :ST ZIPST ZIPCITY,ST,ZIPCITY,ST,ZIP 和和CITY,STCITY,STCITY,ST,ZIPCITY,ST,ZIP?，F(xiàn)證明前者。現(xiàn)證明前者。 如果如果A Ai i(i=1,2(i=1,2,n),n)是關(guān)系模式是關(guān)系模式R R 的屬性的屬性, ,則則X XA A1 1A A2 2A An

17、n成立的充分必要條件是成立的充分必要條件是 X XA Ai i(i=1,(i=1,n),n)均成立。均成立。 充分性證明：充分性證明：由條件推出結(jié)論；由條件推出結(jié)論； 必要性證明：必要性證明：假設(shè)結(jié)論成立，推出條件成立。假設(shè)結(jié)論成立，推出條件成立。 已知關(guān)系模式已知關(guān)系模式R(A,B,C)R(A,B,C)上有函數(shù)依賴集上有函數(shù)依賴集 F=AF=AB,BB,BCC，求，求X X分別等于分別等于A A、B B、C C時的時的X X+ +。 解：解： 設(shè)有關(guān)系模式設(shè)有關(guān)系模式R(UR(U，F(xiàn))F)和屬性集和屬性集U=AU=A1 1， A A2 2，A An n 的子集的子集X X、Y Y。則。則X

18、XY Y能用阿姆斯特朗能用阿姆斯特朗 公理從公理從F F導(dǎo)出的充分必要條件是導(dǎo)出的充分必要條件是。 從給定的屬性集從給定的屬性集X X出發(fā)（出發(fā)（設(shè)設(shè)X XX X） 如果發(fā)現(xiàn)如果發(fā)現(xiàn)X X包含了包含了F F中的某個函數(shù)依賴左中的某個函數(shù)依賴左 邊的屬性，就把該依賴右邊的屬性添加到邊的屬性，就把該依賴右邊的屬性添加到X X中。中。 即對于即對于F F中的所有中的所有V VW W，若有，若有V V X X，則有，則有 X X=X=XW W。 循環(huán)第步的過程不斷擴(kuò)充循環(huán)第步的過程不斷擴(kuò)充X X，直到該集，直到該集 合再也無法擴(kuò)展時，得到的結(jié)果就是合再也無法擴(kuò)展時，得到的結(jié)果就是X X 。 。 輸入：

19、輸入：關(guān)系模式關(guān)系模式R R的全部屬性集的全部屬性集U,UU,U上的函數(shù)依賴上的函數(shù)依賴 集集F F，U U的子集的子集X X。 輸出：輸出：X X關(guān)于關(guān)于F F的閉包的閉包X X 。 。 方法：方法：（1 1）X X(0) (0)=X =X。 （2 2）從）從F F中找出滿足條件中找出滿足條件V V X X(i) (i)的所有函數(shù)依賴 的所有函數(shù)依賴 VWVW，并把所有的，并把所有的VWVW中的屬性中的屬性W W組成的集合記為組成的集合記為Z Z； 也即從也即從F F中找出那些其決定因素是中找出那些其決定因素是X X(i) (i)的子集的函數(shù)依 的子集的函數(shù)依 賴，并由這些函數(shù)依賴的被決定因

20、素組成一個集合，賴，并由這些函數(shù)依賴的被決定因素組成一個集合， 設(shè)其（被記為）設(shè)其（被記為）Z Z。 （3 3）若）若Z Z X X(i) (i)，則轉(zhuǎn)（ ，則轉(zhuǎn)（5 5）。）。 （4 4）否則，）否則，X X(i+1) (i+1)=X =X(i) (i)Z Z，并轉(zhuǎn)（ ，并轉(zhuǎn)（2 2）。）。 （5 5）停止計(jì)算，輸出）停止計(jì)算，輸出X X(i) (i)，即為 ，即為X X+ +。 例例6.46.4 已知有函數(shù)依賴集已知有函數(shù)依賴集 F=ABC, BCD, F=ABC, BCD, ACDB,DEG,BECACDB,DEG,BEC，屬性集，屬性集U=A,B,C,D,E,GU=A,B,C,D,E,

21、G， 且且X=BDX=BD，求，求X X 。 。 解：解： 輸入：輸入：關(guān)系模式關(guān)系模式R R的全部屬性集的全部屬性集U,UU,U上的函數(shù)依賴上的函數(shù)依賴 集集F F，U U的子集的子集X X。 輸出：輸出：X X關(guān)于關(guān)于F F的閉包的閉包X X 。 。 方法：方法：（1 1）X X(0) (0)=X =X。 （2 2）從）從F F中找出滿足條件中找出滿足條件V V X X(i) (i)的所有函數(shù)依賴 的所有函數(shù)依賴 VWVW，并把所有的，并把所有的VWVW中的屬性中的屬性W W組成的集合記為組成的集合記為Z Z； 也即從也即從F F中找出那些其決定因素是中找出那些其決定因素是X X(i) (

22、i)的子集的函數(shù)依 的子集的函數(shù)依 賴，并由這些函數(shù)依賴的被決定因素組成一個集合，賴，并由這些函數(shù)依賴的被決定因素組成一個集合， 設(shè)其（被記為）設(shè)其（被記為）Z Z。 （3 3）若）若Z Z X X(i) (i)，則轉(zhuǎn)（ ，則轉(zhuǎn)（5 5）。）。 （4 4）否則，）否則，X X(i+1) (i+1)=X =X(i) (i)Z Z，并轉(zhuǎn)（ ，并轉(zhuǎn)（2 2）。）。 （5 5）停止計(jì)算，輸出）停止計(jì)算，輸出X X(i) (i)，即為 ，即為X X+ +。 U=A,B,C,D,E,G F=ABC, BCD,ACDB,DEG,BEC X=BD 定義定義6.56.5 定理定理6.46.4 根據(jù)集合運(yùn)算規(guī)則根

23、據(jù)集合運(yùn)算規(guī)則 推論推論6.46.4 每一個函數(shù)依賴集都被其右端只每一個函數(shù)依賴集都被其右端只 有一個屬性的函數(shù)依賴組成的依賴集所覆蓋。有一個屬性的函數(shù)依賴組成的依賴集所覆蓋。 推論推論6.46.4證明的主要理論根據(jù)：證明的主要理論根據(jù)：分解規(guī)則與分解規(guī)則與 合并過則。合并過則。 滿足下列條件的函數(shù)依賴集滿足下列條件的函數(shù)依賴集F F稱為稱為 最小函數(shù)依賴集。最小函數(shù)依賴集。 F F中每一個函數(shù)依賴的右端都是單個屬性；中每一個函數(shù)依賴的右端都是單個屬性； 對對F F中任何函數(shù)依賴中任何函數(shù)依賴X XA A，F(xiàn)-XF-XAA不等不等 價于價于F;F; 對對F F中的任何函數(shù)依賴中的任何函數(shù)依賴X

24、 XA A和和X X的任何真子的任何真子 集集Z Z，(F-X(F-XA)ZA)ZAA不等價于不等價于F F。 用分解規(guī)則將用分解規(guī)則將F F中的所有函數(shù)依賴分解成右端中的所有函數(shù)依賴分解成右端 為單個屬性的函數(shù)依賴；為單個屬性的函數(shù)依賴； 去掉去掉F F中冗余的函數(shù)依賴，即對于中冗余的函數(shù)依賴，即對于F F中任一函中任一函 數(shù)依賴數(shù)依賴X XY Y： 設(shè)設(shè)G = F-XG = F-XYY； 求求X X關(guān)于關(guān)于G G的閉包的閉包X XG G+ +； 看看X XG G+ +是否包含是否包含Y Y。如果。如果X XG G+ +包含包含Y Y，則在，則在G G中邏輯中邏輯 蘊(yùn)涵蘊(yùn)涵X XY Y，說明

25、，說明X XY Y是多余的函數(shù)依賴，從而可得到是多余的函數(shù)依賴，從而可得到 較小的函數(shù)依賴集較小的函數(shù)依賴集F=GF=G；如果；如果X XG G+ +不包含不包含Y Y，則保留，則保留X XY Y。 按上述方法逐個考察按上述方法逐個考察F F中的每一個函數(shù)依賴中的每一個函數(shù)依賴, ,直直 到其中所有函數(shù)依賴都考察完為止。到其中所有函數(shù)依賴都考察完為止。 注注： 去掉去掉 F F 中函數(shù)依賴左端多余的屬性，即對于中函數(shù)依賴左端多余的屬性，即對于F F中中 左端左端的函數(shù)依賴（的函數(shù)依賴（XYXYA A），要判斷），要判斷X X或或Y Y是是 不是多余的屬性。不是多余的屬性。當(dāng)要判斷當(dāng)要判斷Y Y

26、是否是多余的屬性時是否是多余的屬性時： 設(shè)設(shè)G = (F-XYG = (F-XYA)XA)XAA； 求求XYXY關(guān)于關(guān)于G G的閉包，（的閉包，（XY)XY)G G+ +； 如果如果 (XY) (XY)G G+ +包含包含A A，則說明，則說明 Y Y是多余的屬性，是多余的屬性， 從而可得到較小的函數(shù)依賴集從而可得到較小的函數(shù)依賴集F=GF=G；如果；如果(XY)(XY)G G+ +不包含不包含A A， 則說明則說明XYXYA A不被不被G G邏輯隱含邏輯隱含，說明說明 Y Y不是多余的屬性。不是多余的屬性。 或者或者 求求X X關(guān)于關(guān)于F F的閉包，的閉包， （X)X)F F+ + ； 如果

27、如果（X)X)F F+ +包含包含A A，則，則Y Y是多余屬性是多余屬性 當(dāng)當(dāng)Y Y不是多余屬性時，要接著用類似的方法判斷不是多余屬性時，要接著用類似的方法判斷X X 是不是多余的屬性（是不是多余的屬性（ ）。）。 如果如果X X和和Y Y都不是多余的屬性時，則保留該函數(shù)依都不是多余的屬性時，則保留該函數(shù)依 賴賴XYXYA A。 接著按上述方法逐個考察接著按上述方法逐個考察F F中左端是非單屬性的中左端是非單屬性的 其他函數(shù)依賴，直到其中的所有左端是非單屬性的函數(shù)其他函數(shù)依賴，直到其中的所有左端是非單屬性的函數(shù) 依賴都考察完為止。依賴都考察完為止。 求函數(shù)依賴集求函數(shù)依賴集F F的最小函數(shù)依

28、賴集，其中的最小函數(shù)依賴集，其中: : 求函數(shù)依賴集求函數(shù)依賴集F F的最小函數(shù)依賴集。的最小函數(shù)依賴集。 即試著去掉即試著去掉F1F1中的每中的每 一個函數(shù)依賴，看它是否被一個函數(shù)依賴，看它是否被F1F1中剩余的函數(shù)依賴蘊(yùn)含。中剩余的函數(shù)依賴蘊(yùn)含。 對于對于ABABC C，求，求ABAB關(guān)于關(guān)于F F1 1-AB-ABCC的閉包。的閉包。 顯然，對于顯然，對于(AB)(AB)(0) (0)=AB =AB，在，在F F1 1-AB-ABCC中不存在決中不存在決 定因素是定因素是ABAB的子集的函數(shù)依賴，也即有的子集的函數(shù)依賴，也即有(AB)(AB)+ +=AB=AB，且，且 C (AB)C (

29、AB)+ +，所以，所以ABABC C不多余。不多余。 F1= 求函數(shù)依賴集求函數(shù)依賴集F F的最小函數(shù)依賴集。的最小函數(shù)依賴集。 對于對于ACDACDB B，求，求ACDACD關(guān)于關(guān)于F F1 1-ACD-ACDB B 的閉包。的閉包。 由于對于由于對于(ACD)(ACD)+ +=ABCDEG=ABCDEG，且，且B B (ACD)(ACD)+ +=ABCDEG,=ABCDEG, 所以所以ACDACDB B是多余的。是多余的。 按照上述思路依次考察按照上述思路依次考察F F1 1中的每個函數(shù)依賴，可中的每個函數(shù)依賴，可 得：得： F1= 求函數(shù)依賴集求函數(shù)依賴集F F的最小函數(shù)依賴集。的最小

30、函數(shù)依賴集。 解：解： ABABC C，C CA A，BCBCD D， D DE E，D DG G，BEBEC C， CGCGB B，CECEG G F21= ABABC C，C CA A，BCBCD D， ACDACDB B，D DE E，D DG G， BEBEC C，CGCGD D，CECEG G F22= 求函數(shù)依賴集求函數(shù)依賴集F F的最小函數(shù)依賴集。的最小函數(shù)依賴集。 F Fmin min= = 或或 F Fmin min= = ABABC C，C CA A，BCBCD D， D DE E，D DG G，BEBEC C CGCGB B，CECEG G ABABC C，C CA A，

31、BCBCD D， CDCDB B，D DE E，D DG G， BEBEC C，CGCGD D，CECEG G 本章的本章的6.26.2節(jié)所述，為了消除某些關(guān)系節(jié)所述，為了消除某些關(guān)系 模式可能存在的數(shù)據(jù)冗余、插入異常、刪除異模式可能存在的數(shù)據(jù)冗余、插入異常、刪除異 常和修改異常，就需要對這些關(guān)系模式進(jìn)行分常和修改異常，就需要對這些關(guān)系模式進(jìn)行分 解。解。 設(shè)設(shè)U Ui i是屬性集是屬性集U U的一個子集，則函數(shù)的一個子集，則函數(shù) 依賴集合依賴集合XY|XYXY|XY F F+ +XYXY U Ui i 的一個覆蓋的一個覆蓋F Fi i， 稱為稱為F F在在U Ui i上的投影。上的投影。 定

32、義定義6.76.7的含義和要說明的問題：的含義和要說明的問題： 對于屬性集對于屬性集U U的子集的子集U Ui i，存在一個與其對應(yīng)的依賴，存在一個與其對應(yīng)的依賴 子集子集F Fi i，且由，且由F Fi i中的每個函數(shù)依賴中的每個函數(shù)依賴XYXY的決定因素的決定因素X X和和 被決定因素被決定因素Y Y組成的屬性子集組成的屬性子集XYXY均是均是U Ui i的子集。的子集。 設(shè)有關(guān)系模式設(shè)有關(guān)系模式R(UR(U，F(xiàn))F)和和 U=A1,A2,U=A1,A2,An,An的子集的子集Z Z，把，把F F+ +中所有滿足中所有滿足XYXY Z Z 的函數(shù)依賴的函數(shù)依賴XYXY組成的集合，稱為依賴集

33、組成的集合，稱為依賴集F F在屬性在屬性 集集Z Z上的投影，記為上的投影，記為z z(F)(F)。 由定義由定義5.85.8知，顯然有：知，顯然有： z z(F)(F)XY|XYXY|XY F F+ +，且，且XYXY ZZ 所以定義所以定義5.85.8和定義和定義5.75.7本質(zhì)上是相同的。本質(zhì)上是相同的。 設(shè)有關(guān)系模式設(shè)有關(guān)系模式R(U,F)R(U,F)，如果，如果U=UU=U1 1UU2 2 UUk k，并且對于任意的，并且對于任意的i,j(1i,jk)i,j(1i,jk)，不成，不成 立立U Ui i U Uj j，且，且F Fi i是是F F在在U Ui i上的投影，則稱：上的投影

34、，則稱： =R =R1 1(U(U1 1,F,F1 1) )，R R2 2(U(U2 2,F,F2 2) )，R Rk k(U(Uk k,F,Fk k) 是關(guān)系模式是關(guān)系模式R(U,F)R(U,F)的一個分解。的一個分解。 例例6.6 6.6 設(shè)有關(guān)系模式設(shè)有關(guān)系模式R(U,F)R(U,F)，U=S#,SD,SMU=S#,SD,SM， F=S#SD,SDSMF=S#SD,SDSM，并設(shè)關(guān)系，并設(shè)關(guān)系R R有如下表的當(dāng)前值有如下表的當(dāng)前值 r r。 下面采用三種不同方法對關(guān)系下面采用三種不同方法對關(guān)系R R進(jìn)行分解。進(jìn)行分解。 F=S#SD,SDSMF=S#SD,SDSM 設(shè)：設(shè)：11R1(S#

35、,)R1(S#,)，R2(SD,)R2(SD,)，R3(SM,)R3(SM,) 即有，即有，F(xiàn) Fi i= = 和和 R Ri i=i i(R(U) (R(U) 對于已知關(guān)系對于已知關(guān)系r r在在i i(R(U)(R(U)上的投影，有：上的投影，有： r1=S1,S2,S3 r1=S1,S2,S3 r2=D1,D2,D3 r2=D1,D2,D3 r3=M1,M2 r3=M1,M2 S1 D1 M1， S2 D1 M1， S3 D1 M1， S1 D1 M2， S2 D1 M2， S3 D1 M2， S1 D2 M1， S2 D2 M1， S3 D2 M1， S1 D2 M2， S2 D2 M2

36、， S3 D2 M2， S1 D3 M1， S2 D3 M1， S3 D3 M1， S1 D3 M2， S2 D3 M2， S3 D3 M2 對關(guān)系模式的分解，理應(yīng)要求分解后的各關(guān)系能恢對關(guān)系模式的分解，理應(yīng)要求分解后的各關(guān)系能恢 復(fù)原關(guān)系的原值，一般采用自然聯(lián)接方法恢復(fù)可得：復(fù)原關(guān)系的原值，一般采用自然聯(lián)接方法恢復(fù)可得： r1r1 r2r2 r3rr3r r1 r2 r3=r1 r1 r2 r3=r1r2r2r3r3 聯(lián)接結(jié)果為：聯(lián)接結(jié)果為： 比較關(guān)系比較關(guān)系R R原來的當(dāng)前值：原來的當(dāng)前值： 和向和向R1R1、R2 R2 和和 R3 R3投影后，再聯(lián)接恢復(fù)的值：投影后，再聯(lián)接恢復(fù)的值： S

37、1 D1 M1， S2 D1 M1， S3 D1 M1， S1 D1 M2， S2 D1 M2， S3 D1 M2， S1 D2 M1， S2 D2 M1， S3 D2 M1， S1 D2 M2， S2 D2 M2， S3 D2 M2， S1 D3 M1， S2 D3 M1， S3 D3 M1， S1 D3 M2， S2 D3 M2， S3 D3 M2 設(shè)設(shè):2=R1(S#,SD,S#:2=R1(S#,SD,S# SD),R2(S#,SM,S#SM)SD),R2(S#,SM,S#SM) 因?yàn)橛校阂驗(yàn)橛校?S#， S# SD，SD, S#S#， S# SDS#，SDSD, = S#SD， S#

38、SDSD， S#S# SD，S# SDS# SD 1 F S#， S# SM，SM, S#S#， S# SMS#，SMSM, = S#SM， S# SMSM， S#S# SM，S# SMS# SM 2 F 分析可知，原分析可知，原F F中的中的SDSM SDSM 均不在上面均不在上面2 2個閉包中，即：個閉包中，即： F1F2F1F2不等于不等于F F，但可以證明成立：，但可以證明成立： r1 r2 = r r1 r2 = r F=S#SD,SDSM 設(shè)設(shè): :2=R1(S#,SD,S#SD),2=R1(S#,SD,S#SD), R2(SD,SM,SDSM) R2(SD,SM,SDSM) 因?yàn)?/p>

39、有：因?yàn)橛校?r1=(S1,D1),(S2,D2),(S3,D3) r1=(S1,D1),(S2,D2),(S3,D3)； F1 F1S#SD S#SD r2=(D1,M1),(D2,M1),(D3,M2) r2=(D1,M1),(D2,M1),(D3,M2)； F2 F2SDSMSDSM 可以證明成立：可以證明成立： r1 r2=r r1 r2=r 和和 F1F2 = F F1F2 = F 定義5.10 設(shè)有關(guān)系模式設(shè)有關(guān)系模式R(U,F)R(U,F)，=（R R1 1,R,R2 2, , ,R,Rk k）是）是R R的一個分解。如果對于的一個分解。如果對于R R的任一滿足的任一滿足F F的

40、的 關(guān)系關(guān)系r r，成立：，成立： r= r=R1 R1(r) (r) R2 R2(r) (r) Rk Rk(r) (r) 則稱分解則稱分解是無損聯(lián)接分解。也稱該分解是無損聯(lián)接分解。也稱該分解是保持是保持 無損的分解。無損的分解。 判斷一個分解的無損聯(lián)接性判斷一個分解的無損聯(lián)接性 關(guān)系模式關(guān)系模式R(A1,R(A1,An),An)，函數(shù)依賴集，函數(shù)依賴集F F， R R的一個分解的一個分解(R(R1 1,R,R2 2, ,R,Rk k) )。 是否為無損聯(lián)接的判斷。是否為無損聯(lián)接的判斷。 判斷一個分解的無損聯(lián)接性判斷一個分解的無損聯(lián)接性 構(gòu)造一個構(gòu)造一個k k行行n n列列表表S S。其中，第

41、。其中，第i i行對應(yīng)于行對應(yīng)于 關(guān)系模式關(guān)系模式R R分解后的模式分解后的模式R Ri i，第，第j j列對應(yīng)于關(guān)系模式列對應(yīng)于關(guān)系模式 R R的屬性的屬性A Aj j。表中第。表中第i i行第行第j j列位置的元素填入方法列位置的元素填入方法 為：如果為：如果A Aj j在在R Ri i中，則在第中，則在第i i行第行第j j列的位置上填上列的位置上填上 符號符號a aj j, ,否則填上符號否則填上符號b bij ij。 。 對于對于F F中的所有函數(shù)依賴中的所有函數(shù)依賴XYXY，在表中尋找，在表中尋找 在在X X的各個屬性上都分別相同的行，若至少存在兩個的各個屬性上都分別相同的行，若至

42、少存在兩個 或多個這樣的行，則將這些行上對應(yīng)的或多個這樣的行，則將這些行上對應(yīng)的Y Y屬性上的元屬性上的元 素值，修改成具有相同符號的元素值，修改方法為：素值，修改成具有相同符號的元素值，修改方法為： 當(dāng)這些行的當(dāng)這些行的Y Y屬性上的某一行上都為屬性上的某一行上都為a aj j（j j為為Y Y 屬性對應(yīng)的那些列的列序號，且屬性對應(yīng)的那些列的列序號，且j=1,2,j=1,2,n,n）時，）時， 則把該行的則把該行的Y Y屬性上的其它元素都修改成屬性上的其它元素都修改成a aj j； 當(dāng)這些行的當(dāng)這些行的Y Y屬性列中沒有這樣的屬性列中沒有這樣的a aj j時，則以時，則以 Y Y屬性列中下標(biāo)

43、較小的屬性列中下標(biāo)較小的b bij ij為基準(zhǔn)，把這些行的 為基準(zhǔn)，把這些行的Y Y屬性屬性 列上的其它元素都修改成列上的其它元素都修改成b bij ij。 。 按按(2)(2)逐個考察逐個考察F F中的每一個函數(shù)依賴，如中的每一個函數(shù)依賴，如 果發(fā)現(xiàn)某一行變成了果發(fā)現(xiàn)某一行變成了a a1 1，a a2 2，a an n，則分解，則分解具有具有 無損聯(lián)接性；如果直到檢驗(yàn)完無損聯(lián)接性；如果直到檢驗(yàn)完F F中的所有函數(shù)依賴也中的所有函數(shù)依賴也 沒有發(fā)現(xiàn)有這樣的行，表也不再變化，則分解沒有發(fā)現(xiàn)有這樣的行，表也不再變化，則分解不不 具有無損聯(lián)接性。具有無損聯(lián)接性。 設(shè)設(shè)R(ABCDE)R(ABCDE)

44、，F(xiàn)=AC,BC,CD,DEC,CEA,F=AC,BC,CD,DEC,CEA, 分解分解=R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE),=R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE),檢驗(yàn)檢驗(yàn) 分解分解是否具有無損聯(lián)接性。是否具有無損聯(lián)接性。 R(ABCDE)R(ABCDE)， F=AC,BC,CD,DEC,CEA, F=AC,BC,CD,DEC,CEA, =R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE)=R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE) 解：解：第一步，構(gòu)造表第一步，構(gòu)造表S S

45、。 第二步：第二步： 根據(jù)函數(shù)依賴根據(jù)函數(shù)依賴ACAC修正表修正表S S。 第二步：第二步： 根據(jù)函數(shù)依賴根據(jù)函數(shù)依賴BCBC修正表修正表S S。 第二步：第二步： 根據(jù)函數(shù)依賴根據(jù)函數(shù)依賴CDCD修正表修正表S S。 第二步：第二步： 根據(jù)函數(shù)依賴根據(jù)函數(shù)依賴DECDEC修正表修正表S S。 第二步：第二步： 根據(jù)函數(shù)依賴根據(jù)函數(shù)依賴CEACEA修正表修正表S S。 第三步：通過判斷，給出結(jié)論。第三步：通過判斷，給出結(jié)論。 第三步：通過判斷，給出結(jié)論。第三步：通過判斷，給出結(jié)論。 表中的第三行都變成表中的第三行都變成a aj j了，所以分解了，所以分解具有無損具有無損 聯(lián)接性。聯(lián)接性。 設(shè)有

46、關(guān)系模式設(shè)有關(guān)系模式R(U,F)R(U,F)，=(R1=(R1，R2)R2) 是是R R的一個分解，當(dāng)且僅當(dāng)?shù)囊粋€分解，當(dāng)且僅當(dāng): : (R1R2)( (R1R2)()F)F+ + 或或 (R2R1)(R2R1)()F)F+ + 時，時，具有無損聯(lián)接性。具有無損聯(lián)接性。 設(shè)有關(guān)系模式設(shè)有關(guān)系模式R(A,B,C)R(A,B,C)，函數(shù)依賴集，函數(shù)依賴集 F=ABF=AB，CBCB，分解，分解=R1,R2=R1,R2，其中，其中R1=ABR1=AB， R2=BCR2=BC。檢驗(yàn)分解。檢驗(yàn)分解是否具有無損聯(lián)接性。是否具有無損聯(lián)接性。 解：解： 在例在例5.65.6中，已知有關(guān)系模式中，已知有關(guān)系模式

47、 (S#(S#，SDSD，SM)SM)，函數(shù)依賴集，函數(shù)依賴集=S#SD=S#SD，SDSMSDSM。 且對于其中的方法且對于其中的方法(3)(3)，已知有分解，已知有分解=(S#,SD)=(S#,SD)， (SD,SM)(SD,SM)，且已指出分解是無損聯(lián)接分解，下面，且已指出分解是無損聯(lián)接分解，下面 進(jìn)行驗(yàn)證。進(jìn)行驗(yàn)證。 解：解： 對于對于關(guān)系模式關(guān)系模式R(U,F)R(U,F)，保持無損性討論的是，保持無損性討論的是 R(U)R(U)被分解成多個是被分解成多個是R Ri i時的信息保持問題。時的信息保持問題。 對于對于R(F)R(F)，同樣存在分解成多個，同樣存在分解成多個R Ri i時

48、，對應(yīng)的時，對應(yīng)的 R(FR(Fi i) )是否成立，以及能否保持原來是否成立，以及能否保持原來F F的依賴性問題。的依賴性問題。 設(shè)有關(guān)系模式設(shè)有關(guān)系模式R(U,F)R(U,F)，= （R1,R2,R1,R2,Rk,Rk）是）是R R的一個分解。如果所有函數(shù)依的一個分解。如果所有函數(shù)依 賴集賴集Ri Ri(F)(i=1,2, (F)(i=1,2,，k k）的并集邏輯蘊(yùn)含）的并集邏輯蘊(yùn)含F(xiàn) F中的中的 每一個函數(shù)依賴，則稱分解每一個函數(shù)依賴，則稱分解具有依賴保持性，也具有依賴保持性，也 即分解即分解保持依賴集保持依賴集F F。即：。即： k i R FF i 1 | )( 對對中的每一個中的每

49、一個R Ri i求求Ri Ri(F) (F) 求求 對對F F中每一個函數(shù)依賴中每一個函數(shù)依賴XYXY， 判斷能否由判斷能否由 導(dǎo)出，如果均能導(dǎo)出，則分解導(dǎo)出，如果均能導(dǎo)出，則分解具有依賴保具有依賴保 持性；否則分解持性；否則分解不具有依賴保持性。不具有依賴保持性。 k i R F i 1 )( k i R F i 1 )( 例例6.11 6.11 已知有關(guān)系模式已知有關(guān)系模式 R(S#,SD,SM) R(S#,SD,SM)和函數(shù)依賴集和函數(shù)依賴集 F=S#SD,SDSM F=S#SD,SDSM，且知有分解，且知有分解: : 3=R1(S#,SD,S#SD),R2(SD,SM,SDS3=R1(

50、S#,SD,S#SD),R2(SD,SM,SDS M)M)。驗(yàn)證分解。驗(yàn)證分解33是保持依賴的分解。是保持依賴的分解。 F #)()( 21 SMSDSDSFF RR 因?yàn)?,#SMSDSDS 3 所以， 具有保持依賴性。 例例6.12 6.12 已知有關(guān)系模式已知有關(guān)系模式R(S#,SD,SM)R(S#,SD,SM)和函數(shù)依賴集和函數(shù)依賴集 F=S#SD,SDSMF=S#SD,SDSM，且知有分解，且知有分解 2=R1(S#,SD,S#SD),R2(S#,SM,S#SM)2=R1(S#,SD,S#SD),R2(S#,SM,S#SM)。 驗(yàn)證分解驗(yàn)證分解22具有無損聯(lián)接性，但不具有保持依賴性。

51、具有無損聯(lián)接性，但不具有保持依賴性。 因?yàn)橐驗(yàn)?(R1R2)(R1-R2) (R1R2)(R1-R2) (S#,SD S#,SM)(S#,SD-S#,SM)(S#,SD S#,SM)(S#,SD-S#,SM) S#SD F S#SD F 所以分解具有無損聯(lián)接性。所以分解具有無損聯(lián)接性。 例例6.12 6.12 已知有關(guān)系模式已知有關(guān)系模式R(S#,SD,SM)R(S#,SD,SM)和函數(shù)依賴集和函數(shù)依賴集 F=S#SD,SDSMF=S#SD,SDSM，且知有分解，且知有分解 2=R1(S#,SD,S#SD),R2(S#,SM,S#SM)2=R1(S#,SD,S#SD),R2(S#,SM,S#S

52、M)。 驗(yàn)證分解驗(yàn)證分解22具有無損聯(lián)接性，但不具有保持依賴性。具有無損聯(lián)接性，但不具有保持依賴性。 因?yàn)橐驗(yàn)?R1(F)R2(F) R1(F)R2(F) S#SDS#SMS#SDS#SM S#SDS#SD，S#SMS#SM 顯然，顯然，(SDSM) S#SD(SDSM) S#SD，S#SMS#SM 也即，也即，R1(F)R1(F)和和R2(F)R2(F)的并集不邏輯蘊(yùn)含中的函的并集不邏輯蘊(yùn)含中的函 數(shù)依賴數(shù)依賴SDSMSDSM。所以分解。所以分解22不具有保持依賴性。不具有保持依賴性。 課堂練習(xí)課堂練習(xí) 設(shè)有設(shè)有R(ABC), =AC,BCR(ABC), =AC,BC，F(xiàn)=AB,BCF=AB

53、,BC；判；判 斷該分解是否具有無損聯(lián)接和保持函數(shù)依賴。斷該分解是否具有無損聯(lián)接和保持函數(shù)依賴。 對于給定的關(guān)系對于給定的關(guān)系S(U,F)S(U,F)，關(guān)系，關(guān)系S S的的 屬性按其在函數(shù)依賴的左端和右端的出現(xiàn)分為屬性按其在函數(shù)依賴的左端和右端的出現(xiàn)分為4 4類：類： 僅出現(xiàn)在僅出現(xiàn)在F F中的函數(shù)依賴左部的屬性；中的函數(shù)依賴左部的屬性； 僅出現(xiàn)在僅出現(xiàn)在F F中的函數(shù)依賴右部的屬性；中的函數(shù)依賴右部的屬性； 在在F F中函數(shù)依賴的左右兩邊均出現(xiàn)的中函數(shù)依賴的左右兩邊均出現(xiàn)的 屬性。屬性。 在在F F中函數(shù)依賴的左右兩邊均未出現(xiàn)中函數(shù)依賴的左右兩邊均未出現(xiàn) 的屬性；的屬性； 設(shè)有關(guān)系模式設(shè)有關(guān)

54、系模式R(UR(U，F(xiàn))F)和屬性集和屬性集 U=AU=A1 1,A,A2 2, ,A,An n 的子集的子集X X： 若若X X是是L L類屬性，則類屬性，則X X必為必為R R的某一候選鍵的成員；的某一候選鍵的成員； 若若X X是是L L類屬性，且類屬性，且X X+ +包含了包含了R R的全部屬性，則的全部屬性，則X X必為必為R R 的唯一候選鍵；的唯一候選鍵； 若若X X是是R R類屬性，則類屬性，則X X不是任一候選鍵的成員；不是任一候選鍵的成員； 若若X X是是N N類屬性，則類屬性，則X X必包含在必包含在R R的某一候選鍵中；的某一候選鍵中； 若若X X是是R R的的N N類屬

55、性和類屬性和L L類屬性組成的屬性集，且類屬性組成的屬性集，且X X+ +包含包含 了了R R的全部屬性，則的全部屬性，則X X是是R R的唯一候選鍵。的唯一候選鍵。 設(shè)關(guān)系模式設(shè)關(guān)系模式R(U,F)R(U,F)的依賴集的依賴集F F已經(jīng)為最已經(jīng)為最 小依賴集小依賴集( (即即, ,蘊(yùn)含依賴右端只有單個屬性蘊(yùn)含依賴右端只有單個屬性) )，則關(guān)系模式，則關(guān)系模式 R R的函數(shù)依賴圖的函數(shù)依賴圖G G是一個有序二元組是一個有序二元組G=(R,F),G=(R,F),且：且： （1 1）U=AU=A1 1,A,A2 2, ,A,An n 是一個有限非空集，是一個有限非空集，A Ai i是是G G中的中

56、的 結(jié)點(diǎn)。結(jié)點(diǎn)。 （2 2）F F是是G G的一個非空邊集，的一個非空邊集，A Ai iA Aj j是是G G中的一條有向中的一條有向 邊邊(A(Ai i，A Aj j) )。 （3 3）若結(jié)點(diǎn)）若結(jié)點(diǎn)A Ai i與結(jié)點(diǎn)與結(jié)點(diǎn)A Aj j之間存在一條有向邊之間存在一條有向邊(A(Ai i,A,Aj j) )， 則該邊稱為則該邊稱為A Ai i的出邊和的出邊和A Aj j的入邊。的入邊。 （4 4）只有出邊而無入邊的結(jié)點(diǎn)稱為原始點(diǎn)（表示）只有出邊而無入邊的結(jié)點(diǎn)稱為原始點(diǎn)（表示L L類類 屬性）；只有入邊而無出邊的結(jié)點(diǎn)稱為終結(jié)點(diǎn)（表示屬性）；只有入邊而無出邊的結(jié)點(diǎn)稱為終結(jié)點(diǎn)（表示R R類類 屬性）

57、；既有入邊又有出邊的結(jié)點(diǎn)稱為途中點(diǎn)（表示屬性）；既有入邊又有出邊的結(jié)點(diǎn)稱為途中點(diǎn)（表示LRLR 類屬性）；既無入邊又無出邊的結(jié)點(diǎn)稱為孤立點(diǎn)（表示類屬性）；既無入邊又無出邊的結(jié)點(diǎn)稱為孤立點(diǎn)（表示N N 類屬性）。類屬性）。 （5 5）原始點(diǎn)和孤立點(diǎn)統(tǒng)稱為關(guān)鍵點(diǎn)；關(guān)鍵點(diǎn)對應(yīng)的）原始點(diǎn)和孤立點(diǎn)統(tǒng)稱為關(guān)鍵點(diǎn)；關(guān)鍵點(diǎn)對應(yīng)的 屬性稱為關(guān)鍵屬性；其他結(jié)點(diǎn)不能到達(dá)的回路稱為獨(dú)立屬性稱為關(guān)鍵屬性；其他結(jié)點(diǎn)不能到達(dá)的回路稱為獨(dú)立 回路?；芈?。 關(guān)系模式關(guān)系模式R(A1,A2,An)，R的函數(shù)依賴集的函數(shù)依賴集F； R的所有候選鍵。的所有候選鍵。 求求F的最小依賴集的最小依賴集Fmin； 構(gòu)造函數(shù)依賴圖；構(gòu)造函數(shù)依

58、賴圖； 從圖中找出關(guān)鍵屬性集從圖中找出關(guān)鍵屬性集X（X可為空）；可為空）； 查看查看G中有無獨(dú)立回路，若無則中有無獨(dú)立回路，若無則X即為即為R的唯一候選的唯一候選 鍵，轉(zhuǎn)；鍵，轉(zhuǎn)； 從各獨(dú)立回路中各取一結(jié)點(diǎn)對應(yīng)的屬性與從各獨(dú)立回路中各取一結(jié)點(diǎn)對應(yīng)的屬性與X組合成組合成 一候選鍵，并重復(fù)這一過程，取盡所有可能的組合，即為一候選鍵，并重復(fù)這一過程，取盡所有可能的組合，即為 R的全部候選鍵；的全部候選鍵； 輸出候選鍵，算法結(jié)束。輸出候選鍵，算法結(jié)束。 將將R R的所有屬性分為的所有屬性分為L L、R R、N N和和LRLR四類，并令四類，并令X X代表代表L L和和N N 類，類，Y Y代表代表LR

59、LR類；類； 求求X X 。若 。若X X 包含了 包含了R R的全部屬性的全部屬性, ,則則X X是是R R的唯一候選鍵，的唯一候選鍵， 轉(zhuǎn)；否則，轉(zhuǎn)；轉(zhuǎn)；否則，轉(zhuǎn)； 在在Y Y中取一屬性中取一屬性A A，求，求(XA)(XA) ，若它包含了 ，若它包含了R R的全部屬性，的全部屬性， 則則XAXA為為R R的一個候選鍵的一個候選鍵; ; 重復(fù)，直到重復(fù)，直到Y(jié) Y中的屬性依次取完為止；中的屬性依次取完為止； 從從Y Y中除去已成為主屬性的屬性中除去已成為主屬性的屬性A;A; 在剩余屬性中依次取兩個、三個、在剩余屬性中依次取兩個、三個、，將其記為集合，將其記為集合B B， 求求(XB)(XB

60、) ：若 ：若(XB)(XB) 包含了 包含了R R的全部屬性，且自身不包含已求出的全部屬性，且自身不包含已求出 的候選鍵，則的候選鍵，則XBXB為為R R的一個候選鍵；的一個候選鍵； 重復(fù)，直到重復(fù)，直到Y(jié) Y中的屬性按方法的組合依次取完為止；中的屬性按方法的組合依次取完為止； 輸出候選鍵，算法結(jié)束。輸出候選鍵，算法結(jié)束。 設(shè)有關(guān)系模式設(shè)有關(guān)系模式R(A,B,C,D,E)R(A,B,C,D,E)和和R R的函數(shù)依賴集的函數(shù)依賴集 F=A F=ABC,CDBC,CDE,BE,BD,ED,EAA，求，求R R的所有候選鍵。的所有候選鍵。 根據(jù)根據(jù)F F對對R R的所有屬性進(jìn)行分類：的所有屬性進(jìn)行