數(shù)據(jù)庫系統(tǒng)課件：ch7 Relational Database Design (1)

1、7.1華南理工大學(xué) 軟件學(xué)院1DB華南理工大學(xué) 軟件學(xué)院7.2華南理工大學(xué) 軟件學(xué)院n設(shè)計一個好的關(guān)系數(shù)據(jù)庫系統(tǒng)，關(guān)鍵是要設(shè)計一個好的數(shù)據(jù)庫模式（數(shù)據(jù)庫邏輯設(shè)計問題）n數(shù)據(jù)庫邏輯設(shè)計主要解決的問題：l關(guān)系數(shù)據(jù)庫應(yīng)該組織成幾個關(guān)系模式l關(guān)系模式中有包括哪些屬性n在關(guān)系數(shù)據(jù)庫設(shè)計理論的指導(dǎo)下，選擇較好的關(guān)系模式集合7.3華南理工大學(xué) 軟件學(xué)院要求設(shè)計教學(xué)管理數(shù)據(jù)庫，其關(guān)系模式SCD如下：SCD(SNO,SN,AGE,DEPT,MN,CNO,SCORE)l其中，SNO表示學(xué)生學(xué)號，SN表示學(xué)生姓名，AGE表示學(xué)生年齡，DEPT表示學(xué)生所在的學(xué)院，MN表示院長姓名，CNO表示課程號，SCORE表示成績

2、。 7.4華南理工大學(xué) 軟件學(xué)院根據(jù)實際情況，這些數(shù)據(jù)有如下語義規(guī)定：1. 一個學(xué)院有若干個學(xué)生，但一個學(xué)生只屬于一個學(xué)院；2. 一個學(xué)院只有一名院長，但一個院長可以同時兼幾個學(xué)院的院長；3. 一個學(xué)生可以選修多門功課，每門課程可有若干學(xué)生選修；4. 每個學(xué)生學(xué)習(xí)課程有一個成績。n在此關(guān)系模式中填入一部分具體的數(shù)據(jù)，則可得到SCD關(guān)系模式的實例，即一個教學(xué)管理數(shù)據(jù)庫，如圖所示7.5華南理工大學(xué) 軟件學(xué)院SNOSNAGEDEPTMNCNOSCORES1趙亦17計算機劉偉C190S1趙亦17計算機劉偉C285S2錢爾18信息王平C557S2錢爾18信息王平C680S2錢爾18信息王平C7 70S2

3、錢爾18信息王平C870S3孫珊20信息王平C180S3孫珊20信息王平C270S3孫珊20信息王平C485S4李思21自動化劉偉C1937.6華南理工大學(xué) 軟件學(xué)院根據(jù)上述的語義規(guī)定，并分析以上關(guān)系中的數(shù)據(jù)，我們可以看出：(SNO,CNO)屬性的組合能唯一標(biāo)識一個元組，所以(SNO,CNO)是該關(guān)系模式的主碼。但在進行數(shù)據(jù)庫的操作時，會出現(xiàn)以下幾方面的。1.數(shù)據(jù)冗余。每個學(xué)院名和院長的名字存儲的次數(shù)等于該系的學(xué)生人數(shù)乘以每個學(xué)生選修的課程門數(shù)，同時學(xué)生的姓名、年齡也都要重復(fù)存儲多次，數(shù)據(jù)的冗余度很大，浪費了存儲空間。SNOSNAGEDEPTMNCNOSCORES2錢爾錢爾18信息信息王平王平

4、C557S2錢爾錢爾18信息信息王平王平C680S2錢爾錢爾18信息信息王平王平C770S2錢爾錢爾18信息信息王平王平C8707.7華南理工大學(xué) 軟件學(xué)院2.插入異常。如果某個新學(xué)院沒有招生，尚無學(xué)生時，則學(xué)院名和院長的信息無法插入到數(shù)據(jù)庫中。l因為在這個關(guān)系模式中，(SNO,CNO)是主碼。根據(jù)關(guān)系的實體完整性約束，主碼的值不能為空，而這時沒有學(xué)生，SNO和CNO均無值，因此不能進行插入操作。l另外，當(dāng)某個學(xué)生尚未選課，即CNO未知，實體完整性約束還規(guī)定，主碼的值不能部分為空，同樣不能進行插入操作。SNOSNAGEDEPTMNCNOSCORE計算機計算機劉偉劉偉計算機計算機劉偉劉偉x7.8

