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

1、關(guān)系數(shù)據(jù)庫部分理論第1頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一 6.1 問題的提出2插入異常BORROWER的主KEY：NO，TNO關(guān)鍵字值非空。（新調(diào)入未借書的人）NO NAME ADDR TNO TLTLE AU DATE001 張 平 A1 T1 DB AU1 D1 001 張 平 A1 T2 OS AU2 D2 001 張 平 A1 T3 MA AU3 D3 001 張 平 A1 T4 DB1 AU4 D3 008 李少林 A2 T3 MA AU3 D4 008 李少林 A2 T7 MA2 AU7 D7 數(shù)據(jù)庫模式一BORROWER（NO,NAME，ADDR，TNO,

2、TITLE，AU,DATE)1、有冗余：對于借書人，每借一次書他本人信息和書的信息都要存放一次。存在數(shù)據(jù)冗余，這樣當(dāng)修改某些數(shù)據(jù)項(xiàng)（如地址時(shí)，則每一個(gè)元組中的地址都要改變。增加更新代價(jià)，更嚴(yán)重的是潛在的不一致性。)存在的問題：3刪除異常如把借的書全部還掉，則就把這個(gè)人連同他的地址都刪掉了,丟失了借書人的基本信息。第2頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一數(shù)據(jù)庫模式二 BORROWER（NO,NAME，ADDR) BOOKS(TNO,TITLE,AU) LOAN(NO，TNO，DATE）由于將借書人、書、及借書分離成不同的關(guān)系，使數(shù)據(jù)冗余大大減少，且不存在插入異常和刪除異常。

3、存在另一問題： 如使用上述模式時(shí)，為找到借MA的借書人名，則需進(jìn)行三個(gè)關(guān)系的連接操作，代價(jià)高。 如何找到一個(gè)好的數(shù)據(jù)庫模式，這正是數(shù)據(jù)庫設(shè)計(jì)理論所研究的問題。主要包括三個(gè)方面的內(nèi)容：數(shù)據(jù)依賴、范式、數(shù)據(jù)庫模式設(shè)計(jì)方法，其中數(shù)據(jù)依賴起核心作用。第3頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一原因： 不僅客觀事物彼此互相聯(lián)系、互相制約?？陀^事物本身的各個(gè)屬性之間也互相聯(lián)系、互相依賴。 如一個(gè)人的住址依賴于他的姓名。屬性之間的這種依賴關(guān)系表達(dá)了一定的語義信息。 在設(shè)計(jì)數(shù)據(jù)庫時(shí)，對于事物之間的聯(lián)系和事物屬性之間的聯(lián)系，都要考慮。 例上例中，借書人的屬性都依賴于NO，但與書,借書的屬性沒有

4、聯(lián)系。把本來無關(guān)的借書人信息和書信息，借書信息拼在一起，就出現(xiàn)了剛才的數(shù)據(jù)冗余和異?，F(xiàn)象。 所以我們在設(shè)計(jì)關(guān)系數(shù)據(jù)庫模式時(shí)，必須從語義上摸清這些數(shù)據(jù)依賴，合理構(gòu)成數(shù)據(jù)庫模式。 數(shù)據(jù)依賴是通一個(gè)關(guān)系中屬性間值的相等與否體現(xiàn)出來的數(shù)據(jù)間的相互聯(lián)系。它是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象，是數(shù)據(jù)內(nèi)在性質(zhì)，是語義的體現(xiàn)。 一般有三種依賴：函數(shù)依賴（FD）、多值依賴（MVD）、連接依賴。 第4頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一 設(shè)R（U）是屬性集U上的關(guān)系模式。X和Y是U的子集。若對于R（U）的任意一個(gè)可能的關(guān)系r，r中不可能存在兩個(gè)元組在X上的屬性值相等，而Y上的屬性值不等，則稱X函

5、數(shù)決定Y或Y函數(shù)依賴于X，記為一、定義6.2 函數(shù)依賴?yán)斫猓喝绻鸕的兩個(gè)元組在屬性X ： 上一致，（即兩個(gè)元組在這些屬性相對應(yīng)的各個(gè)分量具有相同的值），則它們在另一個(gè)屬性B上也應(yīng)該一致，則記為 。如一組屬性函數(shù)決定多個(gè)屬性。如 則可以把這一組依賴關(guān)系簡記為注：函數(shù)依賴不是指關(guān)系模式R的某個(gè)或某些關(guān)系滿足的約束條件，而是指R的一切關(guān)系均要滿足的約束條件。只要有一個(gè)具體關(guān)系R不滿足定義中的條件，就破壞了函數(shù)依賴。第5頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一設(shè)R（U）是屬性集U上的關(guān)系模式。X和Y是U的子集。R是R的任一具體關(guān)系，U,V是r中的任意兩個(gè)元組。如果由UX=VX能導(dǎo)致U

6、Y=VY,則稱X函數(shù)決定Y或Y函數(shù)依賴于X，記為 ，其中UX表示元組U在X上的屬性值。VX，UY，VY有類似的意義。設(shè)R（U）是屬性集U上的關(guān)系模式。X和Y是U的子集。如果R的所有關(guān)系r都存在著：對于X的每一個(gè)具體值，都有Y唯一的具體值與之對應(yīng)，則稱X函數(shù)決定Y，或Y函數(shù)依賴于X。這兩個(gè)定義等價(jià)。第6頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一可斷言如下三個(gè)函數(shù)依賴：即如兩個(gè)元組在title，year分量上具有相同的值，則它們在length，filmType 和studioName上必然也相同。title，year starName TitleYearLengthFilmType

