關(guān)系數(shù)據(jù)庫部分理論第一頁，共六十七頁，編輯于2023年，星期日

6.1問題的提出2．插入異常BORROWER的主KEY：NO，TNO關(guān)鍵字值非空。（新調(diào)入未借書的人）NO

NAMEADDRTNOTLTLEAUDATE001張平A1T1DBAU1D1001張平A1T2OSAU2D2001張平A1T3MAAU3D3001張平A1T4DB1AU4D3┆┆┆┆┆┆008李少林A2T3MAAU3D4008李少林A2T7MA2AU7D7

數(shù)據(jù)庫模式一BORROWER（NO,NAME，ADDR，TNO,TITLE，AU,DATE)1、有冗余：對于借書人，每借一次書他本人信息和書的信息都要存放一次。存在數(shù)據(jù)冗余，這樣當(dāng)修改某些數(shù)據(jù)項(xiàng)（如地址時(shí)，則每一個(gè)元組中的地址都要改變。增加更新代價(jià)，更嚴(yán)重的是潛在的不一致性。)存在的問題：3．刪除異常如把借的書全部還掉，則就把這個(gè)人連同他的地址都刪掉了,丟失了借書人的基本信息。第二頁，共六十七頁，編輯于2023年，星期日數(shù)據(jù)庫模式二