5、華南理工大學(xué) 軟件學(xué)院3.刪除異常。l某學(xué)院學(xué)生全部畢業(yè)而沒有招生時，刪除全部學(xué)生的記錄則學(xué)院名、院長也隨之刪除，而這個學(xué)院依然存在，在數(shù)據(jù)庫中卻無法找到該學(xué)院的信息。l另外，如果某個學(xué)生不再選修C1課程，本應(yīng)該只刪去C1，但C1是主碼的一部分，為保證實體完整性，必須將整個元組一起刪掉，這樣，有關(guān)該學(xué)生的其它信息也隨之丟失。SNOSNAGEDEPTMNCNOSCORES1趙亦趙亦17計算機計算機劉偉劉偉C190S1趙亦趙亦17計算機計算機劉偉劉偉C2857.9華南理工大學(xué) 軟件學(xué)院4.更新異常。l如果學(xué)生改名，則該學(xué)生的所有記錄都要逐一修改SN；l又如某學(xué)院更換院長，則屬于該學(xué)院的學(xué)生記錄都要

6、修改MN的內(nèi)容，稍有不慎，就有可能漏改某些記錄，這就會造成數(shù)據(jù)的不一致性，破壞了數(shù)據(jù)的完整性。SNOSNAGEDEPTMNCNOSCORES2錢爾錢爾18信息信息王平王平C557S2錢爾錢爾18信息信息王平王平C680S2錢爾錢爾18信息信息王平王平C770S2錢爾錢爾18信息信息王平王平C870S3孫珊孫珊20信息信息王平王平C10S3孫珊孫珊20信息信息王平王平C270S3孫珊孫珊20信息信息王平王平C4857.10華南理工大學(xué) 軟件學(xué)院n由于存在以上問題，我們說，SCD是一個不好的關(guān)系模式。產(chǎn)生上述問題的原因，直觀地說，是因為關(guān)系中“包羅萬象”，內(nèi)容太雜了。n那么，怎樣才能得到一個好的關(guān)

7、系模式呢？n我們把關(guān)系模式SCD分解為下面三個結(jié)構(gòu)簡單的關(guān)系模式，如圖所示。l學(xué)生l選課l學(xué)院7.11華南理工大學(xué) 軟件學(xué)院SNOSNAGEDEPTSNOCNOSCORES1趙亦趙亦17計算機計算機S1C190S2錢爾錢爾18信息信息S1C285S3孫珊孫珊20信息信息S2C557S4李思李思21自動化自動化S2C680S2C7S2C570DEPTMNS3C10計算機計算機劉偉劉偉S3C270信息信息王平王平S3C485自動化自動化劉偉劉偉S4C193分解后的關(guān)系模式分解后的關(guān)系模式 7.12華南理工大學(xué) 軟件學(xué)院n在以上三個關(guān)系模式中，實現(xiàn)了信息的某種程度的分離，lS中存儲學(xué)生基本信息，與所

8、選課程及院長無關(guān)；lD中存儲學(xué)院的有關(guān)信息，與學(xué)生無關(guān)；lSC中存儲學(xué)生選課的信息，而與學(xué)生及學(xué)院的有關(guān)信息無關(guān)。7.13華南理工大學(xué) 軟件學(xué)院n與SCD相比，分解為三個關(guān)系模式后，數(shù)據(jù)的冗余度明顯降低。l當(dāng)新插入一個學(xué)院時，只要在關(guān)系D中添加一條記錄。l當(dāng)某個學(xué)生尚未選課，只要在關(guān)系S中添加一條學(xué)生記錄，而與選課關(guān)系無關(guān)，這就避免了插入異常。l當(dāng)一個學(xué)院的學(xué)生全部畢業(yè)時，只需在S中刪除該學(xué)院的全部學(xué)生記錄，而關(guān)系D中有關(guān)該學(xué)院的信息仍然保留，從而不會引起刪除異常。l同時，由于數(shù)據(jù)冗余度的降低，數(shù)據(jù)沒有重復(fù)存儲，也不會引起更新異常。 7.14華南理工大學(xué) 軟件學(xué)院n經(jīng)過上述分析，我們說分解后的