7、StudioNameStarNameStar Wars1977124ColorFoxCarrie FisherStar Wars1977124ColorFoxMark HamillStar Wars1997124ColorFoxHarrison FordStart Wars2000125ColorMriCarrie第7頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一設(shè)有屬性集X、Y，及關(guān)系模式R。如果X、Y之間是“1-1”關(guān)系，則存在函數(shù)依賴： 且 如學(xué)號，姓名（唯一）。如果X、Y之間是“m-1”關(guān)系，則存在函數(shù)依賴： 如學(xué)號（唯 一），宿舍。(一個(gè)宿舍信多個(gè)學(xué)生）如果X、Y之間是“

8、m-m”關(guān)系，則X、Y之間不存在函數(shù)依賴。 如借閱關(guān)系：學(xué)號，書號。也即設(shè)計(jì)者確定函數(shù)依賴時(shí)，可以從分析屬性間的關(guān)系著手。 二、函數(shù)依賴與屬性關(guān)系三、幾種不同的函數(shù)依賴1、非平凡的函數(shù)依賴 但 則稱 是非平凡的函數(shù)依賴。若不特別聲明，總是討論非平凡的函數(shù)依賴。 但 則稱 是平凡的函數(shù)依賴。若 則X叫做決定因素。若 ， 則記作 第8頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一2、完全函數(shù)依賴在R（U）中，如果 ，并且對于X的任何一個(gè)真子集 ，都有 Y ，則稱Y對X完全函數(shù)依賴：記作 。3、部分函數(shù)依賴若 ，但Y不完全函數(shù)依賴于X，則稱Y對X部分函數(shù)依賴，存在：書號 出版社，出版社

9、地址，出版社 書號故有地址對書號的傳遞函數(shù)依賴。4、傳遞函數(shù)依賴在R（U）中，如果 ， ，Y X ， ，則稱Z對X傳遞函數(shù)依賴。如Books（書號，出版社名，出版社地址）一種書對應(yīng)唯一書號，并只能為某一個(gè)出版社出版，一個(gè) 出版社一般只有一個(gè)名稱和唯一地址。一個(gè)出版社可出版多種書。Title,year lengthTitle length第9頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一定義： 對于任給的關(guān)系R，U為其所含全部的屬性集合 X 為U的子集。若有完全函數(shù)依賴 則 四、關(guān)鍵字（碼）作為候選關(guān)鍵字的屬性集X唯一標(biāo)識(shí)R中的元組，但該屬性 集的任何真子集不能唯一標(biāo)識(shí)R中的元組。

10、一個(gè)關(guān)系中可能存在多個(gè)候選關(guān)鍵字。選其一作為主關(guān)鍵字。候選關(guān)鍵字中所含的屬性稱為主屬性，不包含在任何候選關(guān)鍵字中的屬性稱為非主屬性。如 為 的關(guān)鍵字。 它們函數(shù)決定所有其它屬性 均不是鍵碼。如STUDENT(學(xué)號，姓名，性別，班級)，如姓名不重名，則學(xué)號，姓名均為鍵碼最簡單的情況，單個(gè)屬性是碼。最極端的情況，整個(gè)屬性組是碼，稱為全碼。 如關(guān)系模式S（SNO，SDEPT，SAGE） SNO是碼 關(guān)系模式SC（SNO，CNO，G） （SNO，CNO）是碼 關(guān)系模式R（P，W，A），P：演奏者，W：作品，A：聽眾。碼為（P，W，A） X為R的一個(gè)候選關(guān)鍵字。第10頁，共67頁，2022年，5月20日

11、，18點(diǎn)37分，星期一閉包：在關(guān)系模式R中F所邏輯蘊(yùn)涵的函數(shù)依賴的全體叫做F的閉包。記為 。一般情況下，如 則稱F是函數(shù)依賴的完備集。對于給定的一組函數(shù)依賴，我們?nèi)绾闻袛嗔硗庖恍┖瘮?shù)依賴是否成立？如對于關(guān)系模式R有 是否成立？定義：設(shè)F是關(guān)系模式R的一個(gè)函數(shù)依賴集,X、Y是R的屬性子集，如果從F中的函數(shù)依賴能夠推出X Y，則稱F邏輯蘊(yùn)涵 或稱 是F的邏輯蘊(yùn)涵。五、函數(shù)依賴的邏輯蘊(yùn)涵例：若有關(guān)系模式R（X,Y,Z),它的函數(shù)依賴集F=則F的閉包為第11頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一假設(shè)我們已知某關(guān)系所滿足的函數(shù)依賴集，在不知道關(guān)系的具體元組的情況下，通?？赏茢喑鲈撽P(guān)系

12、必然滿足的其他某些函數(shù)依賴。為此，要求有一套推理規(guī)則。Armstrong公理（推理規(guī)則中最主要、最基本的作為公理）Armstrong公理系統(tǒng)：設(shè)U為屬性集總體， F是U上的一組函數(shù)依賴集，于是有關(guān)系模式R。對R來說有以下的推理規(guī)則： A1 自反律：若 為F所蘊(yùn)涵。 A2 增廣律：若 為F所蘊(yùn)涵，且 ，則 為F所蘊(yùn)涵。 A3 傳遞律：若 為F所蘊(yùn)涵，則 為F所蘊(yùn)涵。6.3 函數(shù)依賴公理一、Armstrong公理注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于F。第12頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一定理6.1 Armstrong推理規(guī)則是正確的。

13、證明：設(shè)u、v是r的任意兩個(gè)元組，r是R的任一關(guān)系。若uX=vX,則在u和v中的X的任何子集也必相符。由條件Y是X的子集.必有uY=vY.根據(jù)函數(shù)依賴定義可知：:設(shè)u、v、r含義同上。若uXZ=vXZ，則uXuZ=vXvZ，也即uX=vX，uZ=vZ由條件 ，得如uX=vX則uY=vY uY=vY，uZ=vZ ，即 uYuZ= vYvZ ，也即uYZ= vYZ根據(jù)函數(shù)定義可知： 。： 設(shè)u、v、r含義同上，設(shè)uX= vX uY= vY又 uZ= vZ 第13頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一 合并規(guī)則：若 則 。 分解規(guī)則：若 ，則 ， 。 偽傳遞規(guī)則：若 ，則 。證明

14、： 則 （增廣性） （增廣性） （傳遞性） （反射性） （傳遞性） 同理 （增廣性） 又 （傳遞性） 從合并和分解規(guī)則可得出一個(gè)重要結(jié)論：引理6.1 如果 是關(guān)系模式R的屬性，則 成立的充要條件是 均成立。二、公理的推論從Armstrong公理推理規(guī)則可得如下推論：第14頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一Armstrong公理是有效的、完備的。有效性指：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個(gè)函數(shù)依賴一定在 中。正確性指：只要使F中的函數(shù)依賴為真，則用公理推出的函數(shù)依賴也為真。完備性指： 中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來。

15、即 中的所有函數(shù)依賴都能用Armstrong公理推導(dǎo)出來。幻燈片 18公理的正確性保證推出的所有函數(shù)依賴都為真，公理的完備性保證可以推出所有的函數(shù)依賴。第15頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一定義： 設(shè)F為屬性集U上的一組函數(shù)依賴， ，F(xiàn)是U上一個(gè)函數(shù)依賴集，則稱所有用公理從F推出的函數(shù)依賴 中Ai的屬性集合為X的屬性閉包 稱為屬性集X關(guān)于函數(shù)依賴集F的閉包。計(jì)算 的一個(gè)目的就是要確定某一函數(shù)依賴 是否由F邏輯蘊(yùn)涵。即它是否成立，而通過計(jì)算 我們就能判斷這一結(jié)論的真假。 等價(jià)所有由F邏輯蘊(yùn)涵的 屬性A的集合。三、屬性閉包引理6.2 設(shè)F為屬性集U上的一組函數(shù)依賴， ，