BORROWER（NO,NAME，ADDR)BOOKS(TNO,TITLE,AU)LOAN(NO，TNO，DATE）由于將借書人、書、及借書分離成不同的關(guān)系，使數(shù)據(jù)冗余大大減少，且不存在插入異常和刪除異常。存在另一問題：如使用上述模式時(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ù)依賴起核心作用。第三頁，共六十七頁，編輯于2023年，星期日原因：

不僅客觀事物彼此互相聯(lián)系、互相制約。客觀事物本身的各個(gè)屬性之間也互相聯(lián)系、互相依賴。如一個(gè)人的住址依賴于他的姓名。屬性之間的這種依賴關(guān)系表達(dá)了一定的語義信息。在設(shè)計(jì)數(shù)據(jù)庫時(shí)，對于事物之間的聯(lián)系和事物屬性之間的聯(lián)系，都要考慮。例上例中，借書人的屬性都依賴于NO，但與書,借書的屬性沒有聯(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）、連接依賴。

第四頁，共六十七頁，編輯于2023年，星期日

設(shè)R（U）是屬性集U上的關(guān)系模式。X和Y是U的子集。若對于R（U）的任意一個(gè)可能的關(guān)系r，r中不可能存在兩個(gè)元組在X上的屬性值相等，而Y上的屬性值不等，則稱X函數(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ù)依賴。第五頁，共六十七頁，編輯于2023年，星期日設(shè)R（U）是屬性集U上的關(guān)系模式。X和Y是U的子集。R是R的任一具體關(guān)系，U,V是r中的任意兩個(gè)元組。如果由U[X]=V[X]能導(dǎo)致U[Y]=V[Y],則稱X函數(shù)決定Y或Y函數(shù)依賴于X，記為，其中U[X]表示元組U在X上的屬性值。V[X]，U[Y]，V[Y]有類似的意義。設(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à)。第六頁，共六十七頁，編輯于2023年，星期日可斷言如下三個(gè)函數(shù)依賴：即如兩個(gè)元組在title，year分量上具有相同的值，則它們在length，filmType和studioName上必然也相同。title，yearstarName

TitleYearLengthFilmTypeStudioNameStarNameStarWars1977124ColorFoxCarrieFisherStarWars1977124ColorFoxMarkHamillStarWars1997124ColorFoxHarrisonFordStartWars2000125Color

MriCarrie

第七頁，共六十七頁，編輯于2023年，星期日設(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之間是“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叫做決定因素。若，則記作第八頁，共六十七頁，編輯于2023年，星期日2、完全函數(shù)依賴在R（U）中，如果，并且對于X的任何一個(gè)真子集，都有Y，則稱Y對X完全函數(shù)依賴：記作。3、部分函數(shù)依賴若，但Y不完全函數(shù)依賴于X，則稱Y對X部分函數(shù)依賴，存在：書號出版社，出版社地址，出版社書號故有地址對書號的傳遞函數(shù)依賴。4、傳遞函數(shù)依賴在R（U）中，如果，，YX，，則稱Z對X傳遞函數(shù)依賴。如Books（書號，出版社名，出版社地址）一種書對應(yīng)唯一書號，并只能為某一個(gè)出版社出版，一個(gè)出版社一般只有一個(gè)名稱和唯一地址。一個(gè)出版社可出版多種書。Title,yearlengthTitlelength第九頁，共六十七頁，編輯于2023年，星期日定義：對于任給的關(guān)系R，U為其所含全部的屬性集合X為U的子集。若有完全函數(shù)依賴則

四、關(guān)鍵字（碼）作為候選關(guān)鍵字的屬性集X唯一標(biāo)識R中的元組，但該屬性集的任何真子集不能唯一標(biāo)識R中的元組。一個(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)鍵字。第十頁，共六十七頁，編輯于2023年，星期日閉包：在關(guān)系模式R<U，F(xiàn)>中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ù)依賴能夠推出XY，則稱F邏輯蘊(yùn)涵或稱是F的邏輯蘊(yùn)涵。五、函數(shù)依賴的邏輯蘊(yùn)涵例：若有關(guān)系模式R（X,Y,Z),它的函數(shù)依賴集F=則F的閉包為第十一頁，共六十七頁，編輯于2023年，星期日假設(shè)我們已知某關(guān)系所滿足的函數(shù)依賴集，在不知道關(guān)系的具體元組的情況下，通?？赏茢喑鲈撽P(guān)系必然滿足的其他某些函數(shù)依賴。為此，要求有一套推理規(guī)則。Armstrong公理（推理規(guī)則中最主要、最基本的作為公理）Armstrong公理系統(tǒng)：設(shè)U為屬性集總體，F(xiàn)是U上的一組函數(shù)依賴集，于是有關(guān)系模式R<U,F>。對R<U,F>來說有以下的推理規(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。第十二頁，共六十七頁，編輯于2023年，星期日定理6.1Armstrong推理規(guī)則是正確的。證明：①：設(shè)u、v是r的任意兩個(gè)元組，r是R的任一關(guān)系。若u[X]=v[X],則在u和v中的X的任何子集也必相符。由條件Y是X的子集.∴必有u[Y]=v[Y].根據(jù)函數(shù)依賴定義可知：②:設(shè)u、v、r含義同上。若u[XZ]=v[XZ]，則u[X]u[Z]=v[X]v[Z]，也即u[X]=v[X]，u[Z]=v[Z]由條件，得如u[X]=v[X]則u[Y]=v[Y]∴u[Y]=v[Y]，u[Z]=v[Z]，即u[Y]u[Z]=v[Y]v[Z]，也即u[YZ]=v[YZ]根據(jù)函數(shù)定義可知：。③：設(shè)u、v、r含義同上，設(shè)u[X]=v[X]∵∴u[Y]=v[Y]又∵∴u[Z]=v[Z]∴第十三頁，共六十七頁，編輯于2023年，星期日①

合并規(guī)則：若則。②

分解規(guī)則：若，則，。③

偽傳遞規(guī)則：若，則。證明：①則（增廣性）（增廣性）（傳遞性）

②（反射性）（傳遞性）同理

③（增廣性）又（傳遞性）

從合并和分解規(guī)則可得出一個(gè)重要結(jié)論：引理6.1如果是關(guān)系模式R的屬性，則成立的充要條件是均成立。二、公理的推論從Armstrong公理推理規(guī)則可得如下推論：第十四頁，共六十七頁，編輯于2023年，星期日Armstrong公理是有效的、完備的。有效性指：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個(gè)函數(shù)依賴一定在中。正確性指：只要使F中的函數(shù)依賴為真，則用公理推出的函數(shù)依賴也為真。完備性指：中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來。即中的所有函數(shù)依賴都能用Armstrong公理推導(dǎo)出來。幻燈片18公理的正確性保證推出的所有函數(shù)依賴都為真，公理的完備性保證可以推出所有的函數(shù)依賴。第十五頁，共六十七頁，編輯于2023年，星期日定義：設(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ù)依賴，，能由F根據(jù)Armstrong公理導(dǎo)出的充分必要條件是。第十六頁，共六十七頁，編輯于2023年，星期日算法6.1：求屬性集X關(guān)于U上的函數(shù)依賴集F的屬性閉包。輸入：關(guān)系模式R的全部屬性集U及上的函數(shù)依賴F，U的子集X輸出：。方法：計(jì)算。1、2、求B，B={A|(V)(W)(VWF∧∧)};3、4、判斷嗎？5、若相等或，則就是，算法終止。6、若否，則i=i+1,返回第2步。于是，判定XY是否能由F根據(jù)Armstrong公理推出的問題，就轉(zhuǎn)化為求出停止計(jì)算的幾種判別方法：①②當(dāng)發(fā)現(xiàn)包含了所有屬性時(shí)。③在F中的函數(shù)依賴的右邊屬性中再也找不到中未出現(xiàn)過的屬性。④在F中未用過的函數(shù)依賴的左邊屬性已沒有的子集。第十七頁，共六十七頁，編輯于2023年，星期日

=ABCDE（D→E）例：一具有屬性A、B、C、D、E、F的關(guān)系，假設(shè)該關(guān)系有如下函數(shù)依賴：AB→C，BC→AD，D→E和CF→B。左邊不包含在中。求解：設(shè)X=AB，則有①=AB②C=ABC（AB→C）

=ABCAD=ABCD（BC→AD）在F中未用過的函數(shù)依賴的左邊屬性已沒有Xi的子集。(或計(jì)算X(4)-ABCDE

∴=（ABCDE）例：檢驗(yàn)AB→D是否蘊(yùn)涵于F中。D→A呢？解：計(jì)算及。=ABCDE∴AB→D蘊(yùn)涵于F中。也即AB→D成立。=DE∴D→A不蘊(yùn)涵于F中。也即D→A不成立。第十八頁，共六十七頁，編輯于2023年，星期日證明完備性的逆否命題，即如函數(shù)依賴XY不能由F從Armstrong公理導(dǎo)出，那么它必然不為F所蘊(yùn)涵，證明分三步。定理6.2Armstrong公理系統(tǒng)是有效的、完備的。若VW成立，且，則證因?yàn)?，所以有XV成立；于是XW成立所以。2.構(gòu)造一張二維表r,它由下列兩個(gè)元組組成,可以證明r必是R<U,F>的一個(gè)關(guān)系，即F中的全部函數(shù)依賴在r上成立。

111……1111……1

111……1000……0如r不是R<U,F>的關(guān)系,則必由于F中有函數(shù)依賴VW在r上不成立所致。由r的構(gòu)成可知，V必定是的子集，而W不是的子集，可是由第（1）步，矛盾。所以r必是R<U,F>的一個(gè)關(guān)系。(即證明r滿足F)若XY不能由F從Armstrong公理導(dǎo)出,則Y不是的子集,而因此在關(guān)系r的兩個(gè)元組中X的屬性值一致，而Y的屬性值不一致,則XY在r中不成立,即XY必不為R<U,F>所蘊(yùn)含。Armstrong公理的有效性和完備性說明了“導(dǎo)出”和“蘊(yùn)含”是兩個(gè)完全等價(jià)的概念.于是也可以說成是由F出發(fā)借助Armstrong公理導(dǎo)出的函數(shù)依賴的集合。第十九頁，共六十七頁，編輯于2023年，星期日引理6.3的充要條件是和。證必要性顯然，只證充分性。若，則。任取，則有。所以，即。3.同理可證,所以從蘊(yùn)含（或?qū)С觯┑母拍畛霭l(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第二十頁，共六十七頁，編輯于2023年，星期日例：1.檢查F中的每個(gè)函數(shù)依賴是否屬于取,求=ABCD,則同理可得出2.檢查G中的每個(gè)函數(shù)依賴是否屬于F+取同理可得出所以F與G等價(jià)第二十一頁，共六十七頁，編輯于2023年，星期日引理：每一個(gè)函數(shù)依賴集F都可以由一個(gè)右部只有單個(gè)屬性的函數(shù)依賴集G新覆蓋。(G左部與F相同)證明：設(shè)F中的函數(shù)依賴由兩部分組成：①右邊是1個(gè)以上的屬性的函數(shù)依賴。設(shè)X→Y為其中任一個(gè)，Y=A1…Ak,Ai為單屬性。②右邊是單屬性的函數(shù)依賴。設(shè)V→W為其中任一個(gè)。令G由所有的V→W及XAi(i=1…k)組成。對G中任一XAi,，由于F中有X→Y。根據(jù)分解規(guī)則有XAi(i=1..k),而V→W，在F和G中都有。所以而對于F中任一X→Y，在G中有X→Ai,根據(jù)合成規(guī)則有X→Y?！嗟诙?，共六十七頁，編輯于2023年，星期日函數(shù)依賴的最小集。定義6.15如果函數(shù)依賴集F滿足下列條件,則稱為F為一個(gè)極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。①F中的每個(gè)依賴的右部都是單個(gè)屬性。依賴右部為單屬性。②對于F的任一函數(shù)依賴X→A來說，F(xiàn)與都不等價(jià)，保證F中不存在多余的依賴。③對于F的任一函數(shù)依賴X→A來說，F(xiàn)與都不等價(jià)，其中Z為X的任一真子集，保證每個(gè)依賴的左邊沒有多余的屬性。例2關(guān)系模式S<U,F>,其中U={SNO,SDEPT,MN,CNAME,G}F={SNOSDEPT,SDEPTMN,(SNO,CNAME)G}F’={SNOSDEPT,SDEPTMN,(SNO,CNAME)G,SNOMN,(SNO,SDEPT)SDEPT}根據(jù)定義可以驗(yàn)證F是最小覆蓋,而F’不是。定理5.3：每個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)最小函數(shù)依賴集。此稱為F的最小依賴集。第二十三頁，共六十七頁，編輯于2023年，星期日定理6.3：每個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)最小函數(shù)依賴集。此稱為F的最小依賴集。證這是一個(gè)構(gòu)造性的證明，分三步對F進(jìn)行“極小化處理”，找出F的一個(gè)最小依賴集。逐一查找F中各函數(shù)依賴FDi：XY，若Y=,則用來取代XY。(YA1A2A3YA1)逐一查找F中各函數(shù)依賴FDi：XA，令，若則從F中去掉此函數(shù)依賴。逐一取出F中各函數(shù)依賴FDi：XA，設(shè)X=，逐一考查Bi(I=1,2,…,m)，若，則以X-Bi取代X。最后剩下的F就一定是極小依賴集，并且與原來的F等價(jià)。因?yàn)閷的每一次“改造”都保證了改造前后的兩個(gè)函數(shù)依賴集等價(jià)。應(yīng)當(dāng)指出，F(xiàn)的最小依賴集不一定是唯一的，它與對各函數(shù)依賴Fdi及XA中X各屬性的處置順序有關(guān)。例3F={AB，BA，BC，AC，CA}Fm1={AB,BC,CA}Fm2={AB，BA，AC，CA}Fm1與Fm2均為最小依賴集。第二十四頁，共六十七頁，編輯于2023年，星期日例：求。解：按最小依賴集的定義分別考慮三個(gè)條件：①用分解規(guī)則將所有依賴變?yōu)橛疫吺菃螌傩缘囊蕾嚒?/p>