9、關(guān)系模式是一個好的關(guān)系數(shù)據(jù)庫模式。n從而得出結(jié)論，一個好的關(guān)系模式應(yīng)該具備以下：l1. 盡可能少的數(shù)據(jù)冗余。l2. 沒有插入異常。l3. 沒有刪除異常。l4. 沒有更新異常。7.15華南理工大學(xué) 軟件學(xué)院n但要注意，一個好的關(guān)系模式并不是在任何情況下都是最優(yōu)的，l比如查詢某個學(xué)生選修課程名及所在學(xué)院的院長時，要通過連接S與D，而連接所需要的系統(tǒng)開銷非常大，因此要以實際設(shè)計的目標(biāo)出發(fā)進行設(shè)計SNOSNAGEDEPT SNOCNOSCORES1趙亦17計算機 S1C190S2錢爾18信息 S1C285S3孫珊20信息 S2C557S4李思21自動化 S2C680 S2C7 S2C570DEPTMN

10、 S3C10計算機劉偉 S3C270信息王平 S3C485自動化劉偉 S4C193n如何按照一定的規(guī)范設(shè)計關(guān)系模式，將結(jié)構(gòu)復(fù)雜的關(guān)系分解成結(jié)構(gòu)簡單的關(guān)系，從而把不好的關(guān)系數(shù)據(jù)庫模式轉(zhuǎn)變?yōu)楹玫年P(guān)系數(shù)據(jù)庫模式，這就是關(guān)系的規(guī)范化。7.16華南理工大學(xué) 軟件學(xué)院n規(guī)范化又可以根據(jù)不同的要求而分成若干級別。n我們要設(shè)計的關(guān)系模式中的各屬性是相互依賴、相互制約的，這樣才構(gòu)成了一個結(jié)構(gòu)嚴(yán)謹(jǐn)?shù)恼w。n因此在設(shè)計關(guān)模式時，必須從語義上分析這些依賴關(guān)系。n數(shù)據(jù)庫模式的好壞和關(guān)系中各屬性間的依賴關(guān)系有關(guān)，因此，我們先討論屬性間的依賴關(guān)系，然后再討論關(guān)系規(guī)范化理論。7.17華南理工大學(xué) 軟件學(xué)院不良的模式設(shè)計不良的

11、數(shù)據(jù)依賴范式范式的判定模式分解各種異常部分函數(shù)依賴、傳遞函數(shù)依賴、多值依賴1NF、2NF、3NF、BCNF、4NFArmstrong公理、屬性集的閉包、函數(shù)依賴的推導(dǎo)、候選碼的計算、函數(shù)依賴集的等價和最小覆蓋、模式分解的定義、保持函數(shù)依賴分解和保持無損連接分解的判定和分解算法良好的模式設(shè)計7.18華南理工大學(xué) 軟件學(xué)院n關(guān)系模式的完整表示是一個五元組： RU，D，Dom，F(xiàn).其中：lR為關(guān)系名；lU為關(guān)系的屬性集合；lD為屬性集U中屬性的數(shù)據(jù)域；lDom為屬性到域的映射；lF為屬性集U的數(shù)據(jù)依賴集。n關(guān)系模式可以用三元組簡單表示為： RU，F(xiàn)7.19華南理工大學(xué) 軟件學(xué)院函數(shù)依賴的定義及性質(zhì)n

12、關(guān)系模式中的各屬性之間相互依賴、相互制約的聯(lián)系稱為數(shù)據(jù)依賴。n數(shù)據(jù)依賴一般分為函數(shù)依賴、多值依賴和連接依賴。n其中,函數(shù)依賴是最重要的數(shù)據(jù)依賴。7.20華南理工大學(xué) 軟件學(xué)院n函數(shù)依賴（Functional Dependency）是關(guān)系模式中屬性之間的一種邏輯依賴關(guān)系。l例如在上一節(jié)介紹的關(guān)系模式SCD中，SNO與SN、AGE、DEPT之間都有一種依賴關(guān)系。l由于一個SNO只對應(yīng)一個學(xué)生，而一個學(xué)生只能屬于一個學(xué)院，所以當(dāng)SNO的值確定之后，SN，AGE，DEPT的值也隨之被唯一的確定了。l這類似于變量之間的單值函數(shù)關(guān)系。設(shè)單值函數(shù)Y=F(X)，自變量X的值可以決定一個唯一的函數(shù)值Y。l在這里

