6第6章-關(guān)系數(shù)據(jù)庫模式設(shè)計

第6章關(guān)系數(shù)據(jù)庫模式設(shè)計數(shù)據(jù)庫系統(tǒng)原理與設(shè)計主講人：

聯(lián)系方式：

關(guān)系數(shù)據(jù)庫模式？？？

圖1.14數(shù)據(jù)庫系統(tǒng)的體系結(jié)構(gòu)應(yīng)用程序A1應(yīng)用程序A2應(yīng)用程序B1應(yīng)用程序B2用戶A1用戶A1外模式A外模式B外模式到模式的映象A外模式到模式的映象B邏輯模式模式到內(nèi)模式的映象內(nèi)模式數(shù)據(jù)庫局部邏輯結(jié)構(gòu)概念級DB全局邏輯結(jié)構(gòu)存儲級DB存儲組織結(jié)構(gòu)DBMSOS用戶級DB用戶A1用戶A1學(xué)生關(guān)系（學(xué)號，姓名，性別，出生年月，籍貫，專業(yè)代碼，班級）專業(yè)關(guān)系（專業(yè)代碼，專業(yè)名稱）課程關(guān)系（課程號，課程名，學(xué)時數(shù)）設(shè)置關(guān)系（專業(yè)代碼，課程代碼）學(xué)習(xí)關(guān)系（學(xué)號，課程號，分?jǐn)?shù)）教師關(guān)系（教工號，教員姓名，教員性別，教員出生年月，教研室，電話）講授關(guān)系（教工號，課程號）

關(guān)系數(shù)據(jù)庫模式：在一個實際的數(shù)據(jù)庫應(yīng)用系統(tǒng)中，把構(gòu)成該關(guān)系數(shù)據(jù)庫的全局邏輯模式的基本表的全體，稱為該數(shù)據(jù)庫應(yīng)用系統(tǒng)的關(guān)系數(shù)據(jù)庫模式。

學(xué)生關(guān)系模式：S（S#，SNAME，SSEX，SBIRTHIN，PLACEOFB，SCODE#，CLASS）專業(yè)關(guān)系模式：SS（SCODE#，SSNAME）課程關(guān)系模式：C（C#，CNAME，CLASSH）設(shè)置關(guān)系模式：CS（SCODE#，C#）學(xué)習(xí)關(guān)系模式：SC（S#，C#，GRADE）教師關(guān)系模式：T（T#，TNAME，TSEX，TBIRTHIN，TITLEOF，TRSECTION，TEL）講授關(guān)系模式：TEACH（T#，C#）教學(xué)管理數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)庫模式關(guān)系數(shù)據(jù)庫的模式設(shè)計問題，是數(shù)據(jù)庫應(yīng)用系統(tǒng)設(shè)計中的核心問題之一。本章中，支撐關(guān)系數(shù)據(jù)庫模式設(shè)計的函數(shù)依賴和規(guī)范化理論，是關(guān)系數(shù)據(jù)庫設(shè)計的重要理論基礎(chǔ)，也是本課程學(xué)習(xí)的主要難點內(nèi)容。

6.1關(guān)系約束與關(guān)系模式的表示第6章關(guān)系數(shù)據(jù)庫模式設(shè)計

Question？

關(guān)系數(shù)據(jù)庫模式的設(shè)計有哪幾種方法呢？

1、E-R模型方法：畫出反映用戶組織中相互關(guān)聯(lián)的數(shù)據(jù)及其之間聯(lián)系的E-R圖，再將E-R模型轉(zhuǎn)換成關(guān)系模型對應(yīng)的關(guān)系模式。

2、屬性表方法：收集、整理和歸納用戶組織進(jìn)行信息管理的各種表格，然后把每個表格轉(zhuǎn)換成一個關(guān)系模式。一、關(guān)系數(shù)據(jù)庫模式的設(shè)計方法表6.1大學(xué)教學(xué)信息管理系統(tǒng)中的關(guān)系模式（表）構(gòu)建表名學(xué)生學(xué)籍表課程歸屬表考試成績表授課統(tǒng)計表教員信息表擁有的屬性學(xué)號課程編號學(xué)號課程編號教員編號姓名課程名稱姓名課程名稱教員姓名性別學(xué)時數(shù)課程號學(xué)時數(shù)性別出生年月(歸屬)教研室名稱課程名稱教員編號出生年月籍貫成績教員姓名籍貫班級所屬專業(yè)職稱教研室名稱所屬專業(yè)(任課)教研室名稱由表6.1可直接得到如下關(guān)系模式：學(xué)生學(xué)籍關(guān)系（學(xué)號，姓名，性別，出生年月，籍貫，班級，所屬專業(yè)）課程歸屬關(guān)系（課程編號，課程名稱，學(xué)時數(shù)，教研室名稱）考試成績關(guān)系（學(xué)號，姓名，課程編號，課程名稱，成績，所屬專業(yè)）授課統(tǒng)計關(guān)系（課程編號，課程名稱，學(xué)時數(shù)，教員編號，教員名稱，職稱，教研室名稱）教員信息關(guān)系（教員編號，教員名稱，性別，出生年月，職稱，教研室名稱）

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

分析可知，在這幾個關(guān)系模式中，至少存在有2種由一些屬性值決定教研室名稱屬性值的數(shù)據(jù)依賴關(guān)系。

也就是說，一個關(guān)系模式中的屬性之間存在著一個或多個依賴關(guān)系。由于這種依賴是用屬性的值來體現(xiàn)的，所以稱為數(shù)據(jù)依賴。

當(dāng)一般地用屬性名集合表示其依賴關(guān)系時，就可看作是一種函數(shù)依賴。

綜上可見，當(dāng)把所有這些約束完整地反映到對關(guān)系模式的描述時，就可得到如下結(jié)論：

一個關(guān)系模式是一個五元組{R,U,D,DOM,F}，并可一般地記為：其中，R是關(guān)系名；U是關(guān)系的屬性集合；D是屬性的值域集合；DOM是屬性集到值域集合的映射；F是關(guān)系中屬性集上的一組約束，也即函數(shù)依賴集合。二、五元組/三元組關(guān)系模式在本章的相關(guān)概念討論中，關(guān)系名R、屬性集U和依賴集F三者相互關(guān)聯(lián)，相互依存；而值域集合D和映射DOM與各概念的描述則關(guān)聯(lián)性不太大。

所以為了簡單起見，本教材后續(xù)的內(nèi)容，把關(guān)系模式簡化地看作是一個三元組{R,U,F}。且：當(dāng)且僅當(dāng)U上的一個關(guān)系R滿足F時，將稱R(U,F)為關(guān)系模式{R,U,F}上的一個關(guān)系。

6.2對關(guān)系模式進(jìn)行規(guī)范化設(shè)計的必要性第6章關(guān)系數(shù)據(jù)庫模式設(shè)計

考察關(guān)系模式：

教員任課(教工號,姓名,職稱,教研室，課程號,課程名,學(xué)時)

