關(guān)系數(shù)據(jù)理論

1、關(guān)系數(shù)據(jù)理論 本章主要內(nèi)容： 規(guī)范化的必要性 數(shù)值依賴 關(guān)系模式的規(guī)范化 模式分解原則 一.問(wèn)題的提出 問(wèn)題提出： 針對(duì)一個(gè)具體問(wèn)題，如何構(gòu)造合適的(更好的)數(shù)據(jù) 模式，即如何更好地設(shè)計(jì)數(shù)據(jù)的邏輯結(jié)構(gòu)？ 關(guān)系數(shù)據(jù)理論的研究背景 關(guān)系模型建立在嚴(yán)格的數(shù)據(jù)理論基礎(chǔ)上，并可向別 的數(shù)據(jù)模型轉(zhuǎn)換，因此常以關(guān)系模型為背景來(lái)討論 這個(gè)問(wèn)題 背景知識(shí) 數(shù)據(jù)模式(schema) 數(shù)據(jù)庫(kù)中全體數(shù)據(jù)的邏輯結(jié)構(gòu)和特征描述，如 數(shù)據(jù)記錄的構(gòu)成，數(shù)據(jù)間的聯(lián)系，安全性、完 整性要求等。常以某一種數(shù)據(jù)模型為基礎(chǔ) 關(guān)系模型的形式化定義：R(U,D,dom,F)，本章 簡(jiǎn)化為R(U, F) 關(guān)系模型R的一個(gè)關(guān)系r：U上的一個(gè)關(guān)

2、系r滿 足F 關(guān)系規(guī)范化可能出現(xiàn)的問(wèn)題 存在的問(wèn)題：數(shù)據(jù)冗余(系主任名)、更 新異常(換系主任)、插入異常(系沒(méi)有招 生系主任不能插入)、刪除異常(學(xué)生畢 業(yè))。 怎么改善？ 模式分解是主要方法 學(xué)生關(guān)系可分解為以下三個(gè)關(guān)系： 學(xué)生（學(xué)號(hào)，姓名，所在系） 系（所在系，系主任姓名） 考試（學(xué)號(hào)，課程名，成績(jī)） 新關(guān)系克服了學(xué)生關(guān)系存在的問(wèn)題，更加合理 和實(shí)用。 二 .規(guī)范化 概念：將一個(gè)低一級(jí)范式的關(guān)系模式分解為若 干個(gè)高一級(jí)范式的關(guān)系模式的過(guò)程 目的：設(shè)計(jì)正確、良好的關(guān)系模式 基本思想：逐步消除關(guān)系模式的數(shù)據(jù)依賴中不 合適的部分，使模式達(dá)到一定程度的分離，但 又不丟失原模式中的信息 模式分解的

3、實(shí)質(zhì)：投影 約定：設(shè)R是一關(guān)系模式，U是R的屬性集合，X、 YU，r是R的一個(gè)關(guān)系實(shí)例，元組tR。則用 tX表示元組t在屬性集合X上的值。XY表示X和 Y的并集。 1.函數(shù)依賴 Y=f(X) 函數(shù) Y=sin(X) Y=X+1Y=X2+2X+1 省=f(城市) 姓名=f(學(xué)號(hào)) 函數(shù)依賴的定義 設(shè)R(U)是屬性集U上的關(guān)系模式。X,Y是U的子 集。若對(duì)于R(U)的任意一個(gè)可能的關(guān)系r，r中 不可能存在兩個(gè)元組在X上的屬性值相等，而 在Y上的屬性值不等，則稱X函數(shù)確定Y或Y函 數(shù)依賴于X，記作XY。 學(xué)生（學(xué)號(hào)，姓名，性別，年齡，班級(jí)號(hào)） 存在以下的函數(shù)依賴： 學(xué)號(hào)姓名 學(xué)號(hào)性別 學(xué)號(hào)年齡 學(xué)號(hào)

