數(shù)據(jù)庫(kù)系統(tǒng)原理DatabaseSystemPrinciples課件

1、數(shù)據(jù)庫(kù)系統(tǒng)原理Database System Principles四川大學(xué)計(jì)算機(jī)學(xué)院段 磊2019.92022/8/221數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章第六章 關(guān)系數(shù)據(jù)庫(kù)理論 意義 提供分析和判斷數(shù)據(jù)庫(kù)模式好壞的準(zhǔn)則 指導(dǎo)設(shè)計(jì)好的數(shù)據(jù)庫(kù)模式 難易度 本章是本書最難的部分之一 對(duì)于應(yīng)用設(shè)計(jì)十分有用2022/8/222數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章本章目錄6.1 問(wèn)題的提出6.2 規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)6.4 模式的分解2022/8/223數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.1 問(wèn)題的提出什么是不好的數(shù)據(jù)庫(kù)設(shè)計(jì)我們目前為止掌握的知識(shí)尚無(wú)法解決大量的具體設(shè)計(jì)問(wèn)題，即關(guān)系模式該如何選

2、擇。應(yīng)用數(shù)據(jù)庫(kù)應(yīng)該由多少個(gè)表組成？每個(gè)表有哪些字段？本章從理論上解決關(guān)系數(shù)據(jù)庫(kù)的邏輯設(shè)計(jì)問(wèn)題。2022/8/224數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章關(guān)系模式一個(gè)關(guān)系模式應(yīng)當(dāng)是一個(gè)五元組。 R（U, D, DOM, F） F是本章開始引入的數(shù)據(jù)依賴集。由于D和DOM對(duì)模式設(shè)計(jì)關(guān)系不大,因此我們?cè)诒菊轮邪殃P(guān)系模式看作是一個(gè)三元組：R 當(dāng)且僅當(dāng)U上的一個(gè)關(guān)系r滿足F時(shí)，r稱為關(guān)系模式R的一個(gè)關(guān)系。 關(guān)系，作為一張二維表，我們對(duì)它有一個(gè)最起碼的要求：每一個(gè)分量必須是不可分的數(shù)據(jù)項(xiàng)。滿足了這個(gè)條件的關(guān)系模式就屬于第一范式（1NF）。 2022/8/225數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章數(shù)據(jù)依賴我們的任務(wù)是研究模式設(shè)計(jì)，研

3、究設(shè)計(jì)一個(gè)“好”的（沒(méi)有“毛病”的）關(guān)系模式的辦法。 數(shù)據(jù)依賴是通過(guò)一個(gè)關(guān)系中屬性間值的相等與否體現(xiàn)出來(lái)的數(shù)據(jù)間的相互關(guān)系。它是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象，是數(shù)據(jù)內(nèi)在的性質(zhì),是語(yǔ)義的體現(xiàn)?，F(xiàn)在人們已經(jīng)提出了許多種類型的數(shù)據(jù)依賴，其中最重要的是函數(shù)依賴(Functional Dependency, FD)和多值依賴(Multivalued Dependency, MVD)。2022/8/226數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章函數(shù)依賴函數(shù)依賴極為普遍地存在例如，描述學(xué)生的關(guān)系，可以有學(xué)號(hào)(SNO)，姓名(SNAME)，系名(SDEPT)等幾個(gè)屬性。由于一個(gè)學(xué)號(hào)只對(duì)應(yīng)一個(gè)學(xué)生，一個(gè)學(xué)生只在一個(gè)系學(xué)習(xí)。因而

4、當(dāng)“學(xué)號(hào)”值確定之后，姓名和該生所在系的值也就被唯一地確定了。上述值的確定就象數(shù)學(xué)函數(shù)：自變量x確定之后，相應(yīng)的函數(shù)值f(x)也就唯一地確定。我們說(shuō)SNO函數(shù)決定SNAME和SDEPT，或者說(shuō)SNAME，SDEPT函數(shù)依賴于SNO，記為：SNOSNAME，SNOSDEPT。2022/8/227數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章例：學(xué)生選課模型的關(guān)系模式例如，前面介紹的學(xué)生選課模型，可以用一個(gè)關(guān)系模式表示：SC(Sno,Sname,Sage,Sgendar,Sdept,Cno,Cname,Grade)一個(gè)可能的關(guān)系為：S1 趙一 18 男 CS 1 C語(yǔ)言 80S1 趙一 18 男 CS 2 數(shù)據(jù)庫(kù)原理