13、，我們說SNO決定函數(shù)（SN，AGE，DEPT），或者說（SN，AGE，DEPT）函數(shù)依賴于SNO。SNOSNAGEDEPTMNCNOSCORE7.21華南理工大學(xué) 軟件學(xué)院XYX1Y1X3Y3X5Y5定義 設(shè)關(guān)系模式R(U,F)，U是屬性全集，F(xiàn)是U上的函數(shù)依賴集，X和Y是U的子集，如果對于如果對于R(U)的任意一個可能的的任意一個可能的關(guān)系關(guān)系r，對于，對于X的每一個具體值，的每一個具體值，Y都有唯一的具體值與之都有唯一的具體值與之對應(yīng)（也就是對任意對應(yīng)（也就是對任意t1、t2 r,如果如果t1X=t2X有有t1Y=t2Y），則稱X決定函數(shù)Y，或Y函數(shù)依賴于X，記作XY。我們稱X為決定因素

14、，Y為依賴因素。當(dāng)Y不函數(shù)依賴于X時，記作:X Y。當(dāng)XY且YX時，則記作：X Y。這類似于變量之間的單值函數(shù)關(guān)系。設(shè)單值函數(shù)Y=F(X)，自變量X的值可以決定一個唯一的函數(shù)值Y。 t1t27.22華南理工大學(xué) 軟件學(xué)院n對于關(guān)系模式SCDlU=SNO,SN,AGE,DEPT,MN,CNO,SCORElF=SNOSN，SNOAGE，SNODEPT，n一個SNO有多個SCORE的值與其對應(yīng)，因此SCORE不能唯一地確定，即SCORE不能函數(shù)依賴于SNO，所以有：SNO SCORE。n但是SCORE可以被 _ 唯一地確定。所以可表示為：（SNO，CNO）SCORE（SNO，CNO）7.23華南理工

15、大學(xué) 軟件學(xué)院n例:職工號(A) 基本工資(B)獎金(C) 051390 50 052420 50 053390 80A BA CB AC AB C7.24華南理工大學(xué) 軟件學(xué)院ABC142356346738910說明關(guān)系是否滿足下列函數(shù)依賴：A B A C C A AC BAB和ACB不滿足，因為（3,5,6)和（3,4,6），t1(A)=t2(A)=3,但是t1(B)=5而t2(B)=4; t1(AC)=t2(AC)=(3,6),但是t1(B)=5而t2(B)=4小練習(xí)7.25華南理工大學(xué) 軟件學(xué)院定義(平凡平凡/非平凡的非平凡的FD)設(shè)設(shè)FDXY，如果，如果Y X，則稱，則稱XY為為；否

16、則，若；否則，若Y X，稱，稱XY為為。例如：（SNO，SN） SN是平凡的函數(shù)依賴n若不特別聲明，我們討論的都是非平凡的函數(shù)依賴7.26華南理工大學(xué) 軟件學(xué)院定義(完全函數(shù)依賴完全函數(shù)依賴)設(shè)X Y是關(guān)系模式R（U）的一個函數(shù)依賴，如果存在X的真子集X，使得X Y成立，則稱，記作X p Y。否則，稱，記作X Y。n只有當(dāng)決定因素是組合屬性時，討論部分函數(shù)依賴才有意義，當(dāng)決定因素是單屬性時，只能是完全函數(shù)依賴。7.27華南理工大學(xué) 軟件學(xué)院n設(shè)有關(guān)系模式選課 SCl(SNO,CNO,GRADE, CREDIT)其中，SNO表示學(xué)號，CNO表示課程號，GRADE表示成績，CREDIT表示學(xué)分。n