4、班級(jí)號(hào) 說(shuō)明： 1. 函數(shù)依賴不是指關(guān)系模式R的某個(gè)或某些關(guān)系 實(shí)例滿足的約束條件，而是指R的所有關(guān)系實(shí) 例均要滿足的約束條件。 2. 函數(shù)依賴是語(yǔ)義范疇的概念。只能根據(jù)數(shù)據(jù)的 語(yǔ)義來(lái)確定函數(shù)依賴。 例如“姓名年齡” 3. 數(shù)據(jù)庫(kù)設(shè)計(jì)者可以對(duì)現(xiàn)實(shí)世界作強(qiáng)制的規(guī)定。 例如規(guī)定不允許同名人出現(xiàn)，函數(shù)依賴“姓名 年齡”成立。 非平凡函數(shù)依賴與平凡依賴 如果XY，但Y不包含于X，則稱XY是非平 凡的函數(shù)依賴。如不特別說(shuō)明，我們總是討論 非平凡函數(shù)依賴。 如：(學(xué)號(hào),課程號(hào))成績(jī) 如：(學(xué)號(hào),所在系)所在系 非平凡依賴 平凡依賴 v 如果Y不函數(shù)依賴于X，則記作X Y。 如學(xué)號(hào)不函數(shù)依賴于性別， 則記作

