《數(shù)據(jù)庫原理與應(yīng)用》課件第4章

第4章關(guān)系數(shù)據(jù)庫理論4.1第一范式4.2函數(shù)依賴4.3模式分解4.4第二范式4.5第三范式4.6BC范式4.7第四范式4.8范式小結(jié)習(xí)題在前面幾章，對數(shù)據(jù)庫系統(tǒng)的一般概念、數(shù)據(jù)庫概念模型、關(guān)系數(shù)據(jù)庫的基本概念以及關(guān)系數(shù)據(jù)庫操作的標(biāo)準(zhǔn)語言SQL進(jìn)行了介紹。了解了這些概念和技術(shù)之后，需要解決如何為一個具體應(yīng)用設(shè)計出合適的數(shù)據(jù)模式。針對關(guān)系型數(shù)據(jù)庫來說，就是要確定關(guān)系模型中的各個關(guān)系以及關(guān)系中包含的屬性，這個過程是由關(guān)系數(shù)據(jù)庫邏輯設(shè)計階段來完成的。關(guān)系模型的建立過程本質(zhì)上是關(guān)系模型分解和規(guī)范化的過程。因此，在本章，首先學(xué)習(xí)函數(shù)依賴、模式分解等基本概念，然后學(xué)習(xí)如何通過模式分解和關(guān)系規(guī)范化理論得到滿足要求的關(guān)系。4.1第一范式在關(guān)系數(shù)據(jù)庫中，關(guān)系模式的好壞用范式(NF，NormalForms)來評價。范式有很多，但對關(guān)系模式評價最常用也是最有用范式主要是1NF、2NF、3NF和BCNF，特別是3NF和BCNF。

定義4.1

設(shè)R是一個關(guān)系模式，r是R的一個關(guān)系。如果r的每個屬性值都是不可再分的(或原子的)值，那么稱關(guān)系模式R是第一范式的模式。只有滿足第一范式的模式才是規(guī)范關(guān)系。第一范式的定義表明，一個規(guī)范關(guān)系只有行和列，不存在表中套表(子表)的情況。表4.1(a)所示的關(guān)系不滿足第一范式的定義，不是規(guī)范關(guān)系，因為其包含有子表店長(姓名，任職年月)；表4.1(b)所示的關(guān)系滿足第一范式的定義，是規(guī)范關(guān)系，因為其所有的行和列都不可再分了。另外，對于表的某個屬性，對于一個元組，如果存在多值情況，為了達(dá)到規(guī)范關(guān)系，應(yīng)將該元組分成多個元組進(jìn)行存儲。例如，如果一個門店有多個“聯(lián)系電話”，那么需要為每個聯(lián)系電話用一個元組進(jìn)行存放。表4.1非規(guī)范關(guān)系與規(guī)范關(guān)系4.2函數(shù)依賴在現(xiàn)實世界中，實體的各屬性之間存在依賴關(guān)系。例如，知道了某個地區(qū)的郵政編碼，就可以找到該地區(qū)的名稱；知道了某個學(xué)生的學(xué)號，就可以查到該學(xué)生的姓名。這種屬性之前的依賴關(guān)系，就是函數(shù)依賴(FD，F(xiàn)unctionDependency)。4.2.1基本概念定義4.2

設(shè)R(P)是一個關(guān)系模式，P是R的屬性集，X、Y都是P的子集。如果，對于R的任意兩個元組t1和t2，如果t1在X上的取值t1[X]?與t2在X上的取值t2[X]?相等，即t1[X]?=?t2[X]，那么t1和t2在Y上取值也相等，即t1[Y]?=?t2[Y]?成立。這時，稱Y函數(shù)依賴于X，記為FD：X→Y在關(guān)系模式R(P)上成立?！癤→Y”可以讀作“X函數(shù)決定Y”或“Y函數(shù)依賴于X”。定義4.2表明，在一個關(guān)系模式R(P)中，如果FD：X→Y成立，那么，對于R(P)的任意一個關(guān)系r的任意兩個元組，如果它們在X上的值相同，則也要求它們在Y值上也相同。也就是說，Y的值由X來決定。表4.2所示的商品定價銷售關(guān)系滿足函數(shù)依賴(商品代碼)→(價格)。當(dāng)然，從該關(guān)系可以看出，函數(shù)依賴與關(guān)系的碼是不同的，例如第一元組和第三元組的“商品代碼”都是“010001”，它們對應(yīng)的價格都是12.00，所以是不違反“商品代碼→價格”這一函數(shù)依賴，但顯然“商品代碼”不是這個關(guān)系的碼。表4.2函數(shù)依賴實例由上面的討論可知，利用函數(shù)依賴可以對關(guān)系中數(shù)據(jù)的正確性進(jìn)行驗證，從而使關(guān)系的實現(xiàn)和存儲更加有效。但同時也要注意到，在商品銷售關(guān)系中，如果采用商品代碼→價格這個函數(shù)依賴，那么，該關(guān)系就不是存放異價商品的銷售數(shù)據(jù)了。因為，一件商品會有不同的銷售價格，不滿足商品代碼→價格。因此，函數(shù)依賴也會導(dǎo)致一些信息無法存放到關(guān)系中。針對關(guān)系模式R(P)上的FD：X→Y，根據(jù)X和Y之間的包含關(guān)系，可將函數(shù)依賴X→Y分成以下3種類型：

(1)如果Y?X，那么稱FD：X→Y為平凡的函數(shù)依賴；

(2)如果Y至少有一個屬性不在X中，那么稱FD：X→Y為非平凡的函數(shù)依賴；

(3)如果X∩Y?=?，那么稱FD：X→Y是完全非平凡的函數(shù)依賴。定義4.3

設(shè)X→Y是關(guān)系模式R(P)上的一個函數(shù)依賴，如果不存在X?'?Y使得X?'→Y成立，則稱X→Y是完全函數(shù)依賴或Y完全函數(shù)依賴于X。如果存在X?'?Y使得X?'→Y成立，則稱X→Y是部分函數(shù)依賴或Y部分函數(shù)依賴于X。例如，表4.2所示的商品定價銷售關(guān)系中，函數(shù)依賴(商品代碼)→(價格)是完全函數(shù)依賴，而(商品代碼，營業(yè)員工號，交易日期)→(價格)是部分依賴。定義4.4在關(guān)系R(P)上，如果有非平凡函數(shù)依賴X→Y，但X不函數(shù)依賴于Y，Y→Z成立，那么則稱X→Z為傳遞函數(shù)依賴或Z傳遞函數(shù)于X。4.2.2函數(shù)依賴集及閉包在一個關(guān)系模型R(P)上的一個或多個FD組合的集合F，稱為函數(shù)依賴集。一般地，把帶有FD集的關(guān)系模式記為R(P，F(xiàn))，P是R的屬性集，F(xiàn)是P中屬性滿足的FD集。可以通過已知的FD集得到未知的FD或判斷某FD是否成立。這類問題稱為邏輯蘊(yùn)涵問題。定義4.5

設(shè)R(P，F(xiàn))為一個關(guān)系模式，X和Y是P的子集。如果對于R(P，F(xiàn))的任何一個關(guān)系r，函數(shù)依賴X→Y都成立，那么稱F邏輯蘊(yùn)涵X→Y或稱X→Y為F所邏輯蘊(yùn)涵。F邏輯蘊(yùn)涵的全體函數(shù)依賴的集合，稱為函數(shù)依賴集F的閉包，記為F+。定義4.5表明，針對關(guān)系模式R(P，F(xiàn))，如果要根據(jù)F得到未知函數(shù)依賴，只要將F邏輯蘊(yùn)涵的所有FD推導(dǎo)出即可。如果判斷給定的某個FD是否成立，只是判斷F是否邏輯蘊(yùn)涵該FD。這里，給出R(P，F(xiàn))中FD的推導(dǎo)規(guī)則Armstrong公理系統(tǒng)。

