【教學(xué)課件】第6章 關(guān)系數(shù)據(jù)庫理論

1、第6章 關(guān)系數(shù)據(jù)庫理論,6.1 問題的提出 6.2 規(guī)范化 6.3 數(shù)據(jù)依賴的公理系統(tǒng) 6.4 模式的分解 6.5 小結(jié),6.3 數(shù)據(jù)依賴的公理系統(tǒng),邏輯蘊(yùn)含 定義6.11 對(duì)于滿足一組函數(shù)依賴 F 的關(guān)系模式R ，其任何一個(gè)關(guān)系r，若函數(shù)依賴XY都成立, 則稱 F邏輯蘊(yùn)含X Y,Armstrong公理系統(tǒng),一套推理規(guī)則，是模式分解算法的理論基礎(chǔ) 用途 求給定關(guān)系模式的碼 從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴,1. Armstrong公理系統(tǒng),關(guān)系模式R 來說有以下的推理規(guī)則： Al.自反律（Reflexivity）： 若Y X U，則X Y為F所蘊(yùn)含。 A2.增廣律（Augmentation）：

2、若XY為F所蘊(yùn)含，且Z U，則XZYZ為F所蘊(yùn)含。 A3.傳遞律（Transitivity）：若XY及YZ為F所蘊(yùn)含，則XZ為F所蘊(yùn)含。 注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于F,定理 6.l Armstrong推理規(guī)則是正確的,（l）自反律:若Y X U，則X Y為F所蘊(yùn)含 證: 設(shè)Y X U 對(duì)R 的任一關(guān)系r中的任意兩個(gè)元組t，s： 若tX=sX，由于Y X，有ty=sy， 所以XY成立. 自反律得證,定理6.l (續(xù)),(2)增廣律: 若XY為F所蘊(yùn)含，且Z U，則XZYZ 為F所蘊(yùn)含。 證：設(shè)XY為F所蘊(yùn)含，且Z U。 設(shè)R 的任一關(guān)系r中任意的兩個(gè)

3、元組t，s； 若tXZ=sXZ，則有tX=sX和tZ=sZ； 由XY，于是有tY=sY，所以tYZ=sYZ，所以XZYZ為F所蘊(yùn)含. 增廣律得證。,定理6.l （續(xù)）,(3) 傳遞律：若XY及YZ為F所蘊(yùn)含，則 XZ為 F所蘊(yùn)含。 證：設(shè)XY及YZ為F所蘊(yùn)含。 對(duì)R 的任一關(guān)系 r中的任意兩個(gè)元組 t，s。 若tX=sX，由于XY，有 tY=sY； 再由YZ，有tZ=sZ，所以XZ為F所蘊(yùn)含. 傳遞律得證。,2. 導(dǎo)出規(guī)則,1.根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面三條推理規(guī)則： 合并規(guī)則：由XY，XZ，有XYZ。 （A2， A3） 偽傳遞規(guī)則：由XY，WYZ，有XWZ。 （A2， A

4、3） 分解規(guī)則：由XY及 ZY，有XZ。 （A1， A3）,導(dǎo)出規(guī)則,2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理6.1 引理6.l XA1 A2Ak成立的充分必要條件是XAi成立（i=l，2，k）。,3. 函數(shù)依賴閉包,定義6.l2 在關(guān)系模式R中為F所邏輯蘊(yùn)含 的函數(shù)依賴的全體叫作 F的閉包，記為F+。 定義6.13 設(shè)F為屬性集U上的一組函數(shù)依賴，X U， XF+ = A|XA能由F 根據(jù)Armstrong公理導(dǎo)出，XF+稱為屬性集X關(guān)于函數(shù)依賴集F 的閉包,關(guān)于閉包的引理,引理6.2 設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y U，XY能由F 根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y XF