②去掉F中的多余依賴，具體做法：從第一個(gè)依賴開始，從F中去掉它（假設(shè)為X→Y）然后在剩下的依賴中求，看是否包含Y，若是則去掉X→Y：否則不能去掉，依次做下去。A→B=AC不能去掉B→A=CAB去掉B→C=B不能去掉A→C=ABC去掉C→A=C不能去掉BED=BEAC不能去掉判斷XY→A中X是否成為多余屬性，只要在F中求若包含A，則Y是多余屬性。否則Y不是多余屬性。依次判斷其它屬性即可消除各依賴左邊的多余屬性。③去掉各依賴左邊多余的屬性應(yīng)當(dāng)指出，F(xiàn)的最小依賴集不一定是唯一的，它與對各函數(shù)依賴Fdi及XA中X各屬性的處置順序有關(guān)。B+=BCA不含D，E不多余E+=E，不含D，B不多余第二十五頁，共六十七頁，編輯于2023年，星期日注F的最小依賴集不一定唯一。它和我們對各函數(shù)依賴的處置順序有關(guān)。兩個(gè)關(guān)系模式R1<U,F>，R2<U,G>，如果F與G等價(jià)，那么R1的關(guān)系一定是R2的關(guān)系。反過來，R2的關(guān)系也一定是R1的關(guān)系。所以在R1<U,F>中用與F等價(jià)的依賴集G來取代F是允許的。B+=BCA不含D，E不多余E+=E，不含D，B不多余第二十六頁，共六十七頁，編輯于2023年，星期日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)系是要滿足一定要求的，滿足不同程度要求的為不同范式，滿足最低要求的叫第一范式，簡稱1NF，在1NF中滿足進(jìn)一步一些要求的2NF，…。所謂“第幾范式”，是表示關(guān)系的某一種級別。即符合某一種級別的關(guān)系模式的集合，R為第幾范式就可以寫成。5NF4NFBCNF3NF2NF1NF1NF：每一個(gè)分量必須是不可分的數(shù)據(jù)項(xiàng)。這是最基本的規(guī)范化。5NF4NFBCNF3NF2NF1NF各種范式之間的關(guān)系第二十七頁，共六十七頁，編輯于2023年，星期日二、第一范式（1NF）定義：如果一個(gè)關(guān)系模式R的每個(gè)具體關(guān)系r的每個(gè)屬性值都是不可再分的最小數(shù)據(jù)單位，則R為第一范式。簡稱1NF，r為1NF關(guān)系。注：第一范式不含重復(fù)組，不存在嵌套結(jié)構(gòu)。不滿足1NF的關(guān)系為非規(guī)范關(guān)系。部門名部門號經(jīng)理DN1D1M1AM1DN2D2M2AM2正經(jīng)理副經(jīng)理借書人所借書名日期