5、82S2 錢二 19 男 CS 1 C語(yǔ)言 80可以看出，該模式存在的主要問(wèn)題是冗余。2022/8/228數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章冗余帶來(lái)的問(wèn)題冗余是不可避免的。在一定程度內(nèi)也是合理的。但是，過(guò)度的冗余則會(huì)給數(shù)據(jù)庫(kù)帶來(lái)三類大的問(wèn)題：插入異常（學(xué)生不選課，其基本信息就無(wú)法插入）刪除異常（刪除學(xué)生選課信息，其基本信息也被刪除）修改復(fù)雜（修改某學(xué)生的基本信息，要隨選課多次被修改）2022/8/229數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章解決冗余的方法解決的方法一個(gè)大關(guān)系分解為若干個(gè)小關(guān)系。感性經(jīng)驗(yàn)：多用小關(guān)系，少用字段。如前面的SC大關(guān)系分解為第三章的 Student，SC和Course三個(gè)小關(guān)系，即可消除三類異

6、常。2022/8/2210數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章問(wèn)題的引出為什么小關(guān)系比大關(guān)系好呢？現(xiàn)在我們要討論的就是這個(gè)問(wèn)題。從上面的分解觀察到：如果在一個(gè)關(guān)系模式內(nèi)，函數(shù)依賴形式上如果只有：碼 非主屬性 的形式，冗余就較小，三類異常就沒(méi)有了。2022/8/2211數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章本章目錄6.1 問(wèn)題的提出6.2 規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)6.4 模式的分解2022/8/2212數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2 規(guī)范化目的將具有不合適性質(zhì)的關(guān)系轉(zhuǎn)換為更合適的形式。要求掌握函數(shù)依賴的定義及判定；掌握1NF到BCNF的定義及判定；了解多值依賴，理解4NF的定義。2022/8/2213數(shù)據(jù)庫(kù)系統(tǒng)概

7、論- 第6章6.2.1 函數(shù)依賴(注意：現(xiàn)在還不能用到碼的概念。)定義6.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。2022/8/2214數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.1 函數(shù)依賴XY，且YX，則稱XY是非平凡的函數(shù)依賴。若不特別聲明，我們總是討論非平凡的函數(shù)依賴。 XY，但YX 則稱XY是平凡的函數(shù)依賴。理解為：整體一致，部分一致，沒(méi)有特殊意義（過(guò)于“平凡”）。2022/8/2215數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.1 函數(shù)依賴若XY，則X叫做

8、決定因素(Determinant)。 若XY，YX，則記作XY。在這種情況下，X和Y在R(U)中地位相同。若Y不函數(shù)依賴于X，則記作X Y。2022/8/2216數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.1 函數(shù)依賴定義6.2 (完全函數(shù)依賴和部分函數(shù)依賴的定義)在R(U)中如果XY，并且對(duì)X的任何一個(gè)真子集X，都有XY，則稱Y對(duì)X完全函數(shù)依賴，記作: X Y若X Y，但Y不完全函數(shù)依賴于X，則稱Y對(duì)X部分函數(shù)依賴，記作： X YFP2022/8/2217數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.1 函數(shù)依賴定義6.3（傳遞函數(shù)依賴）在R(U)中，如果XY，(YX)，YX，YZ，則稱Z對(duì)X傳遞函數(shù)依賴。記作： X

9、 Z傳遞2022/8/2218數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.2 碼定義6.4 設(shè)K為R中的屬性或?qū)傩越M，若KU，則K為R的候選碼 (Candidate Key)。若候選碼多于一個(gè)，則選定其中一個(gè)作為主碼(Primary Key)。主屬性(Prime attribute)：包含在任何候選碼中的屬性。非主屬性(Nonprime attribute) ：不包含在任何候選碼中的屬性。 也稱非碼屬性(Non-key attribute).F2022/8/2219數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.2 碼定義6.5 (外碼的定義)關(guān)系模式R中的屬性或?qū)傩越MX并非R的碼，但X是另一個(gè)關(guān)系模式的碼，則稱X是R的