Armstrong公理系統(tǒng)設(shè)P為關(guān)系模式R的屬性總體，F(xiàn)是P上的一個函數(shù)依賴集。對于關(guān)系模式R(P，F(xiàn))有下列三條推理規(guī)則：

(1)自反性規(guī)則：若Y?X?P，則F邏輯蘊(yùn)涵X→Y；

(2)增廣性規(guī)則：若X→Y為F所邏輯蘊(yùn)涵，且Z?P，則XZ→YZ；

(3)傳遞性規(guī)則：若X→Y，Y→Z都為F所邏輯蘊(yùn)涵，則X→Z為F所邏輯蘊(yùn)涵。

定理4.1Armstrong公理系統(tǒng)是正確的。證明利用函數(shù)依賴的定義(定義4.2)來證明：

(1)自反性規(guī)則：很顯然，自反性規(guī)則是正確的。因為在R的一個關(guān)系r上不可能存在兩個元組，它們在屬性集X的值相等，而在X的某個子集上的值不相等。

(2)增廣性規(guī)則：設(shè)r是R的某個關(guān)系，t1和t2是r的兩個元組，它們在X上的值相同，t1[X]?=?t2[X]。假設(shè)t1和t2在XZ上的值相同，t1[XZ]?=?t2[XZ]，而在YZ上的值不相同，t1[YZ]?≠?t2[YZ]，導(dǎo)致這個不等式成立條件是t1[Y]?≠?t2[Y]或t1[Z]?≠?t2[Z]。由FD：X→Y可知t1[Y]?=?t2[Y]，那么只有t1[Z]?≠?t2[Z]?成立才能使t1[YZ]?≠?t2[YZ]?成立。由t1[XZ]?=?t2[XZ]?得到t1[X]?=?t2[X]及t1[Z]?=?t2[Z]。這樣，t1[Z]?≠?t2[Z]?不成立。因此，增廣性規(guī)則成立。

(3)傳遞性規(guī)則：假設(shè)r是R的某個關(guān)系，t1和t2是r的兩個元組，它們在X上的值相同t1[X]?=?t2[X]?但t1[Z]?≠?t2[Z]。由FDX→Y可得t1[Y]?=?t2[Y]，再由Y→Z得t1[Z]?=?t2[Z]，這與題設(shè)t1[Z]?≠?t2[Z]?相矛盾。因此，傳遞性規(guī)則成立。在Armstrong公理系統(tǒng)的基礎(chǔ)上，可得到以下幾個導(dǎo)出規(guī)則：

(1)合并規(guī)則：若X→Y，Y→Z都為F所邏輯蘊(yùn)涵，則X→YZ為F所邏輯蘊(yùn)涵。

(2)分解規(guī)則：若X→V為F所邏輯蘊(yùn)涵，且屬性集Z?V，則X→Z為F所邏輯蘊(yùn)涵。

(3)偽傳遞規(guī)則：若X→Y，VY→Z為F所邏輯蘊(yùn)涵，則XV→Z為F所邏輯蘊(yùn)涵。

證明

(1)合并規(guī)則：假設(shè)r是R的某個關(guān)系，t1和t2是r的兩個元組，它們在X上的值相同，t1[X]?=?t2[X]，由FD：X→Y得到t1[Y]?=?t2[Y]，由Y→Z得到t1[Z]?=?t2[Z]，故t1[YZ]?=?t2[YZ]。因此，X→YZ在R(P，F(xiàn))成立。

(2)分解規(guī)則：設(shè)Z?V，由自反性規(guī)則可知V→Z成立，而X→V為F所邏輯蘊(yùn)涵，由傳遞性規(guī)則可知X→Z成立。

(3)偽傳遞規(guī)則：由增廣性規(guī)則和X→Y得到VX→VY，而VY→Z，由傳遞性規(guī)則可知XV→Z為F所邏輯蘊(yùn)涵。根據(jù)合并規(guī)則和分解規(guī)則，很容易證明下列定理：

定理4.2

如果P1，P2，…，Pn是關(guān)系模式R的屬性集，那么X→P1，P2，…，Pn的充分必要條件是X→Pi

(1≤i≤n)。4.2.3屬性集的閉包

Armstrong公理系統(tǒng)是有效的、完備的。Armstrong公理系統(tǒng)的有效性指的是：在關(guān)系模式R(P，F(xiàn))上，根據(jù)Armstrong公理系統(tǒng)推導(dǎo)出來的任意函數(shù)依賴一定為F所邏輯蘊(yùn)涵的函數(shù)依賴，它保證了推導(dǎo)出來的所有函數(shù)依賴是正確的；Armstrong公理系統(tǒng)的完備性指的是：對于所邏輯蘊(yùn)涵的任意函數(shù)依賴，必定在R(P，F(xiàn))上可以根據(jù)Armstrong公理系統(tǒng)推導(dǎo)出來，它保證了所有被蘊(yùn)涵的函數(shù)依賴都能被推出。

Armstrong公理系統(tǒng)的有效性和完備性的證明需要引入屬性的閉包概念。定義4.6設(shè)R(P，F(xiàn))是一個關(guān)系模式，X是P的子集，那么X關(guān)于函數(shù)依賴集F的閉包(記為)是運用FD推理規(guī)則得到F+?中所有X→Y的屬性Y組成的集合：

=?{Y?|?X→Y在F+

中}根據(jù)定理4.2和定義4.6，可以發(fā)現(xiàn)判斷函數(shù)依賴X→Y是否能由Armstrong公理系統(tǒng)推得F+，也就是要判斷Y是否是的子集。下面的定理能夠幫助快速判斷X→Y是否在F+中。

定理4.3

設(shè)R(P，F(xiàn))是一個關(guān)系模式，X、Y?P。X→Y能由Armstrong公理系統(tǒng)推導(dǎo)的充分必要條件是Y??。利用定理4.2和定義4.6，定理4.3很容易得到證明。這里，不再給出詳細(xì)描述，讀者可自行證明。定理4.2表明，要判斷Y是否是的子集，首先要求得。分析表明，運用Armstrong公理系統(tǒng)推得F+?是指數(shù)級時間。這里，介紹一種求的有效算法。算法4.1

求R(P，F(xiàn))的屬性集X關(guān)于函數(shù)依賴集F的閉包。輸入：關(guān)系模式R的屬性集P，P上的FD集F，X?P。輸出：。過程：result←X；

for對于FD集F中的每個FDW→Z?do

ifW??resultthen

result←result∪W；

until(result不再變化或等P)；

returnresult例4.1已知關(guān)系模式R(P，F(xiàn))，P?=?(ABCDE)，F(xiàn)?=?{A→BC，CD→E，B→D，E→A}試求?。計算步驟：

Step1.result={A}；

Step2.針對FD：A→BC，因為{A}?result，故result?=?{A}?∪?{BC}={ABC}；

Step3.針對FD：CD→E，因為{CD}不在result中，故result保持不變；

Step4.針對FD：B→D，因為?{B}?result，故result?=?result∪{D}?=?{ABCD}；

Step5.針對FD：E→A，因為A已在result中，故result保持不變；

Step6.重新查檢F，由FDCD→E，{CD}?{ABCD}，result?=?result∪{E}?=?{ABCDE}；

