數(shù)據(jù)庫(kù)原理5 關(guān)系數(shù)據(jù)理論

1、數(shù)據(jù)庫(kù)系統(tǒng)原理(第5章)1第五章 關(guān)系數(shù)據(jù)理論意義：提供分析和判斷數(shù)據(jù)庫(kù)模式好壞的準(zhǔn)則；指導(dǎo)設(shè)計(jì)好的數(shù)據(jù)庫(kù)模式。地位：本章是本書最難的部分之一，但對(duì)于應(yīng)用設(shè)計(jì)十分有用。25.1 問題的提出什么是不好的數(shù)據(jù)庫(kù)設(shè)計(jì)我們目前為止掌握的知識(shí)尚無法解決大量的具體設(shè)計(jì)問題，即關(guān)系模式該如何選擇。應(yīng)用數(shù)據(jù)庫(kù)應(yīng)該由多少個(gè)表組成，每個(gè)表有哪些字段。本章即從理論上解決關(guān)系數(shù)據(jù)庫(kù)的邏輯設(shè)計(jì)問題。3一個(gè)關(guān)系模式應(yīng)當(dāng)是一個(gè)五元組。 R（U, D, DOM, F） 由于D和DOM對(duì)模式設(shè)計(jì)關(guān)系不大,因此我們?cè)诒菊轮邪殃P(guān)系模式看作是一個(gè)三元組：RU,F 當(dāng)且僅當(dāng)U上的一個(gè)關(guān)系r滿足F時(shí),r稱為關(guān)系模式RU,F的一個(gè)關(guān)系。

2、關(guān)系,作為一張二維表,我們對(duì)它有一個(gè)最起碼的要求：每一個(gè)分量必須是不可分的數(shù)據(jù)項(xiàng)。滿足了這個(gè)條件的關(guān)系模式就屬于第一范式（1NF）。 4我們的任務(wù)是研究模式設(shè)計(jì)，研究設(shè)計(jì)一個(gè)“好”的（沒有“毛病”的）關(guān)系模式的辦法。 數(shù)據(jù)依賴是通過一個(gè)關(guān)系中屬性間值的相等與否體現(xiàn)出來的數(shù)據(jù)間的相互關(guān)系。它是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象,是數(shù)據(jù)內(nèi)在的性質(zhì),是語義的體現(xiàn)?，F(xiàn)在人們已經(jīng)提出了許多種類型的數(shù)據(jù)依賴,其中最重要的是函數(shù)依賴(Functional Dependency簡(jiǎn)記為FD)和多值依賴(Multivalued Dependency簡(jiǎn)記為MVD)。 5函數(shù)依賴極為普遍地存在例如，描述學(xué)生的關(guān)系,可以有學(xué)

3、號(hào)(SNO),姓名(SNAME),系名(SDEPT)等幾個(gè)屬性。由于一個(gè)學(xué)號(hào)只對(duì)應(yīng)一個(gè)學(xué)生,一個(gè)學(xué)生只在一個(gè)系學(xué)習(xí)。因而當(dāng)“學(xué)號(hào)”值確定之后,姓名和該生所在系的值也就被唯一地確定了。上述值的確定就象數(shù)學(xué)函數(shù)：自變量x確定之后,相應(yīng)的函數(shù)值f(x)也就唯一地確定。我們說SNO函數(shù)決定SNAME和SDEPT,或者說SNAME，SDEPT函數(shù)依賴于SNO,記為SNOSNAME,SNOSDEPT。 6例如，前面介紹的學(xué)生選課模型，可以用一個(gè)關(guān)系模式表示：SC(Sno,Sname,Sage,Sgendar,Sdept,Cno,Cname,Grade)一個(gè)可能的關(guān)系為：95001 趙一 18 男 CS 1

4、 C語言 8095001 趙一 18 男 CS 2 數(shù)據(jù)庫(kù)原理 8292002 錢二 19 男 CS 1 C語言 80可以看出，該模式存在的主要問題是冗余。7冗余是不可避免的。在一定程度內(nèi)也是合理的。但是，過度的冗余則會(huì)給數(shù)據(jù)庫(kù)帶來三類大的問題：插入異常（學(xué)生不選課，其基本信息就無法插入）刪除異常（刪除學(xué)生選課信息，其基本信息也被刪除）修改復(fù)雜（修改某學(xué)生的基本信息，要隨選課多次被修改）8解決的方法一個(gè)大關(guān)系分解為若干個(gè)小關(guān)系。如前面的SC大關(guān)系分解為第三章的 Student，SC和Course三個(gè)小關(guān)系，即可消除三類異常。9為什么小關(guān)系比大關(guān)系好呢？現(xiàn)在我們要討論的就是這個(gè)問題。從上面的分解