10、外部碼，簡(jiǎn)稱外碼。2022/8/2220數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.3 范式滿足最低要求的關(guān)系，叫第一范式，簡(jiǎn)稱1NF。關(guān)系表的每一分量是不可分的數(shù)據(jù)項(xiàng)1NF 不允許表中出現(xiàn)嵌套或復(fù)合的屬性 5NF 4NF BCNF 3NF 2NF 1NF 2022/8/2221數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.4 2NF定義6.6 若R1NF，對(duì)R的每一個(gè)非平凡的函數(shù)依賴XY，要么Y是主屬性，要么X不是任何碼的真子集，則R2NF。2NF 在 1NF基礎(chǔ)上消除了非主屬性對(duì)碼的部分函數(shù)依賴。2022/8/2222數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.4 2NF例：前面的大表SC不是2NF的關(guān)系模式。例4：關(guān)系模式S

11、-L-C(Sno, Sdept, Sloc, Cno, Grade)存在函數(shù)依賴Sno SdeptSdept Sloc(Sno,Cno) Grade唯一候選碼(Sno, Cno)。則SnoSdept是非主屬性對(duì)碼的部分函數(shù)依賴。2022/8/2223數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.4 2NF如果一個(gè)關(guān)系模式不是2NF的，一定存在過(guò)度冗余，帶來(lái)3類異常。解決方法：分解為多個(gè)小表。如S-L-C分解為S-L(Sno, Sdept, Sloc), SC(Sno, Cno, Grade)2NF僅僅具有歷史意義。2022/8/2224數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.5 3NF定義6.7 若R 1NF，對(duì)R

12、中的每一個(gè)非平凡的函數(shù)依賴XY，要么Y是主屬性，要么X中含有碼，則R 3NF。2022/8/2225數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.5 3NF3NF與2NF相比，條件更強(qiáng)。因?yàn)閄中含有碼，則X不會(huì)是任何碼的真子集；而2NF定義中，X不是任何碼的真子集，還可能是非主屬性組。即3NF在2NF的基礎(chǔ)上消除了非主屬性對(duì)碼的傳遞函數(shù)依賴。2022/8/2226數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.5 3NF判斷3NF例子S-L(Sno, Sdept, Sloc)唯一候選碼Sno函數(shù)依賴Sno Sdept, Sdept Sloc沒(méi)有非主屬性對(duì)碼的部分函數(shù)依賴，滿足2NF。存在非主屬性對(duì)非主屬性的函數(shù)依賴，不滿足

13、3NF。非主屬性非主屬性2022/8/2227數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.5 3NF滿足2NF，不滿足3NF，仍有過(guò)度冗余及其帶來(lái)的3類異常。S1CSB01S2CSB01S3CSB01S100MAB022022/8/2228數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.5 3NF解決方法，分解成小關(guān)系S-D(Sno, Sdept)D-L(Sdept, Sloc)2022/8/2229數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.6 BCNF由Boyce和Codd共同提出，屬于修正的3NF。定義6.8 若R1NF，對(duì)R中的每一個(gè)非平凡的函數(shù)依賴XY，X中均含有碼，則RBCNF。2022/8/2230數(shù)據(jù)庫(kù)系統(tǒng)概論- 第

14、6章6.2.6 BCNFBCNF與3NF相比，條件更強(qiáng)。不允許主屬性對(duì)碼的部分和傳遞函數(shù)依賴。到BCNF為止，完全消除了由于函數(shù)依賴帶來(lái)的過(guò)度冗余及相應(yīng)的三類異常。2022/8/2231數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.6 BCNF例7 (BCNF的例子)關(guān)系模式SPJ（學(xué)生，課程，名次）每個(gè)學(xué)生選每門課程有一定名次每門課程中每一名次只有一個(gè)學(xué)生2022/8/2232數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.6 BCNF例7 (BCNF的例子)關(guān)系模式SPJ（學(xué)生，課程，名次）每個(gè)學(xué)生選每門課程有一定名次每門課程中每一名次只有一個(gè)學(xué)生(學(xué)生,課程)-名次(課程,名次)-學(xué)生2022/8/2233數(shù)據(jù)庫(kù)系統(tǒng)