17、SNO或CNO都不能單獨確定成績GRADE。GRADE只能由屬性組合(SNO,CNO)來確定。課程學(xué)分CREDIT是CNO決定的，CNO CREDIT。由此可知：n(SNO,CNO) f GRADEn(SNO,CNO) p CREDITSNOGRADECREDITCNO7.28華南理工大學(xué) 軟件學(xué)院定義(傳遞函數(shù)依賴傳遞函數(shù)依賴)關(guān)系模式R中，如果X Y， Y X ，Y Z ，則稱n例：SCD(SNO,SN,AGE,DEPT,MN,CNO,SCORE) 存在下列依賴關(guān)系：lSNODEPTlDEPTMNlSNO MN (傳遞函數(shù)依賴傳遞函數(shù)依賴)7.29華南理工大學(xué) 軟件學(xué)院1. 函數(shù)依賴是語義

18、范疇的概念函數(shù)依賴是語義范疇的概念. 它反映了一種語義完整性它反映了一種語義完整性約束約束,只能根據(jù)語義來確定一個函數(shù)依賴只能根據(jù)語義來確定一個函數(shù)依賴.l例如，對于關(guān)系模式例如，對于關(guān)系模式S，當(dāng)學(xué)生不存在重名的情況下，可，當(dāng)學(xué)生不存在重名的情況下，可以得到：以得到：4SNAGE4SNDEPTl這種函數(shù)依賴關(guān)系，必須是在沒有重名的學(xué)生條件下才成這種函數(shù)依賴關(guān)系，必須是在沒有重名的學(xué)生條件下才成立的，否則就不存在函數(shù)依賴了。立的，否則就不存在函數(shù)依賴了。l所以函數(shù)依賴反映了一種語義完整性約束。所以函數(shù)依賴反映了一種語義完整性約束。 7.30華南理工大學(xué) 軟件學(xué)院2. 函數(shù)依賴關(guān)系的存在與時間無

19、關(guān)。函數(shù)依賴關(guān)系的存在與時間無關(guān)。l因為函數(shù)依賴是指關(guān)系中的因為函數(shù)依賴是指關(guān)系中的所有元組應(yīng)該滿足所有元組應(yīng)該滿足的約束條件，而的約束條件，而不是指關(guān)系中某個或某些元組所滿足的約束條件。不是指關(guān)系中某個或某些元組所滿足的約束條件。l當(dāng)關(guān)系中的元組增加、刪除或更新后都不能破壞這種函數(shù)依賴。當(dāng)關(guān)系中的元組增加、刪除或更新后都不能破壞這種函數(shù)依賴。l因此，必須根據(jù)語義來確定屬性之間的函數(shù)依賴，而不能單憑因此，必須根據(jù)語義來確定屬性之間的函數(shù)依賴，而不能單憑某一時刻關(guān)系中的實際數(shù)據(jù)值來判斷。某一時刻關(guān)系中的實際數(shù)據(jù)值來判斷。l例如，對于關(guān)系模式例如，對于關(guān)系模式S，假設(shè)沒有給出無重名的學(xué)生這種語義，

20、假設(shè)沒有給出無重名的學(xué)生這種語義規(guī)定，則即使當(dāng)前關(guān)系中沒有重名的記錄，也只能存在函數(shù)依規(guī)定，則即使當(dāng)前關(guān)系中沒有重名的記錄，也只能存在函數(shù)依賴賴SNOSN，而不能存在函數(shù)依賴，而不能存在函數(shù)依賴SNSNO，因為如果新增，因為如果新增加一個重名的學(xué)生，函數(shù)依賴加一個重名的學(xué)生，函數(shù)依賴SNSNO必然不成立。必然不成立。l所以函數(shù)依賴關(guān)系的存在所以函數(shù)依賴關(guān)系的存在與時間無關(guān)與時間無關(guān)，而只與數(shù)據(jù)之間的，而只與數(shù)據(jù)之間的語義語義規(guī)定有關(guān)規(guī)定有關(guān)。 7.31華南理工大學(xué) 軟件學(xué)院3函數(shù)依賴與屬性之間的聯(lián)系類型有關(guān)。函數(shù)依賴與屬性之間的聯(lián)系類型有關(guān)。(了解了解)(1)在一個關(guān)系模式中，如果屬性在一個關(guān)