5、性別 學(xué)號(hào)。 v如果XY，則X稱作決定因素。 如學(xué)號(hào)所在系，則學(xué)號(hào)稱作決定因素 v如果XY，并且YX，則可記作XY。 如果XY，并且對(duì)于X的一個(gè)任意真子集X/ 都有X/ Y，則稱Y完全函數(shù)依賴于X，并記 作 ；如果X/ Y成立，則稱Y部分函數(shù) 依賴于X，并記作 。 YX f YX p ( (學(xué)號(hào), ,課程號(hào))成績(jī) ( (學(xué)號(hào), ,所在系)系主任 完全函數(shù)依賴和部分函數(shù)依賴 完全函數(shù)依賴 部分函數(shù)依賴 傳遞函數(shù)依賴 如果XY（非平凡函數(shù)依賴，并且 Y X）、YZ，則稱Z傳遞函數(shù)依賴于X。 學(xué)生( (學(xué)號(hào)，姓名，所在系，系主任姓名， 課程名，成績(jī)) )，存在如下的函數(shù)依賴： 學(xué)號(hào)所在系， 所在系系

6、主任姓名 學(xué)號(hào)系主任姓名 2.碼 侯選碼：設(shè)K為關(guān)系模式R中的屬性或?qū)?性組合。若K U，則K稱為R的一個(gè)侯選碼 （Candidate Key） 主碼：一個(gè)關(guān)系模式R的候選鍵可以有多個(gè)， 如果在其中選定一個(gè)，則稱該侯選鍵為主碼 （Primary key） 主屬性： 候選碼中任何一個(gè)屬性元素為主屬性 （Prime Attibute） 非主屬性: 不是候選碼中得屬性稱為非主屬性 （NonPrime Attibute） f 3.關(guān)系模式的規(guī)范化 事實(shí)上：如果關(guān)系R上有函數(shù)依賴XY，而屬性 X不是一個(gè)候選碼，則R中可能存在一些數(shù)據(jù)冗 余 范式：符合某種級(jí)別(條件、要求)的關(guān)系模式 范式種類(lèi) 1NF,

7、2NF, 3NF, BCNF, 4NF,5NF 按級(jí)別(條件、要求)由低到高： 1NF 2NF 3NF BCNF 4NF 5NF 通常稱某一關(guān)系模式R為第幾范式，記作R xNF 1NF(First Normal Form) 每個(gè)關(guān)系模式都應(yīng)滿足最低要求：所有分量都 必須是不可分的最小數(shù)據(jù)項(xiàng)，并把其稱為第一 范式（1NF）關(guān)系。 學(xué) 號(hào) 姓 名 S1S1趙 亦 S1S1趙 亦 S2S2錢(qián) 爾 S2S2錢(qián) 爾 S2S2錢(qián) 爾 S2S2錢(qián) 爾 S3S3孫 珊 S3S3孫 珊 S3S3孫 珊 S4S4李 思 系 名 系 主 任 課 號(hào) 課 程 名 計(jì) 算 機(jī) 張 紅 C1C1數(shù) 據(jù) 庫(kù) 計(jì) 算 機(jī) 張

8、 紅 C2C2C C語(yǔ) 言信 息 王 平 C5C5運(yùn) 籌 學(xué) 信 息 王 平 C6C6概 率 論 信 息 王 平 C7C7 高 數(shù)信 息 王 平 C5C5運(yùn) 籌 學(xué) 信 息 王 平 C1C1數(shù) 據(jù) 庫(kù) 信 息 王 平 C2C2C C語(yǔ) 言信 息 王 平 C4C4 數(shù)學(xué)分 析 自 動(dòng) 化 劉 偉 C1C1數(shù) 據(jù) 庫(kù) 分 數(shù) 9090 8585 5757 8080 70 7070 0 0 7070 8585 9393 1NF異常原因： Students (SNo, SName, DName, DDirector, CNo, CName, CScore) 其中的函數(shù)依賴有： SNoSname SNo

9、DName CNoCname DNameDDirector (SNo, CNo) Cscore (SNo, CNo) SName (SNo, CNo) Dname (SNo, CNo) CName 2NF 如果R(U,F) 1NF，并且R中的每個(gè)非主屬性 都完全函數(shù)依賴于碼，則R(U,F) 2NF。 1NF關(guān)系向2NF的轉(zhuǎn)換： 一個(gè)1NF，但非2NF的關(guān)系總是可以被分解成 為一組2NF的關(guān)系 規(guī)范化過(guò)程中通過(guò)一組投影運(yùn)算消除部分依賴， 建議作如下分解(第一步分解) 已知關(guān)系R(A,B,C,D), (A,B)為主碼，即(A,B)-C, (A,B)-D，且A-D, 則將R分解成為兩個(gè)投影: R1(

10、A,D), A為主碼 R2(A,B,C), (A,B)為主碼，A為外碼 這樣，R可以通過(guò)R1和R2的自然連接運(yùn)算得以恢 復(fù). 分解示例： Students (SNo, SName, DName, DDirector, CNo, CName, CScore) (1) Students (SNo, SName, DName, DDirector) (2) Course (CNo, CName) (3) SC (SNo, CNo, CScore) SNOSNOSNAMESNAME S1S1趙亦 S2S2錢(qián)爾 S3S3孫珊 S4S4李思 DNameDDirector 計(jì)算機(jī)張紅 信息王平 信息王平 自

11、動(dòng)化劉偉 Students SNOSNOCNOCNOCSCOCSCO RERE S1S1C1C19090 S1S1C2C28585 S2S2C5C55757 S2S2C6C68080 S2S2C7C770 S2S2C5C57070 S3S3C1C10 0 S3S3C2C27070 S3S3C4C48585 S4S4C1C19393 SC CNOCNAMECNAME C1C1數(shù)據(jù)庫(kù) C2C2C C語(yǔ)言 C4C4數(shù)學(xué)分析 C5C5運(yùn)籌學(xué) C6C6概率論 C7C7高數(shù) Course 2NF異常原因： Students (SNo, SName, DName, DDirector) 其中的函數(shù)依賴有：

12、SNoSname SNoDName DNameDdirector SNoDDirector 3NF 如果R(U,F) 2NF，并且所有非主屬性都不 傳遞依賴于R的任何候選碼，則R(U,F) 3NF。 2NF向3NF的轉(zhuǎn)換: 一個(gè)2NF，但非3NF的關(guān)系總是可以被分解成 為一組3NF的關(guān)系 規(guī)范化過(guò)程中通過(guò)一組投影運(yùn)算消除傳遞依賴， 建議作如下分解(第二步分解) 已知關(guān)系R(A,B,C,D), A為主碼(A-B, A-C)，且B- C, 則將R分解成為兩個(gè)投影: R1(B,C), B為主碼 R2(A,B,D), A為主碼，B為外碼 這樣，R可以通過(guò)R1和R2的自然連接運(yùn)算得以恢 復(fù). Stude

13、nts (SNo, SName, DName, DDirector) 分解為： Students (SNo, SName, DName) Dept (DName, DDirector) SNOSNOSNAMESNAME S1S1趙亦 S2S2錢(qián)爾 S3S3孫珊 S4S4李思 DDirector 張紅 王平 劉偉 DName 計(jì)算機(jī) 信息 自動(dòng)化 Students SNOSNOCNOCNOCSCOCSCO RERE S1S1C1C19090 S1S1C2C28585 S2S2C5C55757 S2S2C6C68080 S2S2C7C770 S2S2C5C57070 S3S3C1C10 0 S3S

14、3C2C27070 S3S3C4C48585 S4S4C1C19393 SC CNOCNAMECNAME C1C1數(shù)據(jù)庫(kù) C2C2C C語(yǔ)言 C4C4數(shù)學(xué)分析 C5C5運(yùn)籌學(xué) C6C6概率論 C7C7高數(shù) Course DName 計(jì)算機(jī) 信息 信息 自動(dòng)化 Dept 3NF的進(jìn)一步說(shuō)明 在不考慮主屬性對(duì)碼的部分依賴和傳遞依賴時(shí)， 可以認(rèn)為是實(shí)現(xiàn)了徹底的分離，已消除了插入異 常，刪除異常，修改異常，冗余等問(wèn)題 但是，當(dāng)關(guān)系中存在兩個(gè)或更多的候選碼時(shí)，尤 其是有幾個(gè)候選碼、且候選碼內(nèi)的屬性又有部分 復(fù)合或交迭時(shí)，僅僅滿足3NF仍有問(wèn)題，需要進(jìn) 一步分解成BCNF 3NF異常示例： STC (SN

15、o, TNo, CNo) 該關(guān)系模式中包含的數(shù)據(jù)語(yǔ)義： 課程與教師之間為1 n的聯(lián)系； 學(xué)生與課程之間為m n的聯(lián)系。 候選碼為： (SNo, CNo), (SNo, Tno) 其中的函數(shù)依賴有： TNoCno (SNo,CNo)Tno (SNo, Tno)CNo SNOTNOCNO S1T1C1 S2T1C1 S3T2C1 S1T4C2 S2T4C2 存在的異常： 1數(shù)據(jù)冗余。雖然每個(gè)教師只開(kāi)一門(mén)課，但每 個(gè)選修該教師該該門(mén)課程的學(xué)生元組都要記錄 這一信息。 2插入異常。當(dāng)某門(mén)課程沒(méi)有學(xué)生選修，則學(xué) 號(hào)為空，因?yàn)橹鲗傩圆荒転榭?，教師上該門(mén)課 程的信息就無(wú)法插入。 3刪除異常。如果選修某門(mén)課程

