第10章 數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

本文格式為Word版，下載可任意編輯——第10章數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

第10章數(shù)據(jù)依靠和關(guān)系模式規(guī)范化10.110.210.310.410.510.6關(guān)系模式設(shè)計(jì)中的數(shù)據(jù)語義問題函數(shù)依靠(FD)多值依靠(MVD)聯(lián)接依靠(JD)*關(guān)系模式的分解及其問題關(guān)系模式的規(guī)范化

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

10.1關(guān)系模式設(shè)計(jì)中的數(shù)據(jù)語義問題前面我們已經(jīng)探討了關(guān)系數(shù)據(jù)庫的基本概念、關(guān)系模型的三個部分以及關(guān)系數(shù)據(jù)庫的標(biāo)準(zhǔn)語言SQL。但是還有一個很基本的問題尚未涉及，針對一個具體問題，應(yīng)當(dāng)如何構(gòu)造一個適合于它的數(shù)據(jù)庫模式，即應(yīng)當(dāng)構(gòu)造幾個關(guān)系模式，每個關(guān)系由哪些屬性組成等。這是數(shù)據(jù)庫設(shè)計(jì)的問題，確鑿地講是關(guān)系數(shù)據(jù)庫規(guī)律設(shè)計(jì)問題。

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

10.1關(guān)系模式設(shè)計(jì)中的數(shù)據(jù)語義問題下面首先回想一下關(guān)系模型的形式化定義。一個關(guān)系模式應(yīng)當(dāng)是一個五元組。R(U,D,DOM,F)這里：–––––關(guān)系名R,它是符號化的元組語義；一組屬性U;屬性組U中屬性所來自的域D;屬性到域的映射DOM;屬性組U上的一組數(shù)據(jù)依靠F

由于D和DOM對模式設(shè)計(jì)關(guān)系不大,因此我們在本章中把關(guān)系模式看作是一個三元組：RU,F當(dāng)且僅當(dāng)U上的一個關(guān)系r滿足F時，稱r為關(guān)系模式RU,F的一個關(guān)系。

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

10.1關(guān)系模式設(shè)計(jì)中的數(shù)據(jù)語義問題關(guān)系作為一張二維表,我們對它有一個最起鍵的要求：每一個分量必需是不可分的數(shù)據(jù)項(xiàng)。滿足了這個條件的關(guān)系模式就屬于第一范式(1NF)。我們的任務(wù)是研究模式設(shè)計(jì)，研究設(shè)計(jì)一個“好〞的(沒有“毛病〞的)關(guān)系模式的方法。數(shù)據(jù)依靠是通過一個關(guān)系中屬性間值的相等與否表達(dá)出來的數(shù)據(jù)間的相互關(guān)系。它是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象，是數(shù)據(jù)內(nèi)在的性質(zhì)，是語義的表達(dá)。現(xiàn)在人們已經(jīng)提出了大量種類型的數(shù)據(jù)依靠，其中最重要的是函數(shù)依靠(FunctionalDependency簡記為FD)和多值依靠(MultivaluedDependency簡記為MVD)。函數(shù)依靠極為普遍地存在于現(xiàn)實(shí)生活中。

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

10.1關(guān)系模式設(shè)計(jì)中的數(shù)據(jù)語義問題譬如描述一個學(xué)生的關(guān)系,可以有學(xué)號(SNO),姓名(SNAME),系名(SDEPT)等幾個屬性。由于一個學(xué)號只對應(yīng)一個學(xué)生,一個學(xué)生只在一個系學(xué)習(xí)。因而當(dāng)“學(xué)號〞值確定之后,姓名和該生所在系的值也就被唯一地確定了。就象自變量x確定之后,相應(yīng)的函數(shù)值f(x)也就唯一地確定了一樣，我們說SNO函數(shù)決定SNAME和SDEPT,或者說SNAME,SDEPT函數(shù)依靠于SNO,記為∶SNO→SNAME,SNO→SDEPT。

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

10.1關(guān)系模式設(shè)計(jì)中的數(shù)據(jù)語義問題現(xiàn)在我們要建立一個數(shù)據(jù)庫來描述學(xué)生的一些倩況。面臨的對象有：學(xué)生(用學(xué)號SNO描述),系(用系名SDEPT描述),系負(fù)責(zé)人(用其姓名MN描述),課程(用課程名CNAME描述)和成績(G)?，F(xiàn)實(shí)世界的已知事實(shí)

告訴我們∶1)2)3)4)一個系有若干學(xué)生,但一個學(xué)生只屬于一個系；一個系只有一名(正職)負(fù)責(zé)人；一個學(xué)生可以選修多門課程,每門課程有若干學(xué)生選修；每個學(xué)生學(xué)習(xí)每一門課程有一個成績；

