《數(shù)據(jù)庫原理與應用》課件第5章

第5章關系數(shù)據(jù)庫理論5.1關系模式的一般表示及設計中的問題5.2函數(shù)依賴5.3函數(shù)依賴的公理系統(tǒng)5.4關系模式規(guī)范形式5.5關系模式的規(guī)范化小結(jié)關系數(shù)據(jù)庫是以關系模型為基礎的數(shù)據(jù)庫，它利用關系描述現(xiàn)實世界。關系模式是用來定義關系的，一個關系數(shù)據(jù)庫包含一組關系，定義這組關系的關系模式的全體就構(gòu)成了該關系數(shù)據(jù)庫的模式。關系數(shù)據(jù)庫模式設計歸根到底是如何構(gòu)造關系，即如何把具體的客觀事物劃分為幾個關系，而每個關系又由哪些屬性組成。在我們構(gòu)造關系時，經(jīng)常會發(fā)現(xiàn)數(shù)據(jù)冗余和更新異常等現(xiàn)象，這是由關系中各屬性之間的相互依賴性和獨立性造成的。前面我們已經(jīng)討論了關系模式的一般概念，但是，當使用關系模式設計數(shù)據(jù)庫時，還面臨一個關系模式的選擇問題，如何挑選一個“好”的模式，這就需要對關系模式的一些性質(zhì)做更深入的研究。

關系數(shù)據(jù)庫設計理論主要包括：數(shù)據(jù)依賴、范式和關系模式的規(guī)范化處理等三方面的內(nèi)容。

本章主要介紹了函數(shù)依賴、函數(shù)依賴的公理系統(tǒng)、關系模式的各種范式及關系模式的規(guī)范化。學習內(nèi)容：

(1)函數(shù)依賴的定義。

(2)

Armstrong公理系統(tǒng)。

(3)關系模式的規(guī)范化形式。

(4)關系模式的規(guī)范化處理。

隨著時間的不斷變化，在不同的時刻，關系模式的關系也會有變化，但是現(xiàn)實世界的許多已知的事實，卻限定了關系模式的所有可能的關系必須滿足一定的約束。這些約束或者通過對屬性取值范圍的限定，如小學生的年齡要求大于等于6歲并且小于18歲；或者通過數(shù)據(jù)間的互相關聯(lián)反映出來。5.1關系模式的一般表示及設計中的問題后者稱為數(shù)據(jù)依賴。數(shù)據(jù)依賴是數(shù)據(jù)庫理論中最主要的組成部分，是數(shù)據(jù)庫模式的理論基礎。數(shù)據(jù)依賴是現(xiàn)實世界屬性間相互聯(lián)系的抽象，它表示數(shù)據(jù)間存在的一種限制或制約關系。人們已經(jīng)提出了許多種類型的數(shù)據(jù)依賴，如函數(shù)依賴、多值依賴、連接依賴等，其中最重要的是函數(shù)依賴，所以函數(shù)依賴是數(shù)據(jù)庫模式設計中的關鍵所在。

首先介紹什么是數(shù)據(jù)庫模式？設任一關系模式用Ri表示，X=R1∪R2∪…∪Rn，則Ω={R1，R2，…，Rn}就是X上的一個數(shù)據(jù)庫模式。并不是任意一個數(shù)據(jù)庫模式都是好的模式。我們研究函數(shù)依賴，其目的之一就是要從理論上找到判斷好的數(shù)據(jù)庫模式的標準。

函數(shù)依賴普遍地存在于現(xiàn)實生活中。例如，描述一個在校大學生所在學院及學習情況會涉及一些屬性：學號sno、姓名sname、所屬學院名dname、院長姓名dmn、課程編號cno、課程名稱cname和成績grade，其屬性集合表示為U={sno，sname，dname，dmn，cno，cname，grade}。由現(xiàn)實世界的已知事實可以得出上述屬性間包含有以下聯(lián)系：

·學生的姓名可能有重名現(xiàn)象，但每名學生的學號是唯一的；

·一名學生只隸屬于一個學院，但一個學院可以接收若干名學生；

·一個學院只有一名院長；

·每門課程的課程號是唯一的；

·一名學生可以選修多門課程，每門課程也可以有若干名學生選修；

·每名學生所學的每門課程都有一個成績。圖5.1在校大學生屬性之間的函數(shù)依賴關系圖根據(jù)上述情況，我們至少可以給出以下兩種關系數(shù)據(jù)庫模式：

(1)

Ω1={R1}

其中：

關系模式R1={sno,sname,dname,dmn,cno,cname,grade}。

(2)

Ω2={R1,R2,R3,R4}

其中：

關系模式R1={sno,sname,dname}

關系模式R2={dname,dmn}

關系模式R3={cno,cname}

關系模式R4={sno,cno,grade}

雖然它們都是符合定義的數(shù)據(jù)庫模式，但使用起來的實際效果卻大不相同。

下面我們先來看Ω1。假設r是R1上的一個關系，如表5.1所示。表5.1關系r針對這個關系r，存在以下一些弊?。?/p>

(1)數(shù)據(jù)冗余大。如果某個學生選修多門課程，則他的姓名、所在學院信息均要被重復保存。例如，學號為“20080101”的學生的姓名、所在學院信息在關系r中被4個元組重復記載，這顯然是一種冗余。

(2)插入異常。如果有一門新增課程，課程號為c08，課程名為“健美操”，但因為目前還未有學生選修，構(gòu)不成一個元組，所以無法插入到關系r中去，也即存在有計劃開設的課程因為暫時沒有學生上，就無法將這些課程號和課程名等信息保存到數(shù)據(jù)庫中的現(xiàn)象，這就產(chǎn)生了插入異常。

(3)刪除異常。如果學號為“20080101”的學生考“c05”課程時違紀，則成績作廢，我們應在關系r中刪去對應的這個元組。但這個元組其實還包含課程號為“c05”，課程名為“離散數(shù)學”等信息，因刪除只能刪除整個元組，所以因?qū)W號為“20080101”的學生的“c05”課成績作廢，而把課程號為“c05”對應課程名為“離散數(shù)學”的信息也給“冤枉”地刪除掉了。事實上，不管目前有無學生學習“離散數(shù)學”這門課程，這門課程的相關信息均應能保留在數(shù)據(jù)庫中，上述這種關系模式則不能保證做到這一點，它可能產(chǎn)生刪除異常。在數(shù)據(jù)庫模式Ω1中，針對關系模式R1的某一關系r為什么會存在上述弊端呢？怎樣才能在同一個屬性集U上給出沒有這些弊端的數(shù)據(jù)庫模式呢？為了解決這些問題，我們先討論幾個重要的概念。

在現(xiàn)實世界中，最廣泛存在的一種數(shù)據(jù)依賴是函數(shù)依賴。

例如，關系模式R1={sno,sname,dname,dmn,cno,cname,grade}中存在的函數(shù)依賴有：cname函數(shù)依賴于cno；dmn函數(shù)依賴于dname；sname函數(shù)依賴于sno；grade函數(shù)依賴于(sno，cno)等。下面給出相關概念的定義。5.2函數(shù)依賴5.2.1函數(shù)依賴的概念

1．函數(shù)依賴(FunctionalDependency，簡稱FD)

定義5.1

設R(U)是屬性集U上的一個關系模式，X、Y

U。若對R(U)中任意一個可能關系r，r中不可能有兩個元組在X的屬性分量值相等，而在Y的那些屬性分量值不相等，則稱“X函數(shù)決定Y”，或“Y函數(shù)依賴于X”，記作X→Y。X稱為決定因子，或稱為函數(shù)依賴的左部，Y稱為函數(shù)依賴的右部。