主鍵：(T#,C#）

（1）問題：存在有

①數(shù)據(jù)冗余；

②更新異常；

③插入異常；

④刪除異常。教工號姓名職稱教研室課程號課程名學(xué)時40301徐楊柳副教授403K40301數(shù)據(jù)庫6040301徐楊柳副教授403K40302網(wǎng)絡(luò)5040302張國慶教授403K40302網(wǎng)絡(luò)5040302張國慶教授403S40303網(wǎng)絡(luò)安全4040303張瑩講師403K40304數(shù)據(jù)挖掘4040304宋歌教授403B40305圖像通信50教員任課(教工號,姓名,職稱,教研室，課程號,課程名,學(xué)時)數(shù)據(jù)冗余存在問題

當(dāng)某教員同時上幾門課程時，教員的基本信息“教工號、姓名、職稱、教研室”重復(fù)存儲，產(chǎn)生了較多的冗余數(shù)據(jù)。教工號姓名職稱教研室課程號課程名學(xué)時40301徐楊柳副教授403K40301數(shù)據(jù)庫6040301徐楊柳副教授403K40302網(wǎng)絡(luò)5040301徐楊柳副教授403K40302網(wǎng)絡(luò)5040302張國慶教授403S40304數(shù)據(jù)挖掘4040302張國慶教授403K40303網(wǎng)絡(luò)安全4040304宋歌講師403B40305圖像通信50教員任課(教工號,姓名,職稱,教研室，課程號,課程名,學(xué)時)數(shù)據(jù)冗余更新異常存在問題

當(dāng)某教員的職稱發(fā)生變化時，就必須對涉及該教員的所有記錄的職稱屬性進(jìn)行修改，存在潛在的數(shù)據(jù)不一致性。教工號姓名職稱教研室課程號課程名學(xué)時40301徐楊柳副教授403K40301數(shù)據(jù)庫6040301徐楊柳副教授403K40302網(wǎng)絡(luò)5040301徐楊柳副教授403K40302網(wǎng)絡(luò)5040302張國慶教授403S40304數(shù)據(jù)挖掘4040302張國慶教授403K40303網(wǎng)絡(luò)安全4040304宋歌講師403B40305圖像通信50教員任課(教工號,姓名,職稱,教研室，課程號,課程名,學(xué)時)數(shù)據(jù)冗余更新異常插入異常存在問題

當(dāng)新調(diào)來的某教員還沒有上課時，該教員的信息就無法輸入數(shù)據(jù)庫，存在插入異常現(xiàn)象。教工號姓名職稱教研室課程號課程名學(xué)時40301徐楊柳副教授403K40301數(shù)據(jù)庫6040301徐楊柳副教授403K40302網(wǎng)絡(luò)5040301徐楊柳副教授403K40302網(wǎng)絡(luò)5040302張國慶教授403S40304數(shù)據(jù)挖掘4040302張國慶教授403K40303網(wǎng)絡(luò)安全4040304宋歌講師403B40305圖像通信50教員任課(教工號,姓名,職稱,教研室，課程號,課程名,學(xué)時)數(shù)據(jù)冗余更新異常插入異常刪除異常存在問題

當(dāng)某教員不再上課時，該教員的信息就必須全部刪除，存在刪除異?，F(xiàn)象。結(jié)論:

當(dāng)關(guān)系模式設(shè)計的不合理時，就會存在數(shù)據(jù)冗余、更新異常、插入異常、刪除異常。

因此，必須對關(guān)系模式進(jìn)行規(guī)范化設(shè)計。（2）關(guān)系模式產(chǎn)生異常的原因

數(shù)據(jù)之間存在著一定的數(shù)據(jù)依賴關(guān)系，其實質(zhì)即是函數(shù)依賴。

（3）解決方法：進(jìn)行關(guān)系模式分解。教員任課(教工號,姓名,職稱,教研室，課程號,課程名,學(xué)時)

教員關(guān)系（教工號,姓名,職稱,教研室）課程關(guān)系（課程號,課程名,學(xué)時)

在本章后續(xù)的內(nèi)容中，涉及到比較嚴(yán)格的定義、定律和公式推導(dǎo)，為了表述上的方便，如不做特殊聲明，總是假設(shè)有如下約定：

（1）用大寫英文字母A、B、C、D等表示關(guān)系的單個屬性。（2）用大寫字母U表示某一關(guān)系的屬性集(全集)，用大寫字母V、W、X、Y、Z等表示屬性集U的子集。

本章后續(xù)內(nèi)容表述上的有關(guān)約定：

（3）不再特意地區(qū)分關(guān)系和關(guān)系模式，并用大寫字母R，R1，R2，…和，S，S1，S2…表示關(guān)系和關(guān)系模式。（4）R(A,B,C)，R(ABC)和ABC三種表示關(guān)系模式的方法是等價的。同理，{A1,A2,…,An}和A1A2…An是等價的，X∪Y和XY是等價的，X∪{A}和XA是等價的。

本章后續(xù)內(nèi)容表述上的有關(guān)約定：

（5）用大寫英文字母F，F(xiàn)1，…，以及G表示函數(shù)依賴集。（6）若X={A,B}，Y={C,D}，則X→Y，{A,B}→{C,D}和AB→CD三種函數(shù)依賴表示方法是等價的。

#

6.3函數(shù)依賴第6章關(guān)系數(shù)據(jù)庫模式設(shè)計

1、函數(shù)依賴的概念

定義6.1設(shè)有關(guān)系模式R(A1,A2,…,An)和屬性集U={A1,A2,…,An}的子集X、Y。如果對于任一具體關(guān)系r的任何兩個元組u和v，只要u[X]=v[X]，就有u[Y]=v[Y]，則稱X函數(shù)地決定Y，或Y函數(shù)依賴X，記為X

Y。