21、系模式中，如果屬性X與與Y有有1:1聯(lián)系時，則存在函數(shù)依賴聯(lián)系時，則存在函數(shù)依賴XY，YX，即，即X Y。l例如，當(dāng)學(xué)生無重名時，例如，當(dāng)學(xué)生無重名時，SNO與與SN。(2)如果屬性如果屬性X與與Y有有m :1的聯(lián)系時，則只存在函數(shù)依賴的聯(lián)系時，則只存在函數(shù)依賴XY。l例如，例如，SNO與與AGE，DEPT之間均為之間均為m:1聯(lián)系，所以有聯(lián)系，所以有SNOAGE，SNODEPT。(3)如果屬性如果屬性X與與Y有有m:n的聯(lián)系時，則的聯(lián)系時，則X與與Y之間不存在任何函數(shù)依賴關(guān)系。之間不存在任何函數(shù)依賴關(guān)系。l例如，一個學(xué)生可以選修多門課程，一門課程又可以為多個學(xué)生選修，例如，一個學(xué)生可以選修多

22、門課程，一門課程又可以為多個學(xué)生選修，所以所以SNO與與CNO之間不存在函數(shù)依賴關(guān)系。之間不存在函數(shù)依賴關(guān)系。n由于函數(shù)依賴與屬性之間的聯(lián)系類型有關(guān)，所以在確定屬性間的函數(shù)依由于函數(shù)依賴與屬性之間的聯(lián)系類型有關(guān)，所以在確定屬性間的函數(shù)依賴關(guān)系時，可以從分析賴關(guān)系時，可以從分析屬性間的聯(lián)系類型屬性間的聯(lián)系類型入手，便可確定屬性間的函數(shù)入手，便可確定屬性間的函數(shù)依賴。依賴。7.32華南理工大學(xué) 軟件學(xué)院n有時候要根據(jù)給定的函數(shù)依賴，判斷另外一些函數(shù)依賴是否存在，例如：n已知對于關(guān)系模式R：nA B,B C,問問A C能否成立？能否成立？n問題：函數(shù)依賴的邏輯蘊涵問題。7.33華南理工大學(xué) 軟件學(xué)院

23、定義(邏輯蘊涵邏輯蘊涵)設(shè)關(guān)系模式設(shè)關(guān)系模式R(U,F)，X,Y U，如果能從函數(shù)依賴集，如果能從函數(shù)依賴集F出函數(shù)依賴出函數(shù)依賴XY，則稱，則稱，或，或稱稱。記為記為。定義(函數(shù)依賴集的閉包函數(shù)依賴集的閉包)在關(guān)系模式在關(guān)系模式R中，為中，為F邏輯蘊涵的所有函數(shù)依賴的集邏輯蘊涵的所有函數(shù)依賴的集合稱作合稱作。7.34華南理工大學(xué) 軟件學(xué)院n是一套推理規(guī)則，是模式分解算法的理論基礎(chǔ)n用途l求給定關(guān)系模式的碼/鍵（Key）l從一組函數(shù)依賴求得蘊含的函數(shù)依賴7.35華南理工大學(xué) 軟件學(xué)院設(shè)U為屬性集，F(xiàn)是U上的函數(shù)依賴集，于是有關(guān)系模式RU，F(xiàn)。對RU，F(xiàn)來說，有以下的推理規(guī)則。1) 自反律：若Y

24、XU，則XY為F所蘊含。2) 增廣律：若XY為F所蘊含，且ZU，則XZYZ為F所蘊含。3) 傳遞律：若XY及YZ為F所蘊含，則XZ為F所蘊含。1) 合并規(guī)則：由XY，XZ，有XYZ。2) 偽傳遞規(guī)則：由XY，WYZ，有XWZ。3) 分解規(guī)則：由XY及ZY，有XZ。7.36華南理工大學(xué) 軟件學(xué)院nAl. （Reflexivity）： 若Y X U，則X Y為F所蘊含。例如：X: (SNO,DEPT) ,Y: (DEPT)(SNO,DEPT) (DEPT) 為F所蘊含。tX = sXYXtY = sYX Y自反律7.37華南理工大學(xué) 軟件學(xué)院nA2. （Augmentation）：若XY為F所蘊含