16、能由F根據(jù)Armstrong公理導(dǎo)出的充分必要條件是 。第16頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一算法6.1：求屬性集X關(guān)于U上的函數(shù)依賴集F的屬性閉包 。輸入：關(guān)系模式R的全部屬性集U及上的函數(shù)依賴F，U的子集X輸出： 。方法：計(jì)算 。 1、 2、 求B，B=A|( V)( W)(V W F ); 3、 4、 判斷 嗎？ 5、 若相等或 ，則 就是 ，算法終止。 6、 若否，則i=i+1,返回第2步。于是，判定X Y是否能由F根據(jù)Armstrong公理推出的問題，就轉(zhuǎn)化為求出 停止計(jì)算的幾種判別方法： 當(dāng)發(fā)現(xiàn) 包含了所有屬性時(shí)。 在F中的函數(shù)依賴的右邊屬性中再也找不到

17、中未出現(xiàn)過的屬性。 在F中未用過的函數(shù)依賴的左邊屬性已沒有 的子集。第17頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一 =ABCDE （DE）例：一具有屬性A、B、C、D、E、F的關(guān)系，假設(shè)該關(guān)系有如下函數(shù)依賴：AB C，BC AD，D E和CFB。左邊不包含在中。 求解：設(shè)X=AB，則有 =AB C =ABC （AB C） =ABCAD=ABCD （BCAD）在F中未用過的函數(shù)依賴的左邊屬性已沒有Xi的子集。(或計(jì)算X(4)-ABCDE =（ABCDE）例：檢驗(yàn)ABD是否蘊(yùn)涵于F中。DA呢？解：計(jì)算 及 。 =ABCDE ABD蘊(yùn)涵于F中。也即ABD成立。 =DE DA不蘊(yùn)涵于

18、F中。也即DA不成立。第18頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一證明完備性的逆否命題，即如函數(shù)依賴X Y不能由F從Armstrong公理導(dǎo)出，那么它必然不為F所蘊(yùn)涵，證明分三步。定理6.2 Armstrong公理系統(tǒng)是有效的、完備的。若V W成立，且 ，則證 因?yàn)?，所以有X V成立；于是X W成立所以 。2. 構(gòu)造一張二維表r,它由下列兩個(gè)元組組成,可以證明r必是R的一個(gè)關(guān)系，即F中的全部函數(shù)依賴在r上成立。 1111 1111 1111 0000如r不是R的關(guān)系,則必由于F中有函數(shù)依賴V W在r上不成立所致。由r的構(gòu)成可知，V必定是 的子集，而W不是 的子集，可是由第

19、（1）步 ，矛盾。所以r必是R的一個(gè)關(guān)系。(即證明r滿足F)若X Y不能由F從Armstrong公理導(dǎo)出,則Y不是 的子集,而因此在關(guān)系r的兩個(gè)元組中X的屬性值一致，而Y的屬性值不一致,則X Y在r中不成立,即X Y必不為R所蘊(yùn)含。Armstrong公理的有效性和完備性說明了“導(dǎo)出”和“蘊(yùn)含”是兩個(gè)完全等價(jià)的概念.于是 也可以說成是由F出發(fā)借助Armstrong公理導(dǎo)出的函數(shù)依賴的集合。第19頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一引理6.3 的充要條件是 和 。證 必要性顯然，只證充分性。若 ，則 。任取 ，則有 。 所以 ，即 。3. 同理可證 ,所以從蘊(yùn)含（或?qū)С觯┑母?/p>

20、念出發(fā)，又引出了兩個(gè)函數(shù)依賴集等價(jià)和最小依賴集的概念定義6.14 設(shè)F和G是兩個(gè)依賴集，如果 ,就說函數(shù)依賴集F覆蓋G(F是G的覆蓋，或G是F的覆蓋),或F與G等價(jià)。 檢查F中的每個(gè)函數(shù)依賴是否屬于 。F和G是否等價(jià)：如對于 ，看是否 。是則 檢查所有其它依賴，若全都滿足，則 。 對G中每一個(gè)依賴也作同樣處理。如 且 。則F和G等價(jià)。幻燈片 50第20頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一例： 1.檢查F中的每個(gè)函數(shù)依賴是否屬于 取 ,求 =ABCD, 則同理可得出 2.檢查G中的每個(gè)函數(shù)依賴是否屬于F+取 同理可得出所以F與G等價(jià)第21頁，共67頁，2022年，5月20日

21、，18點(diǎn)37分，星期一引理：每一個(gè)函數(shù)依賴集F都可以由一個(gè)右部只有單個(gè)屬性的函數(shù)依賴集G新覆蓋。(G左部與F相同)證明：設(shè)F中的函數(shù)依賴由兩部分組成：右邊是1個(gè)以上的屬性的函數(shù)依賴。 設(shè)XY為其中任一個(gè)，Y=A1Ak,Ai為單屬性。右邊是單屬性的函數(shù)依賴。設(shè)VW為其中任一個(gè)。 令G由所有的VW及X Ai(i=1k)組成。對G中任一X Ai,，由于F中有XY 。根據(jù)分解規(guī)則有X Ai(i=1.k),而 VW，在F和G中都有。所以而對于F中任一XY，在G中有XAi,根據(jù)合成規(guī)則有XY。第22頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一函數(shù)依賴的最小集。定義6.15 如果函數(shù)依賴集F滿

22、足下列條件,則稱為F為一個(gè)極小 函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。F中的每個(gè)依賴的右部都是單個(gè)屬性。依賴右部為單屬性。對于F的任一函數(shù)依賴XA來說，F(xiàn)與 都不等價(jià)， 保證F中不存在多余的依賴。對于F的任一函數(shù)依賴XA來說，F(xiàn)與 都不 等價(jià)，其中Z為X的任一真子集，保證每個(gè)依賴的左邊沒有多余的屬性。例2 關(guān)系模式S,其中U=SNO,SDEPT,MN,CNAME,G F=SNO SDEPT,SDEPT MN,(SNO,CNAME) GF= SNO SDEPT,SDEPT MN,(SNO,CNAME) G,SNO MN,(SNO,SDEPT) SDEPT根據(jù)定義可以驗(yàn)證F是最小覆蓋,而F不是。