15、概論- 第6章6.2.6 BCNF例7 (BCNF的例子)關(guān)系模式SPJ（學(xué)生，課程，名次）每個(gè)學(xué)生選每門課程有一定名次每門課程中每一名次只有一個(gè)學(xué)生(學(xué)生,課程)-名次(課程,名次)-學(xué)生候選碼2022/8/2234數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.6 BCNF例8 (是3NF，但不是BCNF的例子)關(guān)系模式STJ（學(xué)生，教師，課程）每一教師只教一門課一個(gè)學(xué)生選定某門課程，就對(duì)應(yīng)一個(gè)固定的教師2022/8/2235數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.6 BCNF例8 (是3NF，但不是BCNF的例子)關(guān)系模式STJ（學(xué)生，教師，名次）每一教師只教一門課一個(gè)學(xué)生選定某門課程，就對(duì)應(yīng)一個(gè)固定的教師教師

16、-課程(學(xué)生,課程)-教師2022/8/2236數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.6 BCNF例8 (是3NF，但不是BCNF的例子)關(guān)系模式STJ（學(xué)生，教師，課程）每一教師只教一門課一個(gè)學(xué)生選定某門課程，就對(duì)應(yīng)一個(gè)固定的教師教師-課程(學(xué)生,課程)-教師候選碼教師,學(xué)生2022/8/2237數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.6 BCNF例8存在的過(guò)度冗余教師學(xué)生課程王紅李明數(shù)據(jù)庫(kù)王紅劉晨數(shù)據(jù)庫(kù)王紅王敏數(shù)據(jù)庫(kù)劉軍張立C語(yǔ)言劉軍劉晨C語(yǔ)言“每個(gè)教師上一門課”隨選課學(xué)生的增加而被重復(fù)存儲(chǔ)2022/8/2238數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.6 BCNF解決方法還是分解分解為兩個(gè)小關(guān)系模式(都是BCN

17、F的)ST(學(xué)生,教師)TJ(教師,課程)或SJ(學(xué)生,課程)TJ(教師,課程)2022/8/2239數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.6 BCNF解決方法還是分解分解為兩個(gè)小關(guān)系模式(都是BCNF的)ST(學(xué)生,教師)TJ(教師,課程)或SJ(學(xué)生,課程)TJ(教師,課程)兩種分解都損失了：“一個(gè)學(xué)生選定某門課程，就對(duì)應(yīng)一個(gè)固定的教師”語(yǔ)義2022/8/2240數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.6 BCNF解決方法還是分解分解為兩個(gè)小關(guān)系模式(都是BCNF的)ST(學(xué)生,教師)TJ(教師,課程)或SJ(學(xué)生,課程)TJ(教師,課程)兩種分解都損失了：“一個(gè)學(xué)生選定某門課程，就對(duì)應(yīng)一個(gè)固定的教師”

18、語(yǔ)義函數(shù)依賴“(學(xué)生,課程)-教師”在分解后沒(méi)有保持！2022/8/2241數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.6 BCNF事實(shí)上，關(guān)系模式即使到了BCNF，還可能存在由于非函數(shù)依賴帶來(lái)的冗余及三類異常。這些數(shù)據(jù)依賴有多值依賴和連接依賴。我們只簡(jiǎn)單要求多值依賴。在多個(gè)實(shí)體間聯(lián)系為1對(duì)多聯(lián)系時(shí)可能出現(xiàn)多值依賴帶來(lái)的問(wèn)題。2022/8/2242數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.7 多值依賴多值依賴定義：設(shè)有關(guān)系模式R(U)，X, Y, Z是U的非空子集。對(duì)于R的任一關(guān)系r，給定一對(duì)(x, z)值，就有一組Y的值與之對(duì)應(yīng)，這組值僅僅決定于x值而與z值無(wú)關(guān)，則稱“Y多值依賴于X”或“X多值決定Y”。記作XY

19、。或記憶為：設(shè)有關(guān)系模式R(U)，X, Y, Z是U的非空子集。對(duì)R(U)的任一關(guān)系r，任意兩元組s和t，如果sX=tX，則交換s和t的Y值所得兩個(gè)新元組必在r中。2022/8/2243數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.7 多值依賴翻譯情況 A B C （姓名 ，東方語(yǔ)言 ，西方語(yǔ)言） 王 紅 日語(yǔ) 法語(yǔ) 王 紅 漢語(yǔ) 英語(yǔ) 王 紅 日語(yǔ) 英語(yǔ) 王 紅 漢語(yǔ) 法語(yǔ)是BCNF , 其中 只有ABC 才是關(guān)鍵字但有冗余, 又有刪除異常例如刪除（王 紅 漢語(yǔ) 法語(yǔ)）2022/8/2244數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.7 多值依賴衣著 （姓名，衣服，褲子）類似，可稱為 完全搭配依賴（課程, 教師, 參