Step7.??result已包含全部屬性，返回result。根據(jù)計算結(jié)果可知，本題中的=?(ABCDE)。

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

Armstrong公理系統(tǒng)的有效性是很顯然的。只需證明Armstrong完備性。對于F所邏輯蘊(yùn)涵的任意函數(shù)依賴，必定在R(P，F(xiàn))上可以根據(jù)Armstrong公理系統(tǒng)推導(dǎo)出來。通過證明完備性的逆否命題可以完成完備性的證明，即證明若FD：X→Y不能由F從Armstrong公司導(dǎo)出，那么它必然不為F所邏輯蘊(yùn)涵。設(shè)有一個FD：X→Y不能由F利用Armstrong公理系統(tǒng)推出。現(xiàn)要證明X→Y不在F+

中，即X→Y在R的某個關(guān)系r上不成立。分兩步：

(1)證明F中的每個FD：V→W在r上均成立。分兩種情況：V?或V未在中。如果V?，由定理4.3可知X→V。再由傳遞性規(guī)則可得X→W成立。再利用定理4.3，可知W?。這樣，V?和W?同時成立，故V→W在r上也成立。如果V未在中，即V有些屬性不在中。此時，關(guān)系r中有兩個元組在V值上不相等，因此，V→W也在r上成立。

(2)證明X→Y在r上不成立。因此X→Y不能從F上利用Armstrong公理系統(tǒng)推導(dǎo)出，根據(jù)定理4.3，可知Y不在中。反映在關(guān)系r上，表現(xiàn)為存在兩個元組在X值上相等，在Y值不相等，這與X→Y相矛盾。由(1)、(2)證明可知，若X→Y不能從F上利用Armstrong公理系統(tǒng)推出，那么，X→Y就不被F所蘊(yùn)涵。這樣，Armstrong公理系統(tǒng)的完備性得以證明。4.2.4最小覆蓋由函數(shù)依賴，引入函數(shù)依賴集的覆蓋和極小覆蓋的概念。定義4.7設(shè)在關(guān)系R上存在兩個函數(shù)依賴集F和G。如果F+

=?G+，那么稱函數(shù)依賴集F覆蓋G(或函數(shù)依賴集G覆蓋F)，或F和G等價。根據(jù)Armstrong公理系統(tǒng)，要判斷函數(shù)依賴集F是否包含于G+，只需針對F中每個FD：X→Y，考查Y?是否成立即可。下面的定理提供了一個判斷兩個函數(shù)依賴集等價的可行算法。定理4.5

關(guān)系R上的兩個函數(shù)依賴集F和G，F(xiàn)+

=?G+

的充分必要條件是F?G+且G?F+。證明先證明必要性。已知，F(xiàn)?F+，G?G+，因為F+

=?G+

，很顯然F?G+

且G?F+成立。再證明充分性。針對某一屬性集X，如果F?G+，則?。設(shè)X→Y是F+

中的任意一個FD，則有Y∈?。因此，X→Y包含在G+

中，即F+?G+

成立。同理可證，G+?F+。故F+

=?G+。定義4.8F是關(guān)系R上的一個函數(shù)依賴集，如果F滿足以下條件，就稱F為一個極小函數(shù)依賴集，也稱極小依賴集或最小覆蓋：

(1)?F中所有函數(shù)依賴X→A，A中僅含有一個屬性；

(2)?F中的任意函數(shù)依賴X→A，都不滿足F和F－(X→A)等價；

(3)?F中的任意函數(shù)依賴X→A，不存在X?‘?X，使得F和F?－?(X→A)∪(X?'→A)成立。例4.2在商品定價銷售關(guān)系S(P)，P?=?(商品代碼，營業(yè)員工號，價格，銷售數(shù)量，交易時間)上有兩個函數(shù)依賴集F和G：

F?=?{商品代碼?→?價格，(商品代碼，營業(yè)員工號，交易時間)?→?銷售數(shù)量}

G?=?{商品代碼?→?價格，(商品代碼，營業(yè)員工號，交易時間)?→?銷售數(shù)量，(商品代碼，營業(yè)員工號，交易時間)?→?價格}不難看出，F(xiàn)是最小覆蓋，而G不是最小覆蓋。因此，由商品代碼?→?價格可推導(dǎo)出(商品代碼，營業(yè)員工號，交易時間)?→?價格。根據(jù)最小覆蓋的定義，采用“極小化處理”可證明以下定理：

定理4.6每一個函數(shù)依賴集F均等價一個極小函數(shù)依賴集Fmin，F(xiàn)min稱為F的最小依賴。算法4.2求關(guān)系模式R(P，F(xiàn))的函數(shù)依賴集F的等價最小依賴集。輸入：關(guān)系模式R(P，F(xiàn))的函數(shù)依賴集F。輸出：F的最小依賴集。過程：

Step1.對F中的每個FD，將其右邊分解成只有一個屬性，如將X→A1A2…Ak(k>2)分解成X→Aj，j?<?k；

Step2.檢查每個X→Aj，令G?=?F?－?(X→Aj)。若Aj∈，則從F中去掉此函數(shù)依賴；

Step3.對F中的每個FD：X→A，將其左側(cè)表示為B1B2…Bm，對每個Bi進(jìn)行判斷，如果A∈，則用X－Bi替代X。最后得到的F就是Fmin。例4.3設(shè)F是關(guān)系模式R(ABC)上的函數(shù)依賴集：F?=?(A→BC，B→C，A→B，AB→C)求F的最小依賴集Fmin。計算步驟：

Step1.將各個FD的右側(cè)都化為只有一個屬性，A→BC化為A→B，A→C；

Step2.令G?=?F?-?(A→C，A→B)?=?(B→C，A→B，AB→C)，?=?(ABC)，故BC都在中。這樣，F(xiàn)?=?G?=?(B→C，A→B，AB→C)；

Step3.對于F中的函數(shù)依賴AB→C，而?=?(ABC)，故C∈，用A→C替換AB→C，但A→C又能從(B→C，A→B)利用傳遞性規(guī)則推出，因此Fmin?=?(B→C，A→B)。注意：F的最小依賴可能有多種情況，它與對各函數(shù)依賴及X→A中X各屬性順序有關(guān)。4.3模式分解4.3.1基本分解定義前面介紹了函數(shù)依賴及其相關(guān)特征。通常情況下，為了建立合適的關(guān)系模式往往需要將一個大的關(guān)系模式分解成幾個小的關(guān)系，這就是模式分解。下面給出模式分解的形式化定義。

定義4.9

設(shè)有關(guān)系模式R(P，F(xiàn))及P的子集P1P2…Pn滿足條件且沒有Pi?Pj，1≤i，j≤n，F(xiàn)1F2…Fn是函數(shù)依賴集F在P1P2…Pn上的投影(即Fi是F+

中在Pi上成立的函數(shù)依賴集)，那么將關(guān)系模式R(P,?F)(稱為泛關(guān)系模式)分解成ρ?=?{R1(P1,?F1),?R2(P2,?F2),?…,?Rn(Pn,?Fn)}的過程，稱為R(P,?F)的模式分解，稱ρ為關(guān)系模式R(P,?F)的一個分解。

例4.4已知關(guān)系模式R(P，F(xiàn))，P?=?(ABCDE)，F(xiàn)?=?{A→BC，CD→E，B→D，E→A}，設(shè)有ρ1?=?{R1，R2，R3}其中R1((ABCD)，(A→BC，B→D))，R2((ABDE)，(B→D，E→A))，R3((ACDE)，(CD→E，E→A))；ρ2?=?{R1，R2，R3，R4}其中R1((ABC)，(A→BC))，R2((ABD)，(B→D))，R3((ABE)，(E→A))，R4((CDE)，(CD→E))；ρ3?=?{R1，R2，R3}其中R1((ABCD)，(A→BC，B→D))，R2((ABD)，(B→D))，R3((ACDE)，(CD→E，E→A))。由定義4.8可知，ρ1，ρ2是R(P，F(xiàn))的分解，而ρ3

不是R(P，F(xiàn))的分解，因為R2的屬性集(ABD)是R2的屬性集(ABCD)的子集。關(guān)系模式的分解需要具有“等價性”，目前，對模型分解的“等價性”定義有以下3種：

(1)具有“無損連接性”；

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

(3)既具有“無損連接性”，又具有“保持函數(shù)依賴性”。4.3.2無損連接分解簡單地說，關(guān)系的“無損連接性”指一個關(guān)系在分解前后具有相同的數(shù)據(jù)。如果一個模式分解具有“無損連接性”，那么這個分解就稱為“無損連接分解”。

定義4.10設(shè)ρ?=?{R1(P1，F(xiàn)1)，R2(P2，F(xiàn)2)，…，Rn(Pn，F(xiàn)n)}是R(P，F(xiàn))的一個分解，如果對R(P，F(xiàn))的任何一個關(guān)系r均有r

=

為r在Pi上的投影)，那么稱將關(guān)系模式R(P，F(xiàn))分解成ρ?=?{R1(P1，F(xiàn)1)，R2(P2，F(xiàn)2)，…，Rn(Pn，F(xiàn)n)}是無損連接分解。例4.5