T1D1張平T2D2T3D3T2D2T4D4李問部門名部門號正經(jīng)理副經(jīng)理DN1D1M1AM1DN2D2M2AM2借書人所借書名日期張平T1D1張平T2D2.第二十八頁，共六十七頁，編輯于2023年，星期日三、第二范式（2NF）定義6.6任給關(guān)系R，若R為INF，且每一個(gè)非主屬性都完全函數(shù)依賴于碼，則R為2NF。關(guān)系模式SLC(SNO,SDEPT,SLOC,CNO,G)碼:(SNO,CNO)(SNO,CNO)F

GSNOSDEPT,(SNO,CNO)P

SDEPTSNOSLOC,(SNO,CNO)PSLOCSDEPTSLOC(每個(gè)系的學(xué)生只住一個(gè)地方)函數(shù)依賴:SNOSDEPTCNOSLOCG非主屬性:SDEPT,SLOC部分函數(shù)依賴于碼。所以SLC為1NF在SLC中，仍存在插入、刪除異常，修改復(fù)雜等問題。解決辦法是用投影分解把關(guān)系SLC分解為兩個(gè)關(guān)系模式：SC（SNO，CNO，G）SL（SNO，SDEPT，SLOC）非主屬性對碼都是完全函數(shù)依賴了

