數(shù)據(jù)庫第六章關(guān)系數(shù)據(jù)理論習(xí)題講解

第六章關(guān)系數(shù)據(jù)理論

(我們數(shù)據(jù)庫老師給的資料，蠻有用的，分享下)

一、求最小依賴集

例：設(shè)有依賴集：F={AB-C,C-A,BC->D,ACD-B,D-?EG,BE—C,CG-BD,CE-

AG},計算與其等價的最小依賴集。

解：

1、將依賴右邊屬性單一化，結(jié)果為：

F1={AB-C,C->A,BC—D,ACD-B,D-E,D-G,BE—C,CG—B,CG-^D,CE—A,

CE-*G}

2、在Fl中去掉依賴左部多余的屬性。對于CE-A,由于C-A成立，故E是多余的；對于ACD

-B,由于(CD)+=ABCEDG,故A是多余的。刪除依賴左部多余的依賴后：

F2={AB-C,C-?A,BC-?D,CD-?B,D->E,D-G,BE->C,CG-B,CG-?D,CE->G}

3、在F2中去掉多余的依賴。對于CG-B,由于(CG)+=ABCEDG,故CG-B是多余的。刪

除依賴左部多余的依賴后：

F3={AB-C,C-A,BC—D,CD->B,D-E,D-G,BE—C,CG—D,CE—G}

CG-B與CD-B不能同時存在，但去掉任何一個都可以，說明最小依賴集不唯一。

二、求閉包

例：關(guān)系模式R(U,F),其中U={A,B,C,D,E,I},F={A-D,AB-E,BI-E,CD-I,

E-C},計算(AE)+°

解：^X={AE},X(0)=AE；

計算X(1);逐一掃描F集合中各個函數(shù)依賴，在F中找出左邊是AE子集的函

數(shù)依賴，其結(jié)果是：A-D,E-*C0于是X(1)=AEUDC=ACDE;

因為X(0)#X(1),且X(1)#U,所以在F中找出左邊是ACDE子集的函

數(shù)依賴，其結(jié)果是：CD-I。于是X⑵=ACDEUI=ACDEIo

雖然X(2)#X(1),但在F中未用過的函數(shù)依賴的左邊屬性已沒有X(2)的子

+

集，所以不必再計算下去，即(AE)=ACDEIO

三、求候選鍵

例1：關(guān)系模式R(U,F),其中U={A,B,C,D},F={A-B,C-D},試求此關(guān)系的候選鍵。

解：首先求屬性的閉包：

(A)+=AB,(B)+=B,(C)+=CD,(D)+=D

(AB)+=AB,(AC)+=ABCD=U,(AD)+=ABD,(BC)+=BCD,(BD)+=BD,(CD)+=CD

(ABD)+=ABD,(BCD)+=BCD,

因(AC)+=ABCD=U,且(A)+=AB,(C)+=CD,由閉包的定義，AC—A,AC—B,AC

—B,AC—D,由合并規(guī)則得AC—ABCD=U；

由候選碼的定義可得AC為候選碼。

后選關(guān)鍵字的求解理論和算法

對于給定的關(guān)系R(Al,A2,…,An)和函數(shù)依賴集F,可將其屬性分為四類：

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

R類：僅出現(xiàn)在F的函數(shù)依賴右部的屬性；

N類：在F的函數(shù)依賴左右兩邊均未出現(xiàn)的屬性；

LR類：在F的函數(shù)依賴左右兩邊均出現(xiàn)的屬性。

定理1對于給定的關(guān)系模式R及其函數(shù)依賴集F,若X(X屬于R)是L類屬性，則

X必為R的任一候選關(guān)鍵字的成員。

例1：關(guān)系模式R(U,F),其中U={A,B,C,D},F={A-B,C-D},試求此關(guān)系的候選鍵。

例2設(shè)有關(guān)系模式R(A,B,C,D),其函數(shù)依賴集F={D-B,B-D,AD-B,AC-D},求R的

所有候選鍵。