5、觀察到：如果在一個(gè)關(guān)系模式內(nèi)，函數(shù)依賴形式上如果只有：碼 非主屬性 的形式，冗余就較小，三類異常就沒有了。105.2 規(guī)范化目的將具有不合適性質(zhì)的關(guān)系轉(zhuǎn)換為更合適的形式。要求掌握函數(shù)依賴的定義及判定；掌握1NF到BCNF的定義及判定；了解多值依賴，理解4NF的定義。115.2.1 函數(shù)依賴(注意：現(xiàn)在還不能用到碼的概念。)定義5.1 設(shè)R(U)是屬性集U上的關(guān)系模式。X，Y是U的子集。若對(duì)于R的任何一個(gè)可能的關(guān)系r，r中不可能存在兩個(gè)元組在X屬性值上相等而在Y屬性值上不等，則稱X函數(shù)確定Y或Y函數(shù)依賴于X，記作 XY.12XY，且YX，則稱XY是非平凡的函數(shù)依賴。若不特別聲明,我們總是討論非平

6、凡的函數(shù)依賴。 XY，但YX 則稱XY是平凡的函數(shù)依賴。全部一致，部分一致，沒有太大意義。13若XY,則X叫做決定因素(Determinant)。 若XY，YX，則記作XY。在這種情況下，X和Y在R(U)中地位相同。若Y不函數(shù)依賴于X,則記作X Y。14定義5.3 (完全函數(shù)依賴和部分函數(shù)依賴的定義)在R(U)中，如果XY，并且對(duì)X的任何一個(gè)真子集X，都有XY，則稱Y對(duì)X完全函數(shù)依賴，記作: X Y定義5.4（傳遞函數(shù)依賴）在R(U)中，如果XY，(YX)，YX，YZ，則稱Z對(duì)X傳遞函數(shù)依賴。155.2.2 碼定義5.4 設(shè)K為R中的屬性或?qū)傩越M，若KU，則K為R的候選碼。若候選碼多于一個(gè)，則

7、選定其中一個(gè)作為主碼。主屬性：包含在任何候選碼中的屬性。非主屬性：不包含在任何候選碼中的屬性。16定義5.5 (外碼的定義)關(guān)系模式R中的屬性或?qū)傩越MX并非R的碼，但X是另一個(gè)關(guān)系模式的碼，則稱X是R的外部碼，簡(jiǎn)稱外碼。175.2.3 范式滿足最低要求的關(guān)系，叫第一范式，簡(jiǎn)稱1NF。關(guān)系表的每一分量是不可分的數(shù)據(jù)項(xiàng)1NF 不允許表中出現(xiàn)嵌套或復(fù)合的屬性 5NF 4NF BCNF 3NF 2NF 1NF 18定義5.6 若R1NF，對(duì)R的每一個(gè)非平凡的函數(shù)依賴XY，要么X是主屬性，要么X不是任何碼的真子集，則R 2NF。2NF 在 1NF基礎(chǔ)上消除了非主屬性對(duì)碼的部分函數(shù)依賴。5.2.4 2NF

8、19例：前面的大表SC不是2NF的關(guān)系模式。如果一個(gè)關(guān)系模式不是2NF的，一定存在過度冗余，帶來3類異常。解決方法：分解為多個(gè)小表。205.2.5 3NF定義5.7 若R 1NF，對(duì)R中的每一個(gè)非平凡的函數(shù)依賴XY，要么Y是主屬性，要么X中含有碼，則R 3NF。213NF與2NF相比，條件更強(qiáng)。因?yàn)閄中含有碼，則X不會(huì)是任何碼的真子集；而2NF定義中，X不是任何碼的真子集，還可能是非主屬性組。即3NF在2NF的基礎(chǔ)上消除了非主屬性對(duì)碼的傳遞函數(shù)依賴。225.2.6 BCNF由Boyce和Codd共同提出，屬于修正的3NF。定義5.8 若R1NF，對(duì)R中的每一個(gè)非平凡的函數(shù)依賴XY，X中均含有碼