另一種定義為：設R(U)是屬性集U上的一個關系模式，X、Y

U。對R(U)中任意一個可能關系r中的任意兩個元組t和s，若有t[X]=s[X]，則有t[Y]=s[Y]，就稱“X函數(shù)決定Y”，或“Y函數(shù)依賴于X”。

對函數(shù)依賴，我們需要強調(diào)幾點：

(1)當我們確定關系模式R中的某個函數(shù)依賴時，是指R的所有可能關系r都必須滿足這個函數(shù)依賴；反之，如果R中只要有一個關系r不滿足這個函數(shù)依賴，我們就認為R不存在這個函數(shù)依賴。

(2)在確定一個關系模式中的函數(shù)依賴時，我們只能從屬性含義上去加以說明，而不能在數(shù)學上加以證明。

(3)只有數(shù)據(jù)庫設計者才能決定是否存在某種函數(shù)依賴。這就使得數(shù)據(jù)庫系統(tǒng)可以根據(jù)設計者的意圖來維護數(shù)據(jù)庫的完整性。例如，關系模式R1={sno,sname,dname,dmn,cno,cname,grade}中的函數(shù)依賴可表示為

sno→sname

sno→dname

dname→dmn

cno→cname

(sno,cno)→grade

等等。

2．函數(shù)依賴模式

定義5.2

設關系模式R(U)，F(xiàn)是關于R的函數(shù)依賴集合(即若X→Y∈F，則X、Y

U)，則稱(R,F)為一個函數(shù)依賴模式。5.2.2幾種特定的函數(shù)依賴

1．非平凡函數(shù)依賴和平凡函數(shù)依賴

定義5.3

設有關系模式R(U)，X、Y

U，如果X→Y，且Y不是X的子集，則稱X→Y為非平凡的函數(shù)依賴；如果X→Y，且Y

X，則稱X→Y為平凡的函數(shù)依賴。

說明：對于任何一個關系模式，平凡函數(shù)依賴總是必然成立的。所以如果不是特別聲明，我們總是討論非平凡函數(shù)依賴。

2．完全函數(shù)依賴和部分函數(shù)依賴

定義5.4

設有關系模式R(U)，X、Y

U，如果X→Y，并且對于X的任何一個真子集Z，Z→Y都不成立，則稱Y完全函數(shù)依賴于X；若X→Y，但對于X的某一個真子集Z，有Z→Y成立，則稱Y部分函數(shù)依賴于X。

上述完全函數(shù)依賴和部分函數(shù)依賴定義可以用圖5.2表示。

例如，關系模式R1={sno,sname,dname,dmn,cno,cname,grade}中存在sno→sname，說明sname完全函數(shù)依賴于sno；又因為其存在sno→sname,(sno,cno)→sname，所以sname部分函數(shù)依賴于(sno,cno)。圖5.2完全函數(shù)依賴和部分函數(shù)依賴定義的圖形表示

(a)完全函數(shù)依賴；(b)部分函數(shù)依賴

3．傳遞函數(shù)依賴

定義5.5

設有關系模式R(U)，X

U，Y

U，Z

U，如果X→Y，Y→Z成立，但Y→X不成立，且Z

-

X、Z

-

Y和Y

-

X均不空，則稱X→Z為傳遞函數(shù)依賴。

上述傳遞函數(shù)依賴定義可以用圖5.3表示。

例如，關系模式R1={sno,sname,dname,dmn,cno,cname,grade}中存在sno→dname，dname→dmn，但不存在dname→sno，則dmn傳遞函數(shù)依賴于sno。圖5.3傳遞函數(shù)依賴定義的圖形表示又例如，關系模式R={A,B,C,D}，其上的函數(shù)依賴集F={A→B,B→C,A→C,AB→D},則A→C為傳遞函數(shù)依賴。

注：在函數(shù)依賴中還有兩種特殊的函數(shù)依賴：X→ф、ф→Y，它們對于任意關系都是成立的，在后面的介紹中我們不考慮這樣的函數(shù)依賴。5.2.3邏輯蘊涵

我們在討論函數(shù)依賴時，有時需要從一些已知的函數(shù)依賴去判斷另一些函數(shù)依賴是否成立。這個問題稱為邏輯蘊涵問題。

1．F邏輯蘊涵X→Y

定義5.6

設有關系模式R(U)，X、Y

U，F(xiàn)是關于R的函數(shù)依賴集合。又設X→Y為R中的一個函數(shù)依賴，

若對R的每一個關系r，滿足F中每一個依賴，則r也必須滿足X→Y，我們就說F邏輯蘊涵X→Y，或稱X→Y是從F推導出來的或稱X→Y邏輯蘊涵于F。例如，設R(U)是一個關系模式，A∈U，B∈U，C∈U，又假定在R中有函數(shù)依賴集F={A→B，B→C}，則稱R中有函數(shù)依賴A→C，即F邏輯蘊涵A→C。

又例如，關系模式R1={sno,sname,dname,dmn,cno,cname,grade}，R1上的函數(shù)依賴集合F1={sno→sname，sno→dname，dname→dmn，cno→cname，(sno,cno)→grade}，則稱R1中有函數(shù)依賴sno→dmn，即F1邏輯蘊涵sno→dmn。

2．函數(shù)依賴集合F的閉包

定義5.7

所有被F邏輯蘊涵的那些函數(shù)依賴組成的集合稱為F的閉包，記為F+。

例如，設有關系模式R(U)，U={A,B,C},F={AB→C,C→B}是R(U)上的一組函數(shù)依賴，則有

F+={A→A,AB→A,AC→A,ABC→A,B→B,AB→B,BC→B,ABC→B,C→C,AC→C,BC→C,ABC→C,AB→AB,ABC→AB,AC→AC,ABC→AC,BC→BC,ABC→BC,ABC→ABC,AB→C,AB→AC,AB→BC,AB→ABC,C→B,C→BC,AC→B}

在關系模式的規(guī)范化處理過程中，只知道一個給定的函數(shù)依賴集合是不夠的，我們需要知道由給定的函數(shù)依賴集合所蘊涵的所有函數(shù)依賴的集合。如果從一個函數(shù)依賴集合出發(fā)，用一個公理系統(tǒng)推出的每個依賴都被該依賴集合所蘊涵，則稱這個公理系統(tǒng)是“有效的”；若該依賴集合所蘊涵的全部依賴都可以從該集合出發(fā)用這個公理系統(tǒng)推出，則稱這個系統(tǒng)是“完備的”。Armstrong公理系統(tǒng)就是這樣一個系統(tǒng)。該公理系統(tǒng)是W.W.Armstrong于1974年提出的。5.3函數(shù)依賴的公理系統(tǒng)5.3.1Armstrong公理系統(tǒng)

1．Armstrong公理系統(tǒng)的三條推理規(guī)則

設有關系模式R(U)，X、Y、Z、W

U，F(xiàn)是R的一個函數(shù)依賴集合，則Armstrong公理系統(tǒng)包含如下三條推理規(guī)則：

(1)自反律(reflexivity)，若Y

X

U，則F蘊涵X→Y。

(2)增廣律(又稱外延性，augmentation)，若F蘊涵X→Y，Z

U，則F蘊涵XZ→YZ。

(3)傳遞律(transitivity)，

若F蘊涵X→Y和Y→Z，

但不存在F蘊涵Y→X，則F蘊涵X→Z。

Armstrong公理系統(tǒng)提供一整套推理規(guī)則，它能從F推導出F+中的所有依賴(所謂完備性)，從F推不出任何不屬于F+的依賴(所謂正確性)。