23、 定理5.3：每個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)最小函數(shù)依賴集 。此 稱為F的最 小依賴集。第23頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一定理6.3：每個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)最小函數(shù)依賴集 。 此 稱為F的最小依賴集。證 這是一個(gè)構(gòu)造性的證明，分三步對F進(jìn)行“極小化處理” ， 找出F的一個(gè)最小依賴集。逐一查找F中各函數(shù)依賴FDi：X Y，若Y= ,則用 來取代X Y。(Y A1A2A3 Y A1)逐一查找F中各函數(shù)依賴FDi：X A，令 ，若 則 從F中去掉此函數(shù)依賴。逐一取出F中各函數(shù)依賴FDi：X A，設(shè)X= ，逐一考查Bi(I=1,2,m)，若 ，則以X-Bi取代X。最后

24、剩下的F就一定是極小依賴集，并且與原來的F等價(jià)。因?yàn)閷的每一次“改造”都保證了改造前后的兩個(gè)函數(shù)依賴集等價(jià)。應(yīng)當(dāng)指出，F(xiàn)的最小依賴集 不一定是唯一的，它與對各函數(shù)依賴Fdi及X A中X各屬性的處置順序有關(guān)。例3 F=A B，B A，B C，A C，C A Fm1=A B, B C, C A Fm2=A B，B A，A C，C A Fm1與Fm2均為最小依賴集。第24頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一例： 求 。解：按最小依賴集的定義分別考慮三個(gè)條件：用分解規(guī)則將所有依賴變?yōu)橛疫吺菃螌傩缘囊蕾嚒?去掉F中的多余依賴，具體做法：從第一個(gè)依賴開始，從F中去掉它（假設(shè)為 XY

25、）然后在剩下的依賴中求 ，看是否包含Y，若是則去掉XY：否則 不能去掉，依次做下去。 A B =AC 不能去掉 BA =CAB 去掉 BC =B 不能去掉 AC =ABC 去掉 C A =C 不能去掉 BE D =BEAC 不能去掉 判斷XYA中X是否成為多余屬性，只要在F中求 若包含A，則Y是多余屬性。否則Y不是多余屬性。依次判斷其它屬性即可消除各依賴左邊的多余屬性。去掉各依賴左邊多余的屬性應(yīng)當(dāng)指出，F(xiàn)的最小依賴集 不一定是唯一的，它與對各函數(shù)依賴Fdi及X A中X各屬性的處置順序有關(guān)。B+=BCA 不含D，E不多余E+=E，不含D，B不多余第25頁，共67頁，2022年，5月20日，18點(diǎn)

26、37分，星期一注 F的最小依賴集不一定唯一。它和我們對各函數(shù)依賴的處置順序有關(guān)。兩個(gè)關(guān)系模式R1 ，R2，如果F 與G等價(jià)，那么R1的關(guān)系一定是R2的關(guān)系。反過來， R2的關(guān)系也一定是R1的關(guān)系。所以在R1 中用與F等價(jià)的依賴集G來取代F是允許的。B+=BCA 不含D，E不多余E+=E，不含D，B不多余第26頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一6.4 關(guān)系模式的規(guī)范化一、范式規(guī)范化：一個(gè)低一級范式的關(guān)系模式，通過模式分解可轉(zhuǎn)換為若干個(gè)高一級范式的關(guān)系模式的集合。這種過程就叫規(guī)范化。是以結(jié)構(gòu)更單純，更規(guī)則的關(guān)系逐步取代原有關(guān)系的過程。關(guān)系數(shù)據(jù)庫中的關(guān)系是要滿足一定要求的，滿

27、足不同程度要求的為不同范式，滿足最低要求的叫第一范式，簡稱1NF，在1NF中滿足進(jìn)一步一些要求的2NF，。所謂“第幾范式”，是表示關(guān)系的某一種級別。即符合某一種級別的關(guān)系模式的集合，R為第幾范式就可以寫成 。5NF 4NF BCNF 3NF 2NF 1NF1NF：每一個(gè)分量必須是不可分的數(shù)據(jù)項(xiàng)。這是最基本的規(guī)范化。5NF4NFBCNF3NF2NF1NF各種范式之間的關(guān)系第27頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一 二、第一范式（1NF） 定義： 如果一個(gè)關(guān)系模式R的每個(gè)具體關(guān)系r的每個(gè)屬性值都是不可再分的最小數(shù)據(jù)單位，則R為第一范式。簡稱1NF，r為1NF關(guān)系。 注：第一范

28、式不含重復(fù)組，不存在嵌套結(jié)構(gòu)。不滿足1NF的關(guān)系為非規(guī)范關(guān)系。部門名部門號經(jīng)理DN1D1M1AM1DN2D2M2AM2正經(jīng)理 副經(jīng)理借書人 所借書名 日期 T1 D1張平 T2 D2 T3 D3 T2 D2 T4 D4 李問部門名部門號正經(jīng)理副經(jīng)理DN1D1M1AM1DN2D2M2AM2借書人所借書名日期張平T1D1張平T2D2.第28頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一三、第二范式（2NF） 定義6.6 任給關(guān)系R，若R為INF，且每一個(gè)非主屬性都完全函數(shù)依賴于碼，則R為2NF。關(guān)系模式 SLC(SNO,SDEPT,SLOC,CNO,G) 碼: (SNO,CNO) (S

29、NO,CNO)F G SNO SDEPT, (SNO,CNO)P SDEPT SNO SLOC, (SNO,CNO) P SLOC SDEPT SLOC (每個(gè)系的學(xué)生只住一個(gè)地方)函數(shù)依賴:SNO SDEPTCNO SLOCG 非主屬性: SDEPT,SLOC 部分函數(shù)依賴于碼。所以 SLC為1NF在SLC中，仍存在插入、刪除異常，修改復(fù)雜等問題。解決辦法是用投影分解把關(guān)系SLC分解為兩個(gè)關(guān)系模式： SC（SNO，CNO，G） SL（SNO，SDEPT，SLOC） 非主屬性對碼都是完全函數(shù)依賴了 第29頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一一個(gè)關(guān)系模式R不屬于2NF,會(huì)產(chǎn)

30、生以下幾個(gè)問題1.插入異常 若新來一個(gè)學(xué)生,該學(xué)生還未選課,即無CNO,這樣的元組就不能插入SLC中。則該學(xué)生的SNO，SDEPT，SLOC信息無法插入。2 刪除異常 假定某個(gè)學(xué)生只選一門課，如S4就選了一門課C3。現(xiàn)在這門課他也不選了，那么C3這個(gè)數(shù)據(jù)項(xiàng)就要?jiǎng)h除。而C3是主屬性，刪除了C3，整個(gè)元組就必須跟著刪除，使得S4的其他信息也被刪除了，造成刪除異常，不應(yīng)刪的信息也被刪除了。3 修改復(fù)雜。如某個(gè)學(xué)生從數(shù)學(xué)系轉(zhuǎn)到計(jì)算機(jī)系，不僅要修改SDEPT分量，還必須修改SLOC分量。另外，如果這個(gè)學(xué)生選修了多門課，SDEPT，SLOC重復(fù)存儲(chǔ)多次，不僅存儲(chǔ)冗余度大，而且必須修個(gè)多個(gè)元組中全部SDEP