9、，則R BCNF。23BCNF與3NF相比，條件更強(qiáng)。不允許主屬性對(duì)碼的部分和傳遞函數(shù)依賴。從3NF到BCNF也是通過分解得到的。到BCNF為止，完全消除了由于函數(shù)依賴帶來的過度冗余及相應(yīng)的三類異常。但事實(shí)上，關(guān)系模式還可能存在由于非函數(shù)依賴帶來的冗余及三類異常。這些數(shù)據(jù)依賴有多值依賴和連接依賴。我們只簡(jiǎn)單要求多值依賴。在多個(gè)實(shí)體間聯(lián)系為1對(duì)多聯(lián)系時(shí)可能出現(xiàn)多值依賴帶來的問題。245.2.7 多值依賴多值依賴定義：設(shè)有關(guān)系模式R(U)，X, Y, Z是U的子集，且Z=U-X-Y。對(duì)于R的任一關(guān)系r, 給定一對(duì)(x, z)值，就有一組Y的值與之對(duì)應(yīng)，這組值僅僅決定于x值而與z值無關(guān)，則稱“Y多值

10、依賴于X”或“X多值決定Y”。記作XY。或記憶為：對(duì)R(U)的任一關(guān)系r，任意兩元組s和t，如果sX=tX，則交換s和t的Y值所得兩個(gè)新元組必在r中。25翻譯情況 A B C （姓名 ，東方語言 ，西方語言） 王 紅 日語 法語 王 紅 漢語 英語 王 紅 日語 英語 王 紅 漢語 法語是BCNF , 其中 只有ABC 才是關(guān)鍵字，沒有違反 法則但有冗余, 又有刪除異常，例如刪除（王 紅 漢語 法語）26衣著 （姓名，衣服，褲子）類似， 可稱為 完全搭配依賴（課程, 教師, 參考書）類似 ，看書上27不是多值依賴的例子：學(xué)生選課表SC（Sno，Cno，G）中一個(gè)Sno（一個(gè)學(xué)生）有一組Cno（

11、選了一組課程）和一組G（有一組成績(jī)），但Cno與G有關(guān)（成績(jī)與課程有關(guān)），所以沒有SnoCno，以及SnoG。28平凡的多值依賴：若XY，而Z= ；則稱X Y是平凡的多值依賴。多值依賴的性質(zhì)：1、對(duì)稱(互補(bǔ))性：若X Y；則X Z，其中Z=U-X-Y。2、傳遞性：若X Y，Y Z；則X Z-Y。3、函數(shù)依賴是多值依賴的特殊情況：若X Y，則X Y。4、若X Y，X Z；則X YZ，X Z-Y， X Y-Z， X YZ。29多值依賴與函數(shù)依賴的區(qū)別1、多值依賴的有效性與屬性集的范圍有關(guān)。若XY在U上成立，則在W（XY W U）上一定成立；反之則不然，即X Y在W（W包含于U）上成立，在U上并不一

12、定成立。這是因?yàn)槎嘀狄蕾嚨亩x中不僅涉及屬性組X和Y，而且涉及U中其余屬性Z。 但是在關(guān)系模式R（U）中，函數(shù)依賴X Y的有效性僅決定于X，Y這兩個(gè)屬性集的值。只要在R的任何一個(gè)關(guān)系r中，元組在X和Y上的值滿足函數(shù)依賴的定義，則該函數(shù)依賴在任何屬性集W（U的子集）上成立。302、子集有效性不同：若函數(shù)依賴X Y在R（U）上成立，則對(duì)于任何Y屬于Y，都有X Y成立。而多值依賴X Y在R（U）上成立，卻不能斷言對(duì)于任何Y屬于Y，有X Y成立。315.2.8 4NF定義5.10 若關(guān)系模式R（U，F(xiàn)）1NF，如果對(duì)于R的每個(gè)非平凡多值依賴X Y（Y不包含于X），X都含有碼，則稱R（U，F(xiàn)）4NF。實(shí)