16、的學(xué)生全部畢 業(yè)，刪除學(xué)生記錄的同時(shí),隨之也刪除了教師開(kāi) 設(shè)該門(mén)課程的信息。 4更新異常。當(dāng)某個(gè)教師開(kāi)設(shè)的某門(mén)課程課號(hào) 修改后，所有選修該教師該門(mén)課程的學(xué)生元組 都要進(jìn)行修改，如果漏改某個(gè)數(shù)據(jù)，則破壞了 數(shù)據(jù)的完整性。 BCNF 由Boyce和Codd提出，故稱BCNF范式。亦被 認(rèn)為是增強(qiáng)的第三范式，有時(shí)也歸入第三范式。 定義：若關(guān)系模式R是1NF，如果對(duì)于R的每 個(gè)函數(shù)依賴XY（Y不是X的子集），X必為 候選碼，則R為BCNF范式。 說(shuō)明 BCNF中所有的依賴都是包含碼的依賴 一個(gè)BCNF范式必是3NF，但一個(gè)3NF范式不一 定是BCNF BCNF是在函數(shù)依賴范疇內(nèi)對(duì)關(guān)系模式的徹底分 離，

17、已消除了插入和刪除異常 通常認(rèn)為BCNF是擴(kuò)充的第三范式，一般數(shù)據(jù)庫(kù) 設(shè)計(jì)達(dá)到BCNF已足夠 3NF關(guān)系向BCNF的轉(zhuǎn)換： 消除那些決定子不是候選碼的函數(shù)依賴，即可將 3NF關(guān)系分解成多個(gè)BCNF關(guān)系模式。 分解示例： STC (SNo, TNo, CNo) ST (SNo, TNo) TC (TNo, CNo) 3NF與BCNF的關(guān)系： 例1: SJP(學(xué)生S, 課程J, 名次P) (S,J)和(J,P) 均為候選碼 函數(shù)依賴為(S,J)P, (J,P) S 其中，兩個(gè)決定因素均包含(是)候選碼 可見(jiàn)SJP BCNF 多值依賴與第四范式 問(wèn)題提出：屬于BCNF范式的關(guān)系模式仍可能 存在問(wèn)題。