一、函數(shù)依賴的定義1、函數(shù)依賴的概念例如：對于課程關(guān)系C(C#,CNAME,CLASSH)，X={C#}、Y={CNAME,CLASSH}及任何具體關(guān)系，當(dāng)給定X中的某一個具體值時，只能查到由該具體值決定的某個具體課程名和學(xué)時數(shù)。

課程號課程名學(xué)時C401001數(shù)據(jù)結(jié)構(gòu)70C401002操作系統(tǒng)60C402001計算機(jī)原理60C402002通信原理60C403001計算機(jī)網(wǎng)絡(luò)60C403002信息安全技術(shù)50C404001信息編碼與加密60一、函數(shù)依賴的定義由上面的定義和例子說明：

函數(shù)依賴描述了每個關(guān)系中主鍵屬性與非主鍵屬性之間的關(guān)系。對于關(guān)系R(A1,A2,…,An)和X→Y來說，屬性子集X中包括，且僅僅包括了關(guān)系R的主鍵屬性，且對于關(guān)系的任何屬性子集Y，一定成立X→Y。

顯然，對于X→Y，可能存在Y

X、兩種情況。

一、函數(shù)依賴的定義2、非平凡函數(shù)依賴與平凡函數(shù)依賴①若有X

Y，且，稱X

Y為非平凡函數(shù)依賴;②若有X

Y，且Y

X，稱X

Y為平凡函數(shù)依賴。

一、函數(shù)依賴的定義在本章后續(xù)的內(nèi)容中，如不特別聲明，總假定討論的是非平凡依賴。且：①若X

Y，則稱X為決定因素。②若Y不依賴于X，則記作XY。③若同時有X

Y和YX成立，則記為XY。一、函數(shù)依賴的定義二、具有函數(shù)依賴約束的關(guān)系模式S（{S#，SNAME，SSEX，SBIRTHIN，PLACEOFB,SCODE#，CLASS}，{SNO}→{SNAME，SSEX，SBIRTHIN，PLACEOFB,SCODE，CLASS}）SS（{SCODE#，SSNAME}，{SCODE#}→{SSNAME}）C（{C#，CNAME，CLASSH}，{C#}→{CNAME，CLASSH}）CS（{SCODE#，C#}，{SCODE#,C#}→{SCODE#,C#}）SC（{S#，C#，GRADE}，{S#，C#}→{GRADE}）T（{T#，TNAME，TSEX，TBIRTHIN，TITLEOF，TRSECTION，TEL}，{TNO}→{TNAME，TSEX，TBIRTHIN，TITLEOF，TRSECTION，TEL}）TEACH（{T#，C#}，{T#，C#}→{T#，C#}）1、邏輯蘊(yùn)涵

定義5.2

設(shè)有關(guān)系模式R(U，F(xiàn))，X、Y是屬性集U={A1,A2,…,An}的子集，如果從F中的函數(shù)依賴能夠推導(dǎo)出X

Y，則稱F邏輯蘊(yùn)涵X

Y，或稱X

Y是F的邏輯蘊(yùn)涵。三、函數(shù)依賴的邏輯蘊(yùn)涵2、F的閉包

所有被F邏輯蘊(yùn)涵的函數(shù)依賴組成的依賴集稱為F的閉包，記為F+。顯然：①F+中的元素是函數(shù)依賴；②如果能計算出F+，就可以很方便地判斷某個函數(shù)依賴是否被F+邏輯蘊(yùn)涵。三、函數(shù)依賴的邏輯蘊(yùn)涵三、函數(shù)依賴的邏輯蘊(yùn)涵3、F的閉包F+的計算是一件非常復(fù)雜的事情，即使F不大，F(xiàn)+也比較大。

A→ο，AB→ο，AC→ο，ABC→ο，B→ο，C→οA→A，AB→A，AC→A，ABC→A，B→B，C→CA→B，AB→B，AC→B，ABC→B，B→C，=A→C，AB→C，AC→C，ABC→C，B→BC，A→AB，AB→AB，AC→AB，ABC→AB，BC→ο，A→AC，AB→AC，AC→AC，ABC→AC，BC→B，A→BC，AB→BC，AC→BC，ABC→BC，BC→C，A→ABC，AB→ABC，AC→ABC，ABC→ABC，BC→BC，舉例：設(shè)有關(guān)系模式R(A,B,C)，其函數(shù)依賴集為:F={A→B，B→C}，則F的閉包為：

顯然，一般地有F

F+。

1、候選鍵的概念

①能夠唯一地標(biāo)識一個關(guān)系中不同元組的一個屬性集合；②該屬性集中不含有多余的屬性。三、候選鍵的形式化定義2、候選鍵的形式化定義

設(shè)有關(guān)系模式R(A1,A2,…,An)和屬性集U={A1,A2,…,An}的子集X、Y，F(xiàn)是R的的函數(shù)依賴集。如果：①X→A1A2…An屬于F+；②不存在X的真子集X’，使X’→A1A2…An∈F+，則稱X是R的一個候選鍵。舉例

在課程關(guān)系C（C#，CNAME，CLASSH）中，有依賴集F={C#→{CNAME，CLASSH}}，判斷候選鍵。

因為F中的唯一的函數(shù)依賴的決定因素{C#}已經(jīng)是單個屬性了，所以{C#}是唯一的候選建。當(dāng)然也就是主鍵了。6.4函數(shù)依賴的公理系統(tǒng)第6章關(guān)系數(shù)據(jù)庫模式設(shè)計

由前述內(nèi)容可知，對于關(guān)系模式來說，關(guān)系的主鍵實質(zhì)上是由其依賴集中的函數(shù)依賴的決定因素確定的。

O、問題的引出

為了從關(guān)系模式的函數(shù)依賴集中的函數(shù)依賴確定該關(guān)系的主鍵，就需要分析各函數(shù)依賴之間的邏輯蘊(yùn)涵關(guān)系，或者至少要根據(jù)給定的函數(shù)依賴集和函數(shù)依賴→，確定→是否屬于，這顯然涉及到的計算。由于的計算是一件非常復(fù)雜的事情，經(jīng)過一些學(xué)者的潛心研究，提出了一組推導(dǎo)函數(shù)依賴邏輯蘊(yùn)涵關(guān)系的推理規(guī)則，并由W.W.Armstrong于1974年歸納成公理體系，就形成了著名的Armstrong(阿姆斯特郎)公理體系。

1、公理

作用：用于從給定的函數(shù)依賴集中推導(dǎo)出被其蘊(yùn)涵的函數(shù)依賴。

一、阿姆斯特朗公理

1、公理

條件：設(shè)有關(guān)系模式R(U,F)，U={A1,A2,…,An}是R的屬性集，F(xiàn)是R的屬性集U上的函數(shù)依賴集，X、Y、Z、W是U的子集。

Armstrong公理為：A1自反律：若Y

X，則X

Y；A2增廣律：若X

Y，則XZ

YZ；A3傳遞律：若X

Y,Y

Z，則X

Z。

一、阿姆斯特朗公理

2、公理的證明定理6.1：Armstrong公理是正確的。證明思路：依據(jù)函數(shù)依賴的定義進(jìn)行證明。一、阿姆斯特朗公理

1、公理的三條推論

合并規(guī)則：若X

Y且X

Z，則X

YZ

分解規(guī)則：若X

Y，且Z

Y，則X

Z

偽傳遞規(guī)則：若X

Y且WY

Z，則WX

Z二、阿姆斯特朗公理的推論

2、推論的正確性定理

證明思路：應(yīng)用Armstrong公理推導(dǎo)出三個推論。二、阿姆斯特朗公理的推論1、合并規(guī)則：若X

Y且X

Z，則X

YZ證明：由條件X→Y，并增廣律可得X→XY。由條件X→Z，并增廣律可得XY→YZ。利用傳遞律，由X→XY和XY→YZ，可得X→YZ。二、阿姆斯特朗公理的推論2、分解規(guī)則：若X

Y，且Z

Y，則X

Z證明：

已知有X→Y。由條件Z

Y，并自反律可得Y→Z。利用傳遞律，由X→Y和Y→Z，可得Z→Z。二、阿姆斯特朗公理的推論3、偽傳遞規(guī)則：若X

Y且WY

Z，則WX

Z證明：由條件X→Y，并增廣律可得WX→WY。利用傳遞律，和已知條件WY→Z，可得WX→Z。

二、阿姆斯特朗公理的推論例6.2

對于關(guān)系模式(CITY，ST，ZIP)，依賴集F={ZIP→CITY,CITYST→ZIP},候選鍵為{CITY，ST}和{ST，ZIP}。證明有:｛STZIP｝→｛CITY,ST,ZIP｝和｛CITY,ST｝→｛CITY,ST,ZIP｝?，F(xiàn)證明前者。證明：

已知有ZIP→CITY由增廣律可得｛ST,ZIP｝→｛CITY,ST｝(1)又已知｛CITY,ST｝→｛ZIP｝由增廣律可得｛CITY,ST｝→｛CITY,ST,ZIP｝(2)由(1)和(2)，并根據(jù)傳遞律即可得到：｛ST,ZIP｝→｛CITY,ST,ZIP｝

3、定理

定理6.2如果Ai(i=1,2,…,n)是關(guān)系模式R的屬性,則X

A1A2…An成立的充分必要條件是X

Ai(i=1,…,n)均成立。

充分性證明：由條件推出結(jié)論；

必要性證明：假設(shè)結(jié)論成立，推出條件成立。

定理5.2的結(jié)論，為關(guān)系數(shù)據(jù)庫模式設(shè)計中的各個關(guān)系主鍵的確定奠定了基礎(chǔ)。

二、阿姆斯特朗公理的推論

1、關(guān)系數(shù)據(jù)庫模式2、進(jìn)行關(guān)系模式規(guī)范化設(shè)計的必要性

數(shù)據(jù)冗余、更新異常、插入異常、刪除異常3、函數(shù)依賴用于確定關(guān)系中一些屬性值決定另一些屬性值的依賴和被依賴關(guān)系，是進(jìn)行關(guān)系模式規(guī)范化的基本依據(jù)

小結(jié)

4、F的閉包概念：所有被F邏輯隱含的函數(shù)依賴組成的集合。5、為了根據(jù)已知的函數(shù)依賴集合

F

判斷某函數(shù)依賴是否被

F

邏輯隱含，或能夠從

F

中推導(dǎo)出來，引入了函數(shù)依賴的公理系統(tǒng)。

公理：自反律、增廣律、傳遞律

推論：合并規(guī)則、分解規(guī)則、偽傳遞規(guī)則

小結(jié)

6、最直觀的判斷某函數(shù)依賴是否能夠被F邏輯隱含的方法，是判別該函數(shù)依賴是否在F+中。7、由于求

F+

是

NP

難問題，所以：

下面將引入X關(guān)于

F

的閉包概念

X+，目的是通過計算

X+，來判斷

X→Y

是否被F邏輯蘊(yùn)涵，從而避開了直接計算

F+

的難題。

小結(jié)

1、X關(guān)于F的閉包定義6.4設(shè)有關(guān)系模式R(U,F)和屬性集U={A1,A2,…,An}的子集X。則稱所有用阿姆斯特朗公理從F推導(dǎo)出的函數(shù)依賴X→Ai的屬性Ai組成的集合稱為X關(guān)于F的閉包，并記為XF+，通常簡記為X+。即X+={Ai|用公理從F推出的X→Ai}顯然有X

X+。三、X關(guān)于F的閉包及其計算例6.3

已知關(guān)系模式R(A,B,C)上有函數(shù)依賴集F={A

B,B

C}，求X分別等于A、B、C時的X+。解：{

求解時的主要依據(jù)是Armstrong公理及推論

}

對于X=A，因為有A→A，且已知A→B，B→C，則有A→C，所以有X+=ABC。

對于X=B，因為有B→B，且已知B→C，所以有B+=BC。

對于X=C，顯然有X+=C。依據(jù)定義6.4計算X關(guān)于F的閉包：定理6.3設(shè)有關(guān)系模式R(U，F(xiàn))和屬性集U={A1，A2，…，An}的子集X、Y。則X

Y能用阿姆斯特朗公理從F導(dǎo)出的充分必要條件是Y

X＋。

該定理的意義:

把判定X

Y是否能從F根據(jù)阿姆斯特朗公理導(dǎo)出，也即該函數(shù)依賴是否被F蘊(yùn)涵的問題，轉(zhuǎn)化成了X＋是否包含Y的問題：即當(dāng)X＋包含Y時，說明X

Y能從F根據(jù)阿姆斯特朗公理導(dǎo)出。（求X+成了關(guān)鍵）利用X+判斷某一函數(shù)依賴是否能從F導(dǎo)出的方法:

2X關(guān)于F的閉包X+的計算

求X＋算法的思路:

①從給定的屬性集X出發(fā)（設(shè)X’＝X）②如果發(fā)現(xiàn)X’包含了F中的某個函數(shù)依賴左邊的屬性，就把該依賴右邊的屬性添加到X’中。即對于F中的所有V

W，若有V

X’，則有X’=X’W。③循環(huán)第②步的過程不斷擴(kuò)充X’，直到該集合再也無法擴(kuò)展時，得到的結(jié)果就是X＋。

三、X關(guān)于F的閉包及其計算

算法6.1

求X＋的算法:

輸入：關(guān)系模式R的全部屬性集U,U上的函數(shù)依賴集F，U的子集X。

輸出：X關(guān)于F的閉包X＋。

方法：（1）X(0)=X。（2）從F中找出滿足條件V

X(i)的所有函數(shù)依賴V→W，并把所有的V→W中的屬性W組成的集合記為Z；也即從F中找出那些其決定因素是X(i)的子集的函數(shù)依賴，并由這些函數(shù)依賴的被決定因素組成一個集合，設(shè)其（被記為）Z。（3）若Z

X(i)，則轉(zhuǎn)（5）。（4）否則，X(i+1)=X(i)Z，并轉(zhuǎn)（2）。（5）停止計算，輸出X(i)，即為X+。

3、應(yīng)用舉例

例6.4

已知有函數(shù)依賴集F={AB→C,BC→D,ACD→B,D→EG,BE→C}，屬性集U={A,B,C,D,E,G}，且X=BD，求X＋。

解：三、X關(guān)于F的閉包及其計算

求X＋的算法:

輸入：關(guān)系模式R的全部屬性集U,U上的函數(shù)依賴集F，U的子集X。

輸出：X關(guān)于F的閉包X＋。

方法：（1）X(0)=X。（2）從F中找出滿足條件V

X(i)的所有函數(shù)依賴V→W，并把所有的V→W中的屬性W組成的集合記為Z；也即從F中找出那些其決定因素是X(i)的子集的函數(shù)依賴，并由這些函數(shù)依賴的被決定因素組成一個集合，設(shè)其（被記為）Z。（3）若Z

X(i)，則轉(zhuǎn)（5）。（4）否則，X(i+1)=X(i)Z，并轉(zhuǎn)（2）。（5）停止計算，輸出X(i)，即為X+。U={A,B,C,D,E,G}F={AB→C,BC→D,ACD→B,D→EG,BE→C}X=BD1、依賴集的等價與覆蓋定義定義6.5

設(shè)F和G是兩個函數(shù)依賴集，如果F＋＝G＋,則稱F和G等價。如果F和G等價，則稱F覆蓋G，同時也稱G覆蓋F。

判斷依賴集等價的方法：定理6.4

F＋＝G＋的充要條件是F

G＋和G

F＋。四、最小函數(shù)依賴集根據(jù)集合運(yùn)算規(guī)則，具體判斷F等價于G的方法：

由定理6.4可知，為了判斷F和G是否等價，只要判斷對于F中的每一個函數(shù)依賴X

Y是否都屬于G+，若都屬于G+，則F

G+。只要發(fā)現(xiàn)某一個函數(shù)依賴X

Y不屬于G+，就說明F+≠G+。對于G中的每一個函數(shù)依賴也作同樣的處理。當(dāng)同時成立F

G+和

GF+時，則F和G等價。四、最小函數(shù)依賴集

由于計算F+和G+是NP難問題，所以在實際中，并不需要計算閉包F+和G+，而只要根據(jù)的定理6.3，分別計算XF+

和XG+：（1）為了判斷F

G+，只要對F中的每一個函數(shù)依賴X

Y計算X關(guān)于G的閉包XG+，若Y

XG+，則說明X

Y屬于G+。（2）同理，為了判斷GF+，只要對G中的每一個函數(shù)依賴X

Y計算X關(guān)于F的閉包XF+

，若Y

XF+，則說明X

Y屬于F+。

由函數(shù)依賴集等價性引出的結(jié)論：

推論6.4

每一個函數(shù)依賴集都被其右端只有一個屬性的函數(shù)依賴組成的依賴集所覆蓋。

推論6.4證明的主要理論根據(jù)：分解規(guī)則與合并過則。

四、最小函數(shù)依賴集

2最小函數(shù)依賴集定義6.6滿足下列條件的函數(shù)依賴集F稱為最小函數(shù)依賴集。①F中每一個函數(shù)依賴的右端都是單個屬性；②對F中任何函數(shù)依賴X

A，F(xiàn)-{X

A}不等價于F;③對F中的任何函數(shù)依賴X

A和X的任何真子集Z，(F-{X

A})∪{Z

A}不等價于F。四、最小函數(shù)依賴集

最小依賴集的求解方法：

（1）用分解規(guī)則將F中的所有函數(shù)依賴分解成右端為單個屬性的函數(shù)依賴；

（2）去掉F中冗余的函數(shù)依賴，即對于F中任一函數(shù)依賴X

Y：

①設(shè)G=F-{X

Y}；②求X關(guān)于G的閉包XG+；

③看XG+是否包含Y。如果XG+包含Y，則在G中邏輯蘊(yùn)涵X

Y，說明X

Y是多余的函數(shù)依賴，從而可得到較小的函數(shù)依賴集F=G；如果XG+不包含Y，則保留X

Y。

④按上述方法逐個考察F中的每一個函數(shù)依賴,直到其中所有函數(shù)依賴都考察完為止。

注：隨著考察順序的不同可能得到不同的結(jié)果。（3）去掉F中函數(shù)依賴左端多余的屬性，即對于F中左端是非單屬性的函數(shù)依賴（XY

A），要判斷X或Y是不是多余的屬性。當(dāng)要判斷Y是否是多余的屬性時：①設(shè)G=(F-{XY

A})∪{X

A}；②求XY關(guān)于G的閉包，（XY)G+；③如果(XY)G+包含A，則說明Y是多余的屬性，從而可得到較小的函數(shù)依賴集F=G；如果(XY)G+不包含A，則說明XY

A不被G邏輯隱含，說明Y不是多余的屬性。

或者求X關(guān)于F的閉包，（X)F+

；

如果（X)F+包含A，則Y是多余屬性