第二十九頁，共六十七頁，編輯于2023年，星期日一個(gè)關(guān)系模式R不屬于2NF,會產(chǎn)生以下幾個(gè)問題1.插入異常若新來一個(gè)學(xué)生,該學(xué)生還未選課,即無CNO,這樣的元組就不能插入SLC中。則該學(xué)生的SNO，SDEPT，SLOC信息無法插入。2刪除異常假定某個(gè)學(xué)生只選一門課，如S4就選了一門課C3?，F(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ù)存儲多次，不僅存儲冗余度大，而且必須修個(gè)多個(gè)元組中全部SDEPT，SLOC信息，選成修改的復(fù)雜化。原因：存在非主屬性對碼的不完全函數(shù)依賴。SDEPT，SLOC對碼不是完全函數(shù)依賴。第三十頁，共六十七頁，編輯于2023年，星期日四、第三范式定義：如果關(guān)系模式R滿足為2NF，且其每一個(gè)非主屬性都不傳遞函數(shù)依賴于任何碼（候選關(guān)鍵字）。則R為第三范式。一個(gè)關(guān)系模式R若不是3NF，就會產(chǎn)生與非2NF相類似的問題。SC（SNO，CNO，G）SL（SNO，SDEPT，SLOC）SNOCNOGSNOSDEPTSLOCSC中的函數(shù)依賴SL中的函數(shù)依賴SC沒有傳遞函數(shù)依賴SL中存在傳遞函數(shù)依賴SNOSDEPT，（SDEPTSNO），SDEPTSLOC可得SNOSLOC為傳遞函數(shù)依賴。所以，SL為2NF一般來說，3NF的關(guān)系大多數(shù)都能解決插入和刪除操作異常的問題，數(shù)據(jù)冗余也能得到有效的控制。解決辦法是將SL分解為：SD（SNO，SDEPT）分解后不再存在傳遞依賴DL（SDEPT，SLOC）第三十一頁，共六十七頁，編輯于2023年，星期日SL（SNO，SDEPT，SLOC）存在問題：1.數(shù)據(jù)冗余如果一個(gè)系有500個(gè)學(xué)生，則地址就要重復(fù)500次。2。插入異常如果成立了一個(gè)新系，分配了在5號樓，而該系還未開始招生，則不能插入SDEPT，SLOC。第三十二頁，共六十七頁，編輯于2023年，星期日五、BCNF定義：任給關(guān)系R，X、Y為其屬性集。F為其函數(shù)依賴集，且F中所有函賴X→Y（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，SAGE不存在對碼的部分依賴與傳遞依賴，所以。同時(shí)S中除SNO，SNAME外沒有其他決定因素，所以S也屬于BCNF。假定沒有重名情況非主屬性：SDEPT，SAGE主屬性：SNO，SNAME第三十三頁，共六十七頁，編輯于2023年，星期日關(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）以外沒有其他決定因素，所以。關(guān)系模式STJ（S，T，J）S：學(xué)生，T：教師，J：課程。每一教師只教一門課，每門課有若干教師，某一學(xué)生選定某門課，就對應(yīng)一固定的教師。由語義可得：（S，J）T；（S，T）J；TJ（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)了徹底的分離，已消除了插入和刪除異常。3NF的不徹底性表現(xiàn)在可能存在主屬性對碼的部分依賴和傳遞依賴。第三十四頁，共六十七頁，編輯于2023年，星期日六、多值依賴?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è)元組。某一門課要去掉一本參考書，則必須刪除多個(gè)元組。對數(shù)據(jù)的增、刪、改很不方便，數(shù)據(jù)的冗余也十分明顯。第三十五頁，共六十七頁，編輯于2023年，星期日物理李勇物理習(xí)題集定義6.9設(shè)R(U)是屬性集U上的一個(gè)關(guān)系模式。X、Y、Z是U的子集，并且Z=U-X-Y。關(guān)系模式R(U)中多值依賴XY成立，當(dāng)且僅當(dāng)對R(U)的任一關(guān)系r，給定的一對（x,z)值，有一組Y的值，這組值僅僅決定于x值而與z值無關(guān)。在R(U)的任一關(guān)系r中，如果存在元組t,s使得t[X]=s[X]，那么就必然存在元組w,vr(w,v可以與s,t相同），使得w[X]=v[X]=t[X],而w[Y]=t[Y],w[Z]=s[Z],v[Y]=s[Y],v[Z]=t[Z]（即交換s,t元組Y值所得的兩個(gè)新元組仍在r中），則Y多值依賴于X，記為XY。這里，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中的元組。若XY，而Z為空，則稱XY為平凡的多值依賴。vtsw第三十六頁，共六十七頁，編輯于2023年，星期日R(U)XYZ=U-X-YSS[X]S[Y]S[Z]…tt[x]t[Y]t[Z]…wW[x]W[Y]=t[Y]W[Z]=s[Z]….VV[X]V[Y]=s[Y]V[Z]=t[Z]第三十七頁，共六十七頁，編輯于2023年，星期日例關(guān)系模式WSC（W，S，C）中，W表示倉庫，S表示保管員，C表示商品。假設(shè)每個(gè)倉庫有若干個(gè)保管員，有若干種商品。每個(gè)保管員保管所在的倉庫的所有商品，每種商品被所有保管員保管。wsCw1s1C1w1s1C2w1S1C3w1s2C1w1S2C2w1s2C3w2s3C4w2s3C5w2s4C4w2S4c5對于W的某一個(gè)值Wi,S有一個(gè)完整的集合與之對應(yīng)而不論C取何值。WS對于W的某一個(gè)值Wi,C有一個(gè)完整的集合與之對應(yīng)而不論S取何值。Wc第三十八頁，共六十七頁，編輯于2023年，星期日多值依賴具有以下性質(zhì)：1.多值依賴具有對稱性。即若XY，則XZ，其中Z=U-X-Y。因?yàn)槊總€(gè)保管員保管所有商品，同時(shí)每種商品被所有保管員保管，顯然若WS，則必然有WC。2.多值依賴的傳遞性。即若XY，YZ，則XZ-Y。3.函數(shù)依賴可以看作是多值依賴的特殊情況。即若XY，則XY。4.若XY，XZ，則XYZ。5.若XY，XZ，則XYZ。6.若XY，XZ，則XY-Z，XZ-Y。第三十九頁，共六十七頁，編輯于2023年，星期日多值依賴與函數(shù)依賴相比，具有下面兩個(gè)基本的區(qū)別:1、XY在U上成立則在W（XYWU）上一定成立；反之則不然，即XY在W（WU）上成立，在U上并不一定成立。因?yàn)槎嘀狄蕾嚨亩x中不僅涉及屬性組X和Y，而且涉及U中其余屬性Z。一般地，在R(U)上若有XY在W(WU)上成立。則稱XY為R（U）的嵌入型多值依賴。但是在關(guān)系模式R（U）中函數(shù)依賴XY的有效性僅決定于X，Y這兩個(gè)屬性集的值。只要在R（U）的任何一個(gè)關(guān)系r中，元組在X和Y上的值滿足定義5.1，則函數(shù)依賴XY在任何屬性集W（XYWU）上成立。2、若函數(shù)依賴XY在R（U）上成立，則對于任何Y’Y均有XY’成立。而多值依賴XY若在R（U）上成立，卻不能斷言對于任何Y’Y有XY’成立。第四十頁，共六十七頁，編輯于2023年，星期日七、4NF定義6.10關(guān)系模式R<U,F>1NF,如果對于R的每個(gè)非平凡多值依賴XY(YX)，X都含有碼，則稱R<U,F>4NF。4NF就是限制關(guān)系模式的屬性之間不允許有非平凡且非函數(shù)依賴的多值依賴。根據(jù)定義，對于每一個(gè)非平凡的多值依賴XY，X都含有候選碼，于是就有XY，所以4NF所允許的非平凡的多值依賴實(shí)際上是函數(shù)依賴。顯然，如果一個(gè)關(guān)系模式是4NF，則必為BCNF。但一個(gè)BCNF不一定是4NF。關(guān)系模式WSC（W，S，C），WS，WC，都為非平凡的多值依賴。碼：（W，S，C）所以WSC4NF。一個(gè)關(guān)系模式如果已達(dá)到了BCNF但不是4NF，這樣的關(guān)系模式仍然具有不好的性質(zhì)。如WSC，是BCNF但不是4NF，對于WSC的某個(gè)關(guān)系，若某一倉庫Wi有n個(gè)保管員，存放m件物品，則關(guān)系中分量為Wi的元組數(shù)目一定有m*n個(gè)。每個(gè)保管員重復(fù)存儲m次，每種物品重復(fù)存儲n次，數(shù)據(jù)的冗于度太大，應(yīng)繼續(xù)規(guī)范化為4NF。可以用投影分解的方法消去非平凡且非函數(shù)依賴的多值依賴。WSC（W，S，C）分解為：WS（W，S），WC（W，C）均為平凡的多值依賴。所以WS4NF，WC4NF。_第四十一頁，共六十七頁，編輯于2023年，星期日一個(gè)滿足4NF的關(guān)系模式的特點(diǎn)是：1.該關(guān)系模式滿足BCNF2該關(guān)系模式只允許出現(xiàn)平凡多值依賴。定義：如果YX或者X∪Y=U，多值依賴XY是平凡的幻燈片37U|第四十二頁，共六十七頁，編輯于2023年，星期日函數(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)系模式。第四十三頁，共六十七頁，編輯于2023年，星期日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ù)依賴的多值依賴。各種范式及規(guī)范化過程第四十四頁，共六十七頁，編輯于2023年，星期日定義6.16關(guān)系模式R<U,F>的一個(gè)分解是指