20、考書）類似，看書上2022/8/2245數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.7 多值依賴不是多值依賴的例子：學(xué)生選課表SC（Sno，Cno，G）中一個(gè)Sno（一個(gè)學(xué)生）有一組Cno（選了一組課程）和一組G（有一組成績(jī)），但Cno與G有關(guān)（成績(jī)與課程有關(guān)），所以沒(méi)有SnoCno，以及SnoG。也就是說(shuō)一個(gè)學(xué)生選的一組課程和一組成績(jī)沒(méi)有形成完全搭配。2022/8/2246數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.7 多值依賴平凡的多值依賴：若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ù)

21、依賴是多值依賴的特殊情況：若X Y，則X Y。4、若X Y，X Z；則X YZ，X Z-Y，XY-Z， X YZ。2022/8/2247數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.8 4NF定義6.10 若關(guān)系模式R（U，F(xiàn)）1NF，如果對(duì)于R的每個(gè)非平凡多值依賴X Y（Y不包含于X），X都含有碼，則稱R（U，F(xiàn)）4NF。實(shí)質(zhì)上4NF消除了多值依賴。為什么？2022/8/2248數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.2.9 規(guī)范化小結(jié)1NF：每個(gè)分量是不可分的數(shù)據(jù)項(xiàng)。2NF：非主屬性完全函數(shù)依賴于碼。3NF：非主屬性既不部分依賴于碼也不傳遞依賴于碼。BCNF：所有屬性都不部分依賴于碼也不傳遞依賴于碼。所有決定因素(

22、屬性集)都包含碼。4NF：所有非平凡的多值依賴都是函數(shù)依賴。2022/8/2249數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章本章目錄6.1 問(wèn)題的提出6.2 規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)6.4 模式的分解2022/8/2250數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章函數(shù)依賴公理系統(tǒng)的背景為了求得給定關(guān)系模式的碼，為了從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴，例如已知函數(shù)依賴集F，要問(wèn)XY是否為F所蘊(yùn)含，就需要一套推理規(guī)則，這組推理規(guī)則是1974年首先由Armstrong提出來(lái)的。它是關(guān)系模式分解算法的理論基礎(chǔ)。要求得給定關(guān)系模式的所有候選碼對(duì)于關(guān)系模式的范式級(jí)別判定具有決定作用：范式級(jí)別的判定需要知道關(guān)系模式的所有候選碼；有的范式

23、級(jí)別還需確定主屬性和非主屬性，也需要知道所有候選碼。2022/8/2251數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊(yùn)含：定義6.11對(duì)于關(guān)系模式R，其任何一個(gè)關(guān)系r，若函數(shù)依賴XY都成立（即r中任意兩元組s，t，若tX=sX，則tY=sY），則稱函數(shù)依賴集F邏輯蘊(yùn)含XY。2022/8/2252數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章Armstrong 公理系統(tǒng)A1 自反律 若Y X U，則XY為F所蘊(yùn)含(給出平凡的函數(shù)依賴)。A2 增廣律 若XY為F所蘊(yùn)含，且Z U，則XZYZ為F所蘊(yùn)含。A3 傳遞律 如XY及YZ為F 所蘊(yùn)含，則XZ為F所蘊(yùn)含。證明見定理6.12022/8/2253數(shù)據(jù)庫(kù)系統(tǒng)概論- 第