④當(dāng)Y不是多余屬性時，要接著用類似的方法判斷X是不是多余的屬性（設(shè)G=(F-{XY

A})∪{Y

A}）。

⑤如果X和Y都不是多余的屬性時，則保留該函數(shù)依賴XY

A。⑥接著按上述方法逐個考察F中左端是非單屬性的其他函數(shù)依賴，直到其中的所有左端是非單屬性的函數(shù)依賴都考察完為止。

3、最小依賴求解方法舉例例6.5求函數(shù)依賴集F的最小函數(shù)依賴集，其中:AB

C，C

A，BC

D，ACD

B，D

EG，BE

C，CG

BD，CE

AGF=AB

C，C

A，BC

D，ACD

B,D

E,D

G，BE

C，CG

BCG

D，CE

A,CE

G解：①分解F，使每個函數(shù)依賴右端均為單個屬性F1=3、舉例：求函數(shù)依賴集F的最小函數(shù)依賴集。②去掉F中冗余的函數(shù)依賴：即試著去掉F1中的每一個函數(shù)依賴，看它是否被F1中剩余的函數(shù)依賴蘊(yùn)含。

◆對于AB

C，求AB關(guān)于F1-{AB

C}的閉包。顯然，對于(AB)(0)=AB，在F1-{AB

C}中不存在決定因素是AB的子集的函數(shù)依賴，也即有(AB)+=AB，且C(AB)+，所以AB