5、+ 用途 將判定XY是否能由F根據(jù)Armstrong公理導(dǎo)出的問題，就轉(zhuǎn)化為求出XF+ ，判定Y是否為XF+的子集的問題,求閉包的算法,算法6.l 求屬性集X（X U）關(guān)于U上的函數(shù)依 賴集F 的閉包XF+ 輸入：X，F(xiàn) 輸出：XF+ 步驟： （1）令X（0）=X，i=0 （2）求B，這里B = A |( V)( W)(VWF V X（i）A W)； （3）X（i+1）=BX（i）,算法 6.l,（4）判斷X（i+1）= X （i）嗎? （5）若相等或X（i）=U , 則X（i）就是XF+ , 算法終止。 （6）若否，則 i=i+l，返回第（2）步。 對(duì)于算法6.l， 令ai =|X（i）|，

6、ai 形成一個(gè)步長(zhǎng)大 于1的嚴(yán)格遞增的序列，序列的上界是 | U |，因 此該算法最多 |U| - |X| 次循環(huán)就會(huì)終止。,U=A, B, C, D; F=A B, BC D; A+ = AB. C+ = C. (AC)+ = ABCD.,實(shí)例,函數(shù)依賴閉包,例1 已知關(guān)系模式R，其中 U=A，B，C，D，E； F=ABC，BD，CE，ECB，ACB。 求（AB）F+ 。 解 設(shè)X（0）=AB； (1)計(jì)算X（1）: 逐一的掃描F集合中各個(gè)函數(shù)依賴， 找左部為A，B或AB的函數(shù)依賴。得到兩個(gè)： ABC，BD。 于是X（1）=ABCD=ABCD。,函數(shù)依賴閉包,(2)因?yàn)閄（0） X（1） ，