其中U=，并且沒有，1<=i,j<=n，是F在上的投影。6.5關(guān)系模式的分解關(guān)系模式設(shè)計(jì)得不好會帶來很多問題。為避免這些問題的發(fā)生，有時(shí)需要把一個(gè)關(guān)系模式分為幾個(gè)關(guān)系模式。一、模式分解的三個(gè)定義對于一個(gè)模式分解是多種多樣的，但是分解后產(chǎn)生的模式應(yīng)與原模式等價(jià)。人們從不同的角度去觀察問題，對“等價(jià)”的概念形成了三種不同的定義：分解具有“無損連接性”。分解要“保持函數(shù)依賴”。分解既要“保持函數(shù)依賴”，又要具有“無損連接性”。所謂“是F在上的投影”的確切定義是：定義6.17函數(shù)依賴集合的一個(gè)覆蓋叫做F在上的投影。例ui=ABCUj=ABCD第四十五頁，共六十七頁，編輯于2023年，星期日例關(guān)系模式R<U,F>，其中U={SNO，SDEPT，MN}，F(xiàn)={SNOSDEPT，SDEPTMN}。語義是學(xué)生SNO正在SDEPT系學(xué)習(xí)，其系主任是MN。一個(gè)學(xué)生只在一個(gè)系學(xué)習(xí)，一個(gè)系只有一個(gè)系主任。由于R中存在傳遞函數(shù)依賴SNOMN，會發(fā)生更新異常。進(jìn)行如下幾種分解：