例如，有關系模式R(CITY,ST,ZIP)，其中CITY表示城市，ST表示城市的街道，ZIP表示街道所在地區(qū)的郵政編碼，函數(shù)依賴集合F={(CITY,ST)→ZIP,ZIP→CITY}，證明

{ST,ZIP}和{CITY,ST}是候選鍵。

證明：因為ZIP→CITY(由給定條件得出)，所以

(ST,ZIP)→(CITY,ST)(由增廣律得出)

又因為(CITY,ST)→ZIP(由給定條件得出)，所以

(CITY,ST)→(CITY,ST,ZIP)(由增廣律得出)

(ST,ZIP)→(CITY,ST,ZIP)(由傳遞律得出)

并且，ST→(CITY,ST,ZIP)和ZIP→(CITY,ST,ZIP)均不成立，所以(ST,ZIP)是候選鍵。

同理可證(CITY,ST)也是候選鍵。證畢。

2．Armstrong公理的三個推論

由Armstrong公理可得到下面三個推論：

(1)合并規(guī)則，若X→Y，X→Z，則X→YZ。

(2)分解規(guī)則，若X→Y且Z

Y，則X→Z。

(3)偽傳遞規(guī)則，若X→Y，YZ→W，則XZ→W。

3．Armstrong公理系統(tǒng)的正確性和完備性

在證明Armstrong公理系統(tǒng)的正確性和完備性之前，有必要引入一個定義和兩個引理。

(1)屬性集合X關于函數(shù)依賴集F的閉包，記為XF+。

定義5.8

設有關系模式R(U)，U={A1,A2,…,An}，Ai∈U，X

U，

X+={Ai|X→Ai能由F根據(jù)Armstrong公理系統(tǒng)導出，且Ai∈U}，則稱

X+是屬性集合X關于函數(shù)依賴集F的閉包。

例如，設有關系模式R(U)，U={A,B,C,D,E}，F(xiàn)={A→BC,CD→E,B→D,E→A}，則BF+={B,D}，AF+={A,B,C,D,E}。

算法5.1

計算屬性集X的閉包X+。

輸入：屬性集X和函數(shù)依賴集F。

輸出：關于F的X的閉包X+。

方法：

①令X(0)=X，i=0。

②令X(i+1)=X(i)∪{A|V

X(i)，V→W∈F,A∈W}。

③若已經(jīng)沒有V→W∈F，能使X(i+1)≠X(i)，則X+=X(i)，輸出X+，算法結(jié)束；否則，令i=i+1，轉(zhuǎn)去執(zhí)行第②步。

例5.1

設關系模式R(U)上的函數(shù)依賴集為F,U={A,B,C,D,E,I}，F(xiàn)={A→D，AB→E，BI→E，CD→I，E→C}，試計算(AE)+。

解：令X(0)=AE，i=0。

在F中找出左邊是AE子集的函數(shù)依賴，因A→D，所以X(1)=AED；因E→C，所以X(2)=AEDC；

因CD→I，所以X(3)=AEDCI；因已沒有V→W∈F，能使X(3+1)≠X(3)，所以X+=X(3)，即(AE)+={A，C，D，E，I}。

(2)引理5.1

設有關系模式R(U)，U={A1,A2,…,An}，Ai∈U，X

U，X→A1A2…An成立的充分必要條件是X→Ai(i=1,2,…,n)都成立。根據(jù)合并規(guī)則和分解規(guī)則，很容易得到這個引理的證明。留給讀者自己證明。

(3)引理5.2

設F是關系模式R(U)上的函數(shù)依賴集，X、Y

U，X→Y能由F根據(jù)

Armstrong公理系統(tǒng)導出的充分必要條件是Y

XF+。

證明：設Y=A1A2…An

(A1,A2,…,An為屬性)。

假設Y

XF+，根據(jù)XF+的定義，對所有i=1,…，n,X→Ai可用Armstrong公理系統(tǒng)從F推出。根據(jù)合并規(guī)則，X→Y也能被從F推出。反之，假設X→Y能用Armstrong公理系統(tǒng)推出。根據(jù)分解規(guī)則，對于所有i=1,2,…，n,X→Ai成立。根據(jù)X+的定義有Ai

XF+，故有A1A2…An

XF+，即Y

XF+。證畢。

(4)定理5.1Armstrong公理系統(tǒng)是正確的和完備的。

證明：[正確性]

設r是關系模式R(U)上的任一關系，t1，t2是r的任意元組，X、Y、Z

U。

①若t1[X]=t2[X]，則X的任意子集在t1，

t2上的屬性值也相等，因Y

X，即有t1[Y]=t2[Y]，根據(jù)函數(shù)依賴的定義，則X→Y成立。

②設t1[XZ]=t2[XZ]，則有t1[X]t1[Z]=t2[X]t2[Z]，則t1[X]=t2[X]，t1[Z]=t2[Z]，由X→Y可知，t1[Y]=t2[Y]。因此有t1[YZ]=t1[Y]t1[Z]=t2[Y]t2[Z]=t2[YZ]，

根據(jù)函數(shù)依賴的定義，XZ→YZ成立。

③設X→Y，Y→Z，則若t1[X]=t2[X]，有t1[Y]=t2[Y]；若t1[Y]=t2[Y]，有t1[Z]=t2[Z]。顯然，若t1[X]=t2[X]，則有t1[Z]=t2[Z]，因此X→Z成立。

[完備性]

(設關系模式R(U)上的函數(shù)依賴集為F，我們采用證明完備性的逆否命題來證明完備性，即如果函數(shù)依賴X→Y不能由F根據(jù)Armstrong公理導出，它必然不為F蘊涵。)設關系模式R(U)上的函數(shù)依賴集為F。函數(shù)依賴X→Y不包含在F+中，給出R上的一個關系r，該關系滿足要求F+但不滿足X→Y。據(jù)此，須證明兩點：r不滿足X→Y；r滿足F中的所有的函數(shù)依賴。

設關系模式R(U)中，U={A1,A2,…,An}，

Ai∈U，且ai、bi是Ai域中的兩個不同元素，1≤i≤n。假設關系r中僅有兩個元組t1和t2。元組t1=(a1,a2,…,an)；元組t2被定義為

先證明r不滿足X→Y。

若t1[X]=t2[X]，假定t1[Y]=t2[Y]，那么t2[Y]必全部為ai，并且Y

X+。但由于X→X+∈F+，通過投影可得X→Y在F+中，這一結(jié)果與X→Y不包含在F+中的假設矛盾，因此，t1[Y]=t2[Y]不成立，即r不滿足X→Y。

再證明r滿足F中的所有的函數(shù)依賴。

設W→Z是F中任一函數(shù)依賴。W在r中有兩種情況：W是X+的子集和W不是X+的子集。

若是，則根據(jù)屬性閉包的定義，有X→W，又因W→Z，由函數(shù)依賴的傳遞性，則有X→Z，所以根據(jù)引理5.2知，Z

X+，即W

X+

和Z

X+同時成立。由r的構(gòu)造可知，W→Z在r上是成立的。若不是，則在r中，t1[W]≠t2[W]，從而W→Z在r上總是成立的。證畢。

Armstrong公理系統(tǒng)的正確性和完備性說明了“通過F推導出的函數(shù)依賴”與“F所蘊涵的函數(shù)依賴”兩種說法是完全等價的。所以，F(xiàn)+也可以說成是由F出發(fā)經(jīng)Armstrong公理系統(tǒng)導出的函數(shù)依賴集合。