18、其原因是由于存在多值依賴情況。 函數(shù)依賴討論的是：元組內(nèi)屬性與屬性間的依賴或 決定關(guān)系對(duì)“屬性取值的影響”，即“屬性級(jí)的影 響”，如：屬性值是否可插入或保留； 現(xiàn)將視線上升到對(duì)元組級(jí)的影響，即：討論元組內(nèi) 屬性間的依賴關(guān)系對(duì)“元組級(jí)的影響”，即：某一 屬性取值在插入與刪除時(shí)是否影響多個(gè)元組。此即 多值依賴討論的問(wèn)題。 沿上思路發(fā)展下去，還會(huì)有對(duì)“關(guān)系級(jí)的影響”， 這就是關(guān)于“連接依賴”討論的問(wèn)題，設(shè)計(jì)5NF略。 BCNF范式異常示例 Teach (CName, TName, RBook) 課程與教師之間為m n的聯(lián)系； 課程與參考書(shū)之間為m n的聯(lián)系。 候選鍵為： (CName, TName,

19、 RBook)。 異常： 插入異常：插入某課程授課教師，因該課程有 多本參考書(shū)，須插入多個(gè)元組。 刪除異常：刪除某門(mén)課程的一本參考書(shū)，因該 課程授課教師有多名，故須刪除多個(gè)元組。 冗余：每門(mén)課程的參考書(shū)，由于有多名授課教 師，故須存儲(chǔ)多次，有大量冗余。 更新異常：修改一門(mén)課程的參考書(shū)，因該課程 涉及多名教師，故須修改多個(gè)元組。 問(wèn)題的根源： 在于參考書(shū)的取值與教師的取值彼此獨(dú)立、毫無(wú) 關(guān)系，它們都取決于課程名。此即：多值依賴之 表現(xiàn)。 多值依賴的定義 設(shè)有關(guān)系模式R(U)，X、Y、Z是U的子集， Z=U-X-Y，如果對(duì)于X的一個(gè)給定值，存在一 組Y值與其對(duì)應(yīng)，而Y的這組值又不以任何方式 與Z的

20、值相關(guān)，則說(shuō)Y多值依賴于X，記為 XY。 若Z=（即Z為空），則將多值依賴 XY稱為平凡的多值依賴。 多值依賴示例： Teach (CName, TName, RBook) 其上的多值依賴為： CNameTname CNameRBook 原因：每個(gè)（CName, RBook）上的值對(duì)應(yīng)一組 TName值，且這種對(duì)應(yīng)與RBook無(wú)關(guān)。 第四范式 設(shè)關(guān)系模式R(U,D)1NF，若對(duì)每個(gè)非平凡 的多值依賴XY（Y不屬于X），X都含有 侯選碼，則R(U,D)4NF。 BCNF關(guān)系向4NF的轉(zhuǎn)換： 分解的一般方法：若在關(guān)系模式R(XYZ)中， XY|Z，則R可無(wú)損分解為R1(XY)和R2(XZ) 兩個(gè)4

21、NF關(guān)系模式。 分解示例： Teach (CName, TName, RBook) CT (CName, TName) CB (CName, RBook) 幾個(gè)事實(shí) 模式分解可以消除冗余，解決更新異常等問(wèn)題， 但也要付出做連接運(yùn)算等昂貴的代價(jià) 需要強(qiáng)調(diào)的是：對(duì)已知關(guān)系模式的范式等級(jí)是 語(yǔ)義上的，而不僅僅是看某個(gè)時(shí)刻關(guān)系中的數(shù) 據(jù)值，必須考察數(shù)據(jù)間的依賴 即便是知道了數(shù)據(jù)依賴，也不能證明一個(gè)關(guān)系 是否3NF。我們只能首先假設(shè)這個(gè)關(guān)系是3NF， 而去驗(yàn)證給出的關(guān)系中沒(méi)有違反數(shù)據(jù)依賴的情 形 如何辨別一個(gè)關(guān)系模式的“好壞”？ 不存在部分和傳遞函數(shù)依賴等“不好”的性質(zhì) 的模式是“好”模式，否則會(huì)出現(xiàn)冗余和插入、 刪除、更新等異常現(xiàn)象 最初的設(shè)計(jì)中盡量做到“概念單一化”，即做 到讓一個(gè)關(guān)系描述一個(gè)概念、一個(gè)實(shí)體或?qū)嶓w 間的一種聯(lián)系，這樣所設(shè)計(jì)的關(guān)系模式將會(huì)接 近或達(dá)到第三范式，甚至達(dá)到BCNF 幾個(gè)事實(shí) 模式分解可以消除冗余，解決更新異常等問(wèn)題， 但也要付出做連接運(yùn)算等昂貴的代價(jià) 需要強(qiáng)調(diào)的是：對(duì)已知關(guān)系模式的范式等級(jí)是 語(yǔ)義上的，而不僅僅是看某個(gè)時(shí)刻關(guān)系中的數(shù) 據(jù)值，必須考察數(shù)據(jù)間的依賴 即便是知道了數(shù)據(jù)依賴，也不能證明