第六章關(guān)系數(shù)據(jù)庫(kù)—數(shù)據(jù)依賴和規(guī)范化

1、An Introduction to Database System數(shù)據(jù)庫(kù)系統(tǒng)原理數(shù)據(jù)庫(kù)系統(tǒng)原理An Introduction to Database System第六章第六章 關(guān)系數(shù)據(jù)理論關(guān)系數(shù)據(jù)理論(3)(3)An Introduction to Database System第六章第六章 關(guān)系數(shù)據(jù)理論關(guān)系數(shù)據(jù)理論6.1 數(shù)據(jù)依賴數(shù)據(jù)依賴6.2 規(guī)范化規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)數(shù)據(jù)依賴的公理系統(tǒng)6.4 模式的分解模式的分解An Introduction to Database System6.3 數(shù)據(jù)依賴的公理系統(tǒng)數(shù)據(jù)依賴的公理系統(tǒng)n邏輯蘊(yùn)含邏輯蘊(yùn)含定義定義6.11 對(duì)于滿足一組對(duì)于

2、滿足一組函數(shù)依賴函數(shù)依賴 F 的系模式的系模式R ，函數(shù)依賴，函數(shù)依賴XY都成立都成立, 則稱則稱 F邏輯蘊(yùn)含邏輯蘊(yùn)含X YAn Introduction to Database SystemArmstrong公理系統(tǒng)公理系統(tǒng)n一套推理規(guī)則，是模式分解算法的理論基礎(chǔ)一套推理規(guī)則，是模式分解算法的理論基礎(chǔ)n用途用途n求給定關(guān)系模式的碼求給定關(guān)系模式的碼n從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴An Introduction to Database System1. Armstrong公理系統(tǒng)公理系統(tǒng) 關(guān)系模式關(guān)系模式R 來(lái)說(shuō)有以下的推理規(guī)則：來(lái)說(shuō)有以下的推理規(guī)則：n A1

3、.自反律自反律（Reflexivity）：）： 若若Y X U，則，則X Y為為F所蘊(yùn)含。所蘊(yùn)含。nA2.增廣律（增廣律（Augmentation）：）：若若XY為為F所蘊(yùn)含，且所蘊(yùn)含，且Z U，則，則XZYZ為為F所蘊(yùn)含。所蘊(yùn)含。nA3.傳遞律傳遞律（Transitivity）：）：若若XY及及YZ為為F所蘊(yùn)含，則所蘊(yùn)含，則XZ為為F所蘊(yùn)含。所蘊(yùn)含。An Introduction to Database System定理定理 6.l Armstrong推理規(guī)則是正確的推理規(guī)則是正確的（1）自反律）自反律:若若Y X U，則，則X Y為為F所蘊(yùn)含所蘊(yùn)含證證: 設(shè)設(shè)Y X U 對(duì)對(duì)R 的任一關(guān)系

4、的任一關(guān)系r中的任意兩個(gè)元組中的任意兩個(gè)元組t，s： 若若tX=sX，由于，由于Y X，有，有ty=sy， 所以所以XY成立成立. 自反律得證自反律得證An Introduction to Database System定理定理6.l(2)增廣律增廣律: 若若XY為為F所蘊(yùn)含，且所蘊(yùn)含，且Z U，則，則XZYZ 為為F所蘊(yùn)含。所蘊(yùn)含。 證：證：設(shè)設(shè)XY為為F所蘊(yùn)含，且所蘊(yùn)含，且Z U。 設(shè)設(shè)R 的任一關(guān)系的任一關(guān)系r中任意的兩個(gè)元組中任意的兩個(gè)元組t，s；若若tXZ=sXZ，則有，則有tX=sX和和tZ=sZ；由由XY，于是有，于是有tY=sY，所以，所以tYZ=sYZ，所以，所以XZYZ為為

5、F所蘊(yùn)含所蘊(yùn)含.增廣律得證。增廣律得證。An Introduction to Database System定理定理6.l(3) 傳遞律：若傳遞律：若XY及及YZ為為F所蘊(yùn)含，則所蘊(yùn)含，則XZ為為 F所蘊(yùn)含。所蘊(yùn)含。證：證：設(shè)設(shè)XY及及YZ為為F所蘊(yùn)含。所蘊(yùn)含。對(duì)對(duì)R 的任一關(guān)系的任一關(guān)系 r中的任意兩個(gè)元組中的任意兩個(gè)元組 t，s。若若tX=sX，由于，由于XY，有，有 tY=sY；再由再由YZ，有，有tZ=sZ，所以，所以XZ為為F所蘊(yùn)含所蘊(yùn)含.傳遞律得證。傳遞律得證。An Introduction to Database System2. 導(dǎo)出規(guī)則導(dǎo)出規(guī)則1.根據(jù)根據(jù)A1，A2，A3這三

