本章內(nèi)容第4章關(guān)系數(shù)據(jù)庫設(shè)計理論4.1問題的提出4.2規(guī)范化4.3數(shù)據(jù)依賴的公理系統(tǒng)*4.4小結(jié)習(xí)題

4.1問題的提出

這一章我們討論關(guān)系數(shù)據(jù)庫設(shè)計理論。即關(guān)于：如何使用關(guān)系模型設(shè)計關(guān)系數(shù)據(jù)庫？也就是面對一個現(xiàn)實問題，如何選擇一個比較好的關(guān)系模式的集合？其中每個關(guān)系模式又由哪些屬性組成？這就是數(shù)據(jù)庫邏輯設(shè)計主要關(guān)心的問題。

這一節(jié)有兩方面的內(nèi)容:

4.1.1規(guī)范化理論概述

4.1.2不合理的關(guān)系模式存在的問題

BACK4.1.1規(guī)范化理論概述

關(guān)系數(shù)據(jù)庫設(shè)計理論主要包括三個方面的內(nèi)容：函數(shù)依賴、范式（NormalForm）和模式設(shè)計。其中函數(shù)依賴起著核心作用，是模式分解和模式設(shè)計的基礎(chǔ)，范式是模式分解的標(biāo)準(zhǔn)。

BACK4.1.2不合理的關(guān)系模式存在的問題

[例1]要求設(shè)計學(xué)生-課程數(shù)據(jù)庫，其關(guān)系模式SDC如下：SDC（SNO，SN，AGE，DEPT，MN，CNO，SCORE）其中:SNO表示學(xué)生學(xué)號

SN表示學(xué)生姓名

AGE表示學(xué)生年齡

DEPT表示學(xué)生所在的系別

MN表示系主任名

CNO表示課程號

SCORE表示成績。

SNOSNAGEDEPTMNCNOSCORES1趙紅

20計算機(jī)

張文斌

C190S1趙紅

20計算機(jī)

張文斌

C285S2王小明

17外語

劉偉華

C557S2王小明

17外語

劉偉華

C680S2王小明

17外語

劉偉華

C7S2王小明

17外語

劉偉華

C470S3吳小林

19信息

劉偉華

C175S3吳小林

19信息

劉偉華

C270S3吳小林

19信息

劉偉華

C485S4張濤

22自動化

鐘志強(qiáng)

C193圖4.1關(guān)系SDC

在進(jìn)行數(shù)據(jù)庫的操作時，會出現(xiàn)以下幾方面的問題。

(1)數(shù)據(jù)冗余。系名,學(xué)生姓名、年齡等等都要重復(fù)存儲多次

(2)插入異常。（SNO，CNO）是主鍵。缺少一個都無法插入數(shù)據(jù)另外，若學(xué)生未選課，同樣也不能進(jìn)行插入操作。

(3)刪除異常。刪去學(xué)生數(shù)據(jù)，導(dǎo)致課程及教師信息丟失。如果某個學(xué)生不再選修某課程，有關(guān)該學(xué)生的其他信息也隨之丟失。

(4)修改異常。如果某學(xué)生改名，則該學(xué)生的所有記錄都要逐一修改SN的值；稍有不慎，就有可能漏改某些記錄。

我們把關(guān)系模式SDC分解為:

學(xué)生關(guān)系S（SNO，SNO，AGE，DEPT）系關(guān)系D（DEPT，MN）選課關(guān)系SC（SNO，CNO，SCORE）SSNOSNAGEDEPTS1趙紅

20計算機(jī)

S2王小明

17外語

S3吳小林

19信息

S4張濤

22自動化

DDEPTMN計算機(jī)

張文斌

外語

劉偉華

信息

劉偉華

自動化

鐘志強(qiáng)

圖4.2關(guān)系SDC經(jīng)分解后的三關(guān)系S、D與SC

SCSNOCNOSCORES1C190S1C285S2C557S2C680S2C7S2C470S3C175S3C270S3C485S4C193

分解后的關(guān)系模式集是一個好的關(guān)系數(shù)據(jù)庫模式。這三個關(guān)系模式都不會發(fā)生插入異常、刪除異常的毛病，數(shù)據(jù)冗余也得到了盡可能地控制。但要注意，一個好的關(guān)系模式并不是在任何情況下都是最優(yōu)的，比如查詢某個學(xué)生選修課程名及所在系的系主任時，要通過連接操作來完成（即由圖4.2中的三張表，連接形成圖4.1中的一張總表），而連接所需要的系統(tǒng)開銷非常大，因此要以實際設(shè)計的目標(biāo)出發(fā)進(jìn)行設(shè)計。

BACK

4.2規(guī)范化

本節(jié)將討論下述內(nèi)容：首先討論一個關(guān)系屬性間不同的依賴情況，討論如何根據(jù)屬性間的依賴情況來判定關(guān)系是否具有某些不合適的性質(zhì)。通常按屬性間依賴情況來區(qū)分關(guān)系規(guī)范化的程度為第一范式、第二范式、第三范式、BC范式和第四范式等。然后直觀地描述如何將具有不合適性質(zhì)的關(guān)系轉(zhuǎn)換為更合適的形式。

BACK4.2.1函數(shù)依賴

⒈函數(shù)依賴

定義4.1設(shè)關(guān)系模式R（U，F(xiàn)），U是屬性全集，F(xiàn)是U上的函數(shù)依賴集，X和Y是U的子集，如果對于R（U）的任意一個可能的關(guān)系r，對于X的每一個具體值，Y都有唯一的具體的值與之對應(yīng)，則稱X函數(shù)決定Y，或Y函數(shù)依賴于X，記X→Y。我們稱X為決定因素，Y為依賴因素。當(dāng)Y不函數(shù)依賴于X時，記作：XY。當(dāng)X→Y且Y→X時，則記作：XY。

對于關(guān)系模式SDC：U={SNO，SN，AGE，DEPT，MN，CNO，SCORE}F={SNO→SN，SNO→AGE，SNO→DEPT，DEPT→MN，SNO→MN，(SNO，CNO)→SCORE}

一個SNO有多個SCORE的值與之對應(yīng)，因此SCORE不能唯一地確定，即SCORE不能函數(shù)依賴于SNO，所以有：SNOSCORE，同樣有：CNOSCORE。但是SCORE可以被（SNO，CNO）唯一地確定。所以可表示為：（SNO，CNO）→SCORE。

函數(shù)依賴有幾點需要說明。（1）

平凡的函數(shù)依賴與非平凡的函數(shù)依賴當(dāng)屬性集Y是屬性集X的子集時，則必然存在著函數(shù)依賴X→Y，這種類型的函數(shù)依賴稱為平凡的函數(shù)依賴。如果Y不是X子集，則稱X→Y為非平凡的函數(shù)依賴。若不特別聲明，我們討論的都是非平凡的函數(shù)依賴。（2）

函數(shù)依賴與屬性間的聯(lián)系類型有關(guān)①

在一個關(guān)系模式中，如果屬性X與Y有1:1聯(lián)系時，則存在函數(shù)依賴X→Y,Y→X，即XY。例如，當(dāng)學(xué)生沒有重名時，SNOSN。

②

如果屬性X與Y有m:1的聯(lián)系時，則只存在函數(shù)依賴X→Y。例如，SNO與AGE，DEPT之間均為m:1聯(lián)系，所以有SNO→AGE，SNO→DEPT。③

如果屬性X與Y有m:n的聯(lián)系時，則X與Y之間不存在任何函數(shù)依賴關(guān)系。例如，一個學(xué)生可以選修多門課程，一門課程又可以為多個學(xué)生選修，所以SNO與CNO之間不存在函數(shù)依賴關(guān)系。由于函數(shù)依賴與屬性之間的聯(lián)系類型有關(guān)，所以在確定屬性間的函數(shù)依賴時，可以從分析屬性間的聯(lián)系入手，便可確定屬性間的函數(shù)依賴。