C不多余。AB

C，C

A，BC

D，ACD

B,D

E,D

G，BE

C，CG

BCG

D，CE

A,CE

GF1=3、舉例：求函數(shù)依賴集F的最小函數(shù)依賴集。②去掉F中冗余的函數(shù)依賴：

◆對于ACDB，求ACD關(guān)于F1-{ACDB}的閉包。由于對于(ACD)+=ABCDEG，且B

(ACD)+=ABCDEG,所以ACD

B是多余的。按照上述思路依次考察F1中的每個函數(shù)依賴，可得：AB

C，C

A，BC

D，ACD

B,D

E,D

G，BE

C，CG

BCG

D，CE

A,CE

GF1=3、舉例：求函數(shù)依賴集F的最小函數(shù)依賴集。解：②去掉F中冗余的函數(shù)依賴：

去掉多余的依賴ACDB,CGD和CEA。可得：

或，去掉多余的函數(shù)依賴CGB和CEA，可得：

AB

C，C

A，BC

D，D

E，D

G，BE

C，CG

B，CE

GF21=AB

C，C

A，BC

D，ACD

B，D

E，D

G，BE

C，CG

D，CE

GF22=3、舉例：求函數(shù)依賴集F的最小函數(shù)依賴集。解：③去掉（F21和F22）左端的多余屬性：

Fmin=或Fmin=AB

C，C

A，BC

D，D

E，D

G，BE

CCG

B，CE

GAB

C，C

A，BC

D，CD

B，D

E，D

G，BE

C，CG

D，CE

G6.5關(guān)系模式的分解第6章關(guān)系數(shù)據(jù)庫模式設(shè)計

如本章的6.2節(jié)所述，為了消除某些關(guān)系模式可能存在的數(shù)據(jù)冗余、插入異常、刪除異常和修改異常，就需要對這些關(guān)系模式進(jìn)行分解。

1、F在Ui上的投影

定義6.7設(shè)Ui是屬性集U的一個子集，則函數(shù)依賴集合{X→Y|X→Y

F+∧XY

Ui}的一個覆蓋Fi，稱為F在Ui上的投影。

定義6.7的含義和要說明的問題：

對于屬性集U的子集Ui，存在一個與其對應(yīng)的依賴子集Fi，且由Fi中的每個函數(shù)依賴X→Y的決定因素X和被決定因素Y組成的屬性子集XY均是Ui的子集。一、關(guān)系模式分解的概念另一個更明確的F在Ui上的投影定義：

定義6.8設(shè)有關(guān)系模式R(U，F(xiàn))和U={A1,A2,…,An}的子集Z，把F+中所有滿足XY

Z的函數(shù)依賴X→Y組成的集合，稱為依賴集F在屬性集Z上的投影，記為πz(F)。

由定義5.8知，顯然有：

πz(F)＝{X→Y|X→Y

F+，且XY

Z}所以定義5.8和定義5.7本質(zhì)上是相同的。

一、關(guān)系模式分解的概念

2、關(guān)系模式的分解

定義6.9設(shè)有關(guān)系模式R(U,F)，如果U=U1∪U2

∪…∪Uk，并且對于任意的i,j(1≤i,j≤k)，不成立Ui

Uj，且Fi是F在Ui上的投影，則稱：ρ={R1(U1,F1)，R2(U2,F2)，…，Rk(Uk,Fk)}是關(guān)系模式R(U,F)的一個分解。

定義6.9指出：屬性子集集合{U1,U2,…,Uk}中的任意一個屬性子集Ui，不會是其它任何一個屬性子集Uj的子集。一、關(guān)系模式分解的概念

關(guān)系模式分解應(yīng)用舉例：