假使只考慮函數(shù)依靠這一種數(shù)據(jù)依靠,我們就得到了一個描述學(xué)校的數(shù)據(jù)庫模式SU,F,它由一個單一的關(guān)系模式構(gòu)成：U={SNO,SDEPT,MN,CNAME,G}F={SNO→SDEPT,SDEPT→MN,(SNO,CNAME)→G}

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

10.1關(guān)系模式設(shè)計(jì)中的數(shù)據(jù)語義問題這個模式有下述三個“毛病〞:1)插入異常：假使一個系剛成立尚無學(xué)生,或者雖然有了學(xué)生但尚未安排課程。那么我們就無法把這個系及其負(fù)責(zé)人的信息存入數(shù)據(jù)庫。刪除異常：反過來,假使某個系的學(xué)生全部畢業(yè)了,我們在刪除該系學(xué)生選修課程的同時,把這個系及其負(fù)責(zé)人的信息也丟掉了。更新異常：譬如，某系負(fù)責(zé)人更換后,就必需逐一修改有關(guān)的每一個元組。數(shù)據(jù)冗余：譬如,每一個系負(fù)責(zé)人的姓名要與該系每一個學(xué)生的每一門功課的成績出現(xiàn)的次數(shù)一樣多。

2)

3)

4)

這樣,一方面浪費(fèi)存儲,另一方面系統(tǒng)耍付出很大的代價(jià)來維護(hù)數(shù)據(jù)庫的完整性。

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

10.1關(guān)系模式設(shè)計(jì)中的數(shù)據(jù)語義問題為什么會發(fā)生插入異常和刪除異常呢?這是由于這個模式中的函數(shù)依靠存在某些不好的性質(zhì)。假使我們把這個單一的模式改造一下,分成三個關(guān)系模式：SSNO,SDEPT,SNO→SDEPT;SGSNO,CNAME,G,(SNO,CNAME)→G;DEPTSDEPT,MN,SDEPT→MN;這三個模式都不會發(fā)生插入異常、刪除異常的毛病,數(shù)據(jù)的冗佘也得到了控制。一個模式的函數(shù)依靠會有哪些不好的性質(zhì),如何改造一個不好的模式,這就是本章要探討的主要內(nèi)容。

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

10.2函數(shù)依靠定義10.1:設(shè)R(U)是屬性集U上的關(guān)系模式。X,Y是U的子集。若對于R(U)的任意一個可能的關(guān)系r,r中不可能存在兩個元組在X上的屬性值相等，而在Y上的屬性值不等，則稱X函數(shù)確定Y或Y函數(shù)依靠于X,記作X→Y。下面介紹一些術(shù)語和記號：–––––X→Y,但YX,則稱X→Y為平凡的函數(shù)依靠。否則，稱X→Y為非平凡的函數(shù)依靠。今后，若不特別聲明，我們總是探討非平凡的函數(shù)依靠。若X→Y,則稱X為決定因素(Determinant)。若X→Y,Y→X,則記作X←→Y。若Y不函數(shù)依靠于X,則記作XY。

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

10.2函數(shù)依靠定義10.2:在R(U)中,假使X→Y,并且對于X的任何一個真子集X',都有X'Y,則稱Y對X完全函數(shù)依靠,記作:XY。若X→Y,但Y不完全函數(shù)依靠于X,則稱Y對X部分函數(shù)依靠,記作XY。定義10.3:在R(U)中,假使X→Y,(YX),YX,Y→Z,則稱Z對X傳遞函數(shù)依靠。加上條件YX,是由于假使Y→X,則X←→Y,實(shí)

際上是,是直接函數(shù)依靠而不是傳遞函數(shù)依靠。定義10.4:對于滿足一組函數(shù)依靠F的關(guān)系模式RU,F,其任何一個關(guān)系r,若函數(shù)依靠X→Y都成立(即r中任意兩元組t,s,若t[X]=s[X],則t[Y]=s[Y]),則稱F規(guī)律蘊(yùn)含X→Y,記為F|=X→Y

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

10.2函數(shù)依靠Armstrong公理系統(tǒng)為了求得給定關(guān)系模式的鍵,為了從一組函數(shù)依靠求得蘊(yùn)含的函數(shù)依靠，例如，已知函數(shù)依靠集F,要問X→Y是否為F所蘊(yùn)含，就需要一套推理規(guī)則，這組推理規(guī)則是l974年首先由Armstrong提出來的。設(shè)U為屬性集總體，F(xiàn)是U上的一組函數(shù)依靠,于是有關(guān)系模式RU,F。對RU,F來說有以下的推理規(guī)則：Al.自反律(Reflexivity):若YXU,則X→Y為F所蘊(yùn)含。A2.增廣律(Augmentation):若X→Y為F所蘊(yùn)含，且ZU,則XZ→YZ為F所蘊(yùn)含。A3.傳遞律(Transitivity):若X→Y及Y→Z為F所蘊(yùn)含，則X→Z為F所蘊(yùn)含。注意，由自反律所得到的函數(shù)依靠均是平凡的函數(shù)依靠，自反律的使用并不依靠于F。

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