(5)定理5.2

合并規(guī)則、分解規(guī)則、偽傳遞規(guī)則是正確的。

證明：①若X→Y，根據(jù)增廣律得XX→XY，即X→XY；若X→Z，根據(jù)增廣律得XY→YZ，根據(jù)傳遞律得X→YZ。

②若Z

Y，根據(jù)自反律得Y→Z，又已知X→Y，根據(jù)傳遞律得X→Z。

③若X→Y，根據(jù)增廣律得XZ→YZ，又已知YZ→W，根據(jù)傳遞律得XZ→W。證畢。5.3.2函數(shù)依賴集合F的極小函數(shù)依賴集

在實際應用中，經(jīng)常需要將一個已知的函數(shù)依賴集變換為其他的或更簡潔的表示形式。例如，需要把一個大的關系模式分解為幾個小的關系模式，這樣就需要將相應的函數(shù)依賴也投影到分解后的模式上。這就涉及一個函數(shù)依賴集的等價問題。下面，從蘊涵(或?qū)С?的概念出發(fā)，再引出兩個概念。這些概念在關系模式規(guī)范化處理中十分重要。

1．兩個函數(shù)依賴集合F和G等價

定義5.9

設模式R上有兩個函數(shù)依賴集F和G，如果有F+=G+，則稱F和G等價，記作F≡G。若F≡G，則F是G的一個覆蓋，同樣，G是F的一個覆蓋。

定理5.3

設G和F是兩個函數(shù)依賴集，則F與G等價的充分必要條件是F

G+，且G

F+。

證明：(先證必要性)設G+=F+，由于F

F+，所以有F

G+。同理可得G

F+。

(再證充分性)

設F

G+且G

F+，對于每個X→Y∈F+，則有X→Y由F出發(fā)使用Armstrong公理導出。因F

G+，所以X→Y可以由G+使用Armstrong公理導出，所以X→Y∈(G+)+=G+，即X→Y∈G+，從而F+

G+。同理可證G+

F+。所以F+=G+，即F與G等價。

2．函數(shù)依賴集F的極小(或最小)函數(shù)依賴集(記為F’)

定義5.10

如果函數(shù)依賴集F滿足下列三個條件：

(1)

F中任一函數(shù)依賴的右部僅含有一個屬性。

(2)

F中不存在函數(shù)依賴X→A，使得F與F-{X→A}等價。

(3)

F中不存在函數(shù)依賴X→A，X包括真子集Z使得(F-{X→A})∪{Z→A}與F等價。稱此函數(shù)依賴集為F的極小(或最小)函數(shù)依賴集，記作F’。

注：(1)條件(1)保證了每一個函數(shù)依賴的右部都不含有多余的屬性；條件(2)保證了在F中不存在多余的函數(shù)依賴；條件(3)保證了F中每個函數(shù)依賴的左邊沒有多余的屬性。

(2)

F的極小依賴集不一定是唯一的。

例如，設關系模式R(U)上的函數(shù)依賴集為F,U={A,B,C,D,E,G}，F(xiàn)={AB→C，BC→D，ACD→B，D→EG，C→A，BE→C，CG→BD，CE→AG}，F(xiàn)1={AB→C，BC→D，D→E，BE→C，CG→D，CE→G，C→A，D→G，CD→B}，則可以驗證F1是F的最小函數(shù)依賴集。

定理5.4

每個函數(shù)依賴集F都與它的極小依賴集F’等價。

證明：采用構(gòu)造性證明的方法。分三步進行：

(1)逐一對函數(shù)依賴集F中的各函數(shù)依賴X→Y進行檢查，只要有Y=A1A2…Am，m≥2，則用{X→Ai|i=1,2,…,m}來取代X→Y。

(2)依次檢查F中各函數(shù)依賴X→A，令G=F-{X→A}，若A∈X+G，則從F中刪除X→A(根據(jù)F與G等價的充分必要條件是A∈X+G)。上述操作循環(huán)進行，直到F不再改變?yōu)橹埂?/p>

(3)循環(huán)檢查F中各函數(shù)依賴X→A，若X=B1B2…Bn，則逐一考查Bi(i=1,2,…,n)，如果A∈(X-Bi)+F，則用(X-Bi)→A取代X→A(因為F與(F-{X→A})∪{(X-Bi)→A}等價的充分必要條件是A∈(X-Bi)+F)，直到F不再改變?yōu)橹埂?/p>

這時得到的就是一個與F等價的極小函數(shù)依賴集。

證畢。

算法5.2

計算函數(shù)依賴集F的極小依賴集F’。

輸入：一個函數(shù)依賴集F。

輸出：F的一個等價極小依賴集F’。

方法：(1)應用分解規(guī)則，使F的每一個函數(shù)依賴的右部屬性單一化。

(2)去掉各函數(shù)依賴左部多余的屬性。具體辦法是：逐個循環(huán)檢查F中左邊是否是非單屬性的依賴X→Y。設X=B1B2…Bn，若Y∈(X-Bi)F+，則以(X-Bi)→Y取代X→Y，直到F不再改變?yōu)橹埂?/p>

(3)去掉多余的函數(shù)依賴。具體辦法是：循環(huán)檢查F中各函數(shù)依賴X→Y，令G=F-{X→Y}，若Y∈XG+，則從F中去掉X→Y；否則，不能去掉X→Y。直到F不再改變?yōu)橹埂?/p>

例5.2

設關系模式R(U)上的函數(shù)依賴集為F,U={A,B,C,D,E,G}，F(xiàn)={AB→C，BC→D，ACD→B，D→EG，C→A，BE→C，CG→BD，CE→AG}，試求其等價的極小函數(shù)依賴集F’。

解：(1)應用分解規(guī)則，使F的每一個函數(shù)依賴的右部屬性單一化。結(jié)果為

F1={AB→C,BC→D,ACD→B,D→E,D→G,C→A,BE→C,CG→B,CG→D,CE→A,CE→G}

(2)去掉各函數(shù)依賴左部多余的屬性。因為CE→A,C→A，

則E是多余的；對于ACD→B,由于(CD)F1+={A,B,C,D,E,G}，則A是多余的。其他函數(shù)依賴中無左部多余的屬性。刪除函數(shù)依賴左部多余的函數(shù)依賴后的結(jié)果為

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

(3)在F2中去掉多余的函數(shù)依賴。對于CG→B，令x=F2

-

{CG→B}由于(CG)+x={A,B,C,D,E,G}，即B∈(CG)+x，因此是多余的。其等價的極小函數(shù)依賴集F’的結(jié)果為：

F’={AB→C,BC→D,CD→B,D→E,D→G,C→A,BE→C,CG→D,CE→G}

關系數(shù)據(jù)庫中的關系是要滿足一定要求的，滿足不同程度要求的為不同范式。關系模式的規(guī)范形式(簡稱范式)是以函數(shù)依賴為基礎的。關系模式的常見范式主要有四種，它們是第一范式、第二范式、第三范式和BC范式。除此以外，還有第四范式和第五范式。滿足這些范式條件的關系模式可以在不同程度上避免本節(jié)開始提到的冗余問題、插入問題和刪除問題。其中最有意義的是“第三范式”和“BC范式”，這兩個范式基本保證了消除冗余問題和異常情況的發(fā)生。5.4關系模式規(guī)范形式根據(jù)規(guī)范化程度的不同，關系模式的范式從低到高有第一范式、第二范式、第三范式、BC范式等。把一個給定關系模式從低一級范式轉(zhuǎn)化為某種較高一級范式的過程稱為關系模式的規(guī)范化過程，簡稱為規(guī)范化。本節(jié)主要介紹關系模式的各種范式的基本概念。關于把一個給定關系模式轉(zhuǎn)化為較好一級范式的規(guī)范化算法，將在下節(jié)詳細介紹。