7、所以再找出左部為ABCD子集的那些函數(shù)依賴，又得到ABC，BD， CE，ACB， 于是X（2）=X（1）BCDE=ABCDE。 (3)因?yàn)閄（2）=U，算法終止 所以（AB）F+ =ABCDE。,4. Armstrong公理系統(tǒng)的有效性與完備性,有效性：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個(gè)函數(shù)依賴一定在F+中 /* Armstrong正確 完備性：F+中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來 /* Armstrong公理夠用，完全 完備性：所有不能用Armstrong公理推導(dǎo)出來f, 都不為真 若 f 不能用Armstrong公理推導(dǎo)出來， f F+

8、,5. 函數(shù)依賴集等價(jià),定義6.14 如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。,函數(shù)依賴集等價(jià)的充要條件,引理6.3 F+ = G+ 的充分必要條件是 F G+ ，和G F+ 證: 必要性顯然，只證充分性。 （1）若FG+ ，則XF+ XG+ 。 （2）任取XYF+ 則有 Y XF+ XG+ 。 所以XY (G+）+= G+。即F+ G+。 （3）同理可證G+ F+ ，所以F+ = G+。,函數(shù)依賴集等價(jià),要判定F G+，只須逐一對(duì)F中的函數(shù)依賴XY，考察 Y 是否屬于XG+ 就行了。因此引理6.3 給出了判斷兩個(gè)函數(shù)依賴集等價(jià)的可行算法。,6.

9、最小依賴集,定義6.15 如果函數(shù)依賴集F滿足下列條件，則稱F為一個(gè)極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。 (1) F中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性。 (2) F中不存在這樣的函數(shù)依賴XA，使得F與 F-XA等價(jià)。 (3) F中不存在這樣的函數(shù)依賴XA， X有真 子集Z使得F-XAZA與F等價(jià)。,最小依賴集（續(xù)）,例2 對(duì)于6.l節(jié)中的關(guān)系模式S，其中： U= SNO，SDEPT，MN，CNAME，G ， F= SNOSDEPT，SDEPTMN， （SNO，CNAME）G 設(shè)F=SNOSDEPT，SNOMN， SDEPTMN，(SNO，CNAME)G， (SNO，SDEPT)SDEP

10、T F是最小覆蓋，而F 不是。 因?yàn)椋篎 -SNOMN與F 等價(jià) F -(SNO，SDEPT)SDEPT也與F 等價(jià) F -(SNO，SDEPT)SDEPT SNOSDEPT也與F 等價(jià),7. 極小化過程,定理6.3 每一個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小 函數(shù)依賴集Fm。此Fm稱為F的最小依賴集 證:構(gòu)造性證明，依據(jù)定義分三步對(duì)F進(jìn)行“極小化處理”，找出F的一個(gè)最小依賴集。 (1)逐一檢查F中各函數(shù)依賴FDi：XY， 若Y=A1A2 Ak，k 2， 則用 XAj |j=1，2， k 來取代XY。 引理6.1保證了F變換前后的等價(jià)性。,極小化過程（續(xù)）,(2)逐一檢查F中各函數(shù)依賴FDi：XA，

11、令G=F-XA， 若AXG+， 則從F中去掉此函數(shù)依賴。 由于F與G =F-XA等價(jià)的充要條件是AXG+ 因此F變換前后是等價(jià)的。,極小化過程（續(xù)）,(3)逐一取出F中各函數(shù)依賴FDi：XA， 設(shè)X=B1B2Bm， 逐一考查Bi （i=l，2，m）， 若A （X-Bi ）F+ ， 則以X-Bi 取代X。 由于F與F-XAZA等價(jià)的充要條件是AZF+ ，其中Z=X-Bi 因此F變換前后是等價(jià)的。,極小化過程（續(xù)）,由定義，最后剩下的F就一定是極小依賴集。 因?yàn)閷?duì)F的每一次“改造”都保證了改造前后的兩個(gè)函數(shù)依賴集等價(jià)，因此剩下的F與原來的F等價(jià)。 證畢 定理6.3的證明過程 也是求F極小依賴集的過

12、程,極小化過程（續(xù)）,例3 F = AB，BA，BC， AC，CA Fm1、Fm2都是F的最小依賴集： Fm1= AB，BC，CA Fm2= AB，BA，AC，CA F的最小依賴集Fm不一定是唯一的它與對(duì)各函數(shù)依賴FDi 及XA中X各屬性的處置順序有關(guān),極小化過程（續(xù)）,極小化過程( 定理6.3的證明 )也是檢驗(yàn)F是否為極小依賴集的一個(gè)算法 若改造后的F與原來的F相同，說明F本身就是一個(gè)最小依賴集,極小化過程（續(xù)）,在R中可以用與F等價(jià)的依賴集G來取代F 原因：兩個(gè)關(guān)系模式R1 ，R2，如果F與G等價(jià)，那么R1的關(guān)系一定是R2的關(guān)系。反過來，R2的關(guān)系也一定是R1的關(guān)系。,第6章 關(guān)系數(shù)據(jù)庫理

13、論,6.1 問題的提出 6.2 規(guī)范化 6.3 數(shù)據(jù)依賴的公理系統(tǒng) 6.4 模式的分解 6.5 小結(jié),6.4 模式的分解,把低一級(jí)的關(guān)系模式分解為若干個(gè)高一級(jí)的關(guān)系模式的方法并不是唯一的 只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)，分解方法才有意義,關(guān)系模式分解的標(biāo)準(zhǔn),三種模式分解的等價(jià)定義 分解具有無損連接性 分解要保持函數(shù)依賴 分解既要保持函數(shù)依賴，又要具有無損連接性,模式的分解（續(xù)）,定義6.16 關(guān)系模式R的一個(gè)分解： = R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，F(xiàn)i 為 F在 Ui 上的投影 定義6.17 函數(shù)依賴集合XY | XY F+XY Ui 的一個(gè)覆蓋 F

14、i 叫作 F 在屬性 Ui 上的投影,模式的分解（續(xù)）,例: SL（Sno， Sdept， Sloc） F= SnoSdept,SdeptSloc,SnoSloc SL2NF 存在插入異常、刪除異常、冗余度大和修改復(fù)雜等問題，分解方法可以有多種,模式的分解（續(xù)）,SL SnoSdeptSloc 95001 CS A 95002 IS B 95003 MA C 95004 IS B 95005 PH B ,模式的分解（續(xù)）,1. SL分解為下面三個(gè)關(guān)系模式： SN(Sno) SD(Sdept) SO(Sloc),分解后的關(guān)系為：,SN SD SO Sno Sdept Sloc 95001 CS

15、A 95002 IS B 95003 MA C 95004 PH 95005 ,模式的分解（續(xù)）,分解后的數(shù)據(jù)庫丟失了許多信息 例如無法查詢95001學(xué)生所在系或所在宿舍。 如果分解后的關(guān)系可以通過自然連接恢復(fù)為原來的關(guān)系，那么這種分解就沒有丟失信息,模式的分解（續(xù)）,2. SL分解為下面二個(gè)關(guān)系模式： NL(Sno, Sloc) DL(Sdept, Sloc) 分解后的關(guān)系為： NL DL Sno Sloc Sdept Sloc 95001 A CS A 95002 B IS B 95003 C MA C 95004 B PH B 95005 B ,模式的分解（續(xù)）,NL DL Sno Sl

16、oc Sdept 95001 A CS 95002 B IS 95002 B PH 95003 C MA 95004 B IS 95004 B PH 95005 B IS 95005 B PH,模式的分解（續(xù)）,NL DL比原來的SL關(guān)系多了3個(gè)元組 無法知道95002、95004、95005 究竟是哪個(gè)系的學(xué)生 元組增加了，信息丟失了,第三種分解方法,3. 將SL分解為下面二個(gè)關(guān)系模式： ND(Sno, Sdept) NL(Sno, Sloc) 分解后的關(guān)系為：,模式的分解（續(xù)）,ND NL Sno Sdept Sno Sloc 95001 CS 95001 A 95002 IS 95002

17、 B 95003 MA 95003 C 95004 IS 95004 B 95005 PH 95005 B ,模式的分解（續(xù)）,ND NL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 CS A 95005 PH B 與SL關(guān)系一樣，因此沒有丟失信息,具有無損連接性的模式分解,關(guān)系模式R的一個(gè)分解 = R1，R2， ，Rn 若R與R1、R2、Rn自然連接的結(jié)果相等，則稱關(guān)系 模式R的這個(gè)分解具有無損連接性（Lossless join） 具有無損連接性的分解保證不丟失信息 無損連接性不一定能解決插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等

18、問題,模式的分解（續(xù)）,第三種分解方法具有無損連接性 問題: 這種分解方法沒有保持原關(guān)系中的函數(shù)依賴 SL中的函數(shù)依賴SdeptSloc 沒有投影到關(guān)系模式ND、NL上,保持函數(shù)依賴的模式分解,設(shè)關(guān)系模式R被分解為若干個(gè)關(guān)系模式 R1，R2，Rn （其中U=U1U2Un，且不存在Ui Uj，F(xiàn)i為F在Ui上的投影），若F所邏輯蘊(yùn)含的函數(shù)依賴一定也由分解得到的某個(gè)關(guān)系模式中的函數(shù)依賴Fi所邏輯蘊(yùn)含，則稱關(guān)系模式R的這個(gè)分解是保持函數(shù)依賴的（Preserve dependency）。,第四種分解方法,將SL分解為下面二個(gè)關(guān)系模式： ND(Sno, Sdept) DL(Sdept, Sloc) 這種分解方法就保持了函數(shù)依賴。,模式的分解（續(xù)）,如果一個(gè)分解具有無損連接性，則它能夠保證不丟失信息。 如果一個(gè)分解保持了函數(shù)依賴，則它可以減輕或解決各種異常情況。 分解具有無損連接性和分解保持函數(shù)依賴是兩個(gè)互相獨(dú)立的標(biāo)準(zhǔn)。具有無損連接性的分解不一定能夠保持函數(shù)依賴。同樣，保持函數(shù)依賴的分解也不一定具有無損連