24、6章Armstrong 公理系統(tǒng)Armstrong公理的推論：合并規(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成立的充分必要條件是XAi (i=1, 2, k)成立。2022/8/2254數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章Armstrong 公理系統(tǒng)定義6.12 F的閉包：函數(shù)集閉包 (找親戚的親戚)在關(guān)系模式R中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫做F的閉包，記作F + 。Armstrong公理是有效的，完備的：有效性：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來(lái)的每個(gè)函數(shù)

25、依賴一定在F +中 。有效性的證明書上定理6.1“Armstrong推理規(guī)則是正確的”可直接得證。完備性： F + 中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來(lái)。 經(jīng)典證明2022/8/2255數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章Armstrong 公理系統(tǒng)定義6.13 (屬性集閉包) XF +的定義 設(shè)F是屬性集U上的一組函數(shù)依賴集，X U，XF + A|XA能由F根據(jù)Armstrong公理導(dǎo)出。引理6.2 設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y U，XY能由F根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y XF +2022/8/2256數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章算法6.1 求

26、XF +的方法 - 非常重要計(jì)算 XF+，滾雪球算法result := X; /從X 開始while (changes to result ) dofor each V W in F dobeginif V result then result := result W endreturn result2022/8/2257數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章例例1 關(guān)系模式R,U=A,B,C,D,E, F= ABC, BD, CE, ECB, ACB, 求(AC)F+0. 初始化 令resultAC1. 第一次循環(huán) 計(jì)算result =ACEB=ABCE2. 第二次循環(huán) 計(jì)算result = ABCDE即

27、得結(jié)果。定義6.13，引理6.2和算法6.1非常重要，可用于求碼。如KF += U, 而KF + != U，即求得K為一候選碼。2022/8/2258數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章求碼方法要點(diǎn)(自己的總結(jié))找出不出現(xiàn)在非平凡函數(shù)依賴右部的屬性組X，它們一定包含于所有候選碼。求XF+，判斷U？成立結(jié)束，否則轉(zhuǎn)3。(自底向上)擴(kuò)展X的X，求XF+，判斷U？直到所有情況找完為止。2022/8/2259數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章例應(yīng)用舉例，對(duì)書上P184例1，求所有候選碼要點(diǎn)：不出現(xiàn)在任何函數(shù)依賴右部的只有A；求AF+A；擴(kuò)展AB，ABF+U；AC，ACF+U；AD，ADF+ ！U；（需再擴(kuò)展）AE， AEF

28、+ ！U；（需再擴(kuò)展）再擴(kuò)展ADE，ADEF+ ！U2022/8/2260數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.3 數(shù)據(jù)依賴的公理系統(tǒng)要證明完備性首先解決如何判定一個(gè)函數(shù)依賴是否屬于由F根據(jù)Armstrong公理推導(dǎo)出來(lái)的函數(shù)依賴的集合。如果能求出這個(gè)集合就很容易判斷，但是求這樣的集合是一個(gè)NP完全問(wèn)題。所以該判定轉(zhuǎn)換為：任一個(gè)函數(shù)依賴X Y是F + 中成員的充分必要條件是：Y XF + 。證明完備性轉(zhuǎn)換為證明它的逆否命題為真。即若函數(shù)依賴不能由F從Armstrong公理導(dǎo)出，那么它必然不為F所蘊(yùn)含。證明分3步（略）證明用到了構(gòu)造(特殊的二維表)、反證，十分巧妙。2022/8/2261數(shù)據(jù)庫(kù)系統(tǒng)概論-

29、第6章6.3 數(shù)據(jù)依賴的公理系統(tǒng)完備性證明要證原命題，只需證明其逆否命題：若函數(shù)依賴XY不能由F出發(fā)從Armstrong公理導(dǎo)出，則它本身不為F所蘊(yùn)含。（1）若VW成立，且V XF + ，則W XF + 。V XF +，則由引理6.2，有XV。由XV，VW，有XW。再由引理6.2，有W XF + 。2022/8/2262數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.3 數(shù)據(jù)依賴的公理系統(tǒng)（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ù)依賴V W在r上不成立所致。觀察r，V XF + ，而W XF + 。與

30、（1）矛盾。2022/8/2263數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.3 數(shù)據(jù)依賴的公理系統(tǒng)（3）若XY不能由Armstrong公理導(dǎo)出則Y不是XF + 的子集，必有Y Y，且Y UXF +。（推） XY本身不為F所蘊(yùn)含。（觀察r）得證。2022/8/2264數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.3 數(shù)據(jù)依賴的公理系統(tǒng)定義6.14 函數(shù)依賴集等價(jià)：如果G +=F + ，就說(shuō)函數(shù)依賴集F覆蓋G（F是G的覆蓋或G是F的覆蓋），或F與G等價(jià)。有相應(yīng)的判定算法。引理6.3的充分性證明的過(guò)程實(shí)際上給出了判斷兩函數(shù)依賴集等價(jià)的方法。引理6.3 F+ =G+的充分必要條件是 F G+ ，和G F+ 。2022/8/2265數(shù)