需要說明的一點是，目前存在很多種關系模式范式的定義，這些定義都是等價的。5.4.1第一范式(1NF)

定義5.11

設R是一個關系模式，如果R的每個屬性的值域(更確切地說是R的每一個關系r的屬性值域)都是不可分的簡單數(shù)據(jù)項(即是原子)的集合，則稱這個關系模式屬于第一范式(FirstNormalForm)，簡記作R∈1NF。

不滿足1NF的關系稱為非規(guī)范化的關系，滿足1NF的關系稱為規(guī)范化的關系。在任何一個關系數(shù)據(jù)庫系統(tǒng)中，關系至少應該是第一范式。不滿足第一范式的數(shù)據(jù)庫模式不能稱為關系數(shù)據(jù)庫。在以后的討論中，我們假定所有關系模式都是1NF的。但注意，第一范式不能排除數(shù)據(jù)冗余和異常情況的發(fā)生。表5.2學生選課關系例如，表5.2描述的學生選課關系不是1NF的，因為課程一列包含多門課，不是原子值，而表5.3所示學生選課1關系是1NF的。

又例如，關系模式R1={sno,sname,dname,dmn,cno,cname,grade}，它的某一關系見表5.1，R1顯然屬于1NF。表5.3學生選課1關系5.4.2第二范式(2NF)

1．2NF

定義5.12

若關系模式R是1NF的，而且每一個非主屬性都完全函數(shù)依賴于R的候選鍵，則R稱為第二范式，記作R∈2NF。

2．求出一個關系模式的所有候選鍵的方法

一個關系模式候選鍵的定義前面已經(jīng)給出，但還存在如何求出一個關系模式的所有候選鍵的問題。下面給出一種方法，供讀者參考。

定理5.5

假設有給定的關系模式R(U)及其函數(shù)依賴集F，XU，并將其屬性分為四類：L類(僅出現(xiàn)在F的函數(shù)依賴左部的屬性)、R類(僅出現(xiàn)在F的函數(shù)依賴右部的屬性)、N類(在F的函數(shù)依賴左、右兩邊均未出現(xiàn)的屬性)和LR類(在F的函數(shù)依賴左、右兩邊均出現(xiàn)的屬性)，則：

(1)若X是L類屬性，則X必為R的任一候選鍵的成員。

(2)若X是L類屬性，且X+包含了R的全部屬性，則X必為R的唯一候選鍵。

(3)若X是N類屬性，則X必包含在R的任一候選鍵中。

(4)若X是R類屬性，則X不在任一候選鍵中。

(5)若X是N類和L類組成的屬性集，且X+包含了R的全部屬性，則X是R的唯一候選鍵。

例如，描述一個在校大學生所在學院及學習情況涉及一些屬性：學號sno、姓名sname、所屬學院名dname、院長姓名dmn、課程編號cno、課程名稱cname和成績grade，以及關系模式R={sno,sname,dname,dmn,cno,cname,grade}，其屬性之間的函數(shù)依賴情況可以用圖5.4表示。圖5.4中虛線表示部分函數(shù)依賴或傳遞依賴，實線表示完全函數(shù)依賴。圖5.4關系模式R屬性之間的函數(shù)依賴關系圖

例5.3

針對關系模式R={sno,sname,dname,dmn,cno,cname,grade}，R上的函數(shù)依賴集合F={sno→sname，sno→dname，dname→dmn，cno→cname，(sno,cno)→grade，sno→dmn，(sno,cno)→sname，(sno,cno)→dname，(sno,cno)→dmn，(sno,cno)→cname}，考慮如何求出關系模式R1的候選鍵，并判斷R是否屬于第二范式。

解：根據(jù)F可以將關系模式R的屬性分為如下四類：

·L類：sno，cno。

·R類：cname，sname，dmn，grade。

·N類：無。

·LR類：dname。

由定理5.5得出sno、cno一定是主屬性。又由于

(sno,cno)+={sno,sname,dname,dmn,cno,cname,grade}

sno+={sno,sname,dname,dmn}

cno+={cno,cname}

即(sno,cno)包含了R的全部屬性，所以，(sno,cno)是關系模式R唯一的候選鍵。

R的主屬性有sno和cno；R的非主屬性有sname、dname、dmn、cname和grade。

由F可以得出sno→dname，(sno,cno)→dname，即存在非主屬性dname部分函數(shù)依賴于(sno,cno)，所以R屬于第一范式，但不屬于第二范式。

以表5.1給出的關系r為例(關系r存在的弊病我們前面已經(jīng)給出)，如若將關系模式R分解成如下三個關系模式R1、R2和R3：

R1={sno,sname,dname,dmn}

R2={cno,cname}

R3={sno,cno,grade}則我們把它描述為關系數(shù)據(jù)庫模式Ω3={R1,R2,R3}，用圖5.5(a)、(b)、(c)分別表示關系模式R1、R2和R3中屬性之間的函數(shù)依賴情況。圖5.5中虛線表示傳遞依賴；實線表示完全函數(shù)依賴。

圖5.5關系模式R1、R2和R3中屬性之間的函數(shù)依賴關系圖根據(jù)定理5.5可以得出，關系模式R1、R2和R3的候選鍵分別為sno、cno和(sno,cno)，顯然，關系模式R1、R2和R3均屬于第二范式。將關系模式R分解為關系模式R1、R2和R3后，關系模式R存在的問題在一定程度上得到了解決。如：

(1)

R1關系中可以插入尚未選修課程的學生信息，減少了由此引起的插入異常問題。

(2)刪除學生選課關系只涉及R3關系，不涉及R1中的學生基本信息，減少了由此引起的刪除異常問題。

(3)由于學生選課信息與學生基本信息分開存放，不論某學生選修了幾門課，dname與dmn的值都只存儲一次，減少了數(shù)據(jù)冗余。

3．2NF的關系模式可能引發(fā)的問題及解決辦法

從上面例子可以看出，R1屬于2NF。現(xiàn)在我們來分析一下R1存在的問題：

(1)插入異常。學院剛成立，無在校學生，無法存入學院信息。

(2)刪除異常。假設某學院的全部學生都畢業(yè)了，則學院的信息也就丟失了。

(3)修改復雜。當某學院更換了院長時，需要修改所有學生的dmn屬性值。

(4)存在數(shù)據(jù)冗余。每一個學院的學生有多個，都要存放學院院長信息，即院長信息要重復出現(xiàn)。

造成上述問題的主要原因是：非主屬性dmn傳遞函數(shù)依賴于候選鍵sno。

解決辦法：將傳遞函數(shù)依賴關系分解出來。5.4.3第三范式(3NF)

定義5.13

如果關系模式R是1NF，而且它的任何一個非主屬性都不傳遞地依賴于任何候選鍵，則R稱為第三范式，記作R∈3NF。

例5.4

證明如果R是3NF的關系模式，則R也是2NF的關系模式。

證明：(思路：關系模式中的非主屬性對候選鍵的部分函數(shù)依賴的存在蘊涵著傳遞依賴的存在。)

設A是R的一個非主屬性，K是R的一個候選關鍵字，且K→A是一個部分依賴，那么，R中必存在某個K’

K，有K’→A成立。由于A是非主屬性，因此A∩KK’=ф。從K’

K可知K不函數(shù)依賴于K’，但K→K’成立。所以從K→K’和K’→A可知K→A是一個傳遞依賴。