S1D1張平無損聯(lián)結(jié)性：分解后的關(guān)系做自然聯(lián)接和分解前的關(guān)系完全一樣嗎？會不會多出某些信息或丟失某些信息。依賴保持性：分解以后的關(guān)系模式能否保持原有的函數(shù)依賴。無損聯(lián)接性和依賴保持性是關(guān)系模式分解和聯(lián)接中的重要問題。

SNOSDEPTMN

S2D1張平S3D2李四S4D3王一分解三既具有無損連接性又保持函數(shù)依賴。它解決了更新異常，又沒有丟失原數(shù)據(jù)庫的信息，所希望的分解。第四十六頁，共六十七頁，編輯于2023年，星期日

SNO={S1,S2,S3,S4}SDEPT{D1,D2,D3}MN={張平，李四，王一}SNOSDEPTMNSnoSdeptMnS1D1張平S1D1李四S1D1王一S1D2張平···失真SnoSdeptS1D1S2D1S3D2S4D3SnoMnS1張平S2張平S3李四S4王一SnoSdeptMnS1D1張平S2D1張平S3D2李四S4D3王一具有無損聯(lián)接性丟失了函數(shù)依賴SDEPTMNF第四十七頁，共六十七頁，編輯于2023年，星期日記號：設(shè)是R〈U，F(xiàn)〉的一個(gè)分解，r是R〈U，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)系。第四十八頁，共六十七頁，編輯于2023年，星期日引理6.4設(shè)有關(guān)系模式R<U,F>，是R〈U，F(xiàn)〉的一個(gè)分解，r是R的一個(gè)關(guān)系。則

證：①任取r中的一個(gè)元組t，設(shè)（i=1,2,…,k)。對k進(jìn)行歸納可以證明，所以。②由①已設(shè)s=，所以，只需證明，就有任取，必有S中的一個(gè)元組v，使得。根據(jù)自然連接的定義，對于其中每一個(gè)必存在r中的一個(gè)元組t，使得。由前面的定義即得。又因，故。又由上面證得，故即。故?！谒氖彭摚擦唔?，編輯于2023年，星期日③定義5.18

是R〈U，F(xiàn)〉的一個(gè)分解，若對R〈U，F(xiàn)〉的任何一個(gè)關(guān)系r均有成立。則稱分解ρ具有無損連接性。ρ為無損分解。不可能通過定義鑒別一個(gè)分解的無損連接性。①的結(jié)論告訴我們，把分解后的關(guān)系做自然聯(lián)接必包含分解前的關(guān)系，即分解是不會丟失元組的。因?yàn)榉纸馐怯猛队胺ò言P(guān)系的某些信息“照”下來。對于每一列屬性值都不會丟失，因而把分解后的關(guān)系再做自然聯(lián)接，其結(jié)果關(guān)系必包含原來的關(guān)系，而且有可能多出來。只有當(dāng)時(shí)，分解才是連接不失真分解。③的結(jié)論說明，關(guān)系模式只有在第一次分解的連接恢復(fù)后有可能丟失信息，此后的多次分解均能使分解不失真。第五十頁，共六十七頁，編輯于2023年，星期日是R〈U，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)的列中具有相同符號的行，考察這些行中列的元素，如果其中有則全部改為；否則全部改為；m是這些行的行號最小值。如果在某次更改之后，有一行成為則算法終止。ρ具有無損連接性，否則ρ不具有無損連接性。對F中p個(gè)FD逐一進(jìn)行一次這相的處置，稱為對F的一次掃描。③比較掃描前后，表有無變化，如有變化，則返回第2步。否則算法終止。如發(fā)生循環(huán)，那么前次掃描至少應(yīng)使該表減少一個(gè)符號，表中符號有限，因此循環(huán)必然終止。定理5.4為無損連接分解的充分必要條件是算法5.2終止時(shí)，表中有一行為。第五十一頁，共六十七頁，編輯于2023年，星期日例已知關(guān)系模式R<U,F>，U={A，B，C，D，E}，F(xiàn)={ABC，CD，DE}，R的一個(gè)分解：首選構(gòu)造初始表。2.逐個(gè)檢查每一個(gè)FDi,修改表中元素。表中第一行成為a1,a2,a3,a4,a5，所以此分解具有無損連接性。ABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5ABCDEABCa1a2a3a4