(3)

函數(shù)依賴的語義范疇的概念我們只能根據(jù)語義來確定一個函數(shù)依賴，而不能按照其形式化定義來證明一個函數(shù)依賴是否成立。例如，對于關(guān)系模式S，當(dāng)學(xué)生不存在重名的情況下，可以得到：

SN→AGE、SN→DEPT

這種函數(shù)依賴關(guān)系，必須是在沒有重名的學(xué)生條件下才成立，否則就不存在函數(shù)依賴了。所以函數(shù)依賴反映了一種語義完整性約束，是語義的要求。

(4)

函數(shù)依賴關(guān)系的存在與時間無關(guān)(5)

函數(shù)依賴可以保證關(guān)系分解的無損連接性

設(shè)R（X，Y，Z），X、Y、Z為不相交的屬性集合，如果X→Y或X→Z則有R（X，Y，Z）=R[X，Y]∞R[X，Z]，其中R[X，Y]表示關(guān)系R在屬性（X，Y）上的投影，即R等于兩個分別含決定因素X的投影關(guān)系（分別是R[X，Y]與R[X，Z]）在X上的自然連接，這樣便保證了關(guān)系R分解后不會丟失原有的信息，稱作關(guān)系分解的無損連接性。

例如，對于關(guān)系模式SDC，有

SNO→（SNO，SN，AGE，DEPT，MN），

SDC（SNO，SN，AGE，DEPT，MN，CNO，SCORE）=SDC[SNO，SN，AGE，DEPT，MN]∞SDC[SNO，CNO，SCORE]，也就是說，用其投影在SNO上的自然連接可復(fù)原關(guān)系模式SDC。這一性質(zhì)非常重要，在后面的關(guān)系規(guī)范化中要用到。

⒉函數(shù)依賴的基本性質(zhì)（1）

投影性根據(jù)平凡的函數(shù)依賴的定義可知，一組屬性函數(shù)決定它的所以子集。例如，在關(guān)系SDC中，（SNO，CNO）→SNO和（SNO，CNO）→CNO。說明：投影性產(chǎn)生的是平凡的函數(shù)依賴，需要時也能使用的。（2）

擴(kuò)張性若X→Y且W→Z，則（X，W）→（Y，Z）。例如，SNO→（SN，AGE），DEPT→MN，則有（SNO，DEPT）→（SN，AGE，MN）。說明：擴(kuò)張性實現(xiàn)了兩函數(shù)依賴決定因素與被決定因素的分別合并作用。

(3)

合并性若X→Y且X→Z則必有X→（Y，Z）。例如，在關(guān)系SDC中，SNO→（SN，AGE），SNO→DEPT，則有SNO→（SN，AGE，DEPT）。說明：決定因素相同的兩函數(shù)依賴被決定因素的可以合并。(4)

分解性若X→（Y，Z），則X→Y且X→Z。很顯然，分解性為合并性的逆過程。說明：決定因素能決定全部，當(dāng)然也能決定全部中的部分。由合并性和分解性，很容易得到以下事實：

X→A1，A2，…,An成立的充分必要條件是X→Ai（i=1,2,…,n）成立。3．完全/部分函數(shù)依賴和傳遞/非傳遞函數(shù)依賴定義4.2

設(shè)有關(guān)系模式R（U），U是屬性全集，X和Y是U的子集，X→Y，并且對于X的任何一個真子集X'，都有X‘

Y，則稱Y對X完全函數(shù)依賴（FullFunctionalDependency）,記作XfY。如果對X的某個真子集X'，有X'→Y，則稱Y對X部分函數(shù)依賴（PartialFunctionalDependency）,記作XpY。例如，在關(guān)系模式SDC中，因為SNOSCORE，且CNOSCORE，所以有：（SNO，CNO）fSCORE。而因為有SNO→AGE，所以有（SNO，CNO）pAGE。

定義4.3

設(shè)有關(guān)系模式R（U），U是屬性全集，X，Y，Z是U的子集，若X→Y，但YX，而Y→Z（Y?X），則稱Z對X傳遞函數(shù)依賴（TransitiveFunctionalDependency）,記作：XtZ。注意：如果有Y→X，則XY，這時稱Z對X直接函數(shù)依賴，而不是傳遞函數(shù)依賴。

4.2.2碼

在第2章中已給出有關(guān)碼的概念。這里用函數(shù)依賴的概念來定義碼。定義4.4

設(shè)K為R（U，F(xiàn)）中的屬性或?qū)傩约?，若Kf

U則K為R的候選碼（或候選關(guān)鍵字或候選鍵）（Candidatekey）。若候選碼多于一個，則選定其中的一個為主碼(或稱主鍵，Primarykey)。

包含在任何一個候選碼中的屬性，叫做主屬性(Primeattribute)。不包含在任何候選碼中的屬性稱為非主屬性(Nonprimeattribute)或非碼屬性（Non-keyattribute）。在最簡單的情況，單個屬性是碼。最極端的情況，整個屬性組U是碼，稱為全碼（All-key）。如在關(guān)系模式S（SNO，DEPT，AGE）中SNO是碼，而在關(guān)系模式SC（SNO，CNO，SCORE）中屬性組合（SNO，CNO）是碼。下面舉個全碼的例子。

關(guān)系模式TCS（T，C，S），屬性T表示教師，C表示課程，S表示學(xué)生。一個教師可以講授多門課程，一門課程可有多個教師講授，同樣一個學(xué)生可以選聽多門課程，一門課程可被多個學(xué)生選聽。教師T，課程C，學(xué)生S之間是多對多關(guān)系，單個屬性T、C、S或兩個屬性組合（T，C）、（T，S）

、（C，S）等均不能完全決定整個屬性組U，只有（T，C，S）→U，所以這個關(guān)系模式的碼為（T，C，S），即All-key。

全碼關(guān)系只有主屬性。

找出已知關(guān)系模式R（U，F(xiàn)）的所有候選鍵的方法：1、查看函數(shù)依賴集F中的每個形如Xi→Yi（要確認(rèn)每個函數(shù)依賴Xi→Yi均為非平凡的完全的函數(shù)依賴）的（i=1,……,n）函數(shù)依賴關(guān)系?？茨男傩栽谒衁i（i=1,……,n）中沒有出現(xiàn)過，設(shè)沒出現(xiàn)過的屬性集為P（P=U-Y1-Y2……-Yn）。則當(dāng)P=φ（表示空集）時，轉(zhuǎn)4

當(dāng)P≠φ時，轉(zhuǎn)2。2、根據(jù)候選鍵的定義，候選鍵中應(yīng)必含P（因為沒有其它屬性能決定P）?？疾霵:

若有PfU成立，則P為候選鍵，并且候選鍵只有一個P,轉(zhuǎn)5結(jié)束若PfU不成立，則轉(zhuǎn)3。

3、P可以分別與{U-P}中的每一個屬性合并，形成P1，P2，……，Pm。再分別判斷Pjf

U（j=1,……,m）是否成立？能成立則找到了一個候選鍵，沒有則放棄。合并一個屬性若不能找到或不能找全候選鍵，可進(jìn)一步考慮P與{U-P}中的兩個（或三個，四個，……）屬性的所有組合分別進(jìn)行合并，繼續(xù)判斷分別合并后的各屬性組對U的完全函數(shù)決定情況……；如此直到找出R的所有候選鍵為止。轉(zhuǎn)5結(jié)束。（需要提醒的是：如若屬性組K已有Kf

U，則完全不必去考察含K的其它屬性組合了，顯然它們都不可能再是候選鍵了）。

4、若P=φ，則可以先考察Xi→Yi（i=1,……,n）中的單個Xi,判斷是否有Xif