31、據(jù)庫(kù)系統(tǒng)概論- 第6章6.3 數(shù)據(jù)依賴的公理系統(tǒng)定義6.15 最小依賴集右部唯一無(wú)多余函數(shù)依賴無(wú)部分函數(shù)依賴定理6.3 每一個(gè)函數(shù)依賴集都等價(jià)于一個(gè)極小函數(shù)依賴集Fm (Fm一定存在，可能不唯一)。定理6.3的證明過(guò)程給出了檢驗(yàn)(或構(gòu)造)Fm的方法。2022/8/2266數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章求解極小函數(shù)依賴集的過(guò)程用分解規(guī)則將F中每一函數(shù)依賴分解為若干個(gè)右部唯一的函數(shù)依賴，新函數(shù)依賴集仍命名為F。判斷當(dāng)前F中有沒(méi)有多余的函數(shù)依賴。注意，檢查XA，要在G集(其中G=F-XA)下考察XA是否被蘊(yùn)含(G集下計(jì)算XG+，看A是否包含在其中)。處理后的函數(shù)依賴集不妨仍命名為F。判斷當(dāng)前F中每一函數(shù)依

32、賴左部有沒(méi)有多余的屬性。注意，檢查ABY中B是否多余時(shí)，令G=F-ABYAY,需要考察AY是否為F所蘊(yùn)含(F集下計(jì)算XF+，看Y是否包含在其中)。最后得到F的函數(shù)依賴集Fm。 2022/8/2267數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.3 數(shù)據(jù)依賴的公理系統(tǒng)例子：設(shè)FABC，AB，求Fm。FmBC，AB ?對(duì)不對(duì)？為什么？2022/8/2268數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.3 數(shù)據(jù)依賴的公理系統(tǒng)上面的F與Fm根本不等價(jià)。FmAC，AB2022/8/2269數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章本章目錄6.1 問(wèn)題的提出6.2 規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)6.4 模式的分解2022/8/2270數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6

33、章6.4 模式的分解要求了解前面我們?yōu)榱私鉀Q設(shè)計(jì)得不好(范式級(jí)別不夠高)的數(shù)據(jù)庫(kù)模式帶來(lái)的問(wèn)題，我們采用了大關(guān)系分解為小關(guān)系的方法來(lái)提高范式級(jí)別。本節(jié)給出分解的理論指導(dǎo)。2022/8/2271數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.4.1 模式分解的三個(gè)定義具有無(wú)損連接性。分解后的(幾個(gè))小模式可自然連接恢復(fù)為原來(lái)的模式。 保持函數(shù)依賴 分解前后函數(shù)依賴集等價(jià)既保持無(wú)損連接，又保持函數(shù)依賴。(理想情況)2022/8/2272數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.4.2 分解的無(wú)損連接性和保持函數(shù)依賴性m(r)R1(r) R2(r) Rk(r) 定義5.18 R1，R2 Rk是R上的一個(gè)分解，若對(duì)于R的任一關(guān)系r，均

34、有r m(r)成立，則具有無(wú)損連接性。此定義無(wú)法用于判斷，無(wú)損連接性只能通過(guò)算法6.2或定理6.5來(lái)判斷。2022/8/2273數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.4.2 分解的無(wú)損連接性和保持函數(shù)依賴性算法6.2 要求會(huì)做。(通過(guò)例子來(lái)學(xué)習(xí))例1 R(S，A，I，P) 分解為R1(S，A)，R2(S，I，P)。F SA, SIPS A I P-a1 a2 b13 b14a1 b22 a3 a4由于有SA，使第二行第二列變成a2。S A I P-a1 a2 b13 b14a1 a2 a3 a42022/8/2274數(shù)據(jù)庫(kù)系統(tǒng)概論- 第6章6.4.2 分解的無(wú)損連接性和保持函數(shù)依賴性補(bǔ)充例 R(A，B，C，D，E)，分解R1=AD,R2=AB, R3=BE, R4=CDE, R5=AE F=AC, BC, CD, DEC, CEAA 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)CEA(