6、條推理規(guī)則可以得到下這三條推理規(guī)則可以得到下面三條推理規(guī)則：面三條推理規(guī)則：n 合并規(guī)則合并規(guī)則：由：由XY，XZ，有，有XYZ。 （A2， A3）n 偽傳遞規(guī)則偽傳遞規(guī)則：由：由XY，WYZ，有，有XWZ。 （A2， A3）n 分解規(guī)則分解規(guī)則：由：由XY及及 Z Y，有，有XZ。 （A1， A3）An Introduction to Database System導(dǎo)出規(guī)則導(dǎo)出規(guī)則2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理根據(jù)合并規(guī)則和分解規(guī)則，可得引理6.1 引理引理6.l XA1 A2Ak成立的充分必要成立的充分必要條件是條件是XAi成立（成立（i=l，2，k）。）。An Introducti

7、on to Database System3. 函數(shù)依賴閉包函數(shù)依賴閉包定義定義6.12 在關(guān)系模式在關(guān)系模式R中為中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作 F的的閉包閉包，記為，記為F+。An Introduction to Database SystemF的閉包的閉包 , F+計(jì)算是計(jì)算是NP完全問(wèn)題，完全問(wèn)題，X A1A2.An F+=X , Y , Z , XY , XZ , YZ , XYZ , X X, Y Y, Z Z, XY X, XZ X, YZ Y, XYZ X,X Y, Y Z , XY Y, XZ Y, YZ Z, XYZ Y,X Z, Y Y

8、Z, XY Z, XZ Z, YZ YZ, XYZ Z,X XY, XY XY, XZ XY, XYZ XY, X XZ, XY YZ, XZ XZ, XYZ YZX YZ, XY XZ, XZ XY, XYZ XZ,X ZYZ, XY XYZ, XZ XYZ, XYZ XYZ F=X Y,Y ZAn Introduction to Database System3. 函數(shù)依賴閉包函數(shù)依賴閉包定義定義6.13 設(shè)設(shè)F為屬性集為屬性集U上的一組函數(shù)依上的一組函數(shù)依賴，賴，X U， XF+ = AXA能由能由F 根根據(jù)據(jù)Armstrong公理導(dǎo)出公理導(dǎo)出，XF+稱為屬性稱為屬性集集X關(guān)于函數(shù)依賴集

9、關(guān)于函數(shù)依賴集F 的閉包的閉包An Introduction to Database System關(guān)于閉包的引理關(guān)于閉包的引理n引理引理6.2 設(shè)設(shè)F為屬性集為屬性集U上的一組函數(shù)依賴，上的一組函數(shù)依賴，X，Y U，XY能由能由F 根據(jù)根據(jù)Armstrong公公理導(dǎo)出的充分必要條件是理導(dǎo)出的充分必要條件是Y XF+n用途用途將判定將判定XY是否能由是否能由F根據(jù)根據(jù)Armstrong公理導(dǎo)公理導(dǎo)出的問(wèn)題，就轉(zhuǎn)化為求出出的問(wèn)題，就轉(zhuǎn)化為求出XF+ ，判定，判定Y是否為是否為XF+的子集的問(wèn)題的子集的問(wèn)題An Introduction to Database System U=A, B, C, D

10、; F=A B, BC D;nA+ =nC+ =n(AC)+ =ExampleAB.C. ABCDAn Introduction to Database System求閉包的算法求閉包的算法算法算法6.l 求屬性集求屬性集X（X U）關(guān)于）關(guān)于U上的上的函數(shù)依賴集函數(shù)依賴集F 的閉包的閉包XF+ 輸入：輸入：X，F(xiàn)輸出：輸出：XF+步驟：步驟：An Introduction to Database System算法算法6.l（1）令）令X（0）=X，i=0（2）求）求B，這里，這里B = A |( V)( W)(VW F V X（i）A W)；（3）X（i+1）=BX（i）（4）判斷）判斷X（