將關(guān)系模式R(ABC)分解成ρ?=?{(AB)，(AC)}。表4.3給出了R的一個關(guān)系r分解成ρ的兩個關(guān)系r1和r1及r1

r2的值。從表中可知，r1

r2≠r，由無損連接定義可知該分解不具無損連接性。表4.3不具備無損連接性的模式分解定義4.10表明，判斷一個模式分解是否為無損連接分解，只要檢查分解后的各個關(guān)系的自然連接與分解前的泛關(guān)系是否相等即可。但多數(shù)情況下直接根據(jù)無損連接分解的定義去判斷一個模式分解的無損連接性是非常困難的。算法4.3是一個鑒別無損連接分解的常用方法。

算法4.3

判斷某一模式分解是否為無損連接分解。輸入：關(guān)系模式R的屬性集P?=?(A1A2…An)及P上的函數(shù)依賴集F、R的一個分解

ρ?=?{R1(P1，F(xiàn)1)，R2(P2，F(xiàn)2)，…，Rn(Pn，F(xiàn)n)}輸出：給出ρ是否為R的一個無損連接分解的判斷。判斷過程如下：

Step1.構(gòu)建一張n列m行的表格，表格的每一列(如列j?)對應(yīng)R的一個屬性Aji(1≤j≤n)，每一行(如行i?)對應(yīng)ρ中的一個關(guān)系Ri?(1≤i≤m)。對表格中第i行，第j列的值這樣來確定：如果Aj在Pi中，則取值為aj；否則，取值為bij。

Step2.對每個關(guān)系Ri的函數(shù)依賴集Fi中的每個函數(shù)依賴X→Y，做如下操作：將表格中所有X分量上相等的行的Y分量的所有列值都改為相等：如果存在某行Y分量的某列Aj上的取值為aj值，那么將其他X分量相等的Aj列值也改為aj；如果不存在某行Y分量的某列Aj上的取值為aj，那么將其他分量相等的Aj列值也改為該列已有的下標(biāo)i較小的bij值。重復(fù)這一過程，直到表格不能修改為止。

Step3.修改結(jié)束后，若在最后的表格中，有一行的值全部是a，即a1a2…an，那么，ρ?就是R的一個無損連接分解。例4.6已知關(guān)系模式R(P，F(xiàn))，P?=?(ABCDE)，F(xiàn)?=?{A→BC，CD→E，B→D，E→A}分解為ρ?=?{R1，R2，R3}，其中R1((ABC)，(A→BC))，R2((ABD)，(B→D))，R3((CDE)，(CD→E))，試判斷ρ是否為R的一個無損連接分解。計算過程如下：

Step1.構(gòu)建初始表，見表4.4(a)。

Step2.利用R1中的函數(shù)依賴集A→BC，因為第1行和第2行的A值都等于a1，而第1行的C值為a3，因此，將b23改為a3；由R2中的函數(shù)依賴B→D，因為第1行和第2行的B值都等于a2，而第2行的D值為a4，故將b14改為a4，修改后的表格見表4.4(b)。在表4.4(b)所示的表格上，利用R3上的函數(shù)依賴集CD→E，發(fā)現(xiàn)表格的全部三行在C和D屬性上的取值都分別是a3和a4，而第3行的E值為a5，因此，將第1、2行的E值改為a5，修改后的表格見表4.4(c)；

Step3.觀察表4.4(c)，發(fā)現(xiàn)第1、2行所有列上取值都為a。因此ρ是R的一個無損連接分解。如果將一個關(guān)系模式R(P，F(xiàn))分解成兩個關(guān)系ρ?=?{R1(P1，F(xiàn)1)，R2(P2，F(xiàn)2)}，可以利用以下定理進(jìn)行快速判斷該分解是否為無損連接分解。

定理4.7

設(shè)將關(guān)系模式R(P，F(xiàn))分解成兩個關(guān)系ρ?=?{R1(P1，F(xiàn)1)，R2(P2，F(xiàn)2)}，ρ是R的無損連接分解的充分必要條件是(P1∩P2)→(P1

－?P2)或(P1∩P2)→(P2

－?P1)。利用算法4.3可以證明這個定理。請讀者自己證明。表4.4利用算法4.3判斷無損連接分解用到的表格4.3.3保持依賴“等價”分解的第二種含義是分解后能否保持函數(shù)依賴集，保持函數(shù)依賴就是保證分解后的各關(guān)系中的數(shù)據(jù)語義完整性不受破壞。定義4.11設(shè)關(guān)系模式R(P，F(xiàn))的一個分解為ρ?=?{R1(P1，F(xiàn)1)，R2(P2，F(xiàn)2)，…，Rn(Pn，F(xiàn)n)}，若，則R的分解ρ保持函數(shù)依賴。定義4.8給出一個判斷分解是否保持函數(shù)依賴的方法，逐個驗證F中的函數(shù)依賴是否被所蘊(yùn)涵，這種方法是可行的。例4.7將加盟門店((門店編號，門店名稱，店長工號，任職年月)，(門店編號→門店名稱，門店編號→店長工號，店長工號→任職年月))分解成兩關(guān)系：門店信息((門店編號，門店名稱)，(門店編號→門店名稱))和店長信息((店長工號，任職年月)，(店長工號→任職年月))試判斷該分解是否保持函數(shù)依賴。通過分析，不難發(fā)現(xiàn)，在分解前的加盟門店的關(guān)系中存在函數(shù)依賴“門店編號→店長工號”不能從分解后的兩個關(guān)系模式的函數(shù)依賴集中導(dǎo)出。因此，此分解不保持函數(shù)依賴。保持函數(shù)依賴的分解，只要能夠保證保存在每個分解后的關(guān)系中的數(shù)據(jù)滿足各個關(guān)系各自的函數(shù)依賴集，那么所有數(shù)據(jù)也滿足分解前的泛關(guān)系模式中的函數(shù)依賴集。這樣，就保證了分解前后數(shù)據(jù)語義的一致性?！暗葍r”的第三種含義是“既具有‘無損連接性’，又‘保持函數(shù)依賴’”。要判斷關(guān)系模式的一個分解是屬性這種“等價”分解，可以利用算法4.3判斷該分解是否是無損連接分解，再利用定義4.11判斷該分解是否保持函數(shù)依賴。4.3.4模式信息冗余至此，了解了模式分解的定義及什么是分解的無損連接性和保持函數(shù)依賴。但為什么要進(jìn)行模式分解？判斷一個分解好壞的標(biāo)準(zhǔn)是什么？要得到一個關(guān)系模式的合理分解，必須先回答這兩個問題。本節(jié)先回答第一個問題。下面通過一個例子來說明模式分解的重要性。表4.5所示是分解前的關(guān)系，它是用來存放5個商品的庫存信息。在這個關(guān)系中，(商品代碼，進(jìn)貨批次，商品名稱，庫存量，生產(chǎn)廠家，廠家所在城市)是其屬性集，這些屬性之間存在函數(shù)依賴集(商品代碼→商品名稱，商品代碼→生產(chǎn)廠家名稱，生產(chǎn)廠家→廠家所在城市，(商品代碼，進(jìn)貨批次)→庫存量)，(商品代碼，進(jìn)貨批次)是該關(guān)系的主碼?，F(xiàn)在來分析這個模式中存在哪些問題：