31、T，SLOC信息，選成修改的復(fù)雜化。原因：存在非主屬性對碼的不完全函數(shù)依賴。SDEPT，SLOC對碼不是完全函數(shù)依賴。第30頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一四、第三范式 定義：如果關(guān)系模式R滿足為2NF，且其每一個(gè)非主屬性都不 傳遞函數(shù)依賴于任何碼（候選關(guān)鍵字）。則R為第三范式。 一個(gè)關(guān)系模式R若不是3NF，就會(huì)產(chǎn)生與非2NF相類似的問題。SC（SNO，CNO，G）SL（SNO，SDEPT，SLOC） SNOCNOGSNOSDEPTSLOCSC中的函數(shù)依賴SL中的函數(shù)依賴SC沒有傳遞函數(shù)依賴 SL中存在傳遞函數(shù)依賴SNO SDEPT，（SDEPT SNO），SDEPT

32、 SLOC可得SNO SLOC為傳遞函數(shù)依賴。所以 ， SL為2NF 一般來說，3NF的關(guān)系大多數(shù)都能解決插入和刪除操作異常的問題，數(shù)據(jù)冗余也能得到有效的控制。解決辦法是將SL分解為： SD（SNO，SDEPT） 分解后不再存在傳遞依賴 DL（SDEPT，SLOC）第31頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一SL（SNO，SDEPT，SLOC）存在問題：1.數(shù)據(jù)冗余如果一個(gè)系有500個(gè)學(xué)生，則地址就要重復(fù)500次。2。插入異常如果成立了一個(gè)新系，分配了在5號樓，而該系還未開始招生，則不能插入SDEPT，SLOC。第32頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期

33、一五、BCNF定義：任給關(guān)系R，X、Y為其屬性集。F為其函數(shù)依賴集，且F中所有函賴XY（Y不屬于X）中的X必包含碼（候選關(guān)鍵字），則R為BCNF。即R中每一函數(shù)依賴的決定因素都包含一候選KEY。由BCNF的定義可以得到結(jié)論，一個(gè)滿足BCNF的關(guān)系模式有： 所有非主屬性對每一個(gè)碼都是完全函數(shù)依賴。 所有的主屬性對每一個(gè)不包含它的碼，也是完全函數(shù)依賴。 沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。由于 ，按定義排除了任何屬性對碼的傳遞依賴與部分依賴，所以 。但是若 ，則R未必屬于BCNF。如對于關(guān)系模式S（SNO，SNAME，SDEPT，SAGE） 碼：SNO，SNAME兩個(gè)。SDEPT，SAG

34、E不存在對碼的部分依賴與傳遞依賴，所以 。同時(shí)S中除SNO，SNAME外沒有其他決定因素，所以S也屬于BCNF。假定沒有重名情況非主屬性：SDEPT，SAGE主屬性：SNO，SNAME第33頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一關(guān)系模式SPJ（S，J，P） S：學(xué)生 ，J：課程，P：名次。每個(gè)學(xué)生選修每門課程的成績有一定的名次，每門課程中每一名次只有一個(gè)學(xué)生。由語義可得到如下的函數(shù)依賴：（S，J） P； （J，P） S 候選碼：（S，J） （J，P） 所有屬性均為主屬性，不存在非主屬性對主屬性的部分依賴和傳遞依賴，所以 。而且除（S，J）和（J，P）以外沒有其他決定因素，所

35、以 。 關(guān)系模式STJ（S，T，J） S：學(xué)生， T：教師， J：課程。每一教師只教一門課，每門課有若干教師，某一學(xué)生選定某門課，就對應(yīng)一固定的教師。由語義可得： （S，J） T；（S，T） J； T J （S，J），（S，T）均為碼STJ是3NF，但STJ不是BCNF。因?yàn)門是決定因素，卻不包含碼。非BCNF的關(guān)系模式也可以通過分解成為BCNF。例如STJ可分解為 ST（S，T）； TJ（T，J） 它們均為BCNF。3NF和BCNF是在函數(shù)依賴的條件下對模式分解所能達(dá)到的分離程度的測度。一個(gè)模式中的關(guān)系模式如果都屬于BCNF，那么在函數(shù)依賴范疇內(nèi)，它已實(shí)現(xiàn)了徹底的分離，已消除了插入和刪除異常

36、。 3NF的不徹底性表現(xiàn)在可能存在主屬性對碼的部分依賴和傳遞依賴。第34頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一六、多值依賴?yán)? 某一門課程由多個(gè)教員講授，他們使用相同的一套參考書。每個(gè)教員可講授多門課程，每種參考書可供多門課程使用。用一個(gè)非規(guī)范化的關(guān)系來表示教員T，課程C和參考書B之間的關(guān)系。課程C教員T參考書B物理 李勇 普通物理學(xué) 王軍 光學(xué)原理 物理習(xí)題集 數(shù)學(xué) 李勇 數(shù)學(xué)分析 張平 微分方程 高等代數(shù) 計(jì)算數(shù)學(xué) 張平 數(shù)學(xué)分析 周峰 物理習(xí)題集 關(guān)系模型TEACHING（C，T，B） 碼：（ C，T，B）問題：當(dāng)某一課程增加一名講課教員，必須插入多個(gè)元組。 某一門課