例6.6設(shè)有關(guān)系模式R(U,F)，U={S#,SD,SM}，F(xiàn)={S#→SD,SD→SM}，并設(shè)關(guān)系R有如下表的當(dāng)前值r。

下面采用三種不同方法對關(guān)系R進(jìn)行分解。S#SDSMS1D1M1S2D2M1S3D3M2一、關(guān)系模式分解的概念4、F={S#→SD,SD→SM}（1）方法1S#SDSMS1D1M1S2D2M1S3D3M2

設(shè)：ρ1＝{R1(S#,φ)，R2(SD,φ)，R3(SM,φ)}即有，F(xiàn)i=φ和Ri=πi(R(U))對于已知關(guān)系r在πi(R(U))上的投影，有：r1={S1,S2,S3}r2={D1,D2,D3}r3={M1,M2}

S1D1M1，S2D1M1，S3D1M1，S1D1M2，S2D1M2，S3D1M2，S1D2M1，S2D2M1，S3D2M1，S1D2M2，S2D2M2，S3D2M2，S1D3M1，S2D3M1，S3D3M1，S1D3M2，S2D3M2，S3D3M2對關(guān)系模式的分解，理應(yīng)要求分解后的各關(guān)系能恢復(fù)原關(guān)系的原值，一般采用自然聯(lián)接方法恢復(fù)可得：

r1

r2

r3≡rr1r2r3=r1×r2×r3聯(lián)接結(jié)果為：

r1={S1,S2,S3}r2={D1,D2,D3}r3={M1,M2}

比較關(guān)系R原來的當(dāng)前值：S#SDSMS1D1M1S2D2M1S3D3M2和向R1、R2和R3投影后，再聯(lián)接恢復(fù)的值：

S1D1M1，S2D1M1，S3D1M1，S1D1M2，S2D1M2，S3D1M2，S1D2M1，S2D2M1，S3D2M1，S1D2M2，S2D2M2，S3D2M2，S1D3M1，S2D3M1，S3D3M1，S1D3M2，S2D3M2，S3D3M2可知：方法1的分解不保持信息無損，不具有無損聯(lián)接性。（2）方法2（F={S#→SD,SD→SM}）設(shè):ρ2={R1({S#,SD},{S#→

SD}),R2({S#,SM},{S#→SM})}

因為有：

S#→φ，S#SD→φ，SD→φ,S#→S#，S#SD→S#，SD→SD,=S#→SD，S#SD→SD，S#→S#SD，S#SD→S#SDS#→φ，S#SM→φ，SM→φ,S#→S#，S#SM→S#，SM→SM,=

S#→SM，S#SM→SM，S#→S#SM，S#SM→S#SM

分析可知，原F中的SD→SM均不在上面2個閉包中，即：F1∪F2不等于F，但可以證明成立：r1r2=r所以：方法2的分解保持信息無損，但不保持函數(shù)依賴。

F={S#→SD,SD→SM}（3）方法3設(shè):ρ2={R1({S#,SD},{S#→SD}),R2({SD,SM},{SD→SM})}因為有：r1={(S1,D1),(S2,D2),(S3,D3)}；F1＝{S#→SD}r2={(D1,M1),(D2,M1),(D3,M2)}；F2＝{SD→SM}

可以證明成立：r1r2=r和F1∪F2=F所以：方法3的分解既能保持信息無損，又能保持函數(shù)依賴。S#SDSMS1D1M1S2D2M1S3D3M2

1、保持無損分解的定義

定義5.10設(shè)有關(guān)系模式R(U,F)，ρ=（R1,R2,…,Rk）是R的一個分解。如果對于R的任一滿足F的關(guān)系r，成立：r=πR1(r)πR2(r)…πRk(r)則稱分解ρ是無損聯(lián)接分解。也稱該分解ρ是保持無損的分解。二、保持無損的分解

2、判斷保持無損分解的方法算法5.2：判斷一個分解的無損聯(lián)接性輸入：關(guān)系模式R(A1,…,An)，函數(shù)依賴集F，R的一個分解ρ＝(R1,R2,…,Rk)。輸出：ρ是否為無損聯(lián)接的判斷。方法：

二、保持無損的分解算法6.2判斷一個分解的無損聯(lián)接性方法：

（1）構(gòu)造一個k行n列表S。其中，第i行對應(yīng)于關(guān)系模式R分解后的模式Ri，第j列對應(yīng)于關(guān)系模式R的屬性Aj。表中第i行第j列位置的元素填入方法為：如果Aj在Ri中，則在第i行第j列的位置上填上符號aj,否則填上符號bij。二、保持無損的分解（2）對于F中的所有函數(shù)依賴X→Y，在表中尋找在X的各個屬性上都分別相同的行，若至少存在兩個或多個這樣的行，則將這些行上對應(yīng)的Y屬性上的元素值，修改成具有相同符號的元素值，修改方法為：①當(dāng)這些行的Y屬性上的某一行上都為aj（j為Y屬性對應(yīng)的那些列的列序號，且j=1,2,…,n）時，則把該行的Y屬性上的其它元素都修改成aj；②當(dāng)這些行的Y屬性列中沒有這樣的aj時，則以Y屬性列中下標(biāo)較小的bij為基準(zhǔn)，把這些行的Y屬性列上的其它元素都修改成bij。（3）按(2)逐個考察F中的每一個函數(shù)依賴，如果發(fā)現(xiàn)某一行變成了a1，a2，…，an，則分解ρ具有無損聯(lián)接性；如果直到檢驗完F中的所有函數(shù)依賴也沒有發(fā)現(xiàn)有這樣的行，表也不再變化，則分解ρ不具有無損聯(lián)接性。

二、保持無損的分解

3、應(yīng)用舉例例6.7

設(shè)R(ABCDE)，F(xiàn)={A→C,B→C,C→D,DE→C,CE→A},分解ρ={R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE)},檢驗分解ρ是否具有無損聯(lián)接性。

R(ABCDE)，F(xiàn)={A→C,B→C,C→D,DE→C,CE→A},ρ={R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE)}

解：第一步，構(gòu)造表S。ABCDER1a1b12b13a4b15R2a1a2b23b24b25R3b31a2b33b34a5R4b41b42a3a4a5R5a1b52b53b54a5二、保持無損的分解第二步：①根據(jù)函數(shù)依賴A→C修正表S。ABCDER1a1b12b13a4b15R2a1a2b23/b13b24b25R3b31a2b33b34a5R4b41b42a3a4a5R5a1b52B53/b13b54a5二、保持無損的分解第二步：②根據(jù)函數(shù)依賴B→C修正表S。ABCDER1a1b12b13a4b15R2a1a2b13b24b25R3b31a2b33/b13b34a5R4b41b42a3a4a5R5a1b52b13b54a5二、保持無損的分解第二步：③根據(jù)函數(shù)依賴C→D修正表S。ABCDER1a1b12b13a4b15R2a1a2b13b24

/a4b25R3b31a2b13b34/a4a5R4b41b42a3a4a5R5a1b52b13b54/a4a5二、保持無損的分解第二步：④根據(jù)函數(shù)依賴DE→C修正表S。ABCDER1a1b12b13a4b15R2a1a2b13a4b25R3b31a2b13/a3a4a5R4b41b42a3a4a5R5a1b52b13/a3a4a5二、保持無損的分解第二步：⑤根據(jù)函數(shù)依賴CE→A修正表S。ABCDER1a1b12b13a4b15R2a1a2b13a4b25R3b31/a1a2a3a4a5R4b41/a1b42a3a4a5R5a1b52a3a4a5

第三步：通過判斷，給出結(jié)論。二、保持無損的分解第三步：通過判斷，給出結(jié)論。

表中的第三行都變成aj了，所以分解ρ具有無損聯(lián)接性。ABCDER1a1b12b13a4b15R2a1a2b13a4b25R3a1a2a3a4a5R4a1b42a3a4a5R5a1b52a3a4a5二、保持無損的分解

4、僅分解成兩個子關(guān)系的無損聯(lián)接性判斷

定理6.5

設(shè)有關(guān)系模式R(U,F)，ρ=(R1，R2)是R的一個分解，當(dāng)且僅當(dāng):(R1∩R2)→(R1-R2)∈F+或

(R2∩R1)→(R2-R1)∈F+時，ρ具有無損聯(lián)接性。二、保持無損的分解例6.9設(shè)有關(guān)系模式R(A,B,C)，函數(shù)依賴集F={A→B，C→B}，分解ρ={R1,R2}，其中R1=AB，R2=BC。檢驗分解ρ是否具有無損聯(lián)接性。

解：

二、保持無損的分解例6.10在例5.6中，已知有關(guān)系模式(S#，SD，SM)，函數(shù)依賴集={S#→SD，SD→SM}。且對于其中的方法(3)，已知有分解={(S#,SD)，(SD,SM)}，且已指出分解是無損聯(lián)接分解，下面進(jìn)行驗證。解：

二、保持無損的分解

對于關(guān)系模式R(U,F)，保持無損性討論的是R(U)被分解成多個是Ri時的信息保持問題。對于R(F)，同樣存在分解成多個Ri時，對應(yīng)的R(Fi)是否成立，以及能否保持原來F的依賴性問題。三、保持依賴的分解

1、函數(shù)依賴分解的定義

定義5.11設(shè)有關(guān)系模式R(U,F)，ρ=（R1,R2,…,Rk）是R的一個分解。如果所有函數(shù)依賴集πRi(F)(i=1,2,…，k）的并集邏輯蘊(yùn)含F(xiàn)中的每一個函數(shù)依賴，則稱分解ρ具有依賴保持性，也即分解ρ保持依賴集F。即：三、保持依賴的分解2、保持依賴分解的判定方法

①對ρ中的每一個Ri求πRi(F)②求③對F中每一個函數(shù)依賴X→Y，判斷能否由導(dǎo)出，如果均能導(dǎo)出，則分解ρ具有依賴保持性；否則分解ρ不具有依賴保持性。三、保持依賴的分解例6.11已知有關(guān)系模式R(S#,SD,SM)和函數(shù)依賴集F={S#→SD,SD→SM}，且知有分解:ρ3={R1({S#,SD},{S#→SD}),R2({SD,SM},{SD→SM})}。驗證分解ρ3是保持依賴的分解。

解：因為所以，具有保持依賴性。

三、保持依賴的分解例6.12已知有關(guān)系模式R(S#,SD,SM)和函數(shù)依賴集F={S#→SD,SD→SM}，且知有分解ρ2={R1({S#,SD},{S#→SD}),R2({S#,SM},{S#→SM})}。驗證分解ρ2具有無損聯(lián)接性，但不具有保持依賴性。

解：（1）驗證無損聯(lián)接性因為(R1∩R2)→(R1-R2)＝({S#,SD}∩{S#,SM})→({S#,SD}-{S#,SM})＝S#→SD∈F所以分解具有無損聯(lián)接性。三、保持依賴的分解例6.12已知有關(guān)系模式R(S#,SD,SM)和函數(shù)依賴集F={S#→SD,SD→SM}，且知有分解ρ2={R1({S#,SD},{S#→SD}),R2({S#,SM},{S#→SM})}。驗證分解ρ2具有無損聯(lián)接性，但不具有保持依賴性。

解：（2）驗證不具有保持依賴性

因為πR1(F)∪πR2(F)＝{S#→SD}∪{S#→SM}＝{S#→SD，S#→SM}顯然，(SD→SM){S#→SD，S#→SM}也即，πR1(F)和πR2(F)的并集不邏輯蘊(yùn)含中的函數(shù)依賴SD→SM。所以分解ρ2不具有保持依賴性。由前述的例子可知，一個關(guān)系模式的分解有四種情況：

（1）既具有無損聯(lián)接性，又具有保持依賴性；（2）具有無損聯(lián)接性，但不具有保持依賴性；（3）不具有無損聯(lián)接性，但具有保持依賴性；（4）既不具有無損聯(lián)接性，又不具有保持依賴性。

顯然，符合要求的關(guān)系模式分解應(yīng)是第(1)種情況。

課堂練習(xí)

設(shè)有R(ABC),ρ={AC,BC}，F(xiàn)={A→B,B→C}；判斷該分解是否具有無損聯(lián)接和保持函數(shù)依賴。6.6關(guān)系模式的規(guī)范化第6章關(guān)系數(shù)據(jù)庫模式設(shè)計

1、關(guān)系屬性的分類一、候選鍵的求解方法定義6.12對于給定的關(guān)系S(U,F)，關(guān)系S的屬性按其在函數(shù)依賴的左端和右端的出現(xiàn)分為4類：

①L類：僅出現(xiàn)在F中的函數(shù)依賴左部的屬性；

②R類：僅出現(xiàn)在F中的函數(shù)依賴右部的屬性；③LR類：在F中函數(shù)依賴的左右兩邊均出現(xiàn)的屬性。④N類：在F中函數(shù)依賴的左右兩邊均未出現(xiàn)的屬性；一、候選鍵的求解方法2、候選鍵的充分條件定義6.13：

設(shè)有關(guān)系模式R(U，F(xiàn))和屬性集U={A1,A2,…,An}的子集X：（1）若X是L類屬性，則X必為R的某一候選鍵的成員；（2）若X是L類屬性，且X+包含了R的全部屬性，則X必為R的唯一候選鍵；（3）若X是R類屬性，則X不是任一候選鍵的成員；（4）若X是N類屬性，則X必包含在R的某一候選鍵中；（5）若X是R的N類屬性和L類屬性組成的屬性集，且X+包含了R的全部屬性，則X是R的唯一候選鍵。

一、候選鍵的求解方法3、單屬性候選鍵的依賴圖判定方法

定義6.14：設(shè)關(guān)系模式R(U,F)的依賴集F已經(jīng)為最小依賴集(即,蘊(yùn)含依賴右端只有單個屬性)，則關(guān)系模式R的函數(shù)依賴圖G是一個有序二元組G=(R,F),且：（1）U={A1,A2,…,An}是一個有限非空集，Ai是G中的結(jié)點。（2）F是G的一個非空邊集，AiAj是G中的一條有向邊(Ai，Aj)。一、候選鍵的求解方法3、單屬性候選鍵的依賴圖判定方法

定義6.14：（3）若結(jié)點Ai與結(jié)點Aj之間存在一條有向邊(Ai,Aj)，則該邊稱為Ai的出邊和Aj的入邊。

（4）只有出邊而無入邊的結(jié)點稱為原始點（表示L類屬性）；只有入邊而無出邊的結(jié)點稱為終結(jié)點（表示R類屬性）；既有入邊又有出邊的結(jié)點稱為途中點（表示LR類屬性）；既無入邊又無出邊的結(jié)點稱為孤立點（表示N類屬性）。一、候選鍵的求解方法3、單屬性候選鍵的依賴圖判定方法

定義6.14：（5）原始點和孤立點統(tǒng)稱為關(guān)鍵點；關(guān)鍵點對應(yīng)的屬性稱為關(guān)鍵屬性；其他結(jié)點不能到達(dá)的回路稱為獨立回路。

定義6.14實質(zhì)上就是函數(shù)依賴圖的構(gòu)建方法。

一、候選鍵的求解方法算法6.3：單個屬性候選鍵的依賴圖判定算法。

輸入：關(guān)系模式R(A1,A2,…,An)，R的函數(shù)依賴集F；輸出：R的所有候選鍵。

方法：①求F的最小依賴集Fmin；②構(gòu)造函數(shù)依賴圖；③從圖中找出關(guān)鍵屬性集X（X可為空）；④查看G中有無獨立回路，若無則X即為R的唯一候選鍵，轉(zhuǎn)⑥；⑤從各獨立回路中各取一結(jié)點對應(yīng)的屬性與X組合成一候選鍵，并重復(fù)這一過程，取盡所有可能的組合，即為R的全部候選鍵；⑥輸出候選鍵，算法結(jié)束。

4、多屬性候選鍵的求解法算法6.4:多屬性候選鍵的依賴圖判定算法

輸入：關(guān)系模式R(A1,A2,…,An)，R的依賴集F；

輸出：R的所有候選鍵。

一、候選鍵的求解方法

①將R的所有屬性分為L、R、N和LR四類，并令X代表L和N類，Y代表LR類；②求X＋。若X＋包含了R的全部屬性,則X是R的唯一候選鍵，轉(zhuǎn)⑤；否則，轉(zhuǎn)③；③在Y中取一屬性A，求(XA)＋，若它包含了R的全部屬性，則XA為R的一個候選鍵;④重復(fù)③，直到Y(jié)中的屬性依次取完為止；⑤從Y中除去已成為主屬性的屬性A;⑥在剩余屬性中依次取兩個、三個、…，將其記為集合B，求(XB)＋：若(XB)＋包含了R的全部屬性，且自身不包含已求出的候選鍵，則XB為R的一個候選鍵；⑦重復(fù)⑥，直到Y(jié)中的屬性按方法⑥的組合依次取完為止；⑧輸出候選鍵，算法結(jié)束。例5.14設(shè)有關(guān)系模式R(A,B,C,D,E)和R的函數(shù)依賴集F={A

BC,CD

E,B

D,E

A}，求R的所有候選鍵。解：①根據(jù)F對R的所有屬性進(jìn)行分類：ABCDE均為LR類屬性，并令Y=ABCDE。②從Y中依次取一個屬性，并計算該屬性關(guān)于F的閉包：A+＝ABCDE，包含了R的全部屬性，所以A為R的一個候選鍵；B+＝BD，沒有包含R的全部屬性，所以B不是R的候選鍵；C+＝C，沒有包含R的全部屬性，所以C不是R的候選鍵；D+＝D，沒有包含R的全部屬性，所以C不是R的候選鍵；E+＝ABCDE,包含了R的全部屬性，所以E為R的一個候選鍵。③從Y中去掉已經(jīng)是候選鍵中的屬性A和E，并令Y=BCD。

④再從Y中依次取兩個屬性，并計算該屬性集合關(guān)于Y的閉包：(BC)+＝ABCDE,包含了R的全部屬性,所以BC為R的一個候選鍵；(BD)+＝BD，沒有包含R的全部屬性，所以BD不是R的候選鍵；(CD)+＝ABCDE，包含了R的全部屬性，所以CD為R的一個候選鍵。綜上可知：R的候選鍵有A、E、BC和CD。

1、第一范式定義定義6.15：如果關(guān)系模式R中的每一個屬性的值域的值都是不可再分的最小數(shù)據(jù)單位，則稱R是滿足第一范式（1NF）的關(guān)系模式，也稱R∈1NF。二、第一范式（1NF）DEPNAMELOCS-PARTDEP1XIANP1P2DEP2WUHANP1P3DEP3CHENGDUP2TNAMEADDRESSPHONE徐浩張明敏李陽洋宋歌郭宏偉5-1-212-2-46-4-723-3-810-2-388992885188882688158(a)屬性S-PART有重復(fù)值(b)屬性PHONE有空白值圖5.10非規(guī)范關(guān)系2、非規(guī)范關(guān)系

二、第一范式（1NF）(a)屬性S-PART的規(guī)范關(guān)系(b)屬性PHONE的規(guī)范關(guān)系把某些非規(guī)范關(guān)系轉(zhuǎn)換成規(guī)范關(guān)系的方法：

TNAMEADDRESSPHONE徐浩張明敏李陽洋宋歌郭宏偉5-1-212-2-46-4-723-3-810-2-3889928851888826NULL88158DEPNAMELOCS-PARTDEP1XIANP1DEP1XIANP2DEP2WUHANP1DEP2WUHANP3DEP3CHENGDUP2圖6.11圖6.10的非規(guī)范關(guān)系轉(zhuǎn)化成的規(guī)范關(guān)系二、第一范式（1NF）

1、部分依賴與完全依賴

定義5.16：設(shè)有關(guān)系模式R(U，F(xiàn))和屬性集U={A1,A2,…,An}的子集X、Y。如果X→Y，并且對于X的任何真子集Xˊ，都有Xˊ→Y不成立，則稱Y完全依賴于X，記為XY。三、第二范式（2NF）例6.15在課程關(guān)系C(C#,CNAME,CLASSH)中，有：{C#}{CNAME}、{C#}{CLASSH}和{C#}{CNAME,CLASSH}

在學(xué)習(xí)關(guān)系SC(S#,C#,GRADE)中，有：

{S#}{GRADE}、{C#}{GRADE}

和

{S#,C#}{GRADE}三、第二范式（2NF）

定義6.17：設(shè)有關(guān)系模式R(U，F(xiàn))和屬性集U={A1,A2,…,An}的子集X、Y。如果X→Y，但Y不完全依賴于X，則稱Y部分依賴于X，記為XY。

比較定義6.16和定義6.17可知：所謂完全依賴，就是不存在X的真子集Xˊ(XˊX

，Xˊ≠X)使Xˊ→Y成立；若存在X的真子集Xˊ使Xˊ→X成立，則稱為部分依賴。三、第二范式（2NF）

定義6.17：設(shè)有關(guān)系模式R(U，F(xiàn))和屬性集U={A1,A2,…,An}的子集X、Y。如果X→Y，但Y不完全依賴于X，則稱Y部分依賴于X，記為XY。

同時，由定義6.16和定義6.17可知，當(dāng)X是僅包含有一個屬性的屬性子集時，Y都是完全依賴于X的，只有當(dāng)X是由多個屬性組成的屬性子集時，才可能會有Y完全依賴于X和Y部分依賴于X二種情況。三、第二范式（2NF）

2、第二范式

定義6.18：如果一個關(guān)系模式R屬于1NF，并且它的每一個非主屬性都完全函數(shù)依賴于它的一個候選鍵，則稱R為滿足第二范式(2NF)的關(guān)系模式，也稱R∈2NF。

換句話說，如果一個關(guān)系模式R屬于1NF，并且不存在非主屬性對候選鍵的部分依賴，則稱該關(guān)系模式R是一個滿足第二范式的關(guān)系模式，也即R屬于2NF。三、第二范式（2NF）

2、第二范式

定義6.18：如果一個關(guān)系模式R屬于1NF，并且它的每一個非主屬性都完全函數(shù)依賴于它的一個候選鍵，則稱R為滿足第二范式(2NF)的關(guān)系模式，也稱R∈2NF。

顯然，如果一個關(guān)系模式屬于1NF，并且它的主鍵只由一個屬性組成(單屬性主鍵)時，就不可能存在非主屬性對候選鍵的部分依賴，所以一定屬于2NF。

如果關(guān)系模式的候選鍵是復(fù)合候選鍵(由多個屬性組成的候選鍵)，才可能出現(xiàn)非主屬性部分依賴于候選鍵的情況。

三、第二范式（2NF）例6.16:設(shè)有關(guān)系模式SCT(S#,C#,GRADE,TNAME,TRESECTION)和關(guān)系模式SCT的具體關(guān)系：S#C#GRADETNAMETRSECTION200401001C40100190徐浩計算機(jī)200401001C40200290李陽洋指揮自動化200401001C40300185宋歌網(wǎng)絡(luò)工程200401002C40100175徐浩計算機(jī)200401002C40200288李陽洋指揮自動化200401003C40200269李陽洋指揮自動化200402001C40100187徐浩計算機(jī)200402001C40100290張國慶計算機(jī)200402002C40300192宋歌網(wǎng)絡(luò)工程

分析可知有函數(shù)依賴集F={(S#,C#)

GRADE,C#

TNAME,TNAME

TRESECTION},R是滿足第幾范式的關(guān)系模式？

例6.16：SCT(S#,C#,GRADE,TNAME,TRESECTION)F={(S#,C#)

GRADE,C#

TNAME,TNAME

TRESECTION}結(jié)論：R滿足1NF，不是2NF。當(dāng)將SCT分解成SC、CT后，才均為2NF：SC(S#,C#,GRADE)F1={(S#,C#)

GRADE}CT(C#,TNAME,TRESECTION)F2={C#

TNAME,TNAME

TRESECTION}

◆需要注意的是，在一個1NF關(guān)系模式轉(zhuǎn)換成2VF關(guān)系模式后，可以在一定程度上減少原1NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余等問題，但并不能完全消除該關(guān)系中的所有異常和數(shù)據(jù)冗余。

2、第二范式三、第二范式（2NF）1、傳遞依賴

設(shè)有關(guān)系模式R(U,F)和屬性集U={A1,A2,…,An}的子集X、Y、Z。如果有X

Y、Y

Z、Z-Y≠φ，Z-X≠φ和YX，則稱Z傳遞依賴于X，記為XZ。四、第三范式（3NF）1、傳遞依賴

設(shè)有關(guān)系模式R(U,F)和屬性集U={A1,A2,…,An}的子集X、Y、Z。如果有X

Y、Y

Z、Z-Y≠φ，Z-X≠φ和YX，則稱Z傳遞依賴于X，記為XZ。

在定義5.19中，Z-Yф說明在屬性子集Z中至少存在一個屬性不在屬性子集Y中，因而保證了Y→Z是非平凡依賴。同理，Z-Xф說明在屬性子集Z中至少存在一個屬性不在屬性子集X中，因而保證了X→Z是非平凡依賴；如果同時存在X→Y，Y→X，則有XY，而YX保證了該定義中只成立X→Y而不成立Y→X