11、i+1）= X （i）嗎嗎?（5）若相等或）若相等或X（i）=U , 則則X（i）就是就是XF+ , 算法終止。算法終止。（6）若否，則）若否，則 i=i+l，返回第（，返回第（2）步。）步。An Introduction to Database System算法算法6.l對(duì)于算法對(duì)于算法6.l， 令令ai =|X（i）|，ai 形成形成一個(gè)步長(zhǎng)大于一個(gè)步長(zhǎng)大于1的嚴(yán)格遞增的序列，序列的嚴(yán)格遞增的序列，序列的上界是的上界是 | U |，因此該算法最多，因此該算法最多 |U| - |X| 次循環(huán)就會(huì)終止。次循環(huán)就會(huì)終止。An Introduction to Database System函數(shù)依賴

12、閉包函數(shù)依賴閉包例例1 已知關(guān)系模式已知關(guān)系模式R，其中，其中U=A，B，C，D，E；F=ABC，BD，CE，ECB，ACB。求（求（AB）F+ 。解解 設(shè)設(shè)X（0）=AB； (1)計(jì)算計(jì)算X（1）: 逐一的掃描逐一的掃描F集合中各個(gè)函數(shù)依賴，集合中各個(gè)函數(shù)依賴， 找左找左部為部為A，B或或AB的函數(shù)依賴。的函數(shù)依賴。得到兩個(gè)：得到兩個(gè)：ABC，BD。 于是于是X（1）=ABCD=ABCD。An Introduction to Database System函數(shù)依賴閉包函數(shù)依賴閉包(2)因?yàn)橐驗(yàn)閄（0） X（1） ，所以再找出左部為，所以再找出左部為ABCD子子集的那些函數(shù)依賴，又得到集的那些

13、函數(shù)依賴，又得到ABC，BD， CE，ACB， 于是于是X（2）=X（1）BCDE=ABCDE。(3)因?yàn)橐驗(yàn)閄（2）=U，算法終止，算法終止所以（所以（AB）F+ =ABCDE。An Introduction to Database System4. Armstrong公理系統(tǒng)的有效性與完備性公理系統(tǒng)的有效性與完備性n建立公理系統(tǒng)體系建立公理系統(tǒng)體系目的目的：從已知的：從已知的 f 推導(dǎo)出未知的推導(dǎo)出未知的fn明確：明確：1.公理系統(tǒng)推導(dǎo)出來(lái)的公理系統(tǒng)推導(dǎo)出來(lái)的 f 正確？正確？ 2. F+中的每一個(gè)中的每一個(gè) f 都能推導(dǎo)出來(lái)？都能推導(dǎo)出來(lái)？f 不能由不能由F 導(dǎo)出導(dǎo)出, f F+ F+f