37、要去掉一本參考書，則必須刪除多個(gè)元組。對數(shù)據(jù)的增、刪、改很不方便，數(shù)據(jù)的冗余也十分明顯。第35頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一物理 李勇 物理習(xí)題集 定義6.9 設(shè)R(U)是屬性集U上的一個(gè)關(guān)系模式。X、Y、Z是U的子集，并且Z=U-X-Y。關(guān)系模式R(U)中多值依賴X Y成立，當(dāng)且僅當(dāng)對R(U)的任一關(guān)系r，給定的一對（x,z)值，有一組Y的值，這組值僅僅決定于x值而與z值無關(guān)。在R(U)的任一關(guān)系r中，如果存在元組t,s使得tX=sX，那么就必然存在元組w,v r(w,v可以與s,t相同），使得wX=vX=tX,而wY=tY,wZ=sZ,vY=sY,vZ=tZ（即

38、交換s,t元組Y值所得的兩個(gè)新元組仍在r中），則Y多值依賴于X，記為X Y。這里，X，Y是U的子集，Z=U-X-Y。課程C教員T參考書B物理 李勇 普通物理學(xué) 物理 李勇 光學(xué)原理 數(shù)學(xué) 李勇 數(shù)學(xué)分析 數(shù)學(xué) 李勇 微分方程 數(shù)學(xué) 李勇 高等代數(shù) 物理 王軍 普通物理學(xué) 物理 王軍 光學(xué)原理 物理 王軍 物理習(xí)題集 即如果r有兩個(gè)元組在X屬性上的值相等，則交換這兩個(gè)元組在Y上的屬性值，得到的兩個(gè)新元組也必是r中的元組。若X Y，而Z為空，則稱X Y為平凡的多值依賴。vtsw第36頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一R(U)XYZ=U-X-YSSXSYSZttxtYtZwW

39、xWY=tYWZ=sZ.VVXVY=sYVZ=tZ第37頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一例 關(guān)系模式WSC（W，S，C）中，W表示倉庫，S表示保管員，C表示商品。假設(shè)每個(gè)倉庫有若干個(gè)保管員，有若干種商品。每個(gè)保管員保管所在的倉庫的所有商品，每種商品被所有保管員保管。wsCw1s1C1w1s1C2w1S1C3w1s2C1w1S2C2w1s2C3w2s3C4w2s3C5w2s4C4w2S4c5對于W 的某一個(gè)值Wi,S有一個(gè)完整的集合與之對應(yīng)而不論C取何值。W S對于W 的某一個(gè)值Wi, C有一個(gè)完整的集合與之對應(yīng)而不論S取何值。W c第38頁，共67頁，2022年，5月

40、20日，18點(diǎn)37分，星期一多值依賴具有以下性質(zhì)：1.多值依賴具有對稱性。即若X Y，則X Z，其中Z=U-X-Y。因?yàn)槊總€(gè)保管員保管所有商品，同時(shí)每種商品被所有保管員保管，顯然若W S，則必然有W C。2.多值依賴的傳遞性。即若X Y，Y Z，則X Z-Y。3.函數(shù)依賴可以看作是多值依賴的特殊情況。即若X Y，則X Y。4.若X Y，X Z，則X YZ。5.若X Y，X Z，則X Y Z。6.若X Y，X Z，則X Y-Z，X Z-Y。第39頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一多值依賴與函數(shù)依賴相比，具有下面兩個(gè)基本的區(qū)別:1、X Y在U上成立則在W（XY W U）上一

41、定成立；反之則不然，即X Y在W（W U）上成立，在U上并不一定成立。因?yàn)槎嘀狄蕾嚨亩x中不僅涉及屬性組X和Y，而且涉及U中其余屬性Z。一般地，在R(U)上若有X Y在W(W U)上成立。則稱X Y為R（U）的嵌入型多值依賴。但是在關(guān)系模式R（U）中函數(shù)依賴X Y的有效性僅決定于X，Y這兩個(gè)屬性集的值。只要在R（U）的任何一個(gè)關(guān)系r中，元組在X和Y上的值滿足定義5.1，則函數(shù)依賴X Y在任何屬性集W（XY W U）上成立。2、若函數(shù)依賴X Y在R（U）上成立，則對于任何Y Y 均有X Y成立。而多值依賴X Y若在R（U）上成立，卻不能斷言對于任何Y Y有X Y成立。第40頁，共67頁，2022

42、年，5月20日，18點(diǎn)37分，星期一七、4NF定義6.10 關(guān)系模式R 1NF,如果對于R的每個(gè)非平凡多值依賴X Y(Y X)，X都含有碼，則稱R 4NF。4NF就是限制關(guān)系模式的屬性之間不允許有非平凡且非函數(shù)依賴的多值依賴。根據(jù)定義，對于每一個(gè)非平凡的多值依賴X Y，X都含有候選碼，于是就有X Y，所以4NF所允許的非平凡的多值依賴實(shí)際上是函數(shù)依賴。顯然，如果一個(gè)關(guān)系模式是4NF，則必為BCNF。但一個(gè)BCNF不一定是4NF。關(guān)系模式WSC（W，S，C）， W S，W C，都為非平凡的多值依賴。 碼：（W，S，C） 所以WSC 4NF。一個(gè)關(guān)系模式如果已達(dá)到了BCNF但不是4NF，這樣的關(guān)系

43、模式仍然具有不好的性質(zhì)。如WSC，是BCNF但不是4NF，對于WSC的某個(gè)關(guān)系，若某一倉庫Wi有n個(gè)保管員，存放m件物品，則關(guān)系中分量為Wi的元組數(shù)目一定有m*n個(gè)。每個(gè)保管員重復(fù)存儲(chǔ)m次，每種物品重復(fù)存儲(chǔ)n次，數(shù)據(jù)的冗于度太大，應(yīng)繼續(xù)規(guī)范化為4NF。可以用投影分解的方法消去非平凡且非函數(shù)依賴的多值依賴。WSC（W，S，C）分解為： WS（W，S），WC（W，C）均為平凡的多值依賴。所以 WS 4NF，WC 4NF。_第41頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一一個(gè)滿足4NF的關(guān)系模式的特點(diǎn)是：1.該關(guān)系模式滿足BCNF2 該關(guān)系模式只允許出現(xiàn)平凡多值依賴。定義：如果Y X

44、或者XY=U，多值依賴X Y是平凡的幻燈片 37U|第42頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一函數(shù)依賴和多值依賴是兩種最重要的數(shù)據(jù)依賴。如果只考慮函數(shù)依賴，則屬于BCNF的關(guān)系模式規(guī)范化程度已經(jīng)是最高的了。如果考慮多值依賴，則屬于4NF的關(guān)系模式規(guī)范化程度是最高的。事實(shí)上，數(shù)據(jù)依賴中除函數(shù)依賴和多值依賴之外，還有其他數(shù)據(jù)依賴。如有一種連接依賴。函數(shù)依賴是多值依賴的一種特殊情況，而多值依賴實(shí)際上又是連接依賴的一種特殊情況。存在連接依賴的關(guān)系模式仍可能遇到數(shù)據(jù)冗于及插入、修改、刪除異常等問題。如果消除了屬于4NF的關(guān)系模式中存在的連接依賴，則可以進(jìn)一步達(dá)到5NF的關(guān)系模式。第