13、質(zhì)上4NF消除了多值依賴。為什么？32一個(gè)關(guān)系模式到了BCNF可能還有不合適的性質(zhì)WSC（倉(cāng)庫(kù)、管理員、物品）中，倉(cāng)庫(kù)的管理員與物品無關(guān)，存放的物品也與管理員無關(guān)；每一管理員隨物品增加而重復(fù)被存儲(chǔ)，類似地，每一物品也隨管理員增加而重復(fù)被存儲(chǔ)，存在過度冗余；三類異常同樣存在?？梢酝ㄟ^分解方法將其分解為一組4NF 的關(guān)系模式WSC分解為WS和WC兩個(gè)關(guān)系模式即可使之達(dá)到4NF，解決上述問題335.2.9 規(guī)范化小結(jié)1NF：每個(gè)分量是不可分的數(shù)據(jù)項(xiàng)。2NF：非主屬性完全函數(shù)依賴于碼。3NF：非主屬性即不部分依賴于碼也不傳遞依賴于碼。BCNF：所有屬性都不部分依賴于碼也不傳遞依賴于碼。所有決定因素(屬

14、性集)都包含碼。4NF：所有非平凡的多值依賴都是函數(shù)依賴。345.3 數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊(yùn)含：定義5.11對(duì)于關(guān)系模式R，其任何一個(gè)關(guān)系r，若函數(shù)依賴X Y都成立（即r中任意兩元組s，t，若tX=sX，則tY=sY），則稱函數(shù)依賴集F邏輯蘊(yùn)含XY。35為了求得給定關(guān)系模式的碼，為了從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴，例如已知函數(shù)依賴集F，要問XY是否為F所蘊(yùn)含，就需要一套推理規(guī)則，這組推理規(guī)則是1974年首先由Armstrong提出來的。它是關(guān)系模式分解算法的理論基礎(chǔ)。要求得給定關(guān)系模式的所有候選碼對(duì)于關(guān)系模式的范式級(jí)別判定具有決定作用：范式級(jí)別的判定需要知道關(guān)系模式的所有候選碼；有的范式級(jí)

15、別還需確定主屬性和非主屬性，也需要知道所有候選碼。36Armstrong 公理系統(tǒng)A1 自反律 若Y X U，則X Y為F所蘊(yùn)含(給出平凡的函數(shù)依賴)。A2 增廣律 若X Y為F所蘊(yùn)含，且Z U，則XZ YZ為F所蘊(yùn)含。A3 傳遞律 如X Y及Y Z為F 所蘊(yùn)含，則X Z為F所蘊(yùn)含。37Armstrong公理的推論：合并規(guī)則：若X Y，X Z，有X YZ。分解規(guī)則：由X Y及Z包含于Y，有X Z。偽傳遞規(guī)則：若X Y，WY Z，有XW Z。根據(jù)合并規(guī)則和分解規(guī)則，得到一個(gè)重要事實(shí)：X A1A2AK成立的充分必要條件是X Ai成立（i=1,2,k)。38F的閉包：在關(guān)系模式R（U，F(xiàn)）中為F所邏

16、輯蘊(yùn)含的函數(shù)依賴的全體叫做F的閉包，記作F + 。Armstrong公理是有效的，完備的：有效性：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每個(gè)函數(shù)依賴一定在F +中 。有效性的證明書上定理5.1“Armstrong推理規(guī)則是正確的”可直接得證。完備性： F + 中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來。 經(jīng)典證明39定義5.13 XF +的定義 設(shè)F是屬性集U上的一組函數(shù)依賴集，X U， XF + A|XA能由F根據(jù)Armstrong公理導(dǎo)出。引理5.2 設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y U，XY能否由F根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y

17、XF +算法5.1 求XF +的方法。非常重要。例1.P185增加要求 求(AC) F +40令X(0)AC計(jì)算X(1)=ACEB=ABCE計(jì)算X(2)ABCDE即得結(jié)果。定義5.13,引理5.2和算法5.1非常重要，可用于求碼。如KF +=U, 而KF + ！=U，即求得K為一候選碼。41求碼方法要點(diǎn)(自己的總結(jié))找出不出現(xiàn)在非平凡函數(shù)依賴右部的屬性組X，它們一定包含于所有候選碼。求XF +，判斷U？成立結(jié)束，否則轉(zhuǎn)3。(自底向上)擴(kuò)展X的X，求XF +，判斷U？直到所有情況找完為止。42應(yīng)用舉例，對(duì)書上P185例1，求所有候選碼要點(diǎn)：不出現(xiàn)在任何函數(shù)依賴右部的只有A；求AF+A；擴(kuò)展AB，

18、ABF+U；AC，ACF+U；AD，ADF+ ！U；（需再擴(kuò)展）AE， AEF+ ！U；（需再擴(kuò)展）再擴(kuò)展ADE，ADEF+ ！U43要證明它首先解決如何判定一個(gè)函數(shù)依賴是否屬于由F根據(jù)Armstrong公理推導(dǎo)出來的函數(shù)依賴的集合。如果能求出這個(gè)集合就很容易判斷，但是求這樣的集合是一個(gè)NP完全問題。所以該判定轉(zhuǎn)換為：任一個(gè)函數(shù)依賴X Y是F + 中成員的充分必要條件是：Y XF + 。證明完備性轉(zhuǎn)換為證明它的逆否命題為真。即若函數(shù)依賴不能有F從Armstrong公理導(dǎo)出，那么它必然不為F所蘊(yùn)含。證明分3步（略）證明用到了構(gòu)造(特殊的二維表)、反證，十分巧妙。44完備性證明。要證原命題，只需證