(1)數(shù)據(jù)冗余。如果對某個廠家生產(chǎn)的某種商品進(jìn)貨多次，這個商品的商品名稱、生產(chǎn)廠家及廠家所在城市就需要重復(fù)存放多次。例如，在關(guān)系中，商品代碼為“01001”的“東北大米”進(jìn)貨兩次，對應(yīng)的商品名稱、生產(chǎn)廠家、廠家所在城市都重復(fù)存放了2遍。表4.5分解前的商品庫存表

(2)修改異常。數(shù)據(jù)冗余會導(dǎo)致數(shù)據(jù)修改產(chǎn)生問題。由于商品代碼為“01001”商品在該關(guān)系中重復(fù)存放了兩次，如果生產(chǎn)廠家搬遷到其他城市，必須對所有該生產(chǎn)廠家所在的元組的“廠家所在城市”進(jìn)行修改。如果由于疏漏導(dǎo)致某一個元組沒有修改成功，就會造成該廠家有多個城市與其相對應(yīng)，這就產(chǎn)生了修改異常。

(3)刪除異常。數(shù)據(jù)庫的數(shù)據(jù)經(jīng)常需要進(jìn)行清理，避免不了對表中的數(shù)據(jù)進(jìn)行刪除操作。例如，在表4.5所示的關(guān)系中，想刪除商品代碼為“020015”商品的庫存數(shù)據(jù)，包括商品代碼、進(jìn)貨批次、商品名稱、庫存量。如果刪除整個元組，就會把不應(yīng)刪除數(shù)據(jù)(如生產(chǎn)廠家，廠家所在城市)也刪除了，這種刪除操作顯然是不適合的。

(4)插入異常。有的時候，針對一個生產(chǎn)廠家，在庫存關(guān)系中并不一定存在該廠家生產(chǎn)的商品，也就是說，需要把某個生產(chǎn)廠家和廠家所在城市插入到關(guān)系中。由于缺少商品信息對應(yīng)的屬性值，所以一種可能的方法就是將對應(yīng)的屬性值置為空。但置空也產(chǎn)生問題，一是空值難于理解，再者在該關(guān)系中，商品代碼和批次是主屬性，是不允許取空值的。根據(jù)上面的分析，可以說表4.5所示關(guān)系對應(yīng)的關(guān)系模式，不是一個“好”的關(guān)系模式。如果將該關(guān)系分解成表4.6所示的3個關(guān)系：商品關(guān)系(商品代碼，商品名稱，生產(chǎn)廠家名稱)、生產(chǎn)廠家關(guān)系(生產(chǎn)廠家名稱、廠家所在城市)及進(jìn)貨關(guān)系(商品代碼，進(jìn)貨批次，庫存量)，那么就不會產(chǎn)生前面提到的數(shù)據(jù)冗余、數(shù)據(jù)插入、數(shù)據(jù)刪除和數(shù)據(jù)修改等異?，F(xiàn)象。表4.6商品庫存關(guān)系的一種分解上述分析表明，模式分解對保證數(shù)據(jù)庫的數(shù)據(jù)正確性是十分重要的，這回答了為什么要進(jìn)行模式分解的問題。但是否只要將“大”關(guān)系分解成“小”關(guān)系就一定不會產(chǎn)生異常了嗎？顯然不是。那又如何判斷一個模式分解的好壞呢？為了解決這個問題，提出關(guān)系的“規(guī)范化”理論。也就是說，一個關(guān)系分解后的關(guān)系應(yīng)該達(dá)到一定的標(biāo)準(zhǔn)才不會產(chǎn)生異常。這些標(biāo)準(zhǔn)稱為關(guān)系的“范式(NF)”。范式有多種，常用的有4.1節(jié)定義的第一范式(1NF)，以及下面即將介紹的第二范式(2NF)、第三范式(3NF)、BC范式(BCNF)和第四范式(4NF)。4.4第二范式第一范式告訴我們，一個規(guī)范關(guān)系是由行與列組成的二維表，不存在表中套表(或稱復(fù)合列)的情況，這是關(guān)系型數(shù)據(jù)庫中的關(guān)系應(yīng)滿足的最基本的條件。但僅僅滿足第一范式是遠(yuǎn)遠(yuǎn)不夠的，在4.3節(jié)例子中的商品庫存關(guān)系說明了這個問題。因此，要建立一個適合的關(guān)系模式必須滿足更加嚴(yán)格的條件。為了更好地說明問題，從函數(shù)依賴角度對候選碼進(jìn)行定義。定義4.12設(shè)關(guān)系模式R(P，F(xiàn))，其中P?=?(A1A2…An)是R的屬性集，F(xiàn)是P上成立的函數(shù)依賴集。如果F+?存在X?P使得X→A1A2…An成立，并且X中不存在真子集X?'?X，使得X?'→A1A2…An在F+?中成立。那么，稱X為關(guān)系R(P，F(xiàn))的一個候選碼。主碼是候選碼之一，通常是指數(shù)據(jù)庫中正在使用的候選碼。下文中所說的碼，如不加專門說明，就是指的“候選碼”。定義4.13