U？若成立則Xi為候選鍵。剩下不是候選鍵的Xi,可以考察它們兩個或多個的組合，查看其是否能完全函數(shù)決定U，從而找出其它還有可能的候選鍵。轉(zhuǎn)5結(jié)束。

5、本方法結(jié)束。

定義4.5

關(guān)系模式R中屬性或?qū)傩越MX并非R的主碼，但X是另外一個關(guān)系模式S的主碼，則稱X是R的外部碼或外部關(guān)系鍵（ForeignKey），也稱外碼。如在SC（SNO，CNO，SCORE）中，單SNO不是主碼，但SNO是關(guān)系模式S（SNO，SN，SEX，AGE，DEPT）的主碼，則SNO是SC的外碼。主碼與外碼提供了一個表示關(guān)系間聯(lián)系的手段。如關(guān)系模式S與SC的聯(lián)系就是通過SNO這個在S中是主碼又在SC中是外碼的屬性來體現(xiàn)的。

4.2.3范式

關(guān)系數(shù)據(jù)庫的規(guī)范化過程中為不同程度的規(guī)范化要求設(shè)立的不同的標(biāo)準(zhǔn)或準(zhǔn)則稱為范式（NormalForm）。滿足最低要求的叫第一范式,簡稱1NF。在第一范式中滿足進(jìn)一步要求的為第二范式(2NF),其余以此類推。R為第幾范式就可以寫成R∈xNF（x表示某范式名）。

各個范式之間的集合關(guān)系可以表示為：5NF?4NF?BCNF?3NF?2NF?1NF圖4.3各范式之間的關(guān)系

一個低一級范式的關(guān)系模式，通過模式分解

可以轉(zhuǎn)換為若干個高一級范式的關(guān)系模式的集合，這種過程就叫規(guī)范化。

4.2.4第一范式

第一范式（FirstNormalForm）是最基本的規(guī)范化形式，即關(guān)系中每個屬性都是不可再分的簡單項。定義4.6如果關(guān)系模式R所有的屬性均為簡單屬性，即每個屬性都是不可再分的，則稱R屬于第一范式，簡稱1NF，記作R∈1NF。在關(guān)系數(shù)據(jù)庫系統(tǒng)中只討論規(guī)范化的關(guān)系，凡是非規(guī)范化的關(guān)系模式必須轉(zhuǎn)化成規(guī)范化的關(guān)系。在非規(guī)范化的關(guān)系中去掉組合項就能轉(zhuǎn)化成規(guī)范化的關(guān)系。每個規(guī)范化的關(guān)系都是屬于1NF。

[例2]如職工號，姓名，電話號碼組成一個表（一個人可能有一個辦公室電話和一個家里電話號碼）規(guī)范成為1NF有四種方法：一是重復(fù)存儲職工號和姓名。這樣關(guān)鍵字是職工號與電話號碼的組合。關(guān)系模式為：職工(職工號，姓名，電話號碼)。二是職工號為關(guān)鍵字，電話號碼分為單位電話和住宅電話兩個屬性。關(guān)系模式為：職工(職工號，姓名，單位電話，住宅電話)。三是職工號為關(guān)鍵字，但強(qiáng)制每條記錄只能有一個電話號碼。關(guān)系模式為：職工(職工號，姓名，電話號碼)。四分析設(shè)計成兩個關(guān)系，關(guān)系模式分別為：職工(職工號，姓名)，職工電話(職工號，電話號碼)，兩關(guān)系的關(guān)鍵字分別是職工號，職工號與電話號碼的組合。以上四個方法，可按實際情況選取使用。

4.2.5第二范式

1．第二范式的定義定義4.7

如果關(guān)系模式R∈1NF，R（U，F(xiàn)）中的所有非主屬性都完全函數(shù)依賴于任意一個候選關(guān)鍵字，則稱關(guān)系R

是屬于第二范式（SecondNormalForm），簡稱2NF，記作R∈2NF。從定義可知，滿足第二范式的關(guān)系模式R中，不可能有某非主屬性對某候選關(guān)鍵字存在部分函數(shù)依賴。下面讓我們來分析下4.1.2節(jié)中給出的關(guān)系模式SDC。

在關(guān)系模式SDC中，它的關(guān)系鍵是（SNO，CNO）的屬性組合，函數(shù)依賴關(guān)系有：

（SNO，CNO）fSCORESNO→SN，（SNO，CNO）pSNSNO→AGE，（SNO，CNO）pAGESNO→DEPT，（SNO，CNO）pDEPT，DEPT→MNSNOtMN,（SNO，CNO）

p

MN

我們可以用函數(shù)依賴圖表示以上函數(shù)依賴關(guān)系，如圖4.4所示。

由此可見，在SDC中，既存在完全函數(shù)依賴，又存在部分函數(shù)依賴和傳遞函數(shù)依賴，所以SDC2NF，這種情況往往在數(shù)據(jù)庫中是不允許的，也正是由于關(guān)系中存在著復(fù)雜的函數(shù)依賴，才導(dǎo)致數(shù)據(jù)操作中出現(xiàn)了數(shù)據(jù)冗余、插入異常、刪除異常、修改異常等弊端。圖4.4SDC中函數(shù)依賴圖

SCORESNOCNOAGESNMNDEPTptpppf2.2NF的規(guī)范化

2NF規(guī)范化是指把1NF關(guān)系模式通過投影分解，消除非主屬性對候選關(guān)鍵字的部分函數(shù)依賴，轉(zhuǎn)換成2NF關(guān)系模式的集合的過程。分解時遵循的原則是“一事一地”，讓一個關(guān)系只描述一個實體或?qū)嶓w間的聯(lián)系。如果多于一個實體或聯(lián)系，則進(jìn)行投影分解。據(jù)此我們可以將關(guān)系模式SDC分解成兩個關(guān)系模式：

SD（SNO，SN，AGE，DEPT，MN），描述學(xué)生實體

SC（SNO，CNO，SCORE），描述學(xué)生與課程的聯(lián)系。

對于分解后的關(guān)系模式SD的碼為SNO，關(guān)系模式SC的候選關(guān)鍵字為（SNO，CNO），非主屬性對候選關(guān)鍵字均是完全函數(shù)依賴的，這樣就消除了非主屬性對候選關(guān)鍵字的部分函數(shù)依賴。即SD∈2NF，SC∈2NF，它們之間通過SC中的外鍵SNO相聯(lián)系，需要時再進(jìn)行自然聯(lián)接，能恢復(fù)成原來的關(guān)系，這種分解不會丟失任何信息，具有無損連接性。分解后的函數(shù)依賴圖如圖4.5和4.6所示。

圖4.5SD中的函數(shù)依賴關(guān)系圖

圖4.6SC中的函數(shù)依賴關(guān)系

SNOSNMNAGEDEPTSNOCNOSCORE

注意：如果R的候選關(guān)鍵字均為單屬性，或R的全體屬性均為主屬性，則R∈2NF。例如，在講述全碼的概念時給出的關(guān)系模式TCS（T，C，S），（T，C，S）三個屬性的組合才是其唯一的候選關(guān)鍵字即關(guān)系鍵，T，C，S均是主屬性，不存在非主屬性，所以也不可能存在非主屬性對候選關(guān)鍵字的部分函數(shù)依賴，因此TCS∈2NF。

4.2.6第三范式

1．第三范式的定義定義4.8

如果關(guān)系模式R∈2NF，R（U，F(xiàn)）中所有非主屬性對任何候選關(guān)鍵字都不存在傳遞函數(shù)依賴，則稱R是屬于第三范式（ThirdNormalForm），簡稱3NF，記作R∈3NF。第三范式具有如下性質(zhì)：

(1)

如果R∈3NF，則R也是2NF。證明：采用反證法。設(shè)R∈3NF，但R?2NF。則根據(jù)判定2NF的定義知，必有非主屬性Ai（Ai?U，U是R的所有屬性集），候選關(guān)鍵字K和K的真子集K’(即K’?K)存在，使得有K’→Ai。由于Ai是非主屬性，所以Ai-K