a5CDb21b22a3a4a5DEb31b32b33a4a5第五十二頁，共六十七頁，編輯于2023年，星期日如在F中，則第2行全a?？芍哂袩o損聯(lián)接性。如果不在F中，但在中，即它可以用公理從F中推出來，從而也能推出。其中，∴用算法可將Ax列的第二行改為a，同樣可將中的其它屬性的第2行也改為a，這樣第2行就變成了全a?！喾纸饩哂袩o損聯(lián)接。②必要性：設(shè)按算法構(gòu)造的表中有一行全a，如第一行全a，則由函數(shù)依賴定義可知。定理6.5R<U,F>的一個(gè)分解

具有無損聯(lián)接性的充要條件是或說明：①充分性：設(shè)按算法構(gòu)造下表：

第五十三頁，共六十七頁，編輯于2023年，星期日例R=（A，B，C），F(xiàn)={AB，CB}，={AB，BC}={AC，BC}解：=B，=A，=C不具有無損連接性。=C，=A，=B因?yàn)镃B屬于F。所以具有無損連接性。定義6.19若,則R<U,F>的分解

保持函數(shù)依賴。引理5.3的充要條件是和。此引理給出了判斷兩個(gè)函數(shù)依賴集等價(jià)的可行算法，也給出了判別R的分解是否保持函數(shù)依賴的方法?；脽羝?9第五十四頁，共六十七頁，編輯于2023年，星期日例設(shè)R<U，F(xiàn)>，U={A，B，C，D}，F(xiàn)={AB，BC，DB}R的一個(gè)分解={AB，AC，BD}，保持函數(shù)依賴嗎？求F在的每個(gè)模式上的投影。求={AB，AC,DB}與F等價(jià)。所以保持函數(shù)依賴。第五十五頁，共六十七頁，編輯于2023年，星期日三、模式分解的算法對于任一關(guān)系模式都可分解為3NF，同時(shí)滿足無損聯(lián)接性和依賴保持性。算法6.3轉(zhuǎn)換為3NF的保持函數(shù)依賴的分解對R<U,F>中的函數(shù)依賴集F進(jìn)行極小化處理。處理后得到的依賴集仍記為F。找出不在F中出現(xiàn)的屬性，將它們構(gòu)成一個(gè)關(guān)系模式，從U中將它們?nèi)サ?，剩余的屬性仍記為U。（雖然其中沒有函數(shù)依賴，但我們可把它的所有屬性當(dāng)作關(guān)鍵字。）如F中有一依賴X→A，且XA=U，則，算法終止。否則，對F按具有相同左部的原則分組（假定分為k組）,每一組函數(shù)依賴所涉及的全部屬性形成一個(gè)屬性集。若就去掉。

由于經(jīng)過了步驟（2），故,于是構(gòu)成R<U,F>的一個(gè)保持函數(shù)依賴的分解，并且每個(gè)均屬3NF。例R（CTHRSG），第五十六頁，共六十七頁，編輯于2023年，星期日顯然屬于3NF，而保持函數(shù)依賴也很顯然。只要判定的無損連接性。證明略。算法6.4轉(zhuǎn)換為3NF既有無損連接性又保持函數(shù)依賴的分解設(shè)X是R<U,F>的碼。R<U,F>已由算法5.3分解為，令若有某個(gè),，將從中去掉。就是所求的分解。第五十七頁，共六十七頁，編輯于2023年，星期日定理6.11若是R<U,F>的一個(gè)具有無損聯(lián)系性的分解，是中的一個(gè)無損連接分解,那么(是R<U,F>包含的關(guān)系模式集合的分解)均是R<U,F>的無損聯(lián)接分解。證：①∵是的無損聯(lián)接分解，故對于滿足的所有關(guān)系有而所以有

=∵是R關(guān)于F的無損聯(lián)接分解，故對于R滿足F的所有關(guān)系r有

由無損聯(lián)接分解的定義可知，是R關(guān)于F的無損分解。第五十八頁，共六十七頁，編輯于2023年，星期日先證下列等式，設(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<U,F>的無損聯(lián)接分解。第五十九頁，共六十七頁，編輯于2023年，星期日因?yàn)槭荝的一個(gè)分解,故

由定義可知，是R關(guān)于F的無損聯(lián)接性分解。第六十頁，共六十七頁，編輯于2023年，星期日算法6.5轉(zhuǎn)換為BCNF的無損連接分解方法：反復(fù)運(yùn)用定理5.11，逐步分解關(guān)系模式R，使得每次分解都具有無損聯(lián)接性，并且分解出來的關(guān)系模式都是BCNF。令檢查中各關(guān)系模式是否均屬于BCNF，若是,則算法終止。設(shè)中不屬于BCNF，那么必有，且X非的碼。對進(jìn)行分解：，，

以代替返回（2）。由于U中屬性有限，因而有限次循環(huán)后算法一定終止。

第六十一頁，共六十七頁，編輯于2023年，星期日例：R（B，D，I，S，O，Q），F(xiàn)={S→D，I→B，IS→Q，B→O}把R分解為BCNF并具有無損聯(lián)接性。候選關(guān)鍵字為IS。解：①={BDISOQ}②

SD

ISBOQ{I→B，IS→Q，B→O}IB