因而，如果R是3NF的關系模式，則它的任何一個非主屬性都不傳遞地依賴于任何候選鍵，也就不可能存在它的任何一個非主屬性部分依賴于任何候選鍵，所以R也是2NF的關系模式。

證畢。

由此例可知，若R∈3NF，則R的每一個非主屬性既不部分函數(shù)依賴于候選鍵，也不傳遞函數(shù)依賴于候選鍵。

根據(jù)第三范式的定義可得，若X→A(A不包含在X中)違反第三范式的條件，則下列兩種情況之一會發(fā)生：X是某一個候選鍵的真子集，或者X是非關鍵字的真子集。

例5.4

分析前面講述的關系數(shù)據(jù)庫模式Ω3={R1,R2,R3}中各關系模式是否屬于第三

范式。

分析：對于R1，函數(shù)依賴集F1={sno→sname，sno→dname，dname→dmn}；sno是R1唯一的候選鍵；其主屬性有sno；其非主屬性有sname、dname和dmn。顯然不存在任何非主屬性對候選鍵的部分依賴。又因為存在sno→dname，dname→dmn，得出非主屬性dmn傳遞依賴于候選鍵sno，所以R1不屬于第三范式，而屬于第二范式。對于R2，函數(shù)依賴集F2={cno→cname}；cno是R2唯一的候選鍵；其主屬性有cno；其非主屬性有cname。因為只存在函數(shù)依賴cno→cname，顯然不存在任何非主屬性對候選鍵的部分依賴和傳遞依賴，所以R2屬于第三范式。

對于R3，函數(shù)依賴集F3={(sno,cno)→grade}；(sno,cno)是R3唯一的候選鍵；其主屬性有sno和cno；其非主屬性有grade。因為只存在函數(shù)依賴(sno,cno)→grade，顯然不存在任何非主屬性對候選鍵的部分依賴和傳遞依賴，所以R3屬于第三范式?？梢詫1分解為關系模式R11和R12：

R11={sno,sname,dname}

R12={dname,dmn}

用圖5.6的(a)、(b)分別表示關系模式R11和R12中屬性之間的函數(shù)依賴情況。

圖5.6關系模式R11和R12中屬性之間的函數(shù)依賴關系圖同理可以得出關系模式R11和R12均屬于第三范式。

部分依賴和傳遞依賴是產(chǎn)生數(shù)據(jù)冗余和插入異常、刪除異常的兩個主要原因。在3NF中不存在非主屬性對候選鍵的部分依賴和傳遞依賴，所以滿足3NF的關系模式可以消除很大一部分數(shù)據(jù)的異常和冗余，但是，3NF并沒有排除主屬性對候選鍵的傳遞依賴，因此，仍有可能存在數(shù)據(jù)的異常現(xiàn)象。

例如，有一個關系模式R(U)，U={S,T,C}，設S表示學生，T表示教師，C表示課程，這些數(shù)據(jù)的語義描述為：

·一名教師只能教一門課程。

·若干教師可以教授同一門課程。

·一旦某一個學生選定了某門課程，就確定了一個固定的教師。

R中的函數(shù)依賴關系如圖5.7所示。由此得出R上的函數(shù)依賴集合

F={(S,C)→T,(S,T)→C,T→C}

根據(jù)定理5.5可以得出：(S,C),(S,T)都是關系模式R的候選鍵；其主屬性有S、C和T；無非主屬性。顯然，不存在任何非主屬性對候選鍵的部分依賴和傳遞依賴，但存在主屬性C對候選鍵(S,T)的部分依賴，所以R∈3NF。

圖5.7關系模式R中屬性之間的函數(shù)依賴關系圖此關系模式R存在如下一些問題：

(1)數(shù)據(jù)冗余較大。雖然一個教師只教一門課程，但每個選修該教師教授的這門課程的學生對應的元組都要記錄這個教師的信息，從而產(chǎn)生一定的冗余。

(2)插入異常。如果出現(xiàn)某個學生剛剛?cè)胄＃€未選修課程或某個教師開設了某門課程，但暫時沒有學生選修的情況，由于受主屬性不能為空的限制，導致有關這個學生或教師的信息無法存入數(shù)據(jù)庫中，造成插入異常。

(3)刪除異常。如果選修了某門課程的學生全部畢業(yè)了，在刪除與這些學生有關的元組的同時，可能將相應教師開設該門課程的信息也同時丟掉了，造成刪除異常。5.4.4Boyce-Codd范式(BCNF)

定義5.14

設關系模式R是1NF。如果對于R的每個函數(shù)依賴X→Y，X必為候選鍵，則R是BCNF。

根據(jù)BCNF的定義可得，R中沒有任何屬性傳遞依賴于R的任一關鍵字。即屬于BCNF的關系模式都具有如下三個性質(zhì)：

(1)所有非主屬性都完全函數(shù)依賴于每個候選鍵；

(2)所有主屬性都完全函數(shù)依賴于每個不包含它的候選鍵；

(3)沒有任何屬性完全函數(shù)依賴于非候選鍵的任何一組屬性。

例5.5

分析前面講述的關系數(shù)據(jù)庫模式Ω2={R1,R2,R3,R4}中各關系模式是否屬于BC范式。

分析：關系數(shù)據(jù)庫模式Ω2中的各關系模式如下：

R1={sno,sname,dname}

R2={dname,dmn}

R3={cno,cname}

R4={sno,cno,grade}對于R1:

·函數(shù)依賴集F1={sno→sname，sno→dname}。

·sno是R1唯一的候選鍵。

·其主屬性有：sno。

·其非主屬性有：sname，dname。

因為只存在函數(shù)依賴sno→sname，sno→dname，顯然不存在任何非主屬性對候選鍵的部分依賴和傳遞依賴，也不存在任何主屬性對候選鍵的部分依賴和傳遞依賴，所以R1屬于BC范式。對于R2:

·函數(shù)依賴集F2={dname→dmn}。

·dname是R1唯一的候選鍵。

·其主屬性有：dname。

·其非主屬性有：dmn。

因為只存在函數(shù)依賴dname→dmn，顯然不存在任何非主屬性對候選鍵的部分依賴和傳遞依賴，也不存在任何主屬性對候選鍵的部分依賴和傳遞依賴，所以R2屬于BC范式。

對于R3:

·函數(shù)依賴集F3={cno→cname}。

·

cno是R3唯一的候選鍵。

·其主屬性有：cno。

·其非主屬性有：cname。

因為只存在函數(shù)依賴cno→cname，顯然不存在任何非主屬性對候選鍵的部分依賴和傳遞依賴，也不存在任何主屬性對候選鍵的部分依賴和傳遞依賴，所以R3屬于BC范式。對于R4:

·函數(shù)依賴集F4={(sno,cno)→grade}。

·(sno,cno)是R4唯一的候選鍵。

·其主屬性有：sno,cno。

·其非主屬性有：grade。

因為只存在函數(shù)依賴(sno,cno)→grade，顯然不存在任何非主屬性對候選鍵的部分依賴和傳遞依賴，也不存在任何主屬性對候選鍵的部分依賴和傳遞依賴，所以R4屬于BCNF。

根據(jù)以上給出的定義，我們可以看出各種范式之間的聯(lián)系有BCNF

3NF

2NF