設(shè)關(guān)系模式R的候選碼為X，那么X中的所有屬性稱為主屬性。反之，不在X中的所有屬性稱為非主屬性?；剡^頭來再分析表4.5中的商品庫存關(guān)系。顯然該關(guān)系的主碼是由(商品代碼，進(jìn)貨批次)組成的復(fù)合碼。其他屬性如商品名稱、庫存量、生產(chǎn)廠家、廠家所在城市都依賴于這個主碼，也即函數(shù)依賴(商品代碼，進(jìn)貨批次)→商品名稱，在該關(guān)系上成立。同時，由題設(shè)可知，函數(shù)依賴(商品代碼→商品名稱)也在該關(guān)系中成立。根據(jù)函數(shù)依賴的定義(定義4.3)，得出(商品名稱)與主碼(商品代碼，批次)之間是部分依賴。這種非主屬性對主碼的部分依賴會導(dǎo)致數(shù)據(jù)冗余(如一個商品的名稱存在多次)、數(shù)據(jù)插入異常(當(dāng)有新商品需要存放在關(guān)系中，但并沒進(jìn)貨，無批次信息就法存放)、數(shù)據(jù)修改異常(同一商品代碼的商品名稱發(fā)生修改，應(yīng)該修改與該商品代碼相同的所有元組的商品名稱屬性，否則，會造成數(shù)據(jù)不一致)、數(shù)據(jù)刪除異常(刪除某次進(jìn)貨信息，同時也將商品名稱也刪除了)。同樣的情況，還發(fā)生在(生產(chǎn)廠家)與主碼之間的部分依賴上。如果將關(guān)系中的非主屬性對主碼的部分依賴消除掉，又會怎樣呢？在表4.7中，將原商品庫存關(guān)系分解成兩個關(guān)系：商品表和進(jìn)貨表。其中，商品關(guān)系的屬性集是(商品代碼，商品名稱，生產(chǎn)廠家名稱，廠家所在城市)，進(jìn)貨關(guān)系的屬性集是(商品代碼，進(jìn)貨批次，庫存量)。在這兩個關(guān)系中都不存在非主屬性對主碼的部分依賴，把這類關(guān)系稱為滿足第二范式(2NF)的關(guān)系。表4.7滿足2NF的關(guān)系實例4.4.1定義定義4.14

設(shè)關(guān)系模式R滿足第一范式，如果R的每個非主屬性都不局部依賴于候選碼，那么稱R是第二范式的關(guān)系模式，記為R∈2NF。如果一個數(shù)據(jù)庫的所有關(guān)系都是第二范式的關(guān)系，那么，這個數(shù)據(jù)庫就稱為第二范式的數(shù)據(jù)庫。在表4.7所示的兩個關(guān)系中，在商品關(guān)系表(表4.7(a))中，由于其候選碼是單屬性(商品代碼)，因此，不存在非主屬性對主屬性的局部依賴問題。所以，該關(guān)系模式是第二范式的關(guān)系模式。同樣，在進(jìn)貨關(guān)系表(表4.7(b))中，只有非主屬性——庫存量，它是完全依賴于候選碼(商品代碼，進(jìn)貨批次)的，因此，進(jìn)貨表也是第二范式的關(guān)系模式。這樣，由這兩個關(guān)系組成的數(shù)據(jù)庫就是第二范式的數(shù)據(jù)庫。從以上的分析可得出，第二范式的關(guān)系模式消除了由于非主屬性對候選碼的部分依賴造成的數(shù)據(jù)冗余和數(shù)據(jù)的插入、刪除和修改異常。但如何才能得到第二范式關(guān)系呢？4.4.2分解算法算法4.4

保持無損連接和函數(shù)依賴的第二范式關(guān)系模式集的分集。輸入：R(P，F(xiàn))，其中P?=?{A1A2…An}是R的屬性集，F(xiàn)是P上成立的函數(shù)依賴集。輸出：R(P，F(xiàn))的一個分解ρ?=?{R1(P1，F(xiàn)1)，R2(P2，F(xiàn)2)，…，Rn(Pn，F(xiàn)n)}，其中每個關(guān)系模式Ri

(Pi，F(xiàn)i)均為第二范式的關(guān)系模式。分解過程如下：

Step1.求R的候選碼，記為K。

Step2.針對R中的每個主屬性(設(shè)為A)，求，并設(shè)結(jié)果集為ρ?=?{}。

Step3.對F中的每個函數(shù)依賴FDi：X→Y，做如下操作：如果X屬于某個主屬性A的閉包，那么，生成關(guān)系Ri((XY)，(X→Y))，Ri的候選碼為X，并檢查ρ中的關(guān)系，如果存在某個關(guān)系(設(shè)為Rj)的候選碼是X，那么將作為非主屬性加入到Rj中；如果不存在這個關(guān)系Rj，那么，ρ?=?ρ∪Ri。

Step4.刪除R中與ρ中所有關(guān)系的非主屬性相同的非主屬性，并將ρ?=?ρ∪R。

Step3.輸出滿足第二范式的分解ρ。下面用實例來說明算法4.4計算過程。例4.8已知關(guān)系模式R(P，F(xiàn))，P?=?(ABCDE)，F(xiàn)?=?{A→BC，B→E，A→C}，試將R(P，F(xiàn))分解成滿足第二范式的關(guān)系模式集。計算過程如下：

Step1.求關(guān)系R(P，F(xiàn))的候選碼K?=?(AD)。

Step2.?R的主屬性的閉包：=?(ABCE)，

=?(D)ρ?=?{}。針對函數(shù)依賴A→BC，因為A?，故產(chǎn)生關(guān)系R1((ABC)，(A→BC))，其主碼是(A)。這樣，ρ?=?{R1}。針對函數(shù)依賴A→C，因為A?，故產(chǎn)生關(guān)系R2((AC)，(A→C))，其主碼是(A)。因為ρ中R1的主碼也是(A)，將R1和R2合并為新的R1((ABC)，(A→BC，A→C))，其主碼為{A}。針對函數(shù)依賴B→E，而A→B，故有A→E。因為A?，故產(chǎn)生關(guān)系R3((AE)，(A→E))，其主碼是(A)。因為ρ中R1的主碼也是A，將R1和R3合并為新的R1((ABCE)，(A→BC，A→C，B→E))，其主碼為{A}。

Step3.檢查R中的非主屬性，發(fā)現(xiàn)BCE也是R1的非主屬性。因此，需要將BCE從R中刪除，這樣，R(AD)。

Step4.這樣，求得R(P，F(xiàn))滿足第二范式的分解ρ?=?{R1((ABCE)，(A→BC，A→C，B→E))，R2(AD)}。很容易利用判斷無損連接算法和保持函數(shù)依賴的定義來證明算法4.4得到的關(guān)系模式集滿足無損連接和保持函數(shù)依賴。這里，不再詳細(xì)描述證明過程了。4.5第三范式4.5.1定義在2NF的關(guān)系模式中，不存在非主屬性對候選碼的部分依賴，在一定程序上消除了數(shù)據(jù)冗余和數(shù)據(jù)的插入、刪除、修改可能產(chǎn)生的異常。但滿足2NF的關(guān)系模式仍然還存在一些問題。在表4.7(a)所示的商品關(guān)系表中，此關(guān)系只有一個主屬性，因此肯定是2NF的。但仔細(xì)分析后會發(fā)現(xiàn)該關(guān)系仍存在數(shù)據(jù)冗余及數(shù)據(jù)的插入、刪除和修改異常。

(1)數(shù)據(jù)冗余。例如有兩種商品產(chǎn)自“上海光明乳業(yè)集團(tuán)”，因此，該生產(chǎn)廠家的信息重復(fù)存了兩遍。如果某生產(chǎn)廠家供應(yīng)N種商品，那么該生產(chǎn)廠家的信息就要重復(fù)存N次，這會造成大量數(shù)據(jù)冗余。

(2)插入異常。如果有新的生產(chǎn)廠家的信息需要存在放到該關(guān)系中，但該生產(chǎn)廠家還未供應(yīng)任何商品，因為(商品代碼)是主碼，因此無法插入。

(3)修改異常。如果某個生產(chǎn)廠家的信息發(fā)生變化了，必須修改該廠家所有商品對應(yīng)的元組，否則就造成數(shù)據(jù)的不一致。