45、43頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一6.5 規(guī)范化小節(jié)規(guī)范化的基本思想是逐步消除數(shù)據(jù)依賴中不合適的部分,使模式中的各個(gè)關(guān)系模式達(dá)到某種程度的分離.讓一個(gè)關(guān)系描述一個(gè)概念、一個(gè)實(shí)體或者實(shí)體間的一種聯(lián)系。若多余一個(gè)概念就把它分離出去。關(guān)系模式的規(guī)范化過程是通過對關(guān)系模式的分解來實(shí)現(xiàn)的。把低一級的關(guān)系模式分解為若干個(gè)高一級的關(guān)系模式。這種分解不是唯一的。下面將進(jìn)一步討論分解后的關(guān)系模式與原關(guān)系模式“等價(jià)”的問題以及分解的算法。1NF2NF3NFBCNF4NF消除非主屬性對碼的部分函數(shù)依賴。消除非主屬性對碼的傳遞函數(shù)依賴。消除主屬性對碼的部分和傳遞函數(shù)依賴。消除非平凡且非函數(shù)

46、依賴的多值依賴。各種范式及規(guī)范化過程第44頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一定義6.16 關(guān)系模式R的一個(gè)分解是指 其中U= ，并且沒有 ，1=i,j=n， 是F在 上的投影。6.5 關(guān)系模式的分解關(guān)系模式設(shè)計(jì)得不好會(huì)帶來很多問題。為避免這些問題的發(fā)生，有時(shí)需要把一個(gè)關(guān)系模式分為幾個(gè)關(guān)系模式。一、模式分解的三個(gè)定義對于一個(gè)模式分解是多種多樣的，但是分解后產(chǎn)生的模式應(yīng)與原模式等價(jià)。人們從不同的角度去觀察問題，對“等價(jià)”的概念形成了三種不同的定義： 分解具有“無損連接性”。 分解要“保持函數(shù)依賴”。 分解既要“保持函數(shù)依賴”，又要具有“無損連接性”。所謂“ 是F在 上的投影

47、”的確切定義是：定義6.17 函數(shù)依賴集合 的一個(gè)覆蓋 叫做F在 上的投影。例 ui=ABC Uj=ABCD第45頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一例 關(guān)系模式R，其中U=SNO，SDEPT，MN， F=SNO SDEPT，SDEPT MN。語義是學(xué)生SNO正在SDEPT系學(xué)習(xí)，其系主任是MN。一個(gè)學(xué)生只在一個(gè)系學(xué)習(xí)，一個(gè)系只有一個(gè)系主任。由于R中存在傳遞函數(shù)依賴SNO MN，會(huì)發(fā)生更新異常。進(jìn)行如下幾種分解： S1 D1 張平無損聯(lián)結(jié)性：分解后的關(guān)系做自然聯(lián)接和分解前的關(guān)系完全一樣嗎？會(huì)不會(huì)多出某些信息或丟失某些信息。依賴保持性：分解以后的關(guān)系模式能否保持原有的函數(shù)依

48、賴。無損聯(lián)接性和依賴保持性是關(guān)系模式分解和聯(lián)接中的重要問題。 SNO SDEPT MN S2 D1 張平S3 D2 李四S4 D3 王一分解三既具有無損連接性又保持函數(shù)依賴。它解決了更新異常，又沒有丟失原數(shù)據(jù)庫的信息，所希望的分解。第46頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一 SNO=S1,S2,S3,S4 SDEPTD1,D2,D3 MN=張平，李四，王一SNO SDEPT MNSnoSdeptMnS1D1張平S1D1李四S1D1王一S1D2張平失真SnoSdeptS1D1S2D1S3D2S4D3SnoMnS1張平S2張平S3李四S4王一SnoSdeptMnS1D1張平S

49、2D1張平S3D2李四S4D3王一具有無損聯(lián)接性丟失了函數(shù)依賴SDEPT MNF第47頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一記號：設(shè) 是RU，F(xiàn)的一個(gè)分解，r是RU，F(xiàn)的一個(gè)關(guān)系。定義即 是r在中各關(guān)系模式上投影的連接。 定義 設(shè)F是關(guān)系模式R的一個(gè)依賴集。 是R的一個(gè)分解。如果對于R的任一滿足F的關(guān)系r都有 則稱這個(gè)分解是滿足依賴集F的無損聯(lián)接性分解。二、無損聯(lián)接性和保持函數(shù)依賴性 無損聯(lián)接分解可以通過自然聯(lián)接恢復(fù)原來的關(guān)系。第48頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一引理6.4 設(shè)有關(guān)系模式R， 是RU，F(xiàn)的一個(gè)分解，r是R的一個(gè)關(guān)系。 則 證：任取

50、r中的一個(gè)元組t， 設(shè) （i=1,2,k)。對k進(jìn)行歸納可以證明 ，所以 。 由 已設(shè)s= ，所以 ，只需證明 ，就有任取 ，必有S中的一個(gè)元組v，使得 。根據(jù)自然連接的定義 ， 對于其中每一個(gè) 必存在r中的一個(gè)元組t，使得 。由前面 的定義即得 。又因 ，故 。又由上面證得 ， 故即 。故 。第49頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一 定義5.18 是RU，F(xiàn)的一個(gè)分解，若對RU，F(xiàn)的任何一個(gè)關(guān)系r均有 成立。則稱分解具有無損連接性。為無損分解。不可能通過定義鑒別一個(gè)分解的無損連接性。的結(jié)論告訴我們，把分解后的關(guān)系做自然聯(lián)接必包含分解前的關(guān)系，即分解是不會(huì)丟失元組的。因

51、為分解是用投影法把原關(guān)系的某些信息“照”下來。對于每一列屬性值都不會(huì)丟失，因而把分解后的關(guān)系再做自然聯(lián)接，其結(jié)果關(guān)系必包含原來的關(guān)系，而且有可能多出來。只有當(dāng) 時(shí)，分解才是連接不失真分解。的結(jié)論說明，關(guān)系模式只有在第一次分解的連接恢復(fù)后有可能丟失信息，此后的多次分解均能使分解不失真。第50頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一 是RU，F(xiàn)的一個(gè)分解，無損聯(lián)接性檢驗(yàn)算法： ，設(shè)F是一極小依賴集，記方法：構(gòu)成一個(gè)k行n列的表。每一列對應(yīng)一個(gè)屬性，每一行對應(yīng)分解中的一個(gè)關(guān)系模式。若屬性 ，則在第i行第j列上填上 ，否則填上 。 對每一個(gè) 做下列操作：找到 所對應(yīng)的列中具有相同符號