推論對于給定的關(guān)系模式R及其函數(shù)依賴集F,若X(X屬于R)是L類屬性，且X+

包含了R的全部屬性，則X必為R的惟一候選關(guān)鍵字。

精品

定理2對于給定的關(guān)系模式R及其函數(shù)依賴集F,若X（X屬于R）是R類屬性，則

X不在任何候選關(guān)鍵字中。

例3關(guān)系模式R（U,F）,其中U={A,B,C,D,E,P},F={A-?B,C-D,E-A,CE-D},

試求此關(guān)系的候選鍵。

定理3對于給定的關(guān)系模式R及其函數(shù)依賴集F,若X（X屬于R）是N類屬性，則

X必為R的任一候選關(guān)鍵字的成員。

例4設(shè)有關(guān)系模式R（A,B,C,D,E,P）,其函數(shù)依賴集F={A-D,E-D,D-B,BC->D,DC

-?A）,求R的所有候選關(guān)鍵字。

推論對于給定的關(guān)系模式R及其函數(shù)依賴集F,若X（X屬于R）是N類和L類組成

的屬性集，且X+包含了R的全部屬性，則X必為R的惟一候選關(guān)鍵字

四、關(guān)系模式規(guī)范化程度的判斷（在BCNF內(nèi)判斷）

例5關(guān)系模式R（U,F）,其中U={A,B,C,D},函數(shù)依賴集F={B-D,AB-C},試求

R最高屬于第幾范式。

解：根據(jù)判定定理及推論得：AB必是候選碼的成員，且（AB）+=ABCD=U,所以

AB為候選碼。則ABTD,又因BTD,存在非主屬性對碼的部分依賴，所以最高為1NF。

例6關(guān)系模式R（U,F）,其中U={A,B,C,D,E},函數(shù)依賴集F={AB-CE,E->AB,

C-D},試求R最高屬于第幾范式。

解：根據(jù)判定定理及推論得：屬性D肯定不在候選碼中，通過計算可得：

精品

(AB)+=ABCDE=U,且(E)+=ABCDE=U,所以AB、E為候選碼；

由于F中不存在部分依賴，故R至少屬于2NF;

因AB-C,AB-E,C-D,存在非主屬性對碼的傳遞依賴，所以最高為2NF。

例7關(guān)系模式R(U,F),其中U={A,B,C},函數(shù)依賴集F={A-B,B-A,A-C},試

求R最高屬于第幾范式。

解：根據(jù)判定定理及推論得：屬性C肯定不在候選碼中，通過計算可得：

(A)+=ABC=U,且(B)+=ABC=U,所以A、B為候選碼；

由于候選碼僅有一個屬性，不存在部分依賴，故R至少屬于2NF;

B-A,A-C,由于A-B,所以不存在非主屬性對碼的傳遞依賴，所以R也是3NF。

又因為F滿足BCNF的定義，故R也是BCNF。

例8關(guān)系模式R(U,F),其中U={A,B,C},函數(shù)依賴集F={A-B,B-A,C-A},試

求R最高屬于第幾范式。

解：根據(jù)判定定理及推論得：屬性C肯定在候選碼中，又因(C)+=ABC=U,所以

C為候選碼；

由于候選碼僅有一個屬性，不存在部分依賴，故R至少屬于2NF;

C-A,A-B,存在非主屬性對碼的傳遞依賴，所以R最高為2NF。

例9關(guān)系模式R(U,F),其中U={A,B,C,D},函數(shù)依賴集F={A->C,D-B},試求R

最高屬于第幾范式。

解：根據(jù)判定定理及推論得：屬性AD肯定在候選碼中，又因(AD)+=ABCD=U,

所以AD為候選碼；

而AD-B,D-B,存在非主屬性對碼的部分依賴，所以R最高為1NF。

例10關(guān)系模式R(U,F),其中U={A,B,C,D},函數(shù)依賴集F={A-C,CD-*B),試求

精品

R最高屬于第幾范式。