（代表空），Ai-K’

。由于K’

?

K，所以K-K’

，并可以斷定K’

K。這樣有K→K’且K’

K，K’→Ai，且Ai-K

，Ai-K’

，即有非主屬性Ai傳遞函數(shù)依賴于候選鍵K(若覺得K’

K，則可以在K’上合并一個Aj，設(shè)Aj亦為非主屬性，此時仍有K→K’Aj且K’Aj?

K，K’AjK，K’Aj→Ai)，所以R?3NF，與題設(shè)R∈3NF相矛盾。從而命題得證。

(2)

如果R∈2NF，則R不一定是3NF。例如：前面講的關(guān)系模式SDC分解為SD和SC，其中SC是3NF，但SD就不是3NF，因為SD中存在非主屬性對候選關(guān)鍵字的傳遞函數(shù)依賴：SNO→DEPT，DEPT→MN，即SNOtMN。

2NF的關(guān)系模式解決了1NF中存在的一些問題，但2NF的關(guān)系模式SDC在進(jìn)行數(shù)據(jù)操作時，仍然存在下面一些問題：

（1）

數(shù)據(jù)冗余。如果每個系名和系主任的名字存儲的次數(shù)等于該系學(xué)生的人數(shù)。（2）

插入異常。當(dāng)一個新系沒有招生時，有關(guān)該系的信息無法插入。（3）

刪除異常。如某系學(xué)生全部畢業(yè)而沒有招生時，刪除全部學(xué)生的記錄也隨之刪除了該系的有關(guān)信息。（4）

修改異常。如更換系主任時仍需要改動較多的學(xué)生記錄。之所以存在這些問題，是由于在SDC中存在著非主屬性對候選關(guān)鍵字的傳遞依賴。消除這種依賴就轉(zhuǎn)換成了3NF。

2．3NF的規(guī)范化

3NF規(guī)范化是指把2NF關(guān)系模式通過投影分解，消除非主屬性對候選關(guān)鍵字的傳遞函數(shù)依賴，而轉(zhuǎn)換成3NF關(guān)系模式集合的過程。

3NF規(guī)范化同樣遵循“一事一地”原則。我們繼續(xù)將只屬于2NF的關(guān)系模式SD規(guī)范為3NF。根據(jù)“一事一地”原則可SD分解為：

S（SNO，SN，AGE，DEPT），描述學(xué)生實體；D（DEPT，MN），描述系的實體。分解后S和D的主鍵分別為SNO和DEPT，不存在傳遞函數(shù)依賴。所以S∈3NF，D∈3NF。S和D的函數(shù)依賴分別如圖4.7和圖4.8所示。

圖4.7S中的函數(shù)倚賴關(guān)系圖

4.8D中的函數(shù)依賴關(guān)系圖

SNODEPTAGESNMNDEPT

由以上兩圖可以看出，關(guān)系模式SD由2NF分解為3NF后，函數(shù)依賴關(guān)系變得更加簡單，既沒有非主屬性對碼的部分依賴，也沒有非主屬性對碼的傳遞依賴，解決了2NF中存在的四個問題，因此，分解后的關(guān)系模式S和D具有以下特點：（1）數(shù)據(jù)冗余度降低了。如系主任的名字存儲的次數(shù)與該系的學(xué)生人數(shù)無關(guān)，只在關(guān)系D中存儲一次。（2）不存在插入異常。如當(dāng)一個新系沒有學(xué)生時，該系的信息可以直接插入到關(guān)系D中，而與學(xué)生關(guān)系S無關(guān)。（3）不存在刪除異常。如當(dāng)要刪除某系的全部學(xué)生而仍然保留該系的有關(guān)信息時，可以只刪除學(xué)生關(guān)系S中的相關(guān)記錄，而不影響系關(guān)系D中的數(shù)據(jù)。（4）不存在修改異常。如更換系主任時，只需修改關(guān)系D中一個相應(yīng)元組的MN屬性值，從而不會出現(xiàn)數(shù)據(jù)的不一致現(xiàn)象。

SDC規(guī)范化到3NF后，所存在的異?，F(xiàn)象已經(jīng)全部消失。但是，3NF只限制了非主屬性對碼的依賴關(guān)系，而沒有限制主屬性對碼的依賴關(guān)系。如果發(fā)生了這種依賴，仍有可能存在數(shù)據(jù)冗余、插入異常、刪除異常和修改異常。這時，則需對3NF進(jìn)一步規(guī)范化，消除主屬性對碼的依賴關(guān)系，向更高一級的范式BCNF轉(zhuǎn)換。4.2.7BC范式

1．BC范式的定義定義4.9

如果關(guān)系模式R∈1NF，且所有的函數(shù)依賴X→Y（Y不包含于X，即YX），決定因素X都包含了R的一個候選碼，則稱R屬于BC范式（Boyce-CoddNormalForm）,記作R∈BCNF。由BCNF的定義可以得到以下結(jié)論，一個滿足BCNF的關(guān)系模式有：（1）所有非主屬性對每一個候選碼都是完全函數(shù)依賴。（2）所有的主屬性對每一個不包含它的候選碼都是完全函數(shù)依賴。（3）沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。

由于R∈BCNF，按定義排除了任何屬性對候選碼的傳遞依賴與部分依賴，所以R∈3NF。證明留給讀書完成。但若R∈3NF，則R未必屬于BCNF。下面舉例說明。例設(shè)有關(guān)系模式SCS（SNO，SN，CNO，SCORE），其中SNO代表學(xué)號，SN代表學(xué)生姓名，并假設(shè)不重名，CNO代表課程號，SCORE代表成績?？梢耘卸?，SCS有兩個候選鍵（SNO，CNO）和（SN，CNO），其函數(shù)依賴如下：

SNOSN

（SNO，CNO）→SCORE

（SN，CNO）→SCORE

唯一的非主屬性SCORE對鍵不存在部分函數(shù)依賴，也不存在傳遞函數(shù)依賴。所以SCS∈3NF。但是，因為SNOSN，即決定因素SNO或SN不包含候選鍵，從另一個角度說，存在著主屬性對鍵的部分函數(shù)依賴：（SNO，CNO）pSN，（SN，CNO）pSNO，所以SCS不是BCNF。正是存在著這種主屬性對鍵的部分函數(shù)依賴關(guān)系，造成了關(guān)系SCS中存在著較大的數(shù)據(jù)冗余，解決這一問題的辦法仍然是通過投影分解進(jìn)一步提高范式的等級，將其規(guī)范到BCNF。

2．

BCNF規(guī)范化

BCNF規(guī)范化是指把3NF的關(guān)系模式通過投影分解轉(zhuǎn)換成BCNF關(guān)系模式的集合。下面以3NF的關(guān)系模式SCS為例，來說明BCNF規(guī)范化的過程。例將SCS（SNO，SN，CNO，SCORE）規(guī)范到BCNF。SCS產(chǎn)生數(shù)據(jù)冗余的原因是因為在這個關(guān)系中存在兩個實體，一個為學(xué)生實體，屬性有SNO，SN；另一個為選課實體，屬性有SNO，CNO和SCORE。根據(jù)分解的原則，我們可以將SCS分解成如下兩個關(guān)系：

S（SNO，SN），描述學(xué)生實體

SC（SNO，CNO，SCORE），描述學(xué)生與課程的聯(lián)系。

圖

4.9S中的函數(shù)依賴關(guān)系圖

圖4.10SC中的函數(shù)依賴關(guān)系圖

對于S，有兩個候選碼SNO和SN；對于SC，主碼為（SNO，CNO）。在這兩個關(guān)系中，無論主屬性還是非主屬性都不存在對碼的部分函數(shù)依賴和傳遞依賴，S∈BCNF，SC∈BCNF。分解后，S和SC的函數(shù)依賴分別如圖4.9和圖4.10所示。