(4)刪除異常。正如前面提到的，如果要刪除商品代碼為“20015”的商品，要么將該商品對應(yīng)的整條元組刪除，要么將商品代碼和商品名稱設(shè)為空值。但在多數(shù)情況下，需要保留廠家信息供以后使用，這表明刪除整條元組是不適合的。如果將商品代碼和商品名稱設(shè)為空值，由于商品代碼是該關(guān)系的主屬性，如果設(shè)為空，就造成了刪除異常。分析表4.7(b)中所示的進(jìn)貨關(guān)系，發(fā)現(xiàn)該關(guān)系無數(shù)據(jù)冗余，也不會發(fā)生數(shù)據(jù)的插入、刪除和修改異常。那么，為什么在商品關(guān)系中存在數(shù)據(jù)冗余及異常產(chǎn)生，而在進(jìn)貨關(guān)系中卻沒有呢？要回答這個問題，需要考察這兩個關(guān)系模式中存在的函數(shù)依賴。在進(jìn)貨關(guān)系(商品代碼，進(jìn)貨批次，庫存量)中，非主屬性只有庫存量，它直接依賴于主碼(商品代碼，進(jìn)貨批次)。也就是說，庫存量只取決于商品代碼和進(jìn)貨批次。因此，該關(guān)系中無數(shù)據(jù)冗余，也不會產(chǎn)生插入、修改、刪除異常。再看看表4.7(a)商品關(guān)系(商品代碼，商品名稱，生產(chǎn)廠家名稱，生產(chǎn)廠家所在城市)，該關(guān)系的主碼是(商品代碼)，因此，其他非主屬性都依賴于(商品代碼)，即(商品代碼)→(商品名稱，生產(chǎn)廠家名稱，廠家所在城市)。但非主屬性對主碼的依賴之外，在非主屬性之間還存在函數(shù)依賴：(生產(chǎn)廠家名稱→生產(chǎn)廠家所在城市)。這樣，(生產(chǎn)廠家所在城市)就傳遞依賴于主碼(商品代碼)。正是由于這個非主屬性對候選碼(主碼)的傳遞依賴導(dǎo)致了數(shù)據(jù)冗余和異常的產(chǎn)生。要消除傳遞依賴帶來的數(shù)據(jù)冗余以及數(shù)據(jù)插入、數(shù)據(jù)修改和數(shù)據(jù)刪除異常，必須使關(guān)系滿足第三范式(3NF)。定義4.15

設(shè)R是一個1NF的關(guān)系模式，K是R的候選碼，A是R的一個非主屬性，如果所有A都不傳遞依賴于K，那R就是第三范式(3NF)的關(guān)系模式。如果一個數(shù)據(jù)庫里的所有關(guān)系模式都是3NF的，那么該數(shù)據(jù)庫也是3NF的。定義4.15表明，在3NF的關(guān)系模式中，消除了非主屬性對候選碼的傳遞依賴，而定義4.14告訴2NF的關(guān)系模式消除了非主屬性對候選碼的局部依賴。那么3NF的關(guān)系模式與2NF的關(guān)系模式究竟存在什么關(guān)系呢？定理4.8

如果關(guān)系模式R是3NF的，那么它一定是2NF的。證明：可采用反證法。設(shè)關(guān)系R是3NF，但不是2NF的。由于R不是2NF的，因此必存在某個非主屬性(設(shè)為A)局部依賴于候選碼K，即存在K?'?K，使得K?'→A成立。因為K?'?K，所以K→K?'，這樣A就傳遞依賴于K，從而得出R不是3NF的。因此，與題設(shè)相矛盾。在實際應(yīng)用中，一般將關(guān)系變換成3NF或更高級別的范式，這個過程稱為“模式的規(guī)范化”。局部依賴和傳遞依賴是造成數(shù)據(jù)冗余和數(shù)據(jù)操縱異常的兩個重要原因。模式的規(guī)范化的目標(biāo)就是要盡可能地消除這些函數(shù)依賴。前面的例子表明，由于1NF、2NF關(guān)系模式自身的弱點，一般不宜做數(shù)據(jù)庫模式。4.5.2分解算法

3NF的關(guān)系模式消除了非主屬性對候選碼的傳遞依賴，在一定程度減小了關(guān)系中數(shù)據(jù)冗余和降低異常的產(chǎn)生。那么，如何將一個泛關(guān)系分解成滿足3NF的關(guān)系集，并且保持函數(shù)依賴性和具有無損連接性？算法4.5

將關(guān)系模式在保持函數(shù)依賴且無損連接的情況下分解成3NF關(guān)系模式集。輸入：R(P，F(xiàn))，其中P?=?{A1A2…An}是R的屬性集，F(xiàn)是P上成立的函數(shù)依賴集。輸出：R(P，F(xiàn))的一個分解ρ?=?{R1(P1，F(xiàn)1)，R2(P2，F(xiàn)2)，…，Rn(Pn，F(xiàn)n)}，其中每個關(guān)系模式Ri(Pi，F(xiàn)i)均為3NF的關(guān)系模式，且ρ保持函數(shù)依賴性和具有無損連接性。計算過程如下：

Step1.求R的候選碼，并設(shè)結(jié)果集ρ?=?()。

Step2.對于F中的每個函數(shù)依賴X→Y，如果ρ中每個模式都不包含XY，那么將XY組成一個關(guān)系模式，并加入ρ，即ρ?=?ρ∪(XY)。

Step3.如果ρ中的所有關(guān)系均不包含的一個候選碼，那么，將R的一個候選碼作為一個關(guān)系加入到ρ中。

Step4.返回結(jié)果集ρ。從算法描述中可知，對于FD集中的每個函數(shù)依賴均生成了一個關(guān)系，因此，很明顯該分解能保持函數(shù)依賴，并且每個關(guān)系都是3NF的。第4步保證了候選碼在關(guān)系中存在。利用算法4.3很容易驗證該分解具有無損連接性。

例4.9已知關(guān)系模式R(P，F(xiàn))，P?=?(ABCDE)，F(xiàn)?=?(A→BC，B→E，D→C)，試將R(P，F(xiàn))分解成滿足第三范式的關(guān)系模式集。計算過程如下：

Step1.??R的候選碼為(AD)，并設(shè)結(jié)果集=()。

Step2.對于FD：A→BC，組成關(guān)系R1?=?{ABC}，由于R1不在ρ中，故ρ?=?{R1}；同理將R2?=?(BE)，R3?=?(DC)加入ρ，即ρ?=?{R1，R2，R3}。

Step3.由于ρ中任何一個關(guān)系模式都不包含候選碼(AD)，故將(AD)作為一個關(guān)系

R4?=?{AD}并加入到ρ中。

Step4.返回ρ?=?{(ABC)，(BE)，(CD)，(AD)}。我們講過，第三范式的關(guān)系模式消除了非主屬性對候選碼的傳遞依賴，并未講它消除了主屬性對候選碼的傳遞依賴，這就意味著有時即使達(dá)到3NF的關(guān)系模式，仍然會造成數(shù)據(jù)冗余和異常產(chǎn)生。4.6BC范式4.6.1BC范式的定義