25、，且Z U，則XZYZ為F所蘊含。例如： SNO DEPT, 則: (SNO ,Ssex ) (DEPT ,Ssex ) tXZ = sXZtX = sXXYtY = sYtXZ = sXZtZ = sZtYZ = sYZXZYZ增廣律7.38華南理工大學(xué) 軟件學(xué)院nA3. （Transitivity）：若XY及YZ為F所蘊含，則XZ為F所蘊含。例如： SNO DEPT ，學(xué)院院長則：學(xué)號院長注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于FX YtX = sXtY = sYY ZtZ = sZX Z傳遞律7.39華南理工大學(xué) 軟件學(xué)院根據(jù)A1，A2，A3這三條推理規(guī)則

26、可以得到下面三條推理規(guī)則：由XY，XZ，有XYZ（A2， A3）例如：sno ssex，sno sage， 則 sno ssex，sageX Y增廣律X XY合并律X Z增廣律XY YZ傳遞律X YZ7.40華南理工大學(xué) 軟件學(xué)院：由XY，WYZ，有XWZ（A2， A3）例如：sno sname，(sname,cno) grade，則(sno,cno) grade 證明：證明：XYXWYWWYZXWZ ：由XY及 ZY，有XZ （A1， A3）例如：sno ssex,sage 則sno sage 證明：證明：Z YYZ XZ 7.41華南理工大學(xué) 軟件學(xué)院根據(jù)合并規(guī)則和分解規(guī)則，可得引理引理

27、XA1 A2Ak成立的充分必要條件是XAi成立（i=l，2，k）。例如：SNO SNAME，SSEX，SAGE，DEPT成立的充要條件是SNO SNAME， SNO SSEX， SNO SAGE， SNO DEPT7.42華南理工大學(xué) 軟件學(xué)院n已知： F = AC ，且B U，試推導(dǎo) F=| ABC證明：由AC和增廣律，得：AB BC;由自反律，得： BC C；由傳遞律，得： AB C 。7.43華南理工大學(xué) 軟件學(xué)院n已知： F = AC，B D ，試推導(dǎo) F=| ABCD證明：由AC和增廣律，得：AB BC；由自反律和傳遞律，得： AB C ；同理，得： AB D；由合并規(guī)則，得： AB

28、 CD。7.44華南理工大學(xué) 軟件學(xué)院n已知： F = AB, CD,且C B試推導(dǎo) F=| AD證明：由CB和自反律，得到BC由AB和BC,得AC由AC和CD,得AD7.45華南理工大學(xué) 軟件學(xué)院n已知：F = XYW, YZ,WZP, WQQR ,QX, 用推理公理證明 F=| XY P證明： 由XYW 和WZP 得 XYZP(偽傳遞律) 由YZ得XYXYZ 由XYXYZ 和XYZP 得到XYP7.46華南理工大學(xué) 軟件學(xué)院 例： 設(shè)F=ABE，AGJ，BEI，EG，GIH 試證：F|= ABGH 證明：用公理系統(tǒng)和F中的函數(shù)依賴，推導(dǎo)過程如下： 1. 已知 ABE，EG 則：ABG； (

29、傳遞律) 2. 已知 ABE 則：ABBE； (增廣律) 3. 已知 BEI，又 ABBE 則：ABI (傳遞律) 4. 由1和3有ABG， ABI 則：ABGI (合成規(guī)則) 5. 由4有 ABGI，又 GIH 則：ABH (傳遞律) 6. 由1和5有 ABH，ABG 則：ABGH (合成規(guī)則)7.47華南理工大學(xué) 軟件學(xué)院 在關(guān)系模式R中為F所邏輯蘊含的函數(shù)依賴的全體叫作 ，記為F+。例：R (A, B, C, G, H, I), F = AB, AC, CGH, CGI, BH 4A H F+ ？4CG HI F+ ？4AG I F+ ？47.48華南理工大學(xué) 軟件學(xué)院F + = Fre

30、peatfor each functional dependency f in F+ apply reflexivity and augmentation rules on f add the resulting functional dependencies to F +for each pair of functional dependencies f1and f2 in F + if f1 and f2 can be combined using transitivity then add the resulting functional dependency to F +until F