SNOSNSNOCNOSCORE

關(guān)系SCS轉(zhuǎn)換成BCNF后，數(shù)據(jù)冗余度明顯降低。學(xué)生的姓名只在關(guān)系S中存儲一次，學(xué)生要改名時，只需改動一條學(xué)生記錄中相應(yīng)的SN值即可，從而不會發(fā)生修改異常。下面再舉一個有關(guān)BCNF規(guī)范化的實例。[例5]

設(shè)有關(guān)系模式STK（S，T，K），S表示學(xué)生，T表示教師，K表示課程。語義假設(shè)是，每一位教師只講授一門課程；每門課程由多個教師講授；某一學(xué)生選定某門課程，就對應(yīng)一個確定的教師。根據(jù)語義假設(shè)，STK的函數(shù)依賴是：（S，K）→T，（S，T）→K，T→K。函數(shù)依賴圖如圖4.11所示。

圖4.11STK中的函數(shù)依賴關(guān)系

TKSKTS

這里（S，K），（S，T）都是候選碼。

STK是3NF，因為沒有任何非主屬性對碼的傳遞依賴或部分依賴（因為STK中沒有非主屬性）。但STK不是BCNF關(guān)系，因為有T→K，T是決定因素，而T不包含候選碼。對于不是BCNF的關(guān)系模式，仍然存在不合適的地方。非BCNF的關(guān)系模式STK可分解為ST（S，T）和TK（T，K），它們都是BCNF。

3NF和BCNF是在函數(shù)依賴的條件下對模式分解所能達(dá)到的分離程度的測度。一個模式中的關(guān)系模式如果都屬于BCNF，那么在函數(shù)依賴范疇內(nèi)，它已實現(xiàn)了徹底的分離，已消除了插入和刪除異常。3NF的“不徹底”性表現(xiàn)在可能存在主屬性對候選碼的部分依賴和傳遞依賴。

1.

多值依賴

(1)多值依賴的定義一個關(guān)系屬于BCNF范式，是否就已經(jīng)很完美了呢？為此，我們先看一個例子。[例6]

假設(shè)學(xué)校中一門課程可由多名教師教授，教學(xué)中他們使用相同的一套參考書，這樣我們可用如圖4.12的非規(guī)范化的關(guān)系來表示課程C、教師T和參考書R間的關(guān)系。如果我們把圖4.12的關(guān)系CTR轉(zhuǎn)化成規(guī)范化的關(guān)系，如圖4.13所示。

4.2.8多值依賴與4NF圖4.12關(guān)系CTR

課程C

教員T

參考書R

數(shù)據(jù)庫系統(tǒng)概論

計算數(shù)學(xué)薩師煊王珊

張平周峰

數(shù)據(jù)庫原理與應(yīng)用數(shù)據(jù)庫系統(tǒng)SQLServer2000數(shù)學(xué)分析微分方程

圖4.13規(guī)范后的關(guān)系CTR

課程C

教師T

參考書R

數(shù)據(jù)庫系統(tǒng)概論數(shù)據(jù)庫系統(tǒng)概論數(shù)據(jù)庫系統(tǒng)概論數(shù)據(jù)庫系統(tǒng)概論數(shù)據(jù)庫系統(tǒng)概論數(shù)據(jù)庫系統(tǒng)概論計算數(shù)學(xué)計算數(shù)學(xué)計算數(shù)學(xué)計算數(shù)學(xué)

薩師煊薩師煊薩師煊王珊王珊王珊張平張平周峰周峰

數(shù)據(jù)庫原理與應(yīng)用數(shù)據(jù)庫系統(tǒng)SQLServer2000數(shù)據(jù)庫原理與應(yīng)用數(shù)據(jù)庫系統(tǒng)SQLServer2000數(shù)學(xué)分析微分方程數(shù)學(xué)分析微分方程

由此可以看出，規(guī)范后的關(guān)系模式CTR，只有唯一的一個函數(shù)依賴（C，T，R）→U（U即關(guān)系模式CTR的所有屬性的集合），其碼顯然是（C，T，R），即全碼，因而CTR屬于BCNF范式。但是進(jìn)一步分析可以看出，CTR還存在著如下弊端：①數(shù)據(jù)冗余大。課程、教師和參考書都被多次存儲。②插入異常。若增加一名教授“計算數(shù)學(xué)”的教師“李靜”時，由于這個教師也使用相同的一套參考書，所以需要添加兩個元組，即：（計算數(shù)學(xué)，李靜，數(shù)學(xué)分析）和（計算數(shù)學(xué)，李靜，微分方程）。③刪除異常。若要刪除某一門課的一本參考書，則與該參考書有關(guān)的元組都要被刪除，如：刪除“數(shù)據(jù)庫系統(tǒng)概論”課程的“數(shù)據(jù)庫系統(tǒng)”，則需要刪除（數(shù)據(jù)庫系統(tǒng)概論，薩師煊，數(shù)據(jù)庫系統(tǒng)）和（數(shù)據(jù)庫系統(tǒng)概論，王珊，數(shù)據(jù)庫系統(tǒng)）兩個元組。

產(chǎn)生以上弊端的原因主要有以下兩方面：①對于關(guān)系CTR中的C的一個具體值來說，有多個T值與其相對應(yīng)；同樣，C與R間也存在著類似的聯(lián)系。②對于關(guān)系CTR中的一個確定的C值，與其所對應(yīng)的一組T值與R值無關(guān)。如：與“數(shù)據(jù)庫系統(tǒng)概論”課程對應(yīng)的一組教師與此課程的參考書毫無關(guān)系。從以上兩個方面可以看出，C與T間的聯(lián)系顯然不是函數(shù)依賴，在此我們稱之為多值依賴（MultivaluedDependency,MVD）。

定義4.10

設(shè)有關(guān)系模式R（U），U是屬性全集，X，Y，Z是屬性集U的子集，且Z=U-X-Y，如果對于R的任一關(guān)系，對于X的一個確定值，存在的一組值與之對應(yīng)，且Y的這組值僅僅決定于X的值而與Z值無關(guān)，此時稱Y多值依賴于X，或X多值決定Y，記作：X→→Y。在多值依賴中，若X→→Y且Z=U-X-Y≠φ，則稱X→→Y是非平凡的多值依賴，否則稱為平凡的多值依賴。如：在關(guān)系模式CTR中，對于某一C、R屬性值組合（數(shù)據(jù)庫系統(tǒng)概論，數(shù)據(jù)庫系統(tǒng)）來說，有一組T值{薩師煊，王珊}，這組值僅僅決定與課程C上的值（數(shù)據(jù)庫系統(tǒng)概論）。也就是說，對于另一個C、R屬性值組合(數(shù)據(jù)庫系統(tǒng)概論，SQLServer2000),它對應(yīng)的一組T值仍是{薩師煊，王珊}，盡管這時參考書R的值已經(jīng)改變了。因此T多值依賴于C，即：C→→T。

下面是多值依賴的另一形式化定義：設(shè)有關(guān)系模式R（U），U是屬性全集，X、Y、Z是屬性集合U的子集，且Z=U-X-Y，r是關(guān)系模式R的任一關(guān)系，t,s是r的任意兩個元組，如果t[X]=s[X],r中必有的兩個元組u、v存在，使得：①s[x]=t[X]=u[X]=v[X]②u[Y]=t[Y]且u[Z]=s[Z]③v[Y]=s[Y]且v[Z]=t[Z]

則稱X多值決定Y或Y多值依賴于X。

(2)