14、FAn Introduction to Database System4. Armstrong公理系統(tǒng)的有效性與完備性公理系統(tǒng)的有效性與完備性n有效性有效性：由：由F出發(fā)根據(jù)出發(fā)根據(jù)Armstrong公理推導(dǎo)出來(lái)的公理推導(dǎo)出來(lái)的每一個(gè)函數(shù)依賴一定在每一個(gè)函數(shù)依賴一定在F+中中 /* Armstrong正確正確n完備性完備性：F+中的每一個(gè)函數(shù)依賴，必定可以由中的每一個(gè)函數(shù)依賴，必定可以由F出出發(fā)根據(jù)發(fā)根據(jù)Armstrong公理推導(dǎo)出來(lái)公理推導(dǎo)出來(lái) /* Armstrong公理夠用，完全公理夠用，完全完備性完備性：所有不能用：所有不能用Armstrong公理推導(dǎo)出來(lái)公理推導(dǎo)出來(lái)f, 都不為真都不

15、為真 若若 f 不能用不能用Armstrong公理推導(dǎo)出來(lái)，公理推導(dǎo)出來(lái)， f F+ An Introduction to Database System有效性與完備性的證明有效性與完備性的證明證明：證明：1. 有效性有效性2. 完備性完備性只需證明只需證明逆否命題逆否命題: 若函數(shù)依賴若函數(shù)依賴XY不能由不能由F從從Armstrong公理導(dǎo)出，那么它必然不為公理導(dǎo)出，那么它必然不為F所所蘊(yùn)含蘊(yùn)含分三步證明：分三步證明：An Introduction to Database System有效性與完備性的證明有效性與完備性的證明(1)引理引理: 若若VW成立，且成立，且V XF+，則，則W XF

16、+ 證證 因?yàn)橐驗(yàn)?V XF+ ，所以有，所以有XV成立；成立； 因?yàn)橐驗(yàn)閄 V，VW，于是，于是XW成立成立 所以所以W XF+ (2)/* 若若 f 不能用不能用Armstrong公理推導(dǎo)出來(lái)，公理推導(dǎo)出來(lái)， f F+ /* 若存在若存在r， F+中的全部函數(shù)依賴在中的全部函數(shù)依賴在 r上成立。上成立。 /* 而不能用而不能用Armstrong公理推導(dǎo)出來(lái)的公理推導(dǎo)出來(lái)的f , 在在r上不成立。上不成立。 構(gòu)造一張二維表構(gòu)造一張二維表r，它由下列兩個(gè)元組構(gòu)成，可以證明，它由下列兩個(gè)元組構(gòu)成，可以證明r必是必是R（U，F(xiàn)）的一個(gè)關(guān)系）的一個(gè)關(guān)系，即，即F+中的全部函數(shù)依賴在中的全部函數(shù)依賴在

17、 r上成立上成立。 An Introduction to Database SystemArmstrong公理系統(tǒng)的有效性與完備性公理系統(tǒng)的有效性與完備性(續(xù)續(xù)) XF+ U-XF+ 11.1 00.0 11.1 11.1 若若r不是不是R 的關(guān)系，則必由于的關(guān)系，則必由于F中有函數(shù)依中有函數(shù)依賴賴VW在在r上不成立所致。由上不成立所致。由r的構(gòu)成可知的構(gòu)成可知，V必必定是定是XF+ 的子集，而的子集，而W不是不是XF+ 的子集，可是由第的子集，可是由第（1）步，）步，W XF+，矛盾。所以，矛盾。所以r必是必是R的一個(gè)關(guān)系。的一個(gè)關(guān)系。 An Introduction to Database

18、 SystemArmstrong公理系統(tǒng)的有效性與完備性公理系統(tǒng)的有效性與完備性(續(xù)續(xù))(3) )/* 若若 f 不能用不能用Armstrong公理推導(dǎo)出來(lái)，公理推導(dǎo)出來(lái)， f F+ /* 而不能用而不能用Armstrong公理推導(dǎo)出來(lái)的公理推導(dǎo)出來(lái)的 f , 在在r上不成立。上不成立。n若若XY 不能由不能由F從從Armstrong公理導(dǎo)出，則公理導(dǎo)出，則Y 不不是是XF+ 的子集。（引理的子集。（引理6.2）n因此必有因此必有Y 的子集的子集Y 滿足滿足 Y U-XF+， 則則XY在在 r 中不成立，即中不成立，即XY必不為必不為 R 蘊(yùn)含蘊(yùn)含 /* 因?yàn)橐驗(yàn)?F+中的全部函數(shù)依賴在中的全

19、部函數(shù)依賴在 r上成立。上成立。An Introduction to Database System6. 函數(shù)依賴集等價(jià)函數(shù)依賴集等價(jià)定義定義6.14 如果如果G+=F+，就說(shuō)函數(shù)依賴，就說(shuō)函數(shù)依賴集集F覆蓋覆蓋G（F是是G的覆蓋，或的覆蓋，或G是是F的覆的覆蓋），或蓋），或F與與G等價(jià)等價(jià)。An Introduction to Database System函數(shù)依賴集等價(jià)的充要條件函數(shù)依賴集等價(jià)的充要條件引理引理6.3 F+ = G+ 的充分必要條件是的充分必要條件是 F G+ ，和，和G F+ 證證: 充分性顯然，只證必要性。充分性顯然，只證必要性。 （1）若）若F G+ ，則，則XF+

20、XG+ 。 （2）任?。┤稳Y F+ 則有則有 Y XF+ XG+ 。 所以所以XY (G+）+= G+。即。即F+ G+。 （3）同理可證）同理可證G+ F+ ，所以，所以F+ = G+。An Introduction to Database System函數(shù)依賴集等價(jià)函數(shù)依賴集等價(jià)n要判定要判定F G+，只須逐一對(duì)，只須逐一對(duì)F中的函數(shù)依中的函數(shù)依賴賴XY，考察，考察 Y 是否屬于是否屬于XG+ 就行了。就行了。因此引理因此引理6.3 給出了判斷兩個(gè)函數(shù)依賴給出了判斷兩個(gè)函數(shù)依賴集等價(jià)的可行算法。集等價(jià)的可行算法。 An Introduction to Database System函數(shù)

21、依賴集等價(jià)函數(shù)依賴集等價(jià)nF1=A-BD , C-D, B-C n F2=A-B, B-CD, C-DAn Introduction to Database System6. 最小依賴集最小依賴集 定義定義6.15 如果函數(shù)依賴集如果函數(shù)依賴集F滿足下列條件，則稱滿足下列條件，則稱F為一個(gè)為一個(gè)極小函數(shù)依賴集極小函數(shù)依賴集。亦稱為。亦稱為最小依賴集最小依賴集或或最最小覆蓋小覆蓋。 (1) F中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性。中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性。 (2) F中不存在這樣的函數(shù)依賴中不存在這樣的函數(shù)依賴XA，使得，使得F與與F-XA等價(jià)。等價(jià)。 (3) F中不存在這樣的函數(shù)依賴中

22、不存在這樣的函數(shù)依賴XA， X有真有真 子集子集Z使得使得F-XAZA與與F等價(jià)。等價(jià)。An Introduction to Database System最小依賴集最小依賴集例例2 對(duì)于對(duì)于6.1節(jié)中的關(guān)系模式節(jié)中的關(guān)系模式S，其中：，其中： U= SNO，SDEPT，MN，CNAME，G ， F= SNOSDEPT，SDEPTMN， （SNO，CNAME）G 設(shè)設(shè)F=SNOSDEPT，SNOMN， SDEPTMN，(SNO，CNAME)G， (SNO，SDEPT)SDEPTF是最小覆蓋，而是最小覆蓋，而F 不是。不是。因?yàn)椋阂驗(yàn)椋篎 -SNOMN與與F 等價(jià)等價(jià) F -(SNO，SDEPT

23、)SDEPT也與也與F 等價(jià)等價(jià) F -(SNO，SDEPT)SDEPT SNOSDEPT也與也與F 等價(jià)等價(jià)An Introduction to Database System7. 極小化過(guò)程極小化過(guò)程定理定理6.3 每一個(gè)函數(shù)依賴集每一個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小均等價(jià)于一個(gè)極小 函數(shù)依賴集函數(shù)依賴集Fm。此。此Fm稱為稱為F的最小依賴集的最小依賴集證證:構(gòu)造性證明，依據(jù)定義分三步對(duì)構(gòu)造性證明，依據(jù)定義分三步對(duì)F進(jìn)行進(jìn)行“極小極小化處理化處理”，找出，找出F的一個(gè)最小依賴集。的一個(gè)最小依賴集。(1)逐一檢查逐一檢查F中各函數(shù)依賴中各函數(shù)依賴FDi：XY， 若若Y=A1A2 Ak，k 2，

24、 則用則用 XAj |j=1，2， k 來(lái)取代來(lái)取代XY。 引理引理6.1保證了保證了F變換前后的等價(jià)性。變換前后的等價(jià)性。An Introduction to Database System極小化過(guò)程極小化過(guò)程(2)逐一檢查逐一檢查F中各函數(shù)依賴中各函數(shù)依賴FDi：XA， 令令G=F-XA， 若若A XG+， 則從則從F中去掉此函數(shù)依賴。中去掉此函數(shù)依賴。 由于由于F與與G =F-XA等價(jià)的充要條件是等價(jià)的充要條件是A XG+ 因此因此F變換前后是等價(jià)的。變換前后是等價(jià)的。An Introduction to Database System極小化過(guò)程極小化過(guò)程(3)逐一取出逐一取出F中各函數(shù)依賴中各函數(shù)依賴FDi：XA， 設(shè)設(shè)X=B1B2Bm， 逐一考查逐一考查Bi （i=l，2，m），）， 若若A （X-Bi ）F+ ， 則以則以X-Bi 取代取代X。 由于由于F與與F-XAZA等價(jià)的充要條件等價(jià)的充要條件是是A ZF+ ，其中，其中Z=X-Bi 因此因此F變換前后是等價(jià)的。變換前后是等價(jià)的。An Introduction to Database System極小化過(guò)程極小化過(guò)程由定義，最后剩下的由定義，最后剩下的F 就一定是極小