3NF消除了非主屬性對候選碼的傳遞依賴，并沒有考慮主屬性對候選碼的傳遞依賴。那么，如果關(guān)系模式符合3NF，但卻存在主屬性對候選碼的傳遞依賴，又會產(chǎn)生什么問題呢？下面仍然通過一個例子來說明。例4.10設(shè)有關(guān)系模式R((ABC)，(A→B，BC→A))，不難求得R的候選碼為(BC)或(AC)。這樣，關(guān)系模式R的所有屬性都是主屬性，表明R是3NF的關(guān)系模式。表4.8給出R的一個關(guān)系r，可以看出關(guān)系r中仍存在大量的數(shù)據(jù)冗余，從而會造成數(shù)據(jù)插入、數(shù)據(jù)修改和數(shù)據(jù)刪除異常。造成這一問題的根源是主屬性(如B)傳遞依賴于候選碼(BC)。如果將R分解成R1((AB)，(A→B))和R2(AC)，那么可以大大減少數(shù)據(jù)冗余和異常的產(chǎn)生。但同時也帶來了一新問題，分解丟失了函數(shù)依賴BC→A，這個問題將在下一節(jié)討論。上述R1((AB)，(A→B))和R2(BC)相較R((ABC)，(A→B，BC→A))來說性能較好，是因為它們消除了所有屬性對候選碼的傳遞依賴，即滿足BC范式(BCNF)。表4.8滿足3NF但不滿足BC范式的關(guān)系定義4.16

給定一個1NF的關(guān)系模式R，對于R中的所有非平凡函數(shù)依賴X→Y，X中一定含有候選碼，那么稱R是BCNF的關(guān)系模式。定義4.16表明BCNF關(guān)系模式中，所有非主屬性都完全函數(shù)依賴于候選碼(2NF)，所有主屬性完全函數(shù)依賴于不包含它的候選碼，沒有屬性完全函數(shù)依賴于除候選碼之外的屬性集(3NF)。因此，BCNF關(guān)系模式一定是滿足3NF的關(guān)系模式。還可以這么說：若一個關(guān)系達(dá)到了第三范式，并且它只有一個候選碼，或者它的每個候選碼都是單屬性的，則該關(guān)系一定滿足BCNF。4.6.2分解算法算法4.6

把某關(guān)系模式無損連接地分解成BCNF關(guān)系模式集。輸入：R(P，F(xiàn))，其中P?=?{A1A2…Am}是的屬性集，F(xiàn)是P上成立的函數(shù)依賴集。輸出：R(P，F(xiàn))的一個分解ρ?=?{R1(P1，F(xiàn)1)，R2(P2，F(xiàn)2)，…，Rn(Pm，F(xiàn)m)}，其中每個關(guān)系模式Ri(Pi，F(xiàn)i)均為BCNF的關(guān)系模式，ρ具無損連接性。計算過程如下：

Step1.?ρ?=?{R}。

Step2.求R的所有候選碼。

Step3.針對ρ中的關(guān)系模式，做下列循環(huán)：(i)若ρ中有某個關(guān)系模式Rk(Pk，F(xiàn)k)不是BCNF的關(guān)系模式，那么必能在Rk中找到一個非平凡函數(shù)依賴X→Y，且X中不包含Rk的任何候選碼，將Rk分解成兩個關(guān)系Rk((Pk

－?Y)，(Fk

－?(X→Y)))和Rmax+1((XY)，(X→Y))，用Rk和Rmax+1代替Rk，并求Rmax+1的候選碼。(ii)若ρ中所有關(guān)系模式都是BCNF的，那么停止循環(huán)；回到Step3。

Step4.返回ρ。算法4.6的關(guān)鍵步驟是Rk((Pk

－?Y)，(Fk

－?(X→Y)))和Rmax+1(XY，X→Y)，其中Rmax+1表示當(dāng)前ρ中關(guān)系模式的個數(shù)加1。利用定理4.7很容易判斷該分解是無損連接分解。因此，利用算法4.6分解成的BCNF具有無損連接性。算法4.6不一定能保證分解保持函數(shù)依賴。利用算法4.6將例4.10中的關(guān)系模式R((ABC)，(A→B，BC→A))分解成BCNF的關(guān)系模式集：R1((AB)，(A→B))和R2(AC)，R1和R2中的函數(shù)依賴只有(A→B)，丟失了(BC→A)。例4.11設(shè)關(guān)系模式R(P，F(xiàn))，P?=?(ABCDEG)，F(xiàn)?=?(D→G，CD→E，C→A，A→B)，試將R無損連接地分解成BCNF關(guān)系模式集。計算過程如下：

Step1.??R1?=?R，ρ?=?{R1}。

Step2.??R1的候選碼為{CD}。

Step?3.在R1中針對FD：D→G得到部分函數(shù)依賴候選碼{CD}，故將R1分解為R1(ABCDE)和R2(DG)，這時R2已為BCNF，ρ?=?{R1，R2}；同理，可將R1分解為R1(BCDE)和R3(AC)，分析可知此時R1的候選碼{BCD}滿足BCNF，R3也滿足BCNF。因此，ρ?=?{R1,R2,R3}。

Step4.返回ρ。從上例的返回可以看出，分解后的關(guān)系模式不保持函數(shù)依賴(丟失了A→B)。另外，分解后的關(guān)系模式集的組成與分解過程中利用函數(shù)依賴的順序有關(guān)。4.7第四范式無論是2NF、3NF還是BCNF，都是依據(jù)函數(shù)依賴對關(guān)系模式進(jìn)行分解的，這些分解消除了由于屬性對不包含它的候選碼的函數(shù)依賴而造成性能不足?，F(xiàn)在來考察多值依賴對關(guān)系模式的影響。4.7.1多值依賴定義4.17

設(shè)關(guān)系模式R的屬性集為P，X、Y和Z是P的子集，且Z?=?P?-?X?-?Y。如果在R的任一關(guān)系r中，給定一對X、Z的取值，都有一組Y值與之對應(yīng)，并且這組Y值僅取決于值而與值無關(guān)，那么稱在上存在Y對X多值依賴(MVD)，記為X→→Y。如果X→→Y且Y?X或Z?=?，那么稱X→→Y為平凡的多值依賴。多值依賴定義表明，X與Y是多對一的關(guān)聯(lián)，X與Z也是多對一的關(guān)聯(lián)，但Y和Z之間不直接關(guān)聯(lián)。例4.12

在連鎖超市經(jīng)營管理中，如果規(guī)定每個加盟門店可進(jìn)多種商品、有多名營業(yè)員，每個營業(yè)員可銷售門店內(nèi)的所有商品。這樣，在加盟門店和商品之間是一對多的關(guān)聯(lián)、加盟門店和營業(yè)員之間也是一對多的關(guān)聯(lián)，而營業(yè)員與商品之間無直接關(guān)聯(lián)(每個營業(yè)員跟每個商品都相關(guān))，表明加盟門店與商品、加盟門店與營業(yè)員之間存在多值依賴。門店、商品、營業(yè)員之間的關(guān)系可用表4.9來表示。表4.9存在多值依賴的關(guān)系分析表4.9所示的關(guān)系發(fā)現(xiàn)，該關(guān)系的主碼(營業(yè)員，商品)由所有屬性組成(稱為復(fù)合碼)，因而符合BCNF。但通過觀察關(guān)系中的元組，可以發(fā)現(xiàn)這個關(guān)系存在很多不足。如果某個加盟門店(如A門店)增加一個營業(yè)員，必須插入多個(表中為4個)元組：(A門店，張A，商品M1)、(A門店，張A，商品M2)、(A門店，張A，商品M3)和(A門店，張A，商品M4)，可見有很大的數(shù)據(jù)冗余；如果要刪除某個門店(如A門店)的某個營業(yè)員(李B)，也要同時刪除多個元組(表中為4個)。造成上述數(shù)據(jù)冗余及刪除麻煩的原因就是因為加盟門店與商品、加盟門店與營業(yè)員之間存在多值依賴。如果要克服這些不足，需要對存在多值依賴的關(guān)系進(jìn)行分解，即使關(guān)系達(dá)到第四范式(4NF)。在討論什么是4NF之前，先來了解