1NF。它們之間的轉(zhuǎn)換方法為：對于1NF，通過消除其中任何非主屬性對候選鍵的部分依賴，可以變成2NF；對于1NF，通過消除其中任何非主屬性對候選鍵的部分依賴和傳遞依賴，可以變成3NF；對于3NF，通過消除其中任何主屬性對候選鍵的部分依賴和傳遞依賴，可以變成BCNF。前面已經(jīng)介紹過，不好的數(shù)據(jù)庫模式中可能存在冗余異常、插入異常、刪除異常、修改異常等。產(chǎn)生這些異常的主要原因是因為它們不屬于3NF或BCNF。一般說來，如果一個關系數(shù)據(jù)庫中的所有關系模式都屬于BCNF，那么在函數(shù)依賴范疇內(nèi)，它已實現(xiàn)了模式的徹底分解，達到了最高的規(guī)范化程度，消除了插入異常和刪除異常。

那么，對于不好的數(shù)據(jù)庫模式，怎樣才能消除這些異常呢？其方法就是對存在異常的那些關系模式進行分解。通過對關系模式的分解，可以達到使關系模式變成第三范式或更高級范式的要求。5.4.5多值依賴和第四范式(4NF)

當我們完全在函數(shù)依賴的范疇內(nèi)討論關系模式的范式問題時，僅僅考慮的是函數(shù)依賴這一種數(shù)據(jù)依賴，關系數(shù)據(jù)庫中的關系模式能達到BCNF我們就認為很完美了。但如果考慮其他數(shù)據(jù)依賴(如多值依賴)，就可能發(fā)現(xiàn)，屬于BCNF的關系模式仍可能存在問題。

1．多值依賴

定義5.15

設有關系模式R(U)，X、Y、Z

U，并且Z=U-X-Y。當且僅當R的任一關系r，r在(X,Z)上的每一個值對應一組Y的值，這組值僅僅決定于X值而與Z值無關時，稱多值依賴X→→Y成立。注：(1)若X→→Y，而Z=Ф，則稱X→→Y為平凡的多值依賴；否則稱X→→Y為非平凡的多值依賴。

(2)函數(shù)依賴X→Y的有效性僅決定于X和Y這兩個屬性集的值，與其他屬性無關。如果X→Y在屬性集W上成立，則X→Y在屬性集U(W

U)上必成立。而多值依賴的定義中不僅涉及屬性組X和Y，而且涉及U中其余屬性Z，所以如果X→→Y在U上成立，則在W(X、Y

W

U)上一定成立；但如果X→→Y在W(W

U)上成立，在U上并不一定成立。例如，設某中學中某一門課程由多個教師講授，他們都使用一套相同的參考書。我們用關系模式R(U)表示。U={C,T,B}，其中C表示課程，T表示教師姓名，B表示參考書名。表5.4表示了關系模式R的一個關系實例。表5.4關系模式R的一個關系實例關系模式R具有唯一的候選鍵(C,T,B)，顯然R∈BCNF。但關系模式R存在一些問題：

(1)當某一門課程(如數(shù)學)增加一名新教師時，需要插入多個(針對數(shù)學是四個)元組，增加了插入操作的復雜性；

(2)當某門課(如英語)根據(jù)需要，要去掉一本參考書時，也要去掉多個(針對英語是兩個)元組，帶來刪除操作的復雜性；

(3)數(shù)據(jù)冗余也是很明顯的。

存在這些問題的原因是什么呢？經(jīng)過分析我們發(fā)現(xiàn)，在這個關系模式R中，每個(C,B)上的值對應一組T值，而且這種對應與B無關。如與(C,B)對應的兩個元組(數(shù)學，初等幾何)和(數(shù)學，初等代數(shù))在B屬性上的值不同，但它們對應同一組T值{王輝，張強}，由此得出T多值依賴于C，即C→→T。就是關系模式R中存在的這種多值依賴的數(shù)據(jù)依賴，造成了上述問題的存在。

多值依賴具有以下性質(zhì)(設U是一個關系模式R的屬性集合，X、Y、Z、V、W都是U的子集合)：

(1)替代性，若X→Y，則X→→Y。

(2)對稱性，若X→→Y，則X→→U-X-Y。

(3)多值增廣性，若X→→Y，V

W，則WX→→VY。

(4)多值傳遞性，若X→→Y，Y→→Z，則X→→Z-Y。

(5)聚集性，若X→→Y，Z

Y，W∩Y=ф，W→Z，則X→Z。

(6)多值合并性，若X→→Y，X→→Z，則X→→YZ。

(7)多值偽傳遞性，若X→→Y，WY→→Z，則WX→→(Z-WY)。

(8)多值分解性，若X→→Y，X→→Z，則X→→Y∩Z，X→→Y-Z，X→→Z-Y。

(9)混合偽傳遞性，若X→→Y，XY→Z，則X→(Z-Y)。

2．第四范式

定義5.16

如果關系模式R是1NF，且對于R的每個非平凡多值依賴X→→Y(Y不是X的子集，XY未包含R的全部屬性)，X都含有R的候選鍵，則R是第四范式，記為R∈4NF。

如果一個關系模式是4NF，則它一定是BCNF；反之不然。

函數(shù)依賴是多值依賴的一種特殊情況，這兩種依賴是最重要的數(shù)據(jù)依賴。事實上，數(shù)據(jù)依賴中除函數(shù)依賴和多值依賴之外，還有一種連接依賴。多值依賴又是連接依賴的一種特殊情況。關于連接依賴的概念在此不再介紹，有興趣的讀者可以參閱有關書籍。

根據(jù)需求分析中得到的用戶要求，我們可以把關系分為兩類：

(1)靜態(tài)關系，其特點是一旦數(shù)據(jù)已加載，用戶就只能在這個關系上運行查詢操作。這種關系的要求是必須屬于1NF。

(2)動態(tài)關系，其特點是當數(shù)據(jù)加載后，可經(jīng)常對數(shù)據(jù)進行增、刪、改操作。這種關系的要求是至少屬于3NF。5.5關系模式的規(guī)范化一個低級范式的關系模式，通過分解(投影)可轉(zhuǎn)換成多個高一級范式的關系模式的集合，這種過程稱為規(guī)范化，如圖5.8所示。

圖5.8規(guī)范化過程關系模式的規(guī)范化過程是通過對關系模式的分解來實現(xiàn)的。可以把低一級的關系模式分解為若干個高一級的關系模式。這種分解不是唯一的。

一旦關系模式不滿足要求，就要對此關系模式進行分解，這是關系模式規(guī)范化的主要方法。但問題是，分解后的多個模式是否與原來的模式完全一樣呢？即所表示的信息是否與原來的信息一致呢？所表達的函數(shù)依賴集是否與原來的函數(shù)依賴集等價呢？這就涉及分解的概念和原則。5.5.1關系模式分解的概念

1．關系模式分解

設有關系模式R(U)，U={A1,A2,…,An},F是R(U)上的函數(shù)依賴的集合。ρ={R1,R2,…,Rn}，是R的一個分解，使得R1∪R2∪…∪Rn=R,U=U1∪U2∪…∪Un，F(xiàn)在Ri的屬性集合Ui上的投影是Fi={X→Y|X→Y∈F+,X,Y∈Ui}

2．關系模式分解的主要目的

關系模式分解的主要目的就是為了解決關系模式中可能存在的插入、刪除和修改時的異常情況。

注：一般此工作由數(shù)據(jù)庫設計者來進行。

3．關系模式分解的原則

關系模式分解的原則是分解后產(chǎn)生的模式應與原模式等價。

僅當分解滿足下述三種情況之一時，才能保證分解后產(chǎn)生的模式與原模式等價：

(1)分解具有“無損連接性”。

(2)分解具有“保持函數(shù)依賴性”。

(3)分解既要“保持函數(shù)依賴性”，又要具有“無損連接性”。5.5.2具有無損連接性的關系模式分解