31、 + does not change any further7.49華南理工大學(xué) 軟件學(xué)院n問題1：有沒有一般性的算法判定XY是否能由F根據(jù)Armstrong公理導(dǎo)出？l如果計算出F+，再判斷XY是否屬于F+，由于F+的計算非常復(fù)雜，實際上是不可行n問題2：判斷一個屬性集合X是否為超碼？l可以通過計算F+ ，找出所有左半部是X的函數(shù)依賴，并且合并這些函數(shù)依賴的右半部，看是否包含了R上所有的屬性開銷也很大。7.50華南理工大學(xué) 軟件學(xué)院n設(shè)關(guān)系R（A,B,C,D),同時滿足ABC, CD, DA。該關(guān)系的超碼是什么？解：R 的一個屬性集合是R的超碼，當(dāng)且僅當(dāng)這個集合函數(shù)決定該關(guān)系的每個屬性。即超

32、碼函數(shù)決定屬性A,B,C,D。超碼為AB,BC和DB。因為ABA,ABB（自反律）ABC（已知）ABC, CD得到ABD。所以AB是R的超碼，因為它函數(shù)決定R的所有其他屬性。同理：BC,DB也是R的超碼。注意：如果問題是“候選碼”呢？我們考慮計算“屬性集上的閉包”7.51華南理工大學(xué) 軟件學(xué)院 設(shè)F為屬性集U上的一組函數(shù)依賴，XU， XF+ = A|XA能由F 根據(jù)Armstrong公理導(dǎo)出，XF+稱為屬性集n目標(biāo)l通過給定的函數(shù)依賴，找出所有的函數(shù)依賴n方法l利用FD的規(guī)則(傳遞、合并、分解)，推導(dǎo)出函數(shù)依賴的集合，即閉包(closure)7.52華南理工大學(xué) 軟件學(xué)院n算法（求屬性集X的閉

33、包 ）算法會終止嗎？最多|U-X|步FXInput：X，F(xiàn)Output：result result := X;while (result發(fā)生變化）dofor each 函數(shù)依賴 AB in F dobeginif Aresult then result:=result Bend7.53華南理工大學(xué) 軟件學(xué)院nR = (A, B, C, G, H, I)nF = A B, A C, CG H, CG I, B HnQ1: (AG)+1.result = AG2. (A B and A C)result = ABCG3. (CGH and CGAGBC) result = ABCGH 4. (CG

34、I and CGAGBCH) result = ABCGHI 7.54華南理工大學(xué) 軟件學(xué)院nR = (A, B, C, G, H, I)nF = A B, A C, CG H, CG I, B HnQ2: Is AG a candidate key? 1.Is AG a superkey?1.Does AG R? = Is (AG)+ R2.Is any subset of AG a superkey?1.Does A R? = Is (A)+ R2.Does G R? = Is (G)+ R7.55華南理工大學(xué) 軟件學(xué)院nR, U = (A, B, C, D, E), F = ABC, B

35、D, CE, CEB, ACB, Is AB a candidate key? YESFAB)(FAB)(所用依賴ABCABC BDABCDCEABCDE= ABCDEA ABCDEB ABCDE7.56華南理工大學(xué) 軟件學(xué)院nR, U = (A, B, C, D, E, G), F = AE, BEAG, CEA, GD, Is AB a candidate key? NOAB C所用依賴AE ABEBEAG ABEGGD ABEGDFAB)(= ABEGDFAB)(7.57華南理工大學(xué) 軟件學(xué)院n考慮函數(shù)依賴集F及F中函數(shù)依賴：l如果A并且F邏輯蘊涵(F - ) ( - A), 則屬性A在中是無關(guān)的4例如：F上有函數(shù)依賴ABC和AC，那么B在ABC的左半部是無關(guān)的l如果A并且函數(shù)依賴集(F - ) ( - A),邏輯蘊涵F，則屬性A在中是無關(guān)的4例如：F上有函數(shù)依賴ABCD和AC，那么C在ABCD的右半部是無關(guān)的7.58華南理工大學(xué) 軟件學(xué)院n令R為一關(guān)系模式，F(xiàn)是在R上成立的給定函數(shù)依賴集。考慮中的屬性A：lA：考慮 = - A