10.2函數(shù)依靠定理10.l:Armstrong推理規(guī)則是正確(sound)的。證：1)設(shè)YXU。對RU,F的任一關(guān)系r中的任意兩個元組t,s:若t[X]=s[X],由于YX,有t[y]=s[y],所以X→Y成立，自反律得證。設(shè)X→Y為F所蘊(yùn)含,且ZU。設(shè)RU,F的任一關(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)含，增廣律得證。設(shè)X→Y及Y→Z為F所蘊(yùn)含。對RU,F的任一關(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)含，傳遞律得證。

2)

3)

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

10.2函數(shù)依靠根據(jù)這三條推理規(guī)則可以得到下面三條很有用的推理規(guī)則:1)2)3)合并規(guī)則:由X→Y,X→Z,有X→YZ。偽傳遞規(guī)則：由X→Y,WY→Z,有XW→Z。分解規(guī)則：由X→Y及ZY,有X→Z。

根據(jù)合并規(guī)則和分解規(guī)則,很簡單得到這樣一個重要事實(shí)：引理10.l:X→A1A2...Ak成立的充分必要條件是X→Ai成立(i=l,2,...,k)。

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

10.2函數(shù)依靠定義10.5:在關(guān)系模式RU,F中為F所規(guī)律蘊(yùn)含的函數(shù)依靠的全體叫做F的閉包,記為F+。定義10.6:給定關(guān)系模式RU,F,假使能由F根據(jù)Armstrong公理導(dǎo)出X→Y,則稱X→Y是F的規(guī)律導(dǎo)出，記為F=X→Y。人們把自反律,傳遞律和增廣律稱為Armstrong公理系統(tǒng)。Armstrong公理系統(tǒng)是有效的、完備的。Armsttrong公理的有效性指的是：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個函數(shù)依靠一定在F+中；Armsttrong公理的完備性指的是F+中的每一個函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來。

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

10.2函數(shù)依靠要證明Armsttrong公理的完備性，就首先要解決如何判定一個函數(shù)依靠是否屬于由F根

據(jù)Armstrong公理推導(dǎo)出來的函數(shù)依靠的集合。當(dāng)然，假使能求出這個集合，問題就解決了。但不幸的是，這是一個NP完全問題。譬如從F={X→A1...,X→An}出發(fā)，我們至少可以推導(dǎo)出2n個不同的函數(shù)依靠。為此引入下面概念：定義10.7:設(shè)F為屬性集U上的一組函數(shù)依靠，XU,XF+={A|X→A能由F根據(jù)Armstrong公理導(dǎo)出},XF+稱為屬性集X關(guān)于函數(shù)依靠集F的閉包。

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

10.2函數(shù)依靠由引理10.1簡單得出：引理10.2:設(shè)F為屬性集U上的一組函數(shù)依靠，X,YU,X→Y能由F根據(jù)Armstrong公理導(dǎo)出的充分必要條件是YXF+。于是,判定X→Y是否能由F根據(jù)Armstrong公理導(dǎo)出的問題，就轉(zhuǎn)化為求出XF+,并判定Y是否為XF+的子集的問題。這個問題由算法10.l解決了。

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

10.2函數(shù)依靠算法10.l:求屬性集X(XU)關(guān)于U上的函數(shù)依靠集F的閉包XF+。輸入：X,F輸出：XF+步驟：1)2)令X(0)=X,i=0求B,這里B={A|(存在V→W)(V→W∈F∧V∈X(i)∧A∈W)};X(i+1)=X(i)∪B判斷X(i+1)=x(i)嗎?若相等或X(i)=U則X(i)就是XF+,算法終止。若否，則i=i+l,返回第2)步。

3)4)5)6)

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

10.2函數(shù)依靠例1:已知關(guān)系模式RU,F,其中U={A,B,C,D,E};F={AB→C,B→D,C→E,EC→B,AC→B}。求(AB)F+。解：由算法5.1,X(0)=AB;計(jì)算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。對于算法10.l,令ai=|X(i)|,{ai}形成一個步長大于1的嚴(yán)格遞增的序列,序列的上界是|U|,因此該算法最多|U|-|X|次循環(huán)就會終止。

數(shù)據(jù)依靠和關(guān)系模式規(guī)范化

10.2函數(shù)依靠定理10.2:Armstrong公理系統(tǒng)是有效的、完備的。Armstrong公理系統(tǒng)的有效性可由定理1