19、明其逆否命題：若函數(shù)依賴XY不能由F出發(fā)從Armstrong公理導(dǎo)出，則它本身不為F所蘊(yùn)含。（1）若VW成立，且V XF + ，則W XF + 。V XF + ，則由引理5.2，有XV。由XV， VW，有X W。再由引理5.2，有W XF + 。45（2）構(gòu)造如下二維表r，r必是R的一個(gè)關(guān)系。用反證法。 XF + U XF + 11. 1 00 0 11. 1 11 1若r不是R的關(guān)系，必是由F中的函數(shù)依賴VW在r上不成立所致。觀察r，V XF + ，而W XF + 。與（1）矛盾。46（3）若XY不能由Armstrong公理導(dǎo)出則Y不是XF + 的子集，必有Y Y，且Y UXF +。（推）

20、XY本身不為F所蘊(yùn)含。（觀察r）得證。47定義5.14 函數(shù)依賴集等價(jià)：如果G +=F + ，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋或G是F的覆蓋），或F與G等價(jià)。有相應(yīng)的判定算法。引理5.3的充分性證明的過程實(shí)際上給出了判斷兩函數(shù)依賴集等價(jià)的方法。引理5.3 F+ =G+的充分必要條件是 F G+ ，和G F+ 。48定義5.15 最小依賴集右部唯一無多余函數(shù)依賴無部分函數(shù)依賴定理5.3 每一個(gè)函數(shù)依賴集都等價(jià)于一個(gè)極小函數(shù)依賴集Fm (Fm一定存在，可能不唯一。)定理5.3的證明過程給出了檢驗(yàn)(或構(gòu)造)Fm的方法。49例子：設(shè)FABC，AB,求Fm。FmBC，AB ?對(duì)不對(duì)？為什么？50上面

21、的F與Fm根本不等價(jià)。FmAC，AB515.4 模式的分解要求了解前面我們?yōu)榱私鉀Q設(shè)計(jì)得不好(范式級(jí)別不夠高)的數(shù)據(jù)庫(kù)模式帶來的問題，我們采用了大關(guān)系分解為小關(guān)系的方法來提高范式級(jí)別。本節(jié)給出分解的理論指導(dǎo)。5.4.1 模式分解的三個(gè)定義1. 具有無損連接性。分解后的(幾個(gè))小模式可自然連接恢復(fù)位原來的模式。522. 保持函數(shù)依賴 分解前后函數(shù)依賴集等價(jià)3. 既保持無損連接，又保持連接依賴。(理想情況)5.4.2 分解的無損連接性和保持函數(shù)依賴性m(r)R1(r) R2(r) Rk(r) 定義5.18 R1，R2 Rk是R上的一個(gè)分解，若對(duì)于R的任一關(guān)系r，均有r m(r)成立，則具有無損連接

22、性。此定義無法用于判斷，無損連接性只能通過算法5.2來判斷。53算法5.2 要求會(huì)做。(通過例子來學(xué)習(xí))例1 R(S，A，I，P) 分解為R1(S，A)，R2(S，I，P)。FSA,SIPS A I P-a1 a2 b13 b14a1 b22 a3 a4由于有SA，使第二行第二列變成a2。S A I P-a1 a2 b13 b14a1 a2 a3 a454補(bǔ)充例 R(A，B，C，D，E)，分解R1=AD,R2=AB,R3=BE,R4=CDE,R5=AE F=AC, BC, CD, DEC, CE AA B C D E-a1 b12 b13 a4 b15a1 a2 b23 b24 b25b31 a2 b33 b34 a5b41 b42 a3 a4 a5a1 b52 b53 b54 a5AC(b23變b13，b53變b13) , BC(b33變b13) CD (b24,b34,b54變a4), DEC(C 列變a3)CE A(A列變a1) 第三行出現(xiàn)了a1到a5.55定理5.5 R的一個(gè)分解R1，R2具有無損連接性的充分必要條件是U1U2U1U2F+或U1U2U2U1 F+ ?？捎糜诤?jiǎn)單情況(分解為兩個(gè)小關(guān)系模式)的快速判斷。例如：RABC, F=AB,B