52、的行，考察這些行中 列的元素，如果其中有 則全部改為 ；否則全部改為 ；m是這些行的行號最小值。如果在某次更改之后，有一行成為 則算法終止。 具有無損連接性，否則 不具有無損連接性。對F中p個(gè)FD逐一進(jìn)行一次這相的處置，稱為對F的一次掃描。 比較掃描前后，表有無變化，如有變化，則返回第2步。否則算法終止。 如發(fā)生循環(huán)，那么前次掃描至少應(yīng)使該表減少一個(gè)符號，表中符號有限，因此循環(huán)必然終止。定理5.4 為無損連接分解的充分必要條件是算法5.2終止時(shí)，表中有一行為 。 第51頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一例 已知關(guān)系模式R，U=A，B，C，D，E， F=AB C，C D，

53、D E， R的一個(gè)分解： 首選構(gòu)造初始表。2. 逐個(gè)檢查每一個(gè)FDi,修改表中元素。表中第一行成為a1,a2,a3,a4,a5，所以此分解具有無損連接性。 A B C D E ABC a1 a2 a3 b14 b15 CD b21 b22 a3 a4 b25 DE b31 b32 b33 a4 a5 A B C D E ABC a1 a2 a3 a4 a5 CD b21 b22 a3 a4 a5 DE b31 b32 b33 a4 a5第52頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一如 在 F中，則第2行全a。可知具有無損聯(lián)接性。如果 不在F中，但在 中，即它可以用公理從F中推

54、出來，從而也能推出 。其中 ，用算法可將Ax列的第二行改為a，同樣可將 中的其它屬性的第2行也改為a，這樣第2行就變成了全a。 分解 具有無損聯(lián)接。必要性：設(shè)按算法構(gòu)造的表中有一行全a，如第一行全a，則由函數(shù)依賴定義可知 。定理6.5 R的一個(gè)分解 具有無損聯(lián)接性的充要條件是 或 說明：充分性：設(shè)按算法構(gòu)造下表： 第53頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一例 R=（A，B，C），F(xiàn)=A B，C B， =AB，BC =AC，BC解： =B， =A， =C 不具有無損連接性。 =C， =A， =B 因?yàn)?C B屬于F。所以 具有無損連接性。定義6.19 若 ,則R的分解 保持

55、函數(shù)依賴。引理5.3 的充要條件是 和 。此引理給出了判斷兩個(gè)函數(shù)依賴集等價(jià)的可行算法，也給出了判別R的分解 是否保持函數(shù)依賴的方法。幻燈片 19第54頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一例 設(shè)R，U=A，B，C，D，F(xiàn)=A B，B C，D B R的一個(gè)分解 =AB，AC，BD， 保持函數(shù)依賴嗎？求F在 的每個(gè)模式上的投影。求 =A B，A C,D B 與F等價(jià)。所以 保持函數(shù)依賴。第55頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一三、模式分解的算法對于任一關(guān)系模式都可分解為3NF，同時(shí)滿足無損聯(lián)接性和依賴保持性。算法6.3 轉(zhuǎn)換為3NF的保持函數(shù)依賴的分解

56、對R中的函數(shù)依賴集F進(jìn)行極小化處理。處理后得到的依賴集仍記為F。找出不在F中出現(xiàn)的屬性，將它們構(gòu)成一個(gè)關(guān)系模式，從U中將它們?nèi)サ?，剩余的屬性仍記為U。（雖然其中沒有函數(shù)依賴，但我們可把它的所有屬性當(dāng)作關(guān)鍵字。）如F中有一依賴XA，且XA=U，則 ，算法終止。否則，對F按具有相同左部的原則分組（假定分為k組）,每一組函數(shù)依賴 所涉及的全部屬性形成一個(gè)屬性集 。若 就去掉 。 由于經(jīng)過了步驟（2），故 ,于是 構(gòu)成R的一個(gè)保持函數(shù)依賴的分解，并且每個(gè) 均屬3NF。例 R（CTHRSG），第56頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一 顯然屬于3NF，而 保持函數(shù)依賴也很顯然。只要

57、判定 的無損連接性。證明略。算法6.4 轉(zhuǎn)換為3NF既有無損連接性又保持函數(shù)依賴的分解設(shè)X是R的碼。R已由算法5.3分解為 ，令若有某個(gè) , ，將 從 中去掉。 就是所求的分解。第57頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一定理6.11 若 是R的一個(gè)具有無損聯(lián)系性的分解， 是 中的一個(gè)無損連接分解,那么 ( 是R包含 的關(guān)系模式集合的分解)均是R的無損聯(lián)接分解。證： 是 的無損聯(lián)接分解，故對于 滿足 的所有關(guān)系 有而 所以有 = 是R關(guān)于F的無損聯(lián)接分解，故對于R滿足F的所有關(guān)系r有 由無損聯(lián)接分解的定義可知， 是R關(guān)于F的無損分解。第58頁，共67頁，2022年，5月20

58、日，18點(diǎn)37分，星期一先證下列等式，設(shè)r是關(guān)系模式R的一個(gè)關(guān)系， 是R的子集，即有歸納法：i=1,即證由于 ， 本質(zhì)上是一個(gè)選擇運(yùn)算，即選擇公共屬性 上具有相同值的那些r的元組。從而 是r的一個(gè)子集，即 根據(jù)引理，可知 歸納：設(shè)i=K時(shí)結(jié)論為真即則當(dāng)i=K+1時(shí)有： 原結(jié)論為真。 是R的無損聯(lián)接分解。第59頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一因?yàn)?是R的一個(gè)分解,故 由定義可知， 是R關(guān)于F的無損聯(lián)接性分解。第60頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一算法6.5 轉(zhuǎn)換為BCNF的無損連接分解方法：反復(fù)運(yùn)用定理5.11，逐步分解關(guān)系模式R，使得每次分解

59、都具有無損 聯(lián)接性，并且分解出來的關(guān)系模式都是BCNF。令 檢查 中各關(guān)系模式是否均屬于BCNF，若是,則算法終止。設(shè) 中 不屬于BCNF，那么必有 ， 且X非 的碼。 對 進(jìn)行分解： ， ， 以 代替 返回（2）。 由于U中屬性有限，因而有限次循環(huán)后算法一定終止。 第61頁，共67頁，2022年，5月20日，18點(diǎn)37分，星期一例：R（B，D，I，S，O，Q），F(xiàn)=SD，IB，ISQ，BO把R分解為BCNF并具有無損聯(lián)接性。 候選關(guān)鍵字為IS。解：=BDISOQ SD ISBOQ IB，ISQ，BO IB ISOQ I O,ISOQ IO ISQ IS Q =SD，IB，ISQ，ISO為BCNF具有無損聯(lián)接性 。R的分解樹不一定是唯一的。與步驟3中選定X A的順序有