1．分解ρ具有無損連接性

設有關系模式R(U)，F(xiàn)是R上的函數(shù)依賴集合，ρ={R1,R2,…,Rn}是R的一個分解，如果對R的任一滿足F的關系r，下式成立：

則稱分解ρ為具有無損連接性或分解ρ為無損連接分解。一般把關系r在分解ρ上的投影連接記為mρ(r)，即

滿足無損連接的條件可表示為：

r=mρ(r)

無損連接分解的特性說明關系模式分解后所表示的信息應與原模式等價，即分解后的多個關系再連接得到的新關系不能“丟失”信息。實際上，連接后的關系不會丟失任何元組，而是可能多出一些元組，因與原來的關系不等價，所以是有損的。下面的引理表明了r和mρ(r)間的關系。

引理5.3

設有關系模式R(U)及R上的關系r,ρ={R1,R2,…,Rn}是R的一個分解，則有：

(1)?r

mρ(r)

(2)?

(mρ(r))=

(r)

(3)?mρ(mρ(r))=mρ(r)

證明：(1)任取t∈r，則

根據(jù)自然連接的定義，有所以，t∈mρ(r)，即r

mρ(r)。

證畢。

根據(jù)定義直接去鑒別一個分解的無損連接性是不可能的，要通過算法來判定。

2．判定一個分解的無損連接性算法

算法5.3

判定一個分解的無損連接性的算法。

輸入：關系模式R(A1,A2,…,An)，R上的分解ρ={R1,R2,…,Rk}，R上的函數(shù)依賴集為F。

輸出：分解ρ是否具有無損連接性。

方法：

(1)構(gòu)造一個k行n列的初始表，第i行對應于關系模式Ri，第j列對應于屬性Aj。如果Aj∈Ri，則在第i行第j列上填符號ai；否則填符號bij。

(2)逐個檢查F中的每一個函數(shù)依賴，并修改表中的元素。具體辦法為：從函數(shù)依賴集F中取一個函數(shù)依賴X→Y，在X的分量中尋找相同的行，然后將這些行中Y的分量改為相同的符號，如果其中有aj，則將bij改為aj；否則，改為bij(指用其中的一個bij替換另一個，通常是把下標改為較小的那個數(shù))。

(3)反復進行，如果發(fā)現(xiàn)某一行變成了a1,a2,…,an，即存在某一行全為“a”類符號，則分解ρ具有無損連接性；如果F中所有函數(shù)依賴都不能再修改表中的內(nèi)容，且沒有發(fā)現(xiàn)這樣的行，則分解ρ不具有無損連接性。

例5.6

已知關系模式R(U)，U={A,B,C,D,E}，R上的函數(shù)依賴集F={A→C，B→C，C→D，DE→C，CE→A}，分解ρ={R1({A,D})，R2({A,B})，R3({B,E})，R4({C,D,E})，R5({A,E})}，判定ρ是否具有無損連接性。

解：(1)首先構(gòu)造初始表(見表5.5)。表5.5構(gòu)造的初始表

(2)檢查A→C，因為R1[A]=R2[A]=R5[A]，修改b13,b23,b53，使其均用b13代替。修改結(jié)果如表5.6所示。表5.6修改的結(jié)果(一)

(3)檢查B→C，因為R2[B]=R3[B]，修改b13,b33，使其均用b13代替。修改結(jié)果如表5.7所示。表5.7修改的結(jié)果(二)

(4)檢查C→D，因為R1[C]=R2[C]=R3[C]=R5[C]，修改b24,b34,b54，使其均用a4代替。修改結(jié)果如表5.8所示。

表5.8修改的結(jié)果(三)

(5)檢查DE→C，因為R3[DE]=R4[DE]=R5[DE]，修改R3[C]，R5[C]，使其均用a3代替。修改結(jié)果如表5.9所示。

表5.9修改的結(jié)果(四)

(6)檢查CE→A，因為R3[CE]=R4[CE]=R5[CE]，修改R3[A]，R4[A]，使其均用a1代替。修改結(jié)果如表5.10所示。

表5.10修改的結(jié)果(五)由于此時表中第三行已經(jīng)成為a1,a2,a3,a4,a5,所以ρ具有無損連接性。

定理5.5

算法5.3能正確判斷分解ρ是否是無損連接分解的。

證明：假設算法5.3的輸出結(jié)果是false，即構(gòu)造表(設為T)不可能出現(xiàn)全a行?？蓪⑺惴?.3最后得到的表T看做R上的一個關系r，關系r是滿足函數(shù)依賴集F的。由表T的構(gòu)造知，表T中Ri對應行的Ri所含列Aj上應為aj，因此，r在分解ρ中的每一個Ri上投影連接后應有全a的行，但r中沒有。這也就是說，mρ(r)≠r，即存在無損連接的反例。所以，分解ρ是連接有損的。假設算法5.3的輸出結(jié)果是true，即最后得到的表T中有全a行，要證明ρ是無損連接分解，必須證明滿足F的任何關系r都滿足r=mρ(r)。因為由算法5.3的步驟(2)知，全a行是為滿足F中的函數(shù)依賴將T中元素替代得到的，即若X→Y∈F，就有ti1,ti2,…,tip∈T(1＜p≤K)，當ti1[X]=ti2[X]=…=tip[X]時，則使ti1[Y]=ti2[Y]=…=tip[Y]。因為ti1[X]，ti2[X]，…，tip[X]是屬于不同的Ri的，所以，若對T中的元素賦值，替代的結(jié)果相當于作投影連接，因此，全a行所對應的值是mρ(r)中的一個元組。根據(jù)算法5.3知，構(gòu)造表T的結(jié)果是滿足F的，故對R上滿足函數(shù)依賴集F的任一關系r，如果給表T中的行賦值，使T的每行賦r中一個元組對應列的值，則賦值后T中的行若是可連接的，連接后的元組ui應屬于mρ(r)。又由算法5.3知，元組ui一定與表T中(a1,a2,…,an)所對應的元組值相同，即(a1,a2,…,an)所對應的元組值屬于mρ(r)。由于對表T的賦值可以是r中元組的任意組合，因此，不同的賦值可得到mρ(r)中所有的元組。而對表T的賦值是r中的元組，即ui∈r，因此有mρ(r)

r。由引理5.3知，r

mρ(r)，因此有r=mρ(r)。所以最后得到表T中若有全a行，則分解ρ是無損連接的。

證畢。算法5.3可檢驗任意的分解ρ，如果分解ρ僅含有兩個關系模式，則可用定理5.6來檢驗其是否是無損連接分解的。

定理5.6

設關系模式R的一個分解ρ={R1,R2}，U1、U2和U分別是R1、R2和R的屬性集合，F(xiàn)是R上的函數(shù)依賴集，則ρ具有無損連接性的充分必要條件是：

(U1∩U2)→(U1-U2)∈F+

或(U1∩U2)→(U2-U1)∈F+

證明：對這個分解應用算法5.3，構(gòu)造初始表如表5.11所示，但省略了a和b的角標，因為忽略它們不影響證明的正確性。表5.11構(gòu)造的初始表容易證明，如果在屬性A上的分量b能夠被修改成a，則屬性A屬于(U1∩U2)+。也容易利用Armstrong公理導出：如果(U1∩U2)→Y成立，則在Y上的那些b都將改成a。于是，對應R1的行全變成a當且僅當(U2

-

U1)

(U1∩U2)+(或(U1∩U2)→(U2

-

U1))。類似地，對應R2的行全變成a當且僅當(U1

-