多值依賴與函數(shù)依賴的區(qū)別①在關(guān)系模式R中，函數(shù)依賴X→Y的有效性僅僅決定與X、Y這兩個屬性集，不涉及第三個屬性集，而在多值依賴中，X→→Y在屬性集U（U=X+Y+Z）上是否成立，不僅要檢查屬性集X、Y上的值，而且要檢查屬性集U的其余屬性Z上的值。因此，如果X→→Y在屬性集W（W?U）上成立，而在屬性集U上不一定成立，所以，多值依賴的有效性與屬性集的范圍有關(guān)。如果在R（U）上有X→→Y，在屬性集W（W?U）上也成立，則稱X→→Y為R（U）的嵌入型多值依賴。②如果在關(guān)系模式R上存在函數(shù)依賴X→Y，則任何Y‘包含于Y均有X→Y‘成立，而多值依賴X→→Y在R上成立，但不能斷言對于任何Y'包含于Y有X→→Y'成立。

（３）多值依賴的性質(zhì)①多值依賴具有對稱性。即若X→→Y，則X→→Z，其中Z＝U-X-Y。②多值依賴具有傳遞性。即若X→→Y，Y→→Z，則

X→→Z-Y。③函數(shù)依賴可看作是多值依賴的特殊情況。即若

X→Y，則X→→Y。④函數(shù)依賴合并性。即若X→→Y，X→→Z，則

X→→YZ。⑤多值依賴分解性。即若X→→Y,X→→Z,則X→→

（Y∩Z），X→→Y-Z，X→→Z-Y均成立。這說明，如果兩個相交的屬性子集均多值依賴于另一個屬性子集，則這兩個屬性子集因相交而分割成的三部分也都多值依賴于該屬性子集。

1.第四范式（4NF）（1）

第四范式（4NF）的定義在4.2.8節(jié)中我們分析了關(guān)系CTR雖然屬于BCNF，但還存在著數(shù)據(jù)冗余、插入異常和刪除異常的弊端，究其原因就是CTR中存在非平凡的多值依賴，而決定因素不是碼。因而必須將CTR繼續(xù)分解，如果分解成兩個關(guān)系模式CTR1（C，T）和CTR2（C，R），則它們的冗余度會明顯下降。從多值依賴的定義分析CTR1和CTR2，它們的屬性間各有一個多值依賴C→→T，C→→R，都是平凡的多值依賴。因此，含有多值依賴的關(guān)系模式中，減少數(shù)據(jù)冗余和操作異常的常用方法是將關(guān)系模式分解為僅有平凡的多值依賴的關(guān)系模式。

定義4.11

設(shè)有一關(guān)系模式R（U），U是其屬性全集，X、Y是U的子集，D是R上的數(shù)據(jù)依賴集。如果對于任一多值依賴X→→Y，此多值依賴是平凡的，或者X包含了R的一個候選碼，則稱關(guān)系模式R是第四范式的，記作：R∈4NF。

由此定義可知：關(guān)系模式CTR分解后產(chǎn)生的CTR1（C，T）和CTR2（C，R）中，因為C→→T，C→→R均是平凡的多值依賴，所以CTR1和CTR2都是4NF。經(jīng)過上面分析可以得知：一個BCNF的關(guān)系模式不一定是4NF，而4NF的關(guān)系模式必定是BCNF的關(guān)系模式，即4NF是BCNF的推廣，4NF范式的定義涵蓋了BCNF范式的一定。

(2)

4NF的分解把一個關(guān)系模式分解為4NF的方法與分解為BCNF的方法類似，就是當(dāng)把一個關(guān)系模式利用投影的方法消去非平凡且非函數(shù)依賴的多值依賴，并具有無損連接性。[例7]

設(shè)有關(guān)系模式R（A，B，C，E，F(xiàn)，G），數(shù)據(jù)依賴集D={A→→BGC，B→AC，C→G}，將R分解為4NF。解：利用A→→BGC，可將R分解為R1（{ABCG}，{A→→BGC，B→AC，C→G}）和R2（{AEF}，{}），其中R2既無函數(shù)依賴又無多值依賴，其已是4NF的關(guān)系模式。而R1根據(jù)4NF的定義還不是4NF的關(guān)系模式。再利用B→AC對R1再分解為R11（{ABC}，{B→AC}）和R12（{BG}，{}），顯然R11、R12都是4NF的關(guān)系模式了。

由此對R分解得到的三個關(guān)系模式R11（{ABC}，{B→AC}）、R12（{BG}，{}）和R2（{AEF}，{}），它們都屬于4NF，但此分解丟失了函數(shù)依賴{C→G}。若最后一次分解利用到函數(shù)依賴C→G來做，則由此得到R的另一分解的三個關(guān)系模式R11（{ABC}，{B→AC}）、R12（{CG}，{C→G}）和R2（{AEF}，{}），它們同樣都是屬于4NF的關(guān)系模式，且保持了所有的數(shù)據(jù)依賴。這說明，4NF的分解結(jié)果不是唯一的，結(jié)果與選擇數(shù)據(jù)依賴的次序有關(guān)。任何一個關(guān)系模式都可無損分解成一組等價的4NF關(guān)系模式，但這種分解不一定具有依賴保持性。

⑴連接依賴的定義定義4.12設(shè)有關(guān)系模式R(U)、R1(U1)、R2(U2)、…、Rn(Un)，且U=U1∪U2∪…∪Un，{R1,…,Rn}是R的一個分解，r為R的一個任意的關(guān)系實例，若（表示r在Ri(Ui)上的投影，即，i=1,2,…n）則稱R滿足連接依賴（JoinDependency，簡稱JD），記作∞(R1,…,Rn)。⑵平凡連接依賴和非平凡連接依賴：設(shè)關(guān)系模式R滿足連接依賴，記∞(R1,…,Rn)。若存在Ri∈{R1,R2,…,Rn}，有R=Ri，則稱該連接依賴為平凡的連接依賴，否則稱為非平凡連接依賴。4.2.9連接依賴與5NF*

⑶第五范式(5NF)定義4.13設(shè)有關(guān)系模式R(U)、R1(U1)、R2(U2)、…、Rn(Un)，且U=U1∪U2∪…∪Un，D是R上的函數(shù)依賴、多值依賴和連接依賴的集合。若對于D+（稱為D的閉包，是D所蘊(yùn)含的函數(shù)依賴、多值依賴和連接依賴的全體，可參閱4.3節(jié)中的相關(guān)概念）中的每個非平凡連接依賴∞(R1,…,Rn)，其中的每個Ri都包含R的一個候選鍵，則稱R屬于第五范式，記R∈5NF。4.2.9連接依賴與5NF*

舉例：設(shè)關(guān)系模式SPJ({S,P,J})的屬性分別表示供應(yīng)商、零件、項目等含義，表示三者間的供應(yīng)關(guān)系。如果規(guī)定模式R的關(guān)系是三個二元投影（SP({S,P}、PJ({P,J}JS({J,S}）的連接，而不是其中任何兩個的連接。例如設(shè)關(guān)系中有<S1,P1,J2>、<S1,P2,J1>兩個元組，則SPJ滿足投影分解為SP、PJ、SJ后，SPJ一定是SP、PJ、SJ的連接而非它們間的兩兩連接，那么模式SPJ中存在著一個連接依賴∞(SP,PJ,JS)。在模式SPJ存在這個鏈接依賴時，其關(guān)系將存在冗余和異常現(xiàn)象。元組在插入或刪除時就會出現(xiàn)各種異常，如插入一元組必須連帶插入另一元組，而刪除一元組時必須連帶刪除另外元組等等，因為只有這樣才能不違反模式SPJ存在的連接依賴。4.2.9連接依賴與5NF*

例如，在上面SPJ中有兩個元組的情況下，再插入元組<S2,P1,J1>，讀者會發(fā)現(xiàn)，有三個元組的SPJ，分解后的3個二元關(guān)系SP、PJ、SJ連接后產(chǎn)生的SPJ不等于分解前的SPJ，而是多了一個元組<S1,P1,J1>，這就表明，根據(jù)語義的約束（或為了保證SPJ中連接依賴的存在），在插入<S2,P1,J1>時，必須同時插入<S1,P1,J1>的。讀者還可以驗證，在SPJ中有以上4個元組后，再刪除<S2,P1,J1>或<S1,P1,J1>時，也有需要連帶刪除其余某些元組的現(xiàn)象。這就是SPJ中存在非平凡連接依賴后，存在操作異常的想象。4.2.9連接依賴與5NF*

關(guān)系SPJ，其一個連接依賴∞(SP,PJ,JS)是非平凡的連接依賴，顯然不滿足5NF定義要求，它達(dá)不到5NF。應(yīng)該把SPJ分解成SP({S,P}、PJ({P,J}JS({J,S}三個模式，這樣這個分解是無損分解，并且每個模式都是5NF，各模式已清楚了冗余和異常操作現(xiàn)象。連接依賴也是現(xiàn)實世界屬性間聯(lián)系的一種抽象，是語義的體現(xiàn)。但它不像FD和MVD的語義那么直觀，要判斷一個模式是否是5NF的往往也比較困難?？梢宰C明，5NF的模式也一定是4NF的模式。根據(jù)5NF的定義，可以得出一個模式總是可以無損分解成5NF的模式集。4.2.9連接依賴與5NF*

4.2.9規(guī)范化小結(jié)

1、關(guān)系規(guī)范化過程

非規(guī)范關(guān)系去掉嵌套屬性或重復(fù)組(使每個屬性及其值都成為不可再分的數(shù)據(jù)項)1NF

消去非主屬性對候選KEY的部分FD2NF

消去非主屬性對候選KEY的傳遞FD3NF

消去主屬性對候選KEY的部分和傳遞FDBCNF

2、結(jié)論

1）3NF必定為2NF和1NF，反之不一定；

2）BCNF必為3NF，反之不一定；

3）3NF已在很大程度上控制了數(shù)據(jù)冗余；

4）3NF已在很大程度上消去了插入和刪除操作異常；

5）3NF分解仍不夠徹底（可能存在主屬性對候選碼的部分fd和傳遞fd）；

6）在fd范圍內(nèi)，BCNF下已完全消去了插入刪除異常；

7）范式并非越高越好；范式越高，異常越少，但查詢操作越麻煩；

8）適可而止：理論上：一般到3NF

應(yīng)用：存取垃圾；連接運算。

9）分解不唯一。

BACK4.3數(shù)據(jù)依賴的公理系統(tǒng)*

數(shù)據(jù)依賴的公理系統(tǒng)是模式分解算法的理論基礎(chǔ)，下面先討論函數(shù)依賴的一個有效而完備的公理系統(tǒng)——Armstrong公理系統(tǒng)。定義4.12

對于滿足一組函數(shù)依賴F的關(guān)系模式R（U，F(xiàn)），其任何一個關(guān)系r，若函數(shù)依賴X→Y都成立（即r中任意兩元組t,s，若t[X]=s[X]，則t[Y]=s[Y]），則稱F邏輯蘊(yùn)涵X→Y。為了求得給定關(guān)系模式的碼，為了從一組函數(shù)依賴求得蘊(yùn)涵的函數(shù)依賴，例如已知函數(shù)依賴集F，要問X→Y是否為F所蘊(yùn)含，就需要一套推理規(guī)則，這組推理規(guī)則是1974年首先由Armstrong提出來的。

BACKArmstrong公理系統(tǒng)設(shè)U為屬性集總體，F(xiàn)是U上的一組函數(shù)依賴，于是有關(guān)系模式R（U,F）。對R（U,F）來說有以下的推理規(guī)則：l

A1自反律（Reflexivity）：若Y?X?U，則

X→Y為F所蘊(yùn)含。l

A2增廣律（Augmentation）:若X→Y為F所蘊(yùn)含，且Z?U，則XZ→YZ為F所蘊(yùn)含。l

A3傳遞律（Transitivity）:若X→Y及Y→Z為F所含，則X→Z為F所蘊(yùn)含。注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于F。定理4.1Armstrong推理規(guī)則是正確的。下面從定義出發(fā)證明推理規(guī)則的正確性。證：（1）

Y?X?U。對R（U，F(xiàn)）的任一關(guān)系r中的任意兩個元組t,s:

若t[X]=s[X]，由于Y?X，有t[Y]=s[Y]，所以X→Y成立，自反律得證。（2）

X→Y為F所蘊(yùn)含，且Z?U。設(shè)R（U，F(xiàn)）的任一關(guān)系r中的任意兩個元組t,s:

若t[XZ]=s[XZ]，則有t[X]=s[X]和t[Z]=s[Z]；由

X→Y，于是有t[Y]=s[Y]，所以t[YZ]=s[YZ]，所以XZ→YZ為F所蘊(yùn)含，增廣律得證。（3）

設(shè)X→Y及Y→Z為F所蘊(yùn)含。設(shè)R（U，F(xiàn)）的任一關(guān)系r中的任意兩個元組t,s:

若t[X]=s[X]，由X→Y，有t[Y]=s[Y]；再由Y→Z，有t[Z]=s[Z]，所以X→Z為F所蘊(yùn)含，傳遞律得證。

根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面很有用的推理規(guī)則：

l

合并規(guī)則：由X→Y，X→Z，X→YZ。

l

偽傳遞規(guī)則：由X→Y，WY→Z，有XW→Z。

l

分解規(guī)則：由X→Y及Z?Y，有X→Z。根據(jù)合并規(guī)則和分解規(guī)則，很容易得到這樣一個重要事實：引理4.1X→A1A2…AK成立的充分必要條件是X→成立（i=1，2，…k）。定義4.13

在關(guān)系模式R（U，F(xiàn)）中為F所蘊(yùn)含的函數(shù)依賴的全體叫做F的閉包，記為：F+。

人們把自反律，傳遞律和增廣律稱為Armstrong公理系統(tǒng)。Armstrong公理系統(tǒng)是有效的、完備的。Armstrong公理的有效性指的是：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個函數(shù)依賴一定在F+中；完備性指的是F+中的每一個函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來。要證明完備性，就首先要解決如何判定一個函數(shù)依賴是否屬于由F根據(jù)Armstrong公理推導(dǎo)出來的函數(shù)依賴集合。當(dāng)然，如果能求出這個集合，問題就解決了。但不幸的是，這是個NP完全問題。比如從F={X→A1，…，X→An

}出發(fā)，至少可以推倒出2n個不同的函數(shù)依賴，為此引出了下面的概念：

定義4.14

設(shè)F為屬性集U上的一組函數(shù)依賴，X包含于U，XF+={A|X→A能由F根據(jù)Armstrong公理導(dǎo)出}，成為屬性集X關(guān)于函數(shù)依賴集F的閉包。由引理4.1容易得出：引理4.2

設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y包含于U，X→Y能由F根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y包含于XF+。于是，判定X→Y是否能由F根據(jù)Armstrong公理推導(dǎo)出的問題，就轉(zhuǎn)化為求出XF+的子集的問題。這個問題由算法4.1解決了。

算法4.1求屬性集X（XU）關(guān)于U上的函數(shù)依賴集F的閉包XF+

輸入：X，F(xiàn)

輸出：XF+

步驟：

(1)

令X(0)=X，i=0

(2)

求B，這里

B={A|(?V）(?W）（V→W∈F∧V?X(i)∧A∈W）}；

(3)

X(i+1)

=B∪X(i)(4)

判斷

X(i+1)

=X(i)嗎？

(5)

若相等或X(i+1)

=U，則X(i+1)就是XF+，算法終止。

(6)若否，則i=i+1,返回第（2）步。

[例8]

已知關(guān)系模式R（U，F(xiàn)），其中U={A，B，C，D，E}；F={AB→C，B→D，C→E，EC→B，AC→B}。求(AB)F+。解由算法4.1，設(shè)X(0)=AB；計算X(1)；逐一掃描F集合中各個函數(shù)依賴，找左部為A，B或AB的函數(shù)依賴。得到兩個：AB→C，B→D。于是X(1)=AB∪CD=ABCD。因為X(0)≠X(1)，所以再找出左部為ABCD子集的那些函數(shù)依賴，又得到C→E，AC→B，于是X(2)=X(1)∪BE=ABCDE。因為X(2)已等于全部屬性的集合，所以(AB)F+=ABCDE。

定理4.2

Armstrong公理系統(tǒng)是有效的、完備的。

Armstrong公理系統(tǒng)的有效性可由定理4.1得到證明。這里給出完備性的證明。證明完備性的逆否命題，即若函數(shù)依賴X→Y不能由F從Armstrong公理導(dǎo)出，那么它必然不為F所蘊(yùn)含，它的證明分三步。

(1)

若V→W成立，且V?XF+，則W?XF+

。證：因為V?XF+,所以有X→V成立；于是X→W成立（因為X→V，V→W),所以W?XF+

。

(2)構(gòu)造一張二維表r，它由下列兩個元組構(gòu)成，可以證明r必是R（U，F(xiàn)）的一個關(guān)系，即F中的全部函數(shù)依賴在r上成立。

XF+U-

XF+

11……100……011……111……1

若r不是R（U，F(xiàn)）的關(guān)系，則必由于F中有函數(shù)依賴V→W在r上不成立所致。由r的構(gòu)成可知，V必定是XF+的子集，而W不是XF+的子集，可是由第（1）步，W?XF+

，矛盾。所以r必是R（U，F(xiàn)）的一個關(guān)系。（3）若X→Y不能由F從Armstrong公理導(dǎo)出，則Y不是XF+的子集，因此必有Y的子集Y’滿足Y’?U-XF+

，則X→Y在r中不成立，即X→Y必不為R（U，F(xiàn)）蘊(yùn)含。

Armstrong公理的完備性及有效性說明了“導(dǎo)出”與“蘊(yùn)含”是兩個完全等價的概念。于是F+也可以說成是由F發(fā)出借助Armstrong公理導(dǎo)出的函數(shù)依賴集合。從蘊(yùn)含（或?qū)С觯┑母拍畛霭l(fā)，又引出了兩個函數(shù)依賴集等價和最小依賴集的概念。

定義4.15

如果G+=F+，就說函數(shù)依賴集F覆G（F是G的覆蓋，或G是F的覆蓋），或F與G等價。引理4.3F+=G+的充分必要條件是F?G+

，和G?F+

。證必要性顯然，只證充分性。（1）若F?G+

，則XF+?XG++。（2）任取X→Y∈F+

，則有Y?XF+?XG++

。所以X→Y∈（G+

）+=G+

。即F+?G+

。（3）同理可證G+?F+

，所以F+=G+

。而要判定F?G+

，只需逐一對F中的函數(shù)依賴X→Y，考察Y是否屬于XG++就行了。因此引理4.3給出了判定兩個函數(shù)依賴集等價的可行算法。

定義4.16如果函數(shù)依賴集F滿足下列條件，則稱F為一個極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。

(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等價。

定理4.3

每一個函數(shù)依賴集F均等價一個極小函數(shù)依賴集Fm。此Fm稱為F的最小依賴集。證：這是個構(gòu)造性的證明，分三步對F進(jìn)行“極小化處理”，找出F的一個最小依賴集來。（1）逐一檢查F中個函數(shù)依賴FDi：X→Y，若Y=A1A2…Ak，k>=2,則用{X→Aj|j=1,2,…,k}來取代X→Y。（2）逐一檢查F中各函數(shù)依賴FDi：X→A，令G=F-{X→A}，若A∈XG+，則從F中去掉此函數(shù)依賴（因為F與G等價的充要條件是A∈XG+

）。

（3）逐一取出F中各函數(shù)依賴FDi：X→A，設(shè)X=B1B2

…Bm,逐一考察Bi（i=1,2,…,m）,若A∈(X-Bi)F+,則以X-Bi取代X（因為F與F-{X→A}∪{Z→A}等價的充要條件是A∈ZF+其中Z=X-Bi）。最后剩下的F就一定是極小依賴集，并且與原來的F等價。因為對F的每一次“改造”都保證了改造前后的兩個函數(shù)依賴集等價。這些證明很顯然，請讀者自己補(bǔ)上。應(yīng)當(dāng)指出，F(xiàn)的最小依賴集Fm不一定是唯一的，它與對各函數(shù)依賴FDi及X→A中X各屬性的處置順序有關(guān)。

[例9]F={A→B，B→A，B→C，A→C，C→A}Fm1={A→B，B→C，C→A}Fm2={A→B，B→A，A→C，C→A}這里給出了F的兩個最小依賴Fm1，F(xiàn)m2。若改造后的F與原來的F相同，說明F本身就是一個最小依賴集，因此定理4.3的證明給出的最小化過程也可以看成是檢查F是否為極小依賴集的一個算法。兩個關(guān)系模式（U，F(xiàn)），（U，G），如果F與G等價，那么R1的關(guān)系一定是R2的關(guān)系。反過來，R2的關(guān)系也一定是R1的關(guān)系。所以在R（U，F(xiàn)）中用與F等價的依賴集G取代F是允許的。

定義4.17設(shè)有關(guān)系模式R（U，F(xiàn)），Z?U，則Z所涉及到的F中所有函數(shù)依賴為F在Z上的投影，記為∏Z（F），有∏Z（F）=｛X→Y｜(X→Y)∈F＋且XY?Z｝為函數(shù)依賴集F在Z上的投影。定義4.18設(shè)R（U，F(xiàn)）的一個分解ρ＝｛R1，R2，…，Rk｝，如果F等價于∏R1（F）∪∏R2（F）∪…∪∏Rk（F），則稱分解ρ具有函數(shù)依賴保持性。一個無損連接的分解不一定具有函數(shù)依賴保持性；同樣地，一個具有函數(shù)依賴保持性的分解也不一定具無損連接性。檢驗一個分解是否具有依賴保持性，實際上是檢驗∏R1（F）∪∏R2（F）∪…∪∏Rk（F）是否覆蓋F。

BACK

函數(shù)依賴保持性4.4關(guān)系分解保持性*

關(guān)系模式的規(guī)范化就是要通過對模式進(jìn)行分解，將一個屬于低級范式的關(guān)系模式轉(zhuǎn)換成若干個屬于高級范式的關(guān)系模式，從而解決或部分解決插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題。BACK4.4關(guān)系分解保持性*4.4.1關(guān)系模式的分解⑴關(guān)系模式分解的定義：設(shè)有關(guān)系模式R，U為R的屬性集。R的一個分解定義為ρ={R1，R2，…,Rn}，其中Ri的屬性集為Ui（i=1,2,…,n），且U=U1∪U2∪…∪Un。⑵函數(shù)依賴集的投影：設(shè)有關(guān)系模式R，U為R的屬性集，F(xiàn)為R上的函數(shù)依賴集，ρ={R1，R2，…,Rn}為R的一個分解，其中Ri的屬性集為Ui（i=1,2,…,n），則Fi={X→Y|X→Y∈F+，X?Ui,Y?Ui}稱為函數(shù)依賴集F在屬性集Ui上的投影。⑶對模式分解的要求：一個模式可以有多種分解方法，但要使分解有意義，就應(yīng)當(dāng)保證在分解過程中不丟失原有模式中的信息。模式分解的無損連接性和函數(shù)依賴保持性就是用以衡量一個模式分解是否導(dǎo)致原有模式中部分信息丟失的兩個標(biāo)準(zhǔn)。

BACK