CH5 關系數(shù)據(jù)理論及求精 - 副本

第5章關系數(shù)據(jù)理論及求精數(shù)據(jù)庫系統(tǒng)原理與設計

(第2版)志存高遠，

腳踏實地，

勇于探索！目錄范式

5.4問題提出

5.1函數(shù)依賴定義5.2函數(shù)依賴理論5.3數(shù)據(jù)庫模式求精

模式分解算法5.65.5本章要解決的兩個問題如何判斷一個數(shù)據(jù)庫模式是“好”的模式如何設計出一個“好”模式？數(shù)據(jù)冗余導致的問題數(shù)據(jù)冗余是指同一信息在數(shù)據(jù)庫中存儲了多個副本。它可能引起下列問題：冗余存儲：信息被重復存儲，導致浪費大量存儲空間。更新異常：當重復信息的一個副本被修改，所有副本都必須進行同樣的修改。因此當更新數(shù)據(jù)時，系統(tǒng)要付出很大的代價來維護數(shù)據(jù)庫的完整性，否則會面臨數(shù)據(jù)不一致的危險。插入異常：只有當一些信息事先已經存放在數(shù)據(jù)庫中時，另外一些信息才能存入數(shù)據(jù)庫中。刪除異常：刪除某些信息時可能丟失其它信息。數(shù)據(jù)冗余關系舉例[例5.1]

考慮學生選課關系模式：SCE(studentNo,studentName,courseNo,courseName,score),屬性集{studentNo,courseNo}是唯一候選碼，也是主碼。如果允許一個學生選修多門課程，且一門課程可被多個學生選修，則該關系實例可能出現(xiàn)：冗余存儲：學生姓名和課程名被重復存儲多次；更新異常：當修改某學生的姓名或某課程的課程名時，可能只修改了部分副本的信息，而其他副本未被修改到；插入異常：如果某學生沒有選修課程，或某門課程未被任何學生選修時，則該學生或該課程信息不能存入數(shù)據(jù)庫，因為主碼值不能為空；刪除異常：當一學生的所有選修課程信息都被刪除時，則該學生的信息將被丟失。對課程也是如此。數(shù)據(jù)冗余關系舉例studentNoStudentNamecourseNocourseNamescoreS0700001李小勇C001高等數(shù)學98S0700001李小勇C002離散數(shù)學82S0700001李小勇C006數(shù)據(jù)庫系統(tǒng)原理56S0700002劉方晨C003計算機原理69S0700002劉方晨C004C語言程序設計87S0700002劉方晨C005數(shù)據(jù)結構77S0700002劉方晨C007操作系統(tǒng)90S0700003王紅敏C001高等數(shù)學46S0700003王紅敏C002離散數(shù)學38S0700003王紅敏C007操作系統(tǒng)50圖5-1學生選課關系SCE實例冗余問題？數(shù)據(jù)冗余產生原因及解決方法SCE產生問題的原因：部分函數(shù)依賴該模式中某些屬性之間存在如下函數(shù)依賴關系

studentNo→studentName（即學號決定姓名）courseNo→courseName（即課程編號決定課程名稱）{studentNo,courseNo}→score即studentName、courseName部分依賴于關系的主碼解決方法：關系模式分解分解為三個關系模式

S(studentNo,studentName)C(courseNo,courseName)E(studentNo,courseNo,score)關系模式的設計問題-另解示例 考慮為管理職工的工資信息而設計一個關系模式有沒有問題？關系模式的設計問題問題：信息的不可表示問題(inabilitytorepresentcertaininformation)插入異常：如果沒有職工具有8級工資，則8級工資的工資數(shù)額就難以插入刪除異常：如果僅有職工趙明具有4級工資，如果將趙明刪除，則有關4級工資的工資數(shù)額信息也隨之刪除了信息的冗余問題(repetitionofinformation)數(shù)據(jù)冗余：職工很多，工資級別有限，每一級別的工資數(shù)額反復存儲多次更新異常：如果將5級工資的工資數(shù)額調為2620，則需要找到每個具有5級工資的職工，逐一修改關系模式的設計問題解決之道：分解,分解,再分解!級別工資425005260062700關系模式的設計問題有關學生的關系模式S(S#,SN,SD,DEAN,C#,G)它存在優(yōu)點和哪些不足？原因：不良的數(shù)據(jù)依賴函數(shù)依賴的問題

模式分解導致的問題

將一個關系模式分解為較小關系模式集可解決冗余問題。但由此可能產生兩個新的問題：什么樣的關系模式需要進一步分解為較小的關系模式集？根據(jù)范式要求決定（后面討論）是否所有的模式分解都是有益的？實例

模式分解問題舉例[例5.2]

設一關系模式STU(studentNo,studentName,sex,birthday,native,classNo),其中，studentNo為主碼。假設將STU分解為以下兩個子模式：STU1(studentNo,studentName)STU2(studentName,sex,birthday,native,classNo)分解后會發(fā)生什么問題？

模式分解問題舉例studentNostudnetNamesexbirthdaynativeclassNoS0700005王紅男1992-4-26江西省南昌市CS0702S0800005王紅女1995-8-10湖北省武漢市CP0802studentNostudnetNameS0700005王紅S0800005王紅studnetNamesexbirthdaynativeclassNo王紅男1992-4-26江西省南昌市CS0702王紅女1995-8-10湖北省武漢市CP0802studentNostudnetNameSexbirthdaynativeclassNoS0700005王紅男1992-4-26江西省南昌市CS0702S0700005王紅女1995-8-10湖北省武漢市CP0802S0800005王紅男1992-4-26江西省南昌市CS0702S0800005王紅女1995-8-10湖北省武漢市CP0802圖5-2有損分解舉例

模式分解問題舉例模式分解存在的問題有損分解：兩個分解后的關系通過連接運算還原得到的信息與原來關系的信息不一致。如果能夠通過連接分解后所得到的較小關系完全還原被分解關系的所有實例，稱之為無損分解(losslessdecomposition)，也稱該分解具有無損連接特性。丟失依賴關系sex、birthday、age、native、classNo等與屬性studentNo依賴關系也就不再存在。如果被分解關系模式上的所有依賴關系都在分解得到的關系模式上保留，稱該分解為依賴保持

(dependencypreserving)分解。小結一個“好”的關系模式應該是：數(shù)據(jù)冗余應盡可能少不發(fā)生插入異常、刪除異常、更新異常等問題。模式分解時，分解后的模式應具有無損連接、保持依賴等特性。目錄范式

5.4問題提出

5.1函數(shù)依賴定義

5.2函數(shù)依賴理論5.3數(shù)據(jù)庫模式求精

模式分解算法5.65.5函數(shù)依賴定義

函數(shù)依賴(functionaldependency,簡稱FD)是一種完整性約束,是現(xiàn)實世界事物屬性之間的一種制約關系，它廣泛地存在于現(xiàn)實世界之中。定義5.1

設r(R)為關系模式，R，R。對任意合法關系r及其中任兩個元組ti和tj，ij，若ti[]=tj[]，則ti[]=tj[]，則稱函數(shù)確定，

或函數(shù)依賴于，記作。圖5-3函數(shù)依賴圖函數(shù)依賴舉例[例5.3]

圖5-4所示的是滿足函數(shù)依賴ABC的關系模式r(A,B,C,D)的一個關系實例。對于任意兩個在屬性集{A,B}上取值相同的元組，它們在屬性C上的取值也相同。ABCDa1b1c1d1a1b1c1d2a1b2c1d1a2b1c3d1圖5-4滿足函數(shù)依賴ABC的一個關系實例如果在圖中再增加一個元組(a1,b1,c2,

d1)，ABC

還成立嗎？20函數(shù)依賴檢驗：A→C？C→A？AB→D？辨識（說明之一）滿足依賴的關系：依賴在模式的某個關系實例上成立模式上成立的依賴：依賴在模式的所有關系實例上都成立ABCDa1b1c1d1a1b2c1d2a2b2c2d2a2b3c2d3a3b3c2d4函數(shù)依賴說明對于函數(shù)依賴，需做如下說明：函數(shù)依賴不是指關系模式r(R)的某個或某些關系實例滿足的約束條件，而是指關系模式r(R)的所有關系實例均要滿足的約束條件。函數(shù)依賴是語義范疇的概念，只能根據(jù)數(shù)據(jù)的語義來確定函數(shù)依賴，是不能夠被證明的。數(shù)據(jù)庫設計者可以對現(xiàn)實世界作強制的規(guī)定。碼約束是函數(shù)依賴的一個特例。碼屬性(集)相當于定義5.1中的，關系中的所有屬性相當于定義5.1中的。平凡與非平凡函數(shù)依賴

定義5.2

在關系模式r(R)中，R，R。若，但，則稱是非平凡函數(shù)依賴。否則，若,則稱是平凡函數(shù)依賴。對于任一關系模式，平凡函數(shù)依賴都是必然成立的，它不反映新的語義。(a)非平凡函數(shù)依賴(b)平凡函數(shù)依賴圖5-5非平凡及平凡函數(shù)依賴圖完全函數(shù)依賴和部分函數(shù)依賴

定義5.3

在關系模式r(R)中，R，R，且。若對任意的，都不成立，則稱是完全函數(shù)依賴，簡稱完全依賴。否則，若存在非空的，且成立,則稱是部分函數(shù)依賴，簡稱部分依賴。圖5-6部分依賴的依賴圖完全函數(shù)依賴和部分函數(shù)依賴舉例當是單屬性時，則完全函數(shù)依賴總是成立的。例如，在關系SCE中完全依賴：studentNo

studentNamecourseNo

courseName{studentNo,courseNo}score部分依賴：{studentNo,courseNo}studentName{studentNo,courseNo}courseName部分函數(shù)依賴會導致數(shù)據(jù)冗余和插入、刪除、更新異常！傳遞函數(shù)依賴定義5.4

在關系模式r(R)中，R，R，R，且,。若，，則必存在函數(shù)依賴，并稱是傳遞函數(shù)依賴，簡稱傳遞依賴。注意條件：和。與部分依賴一樣，傳遞依賴也可能會導致數(shù)據(jù)冗余及產生各種異常。圖5-7傳遞依賴的依賴圖傳遞函數(shù)依賴舉例[例5.4]

在關系模式SCI(studentNo,classNo,className,institute)中，屬性studentNo決定屬性classNo，屬性classNo決定className和institute。因此，關系模式SCI中存在下列傳遞函數(shù)依賴：studentNo

classNoclassNo

classNameclassNo

institutestudentNo

classNamestudentNo

instituteSCI中存在傳遞依賴studentNoclassName、institute，因此可能導致數(shù)據(jù)冗余、更新異常、插入異常及刪除異常。函數(shù)依賴小結函數(shù)依賴是指關系模式中屬性之間存在的一種約束關系。這種約束關系既可以是現(xiàn)實世界事物或聯(lián)系的屬性之間客觀存在的約束，也可以是數(shù)據(jù)庫設計者根據(jù)應用需求或設計需要強加給數(shù)據(jù)的一種約束。但不論是那種約束，一旦確定，進入數(shù)據(jù)庫中的所有數(shù)據(jù)都必須嚴格遵守。正確了解數(shù)據(jù)的意義及確定屬性之間的函數(shù)依賴關系，對設計一個好的關系模式是十分重要的。平凡/不平凡，完全/非完全，傳遞函數(shù)依賴目錄范式

5.4問題提出

5.1函數(shù)依賴定義5.2函數(shù)依賴理論5.3數(shù)據(jù)庫模式求精

模式分解算法5.65.5函數(shù)依賴集閉包

對于給定關系模式r(R)及其函數(shù)依賴集F，有時只考慮給定的函數(shù)依賴集是不夠的，而需要考慮在r(R)上總是成立的所有函數(shù)依賴。[例5.5]

給定關系模式r(R)=r(A,B,C)及函數(shù)依賴集F={AB,BC}，證明AC成立。

證明：假設對于關系實例r中的任意兩個元組ti,tj,ij，滿足ti[A]=tj[A]。由于存在AB，則可推出ti[B]=tj[B]。又由于BC，則又可推出ti[C]=tj[C]。因此，ti[A]=tj[A]

ti[C]=tj[C]。按定義5.1有AC。證畢。函數(shù)依賴集閉包定義5.5

若給定函數(shù)依賴集F，可以證明其他函數(shù)依賴也成立，則稱這些函數(shù)依賴被F邏輯蘊涵。定義5.6

令F為一函數(shù)依賴集，F(xiàn)邏輯蘊涵的所有函數(shù)依賴組成的集合稱為F的閉包，記為F+。函數(shù)依賴集F的閉包計算方法Armstrong公理的推理規(guī)則32邏輯蘊涵定義F+?示例R(X,Y),F={XY}F+={X，XX，XY，XXY， Y，YY

XY，XYX，XYY，XYXY}Armstrong公理及推論Armstrong公理

自反律(reflexivityrule)：若存在，則有增補律(augmentationrule)：若存在，則有傳遞律(transitivityrule)：若存在且，則有Armstrong公理三個推論合并律(unionrule)：若有且，則有分解律(decompositionrule)：若有，則有和偽傳遞律(pseudotransitivityrule)：若有且，則有34Armstrong公理系統(tǒng)Armstrong公理

X，Y，Z是屬性集，自反律(reflexivity)：若YX，則XY增廣律(augmentation)：若XY，則XZYZ傳遞律(transitivity)：若XY，YZ，則XZ35Armstrong公理系統(tǒng)關于Armstrong公理正確性按函數(shù)依賴定義r是R<U,F>上的任一關系，t，sr}t[X]=s[X]YXt[Y]=s[Y]XY自反律36Armstrong公理系統(tǒng)t[XZ]=s[XZ]t[X]=s[X]XY}t[Y]=s[Y]t[XZ]=s[XZ]t[Z]=s[Z]}t[YZ]=s[YZ]XZYZ增廣律37Armstrong公理系統(tǒng)}XYt[X]=s[X]t[Y]=s[Y]}YZt[Z]=s[Z]XZ傳遞律38Armstrong公理系統(tǒng)由Armstrong公理導出的推理規(guī)則合并律(unionrule)若XY，XZ，則XYZ分解律(decompositionrule)若XY’，Y’=YZ且則XY，XZ偽傳遞律(pseudotransitivityrule)若XY，WYZ，則WXZ39Armstrong公理系統(tǒng)}XY增廣律}XXY合并律}XZ增廣律XYYZ傳遞律XYZ40Armstrong公理系統(tǒng)}ZY’自反律Y’=YZ}Y’Z分解律XY’傳遞律XZ41Armstrong公理系統(tǒng)}XY增廣律}WXWYWYZ傳遞律WXZ偽傳遞律42Armstrong公理系統(tǒng)示例

R<U,F>,U=(A,B,C,G,H,I),F={AB,AC,CGH,CGI,BH},AH？CGHI？AGI？函數(shù)依賴集閉包計算舉例[例5.6]

令r(R)=r(A,B,C,G,H,I)，函數(shù)依賴集F={AB,AC,CGH,CGI,BH}。我們可列出F+中的幾個依賴：由傳遞律可得AH，因為AB且BH；由合并律可得CGHI，因為CGH，CGI；由偽傳遞律可得AGI，因為AC且CGI。還可以使用上述規(guī)則推導出更多的函數(shù)依賴，讀者可自行推導。屬性集閉包如果想要判斷一個給定的函數(shù)依賴是否在函數(shù)依賴集F的閉包中，不用計算F+就可以判斷出來。定義5.7

令r(R)為關系模式，F(xiàn)為函數(shù)依賴集，AR，則稱在函數(shù)依賴集F下由A函數(shù)確定的所有屬性的集合為函數(shù)依賴集F下屬性集A的閉包，記為A+。屬性集閉包的計算算法：

closure:=A;repeatuntil(closure沒有變化)do

foreach

inFdo

if

closureclosure:=closure

圖5-8計算F下A+算法

屬性集閉包計算舉例[例5.7]

r(R)=r(A,B,C,G,H,I)，F(xiàn)={AB,AC,CGH,CGI,BH}，計算(AG)+。

算法第一次循環(huán)的執(zhí)行步驟：

步驟

FD

closure

1．初值AG2．

ABABG3．ACABCG4．CGHABCGH5．CGIABCGHI6．BHABCGHI算法第二次循環(huán)的結果仍為closure=ABCGHI，沒有變化，算法終止。

結果為：closure=ABCGHI。

最后結果為：(AG)+＝ABCGHI。46閉包的計算示例3

R<U,F>,U=(A,B,C,D,E,G),F={AE,BEAG,CEA,GD},計算

所用依賴

AE ABE

BEAG ABEG GD ABEGD =ABEGD計算屬性集閉包的作用計算屬性集閉包的作用可歸納如下：驗證是否在F+中：看是否有

+。判斷是否為r(R)的超碼：計算

+，看其是否包含R的所有屬性。如(AG)+＝ABCGHI，則AG為r(R)的超碼。判斷是否為r(R)的候選碼：若是超碼，可檢驗包含的所有子集的閉包是否包含R的所有屬性。若不存在任何這樣的屬性子集，則是r(R)的候選碼。計算F+。對于任意R，可通過找出+，對任意的S

+，可輸出一個S。判斷屬性集是否為候選碼舉例[例5.8]

r(R)和F見例5.7，判斷AG是否為r(R)的候選碼。例5.7已計算出(AG)+＝ABCGHI,則還要進一步分別計算A+和G+。經計算得，A+=ABCH、G+=G，它們都不包含R的所有屬性。因此，AG為r(R)的候選碼。

對于一個給定的關系模式r(R)及函數(shù)依賴集F，如何找出它的所有候選碼？這是基于函數(shù)依賴理論和范式概念判斷該關系模式是否是“好”模式的基礎；也是對一個“不好”的關系模式進行分解的基礎。

判斷屬性集是否為候選碼給定關系模式r(R)及函數(shù)依賴集F，找出它的所有候選碼的一般步驟如下：

找出函數(shù)依賴集F中在所有函數(shù)依賴右方都沒有出現(xiàn)的屬性集X，屬性集X中的屬性都一定是候選碼中的屬性。找出F中在所有函數(shù)依賴右方出現(xiàn)但左方沒有出現(xiàn)的屬性集Y，屬性集Y中的屬性都不可能是候選碼中的屬性。如果X非空，則基于F計算X+，并開始發(fā)現(xiàn)所有候選碼：如果X+=R，則X是關系r(R)的唯一候選碼；如果X+≠R，則如果X為空，則從F中的每一個函數(shù)依賴u開始(先從函數(shù)依賴左邊是一個屬性的開始)：首先，試著發(fā)現(xiàn)是否能夠通過增加1個屬性與X聯(lián)合起來構成候選碼,例如，若存在R-X-Y，使(X{})+=R，則(X{})是關系r(R)的一個候選碼；繼續(xù)試著增加另一個屬性，若存在R-X-Y-{}，使(X{})+=R，則(X{})是關系r(R)的另一個候選碼；……。記找到的所有屬性的集合為Z，即Z，使(X{})+=R。接下來，還可以試著發(fā)現(xiàn)是否能夠通過增加2個或多個屬性與X聯(lián)合起來構成候選碼，例如,若存在{,}R-X-Y-Z，使(X{,})+=R;則(X{,})也是關系r(R)的一個候選碼；……。如果+=R，則是關系r(R)的一個候選碼；如果+≠R，類似地，試著發(fā)現(xiàn)是否能夠通過增加1個屬性與聯(lián)合起來構成候選碼；再試著發(fā)現(xiàn)是否能夠通過增加2個或多個屬性與聯(lián)合起來構成候選碼。判斷屬性集是否為候選碼舉例[例5.9]

給定關系模式r(R)=r(A,B,C,D)，函數(shù)依賴集F={BC,DA}，找出r(R)的所有候選碼。屬性集BD沒有在函數(shù)依賴的右部出現(xiàn)，故BD為候選碼的一部分；由于(BD)+=BDCA=R，所以BD為關系模式r(R)的唯一候選碼。判斷屬性集是否為候選碼舉例[例5.10]

給定關系模式r(R)=r(A,B,C,D,E)，函數(shù)依賴集F={AB,BCE,EDA}，找出r(R)的所有候選碼。屬性集CD沒有在函數(shù)依賴的右部出現(xiàn)，故X=CD為候選碼的一部分；因(CD)+=CD≠R，故CD不是候選碼；因沒有在函數(shù)依賴右部出現(xiàn)但左部不出現(xiàn)的屬性，故Y=;在集合R-X-Y=ABE中尋找與X聯(lián)合構成候選碼的屬性(集)：({A,CD})+=ACDBE=R，故ACD為候選碼；({B,CD})+=BCDEA=R，故BCD為候選碼；({E,CD})+=ACDBE=R，故ECD為候選碼。因此，關系模式r(R)的候選碼有ACD、BCD和ECD。判斷屬性集是否為候選碼舉例[例5.11]設關系模式R={A,B,C,D,E,G}，函數(shù)依賴集F={B→ADE,A→BE,AC→G,BC→D}，找出r(R)的所有候選碼。因C沒有在函數(shù)依賴的右部出現(xiàn)，故X=C為候選碼的一部分;因C+=C≠R，故C不是候選碼；在函數(shù)依賴右部出現(xiàn)但左部不出現(xiàn)的屬性有DEG,故Y=DEG;在R-X-Y=AB中尋找與X聯(lián)合起來構成候選碼的屬性(集)：({A,C})+=ACBEGD=R，故AC為候選碼；({B,C})+=BCADEG=R，故BC為候選碼。因此，關系模式r(R)的候選碼有AC和BC。

無關屬性定義

定義5.8

給定函數(shù)依賴集F及→F，如果去除或中的某屬性A之后不會改變F+，則稱屬性A是無關的。定義5.9

給定函數(shù)依賴集F及→F，若A，且F

邏輯蘊涵(F-{→}){(-A)}（即(-A)F+），則屬性A在中是無關的（左無關）。定義5.10

給定函數(shù)依賴集F及→F，若A，且(F-{}){(-A)}邏輯蘊涵F

（即→

((F-{}){(-A)})+），則屬性A在中是無關的（右無關）。無關屬性檢測算法設r(R)為關系模式，F(xiàn)是函數(shù)依賴集，則檢測上的屬性A左無關或右無關的算法分別如圖5-9(a)或(b)所示。if

A:＝

-{A};計算F下的閉包+;

if

+A在中是無關的;if

AF':=(F-{}){((-A)};計算F'下的閉包+;

ifA+A在中是無關的;(a)左無關屬性檢測算法

(b)右無關屬性檢測算法

圖5-9無關屬性檢測算法無關屬性檢測舉例[例5.12]

設F＝{AB→CD,A→E,E→C}，證明C在

AB→CD中為無關屬性。證明：

由于C是AB→CD中的右邊屬性，依圖5-9(b)的算法：

計算F'：F'={AB→D,A→E,E→C}；計算F'下(AB)+：(AB)+=ABCDE；判斷C是否屬于(AB)+：CABCDE。因此，C是AB→CD中的無關屬性。證畢。正則覆蓋定義和計算方法定義5.11

正則覆蓋(canonicalcover)Fc是一個依賴集，使得F邏輯蘊涵Fc中的所有依賴，F(xiàn)c邏輯蘊涵F中的所有依賴，而且必須具有下列特性：Fc中的任何函數(shù)依賴都不包含無關屬性；Fc中函數(shù)依賴的左半部都是唯一的，即Fc中不存在兩個依賴1→1和2→2，且1＝2。根據(jù)上述性質，計算F的正則覆蓋Fc分為兩個步驟：合并函數(shù)依賴：將F中所有形如1→1、1→2的函數(shù)依賴合并為1→12，得到新函數(shù)依賴集F'。去除無關屬性：對F'中的每個函數(shù)依賴，依次判斷是否包含無關屬性。若發(fā)現(xiàn)無關屬性，則用去除無關屬性后的函數(shù)依賴代替F'中的原函數(shù)依賴。計算正則覆蓋舉例[例5.13]

考慮關系模式r(R)=r(A,B,C)和函數(shù)依賴集F={A→BC,B→C,A→B,AB→C},計算F的正則覆蓋Fc。第1步，合并函數(shù)依賴：將A→BC和A→B合并為A→BC。F'={A→BC,B→C,AB→C}。第2步，去除無關屬性：對于AB→C，根據(jù)圖5-9(a)的算法可檢測A是無關的。因此，去除無關屬性A后，AB→C變?yōu)锽→C，而B→C已在F'中存在，則F'={B→C,A→BC}。對于B→C，由于其左右兩邊都為單屬性，故不存在無關屬性。對于A→BC，根據(jù)圖5-9(b)的算法可檢測C是無關的。因此，去除無關屬性C后，A→BC變?yōu)锳→B，則F'={B→C,A→B}。F'中的函數(shù)依賴左半部都是唯一的，且都不存在無關屬性，因此Fc={B→C,A→B}。正則覆蓋說明對于正則覆蓋，需做如下說明：可以證明Fc與F具有相同的閉包；Fc不包含無關屬性，每個依賴是最小的，且是必要的；正則覆蓋不一定唯一。

60無損連接分解-模式分解中存在的問題R(A,B,C)ABC112221AB1122BC1221ABC112221∏AB(R)∏BC(R)∏AB(R)∏BC(R)R(A,B,C)ABC111212AB1121BC1112ABC111112211212∏AB(R)∏BC(R)∏AB(R)∏BC(R)有損分解無損分解無損連接分解

定義5.12

給定關系模式r(R)及函數(shù)依賴集F，若r(R)的任意一個滿足函數(shù)依賴集F的關系實例r都有

=r，其中r1(R1)、r2(R2)分別為分解后的子模式，則稱該分解對于F是無損連接的。無損連接分解能夠根據(jù)分解后的關系通過連接還原原來的關系實例。如何判定一分解是否是無損的？62無損連接分解定義 關系模式R<U,F>，U=Ui， ={R1<U1,F1>,R2<U2,F2>,…,Rn<Un,Fn>}是R<U,F>的一個分解，r是R<U,F>的一個關系定義m(r)=∏Ri(r),若對于R<U,F>的任一個關系r，都有r=m(r)，則稱是R<U,F>的一個無損連接分解。那么判別一個分解是無損分解呢？6364無損連接分解算法：（判別一個分解的無損連接性）

U={A1,A2,…,An} ={R1<U1,F1>,R2<U2,F2>,…,Rk<Uk,Fk>} ⒈建立一個n列k行的矩陣TB={Cij|若Aj

Ui,Cij=aj,否則Cij=bij}A1A2…AnU1…CijUk只是檢測，不證明！65無損連接分解 ⒉對F中每一個函數(shù)依賴XY，若TB中存在元組 t1，t2，使得t1[X]=t2[X]，t1[Y]≠t2[Y]，則對每一個Ai

Y： ①若t1[Ai]，t2[Ai]中有一個等于aj，則另一個也改 為aj； ②若①不成立，則取t1[Ai]=t2[Ai]（t2的行號小 于t1）。 66無損連接分解 ⒊反復執(zhí)行⒉，直至： ①TB中出現(xiàn)一行為a1,a2,…,

an的一行。 ②TB不再發(fā)生變化，且沒有一行為a1,…,

an。

在①情況下，為無損分解，否則為有損分解。67無損連接分解示例一：U={A,B,C,D,E},F={ABC,CD,DE} ={(A,B,C),(C,D),(D,E)}ABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5ABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5ABCABCDEABCa1a2a3a4b15CDb21b22a3a4b25DEb31b32b33a4a5CDABCDEABCa1a2a3a4a5CDb21b22a3a4a5DEb31b32b33a4a5DE68無損連接分解示例二：U={A,B,C,D,E}, F={AC,BC,CD,DEC,CEA} ={(A,D),(A,B),(B,E),(C,D,E),(A,E)}ABCDEADa1b12b13a4b15ABa1a2b23b24b25BEb31a2b33b34a5CDEb41b42a3a4a5AEa1b52b53b54a5ACABCDEADa1b12b13a4b15ABa1a2b13b24b25BEb31a2b33b34a5CDEb41b42a3a4a5AEa1b52b13b54a569無損連接分解BCABCDEADa1b12b13a4b15ABa1a2b13b24b25BEb31a2b13b34a5CDEb41b42a3a4a5AEa1b52b13b54a5CDABCDEADa1b12b13a4b15ABa1a2b13a4b25BEb31a2b13a4a5CDEb41b42a3a4a5AEa1b52b13a4a5示例二：U={A,B,C,D,E}, F={AC,BC,CD,DEC,CEA} ={(A,D),(A,B),(B,E),(C,D,E),(A,E)}70無損連接分解DECABCDEADa1b12b13a4b15ABa1a2b13a4b25BEb31a2a3a4a5CDEb41b42a3a4a5AEa1b52a3a4a5CEAABCDEADa1b12b13a4b15ABa1a2b13a4b25BEa1a2a3a4a5CDEa1b42a3a4a5AEa1b52a3a4a5示例二：U={A,B,C,D,E}, F={AC,BC,CD,DEC,CEA} ={(A,D),(A,B),(B,E),(C,D,E),(A,E)}71無損連接分解無損連接分解定義（分解為兩個關系模式） 關系模式R(U)，U1，U2U，U1U2=U，r是R上的一個關系，r1=∏U1(r)，r2=∏U2(r)，若r=r1r2，則稱(r1，

r2)是r的一個無損連接分解。 注：r∏U1(r)∏U2(r)R(A,B,C)ABC112221AB1122BC1221ABC112221∏AB(R)∏BC(R)∏AB(R)∏BC(R)72無損連接分解定理 關系模式R(U)的分解={R1，R2}，則是一個無損連接分解的充要條件是R1∩R2R1R2（或R1∩R2R2R1）成立R1∩R2R1R2R2R1R1a…aa…ab…bR2a…ab…ba…aR1∩R2R1R2R2R1R1a…aa…ab…bR2a…aa…aa…aR1∩R2R1R273無損連接分解－例題R=ABC,F={AB},1={R1(AB),R2(AC)}是否是無損連接分解？R1∩R2=A,R1－R2=B由AB，得到1是無損連接分解2={R1(AB),R2(BC)}是否是無損連接分解？R1∩R2=B,R1－R2=A,R2－R1=CBA,BC均不成立，所以2不是無損連接分解無損連接分解判斷方法定義5.13

給定關系模式r(R)及函數(shù)依賴集F，則將r(R)分解成r1(R1)、r2(R2)的分解是無損連接分解，當且僅當F+包含函數(shù)依賴R1R2→R1或R1R2→R2.即：在F下，R1(R1R2)+或R2(R1R2)+。因此，當一個關系模式分解為兩個關系模式時，該分解為無損連接分解的充要條件是兩分解關系的公共屬性包含r1(R1)的碼或r2(R2)的碼。即：R1R2是關系r1(R1)

或r2(R2)的超碼。無損連接分解判斷舉例[例5.14]

假設關系模式r(R)=r(A,B,C,D,E),F={ABC,CDE,BD,EA}，則可將r(R)進行兩種不同的分解:分解1：r1(R1)=r1(A,

B,

C)，r2(R2)=r2(A,D,E)；分解2：r1(R1)=r1(A,B,C)，r2(R2)=r2(C,D,E)。對于分解1，R1R2＝A，且AR1，故此分解是無損連接分解。而對于分解2，R1R2＝C，且C→R1、C→R2，故此分解不是無損連接分解。保持依賴分解

關系數(shù)據(jù)庫模式分解的另一個目標是保持依賴。定義5.14

給定關系模式r(R)及函數(shù)依賴集F，r1(R1),r2(R2),...,rn(Rn)為r(R)的分解。F在Ri的投影為閉包F+中所有只包含Ri屬性的函數(shù)依賴的集合，記為Fi。即如果在Fi中，則和的所有屬性均在Ri中。定義5.15

稱具有函數(shù)依賴集F的關系模式r(R)的分解r1(R1),r2(R2),...,rn(Rn)為保持依賴分解，當且僅當(F1F2…Fn)+=F+。保持依賴分解判斷舉例[例5.15]

設關系模式r(R)=r(A,B,C)，F(xiàn)={AB,BC}，有兩種分解：r1(R1)=r1(A,

B)、r2(R2)

=r2(B,

C)F1={AB}、F2={BC}該分解保持函數(shù)依賴，因為(F1F2)+=F+。r1(R1)=r1(A,B)、r2(R2)

=r2(A,

C)。F1={AB}、F2={A→C}（注：{A→C}F+）該分解不保持函數(shù)依賴。因為分解后函數(shù)依賴BC被丟失。目錄范式5.4問題提出

5.1函數(shù)依賴定義5.2函數(shù)依賴理論5.3數(shù)據(jù)庫模式求精

模式分解算法5.65.5范式概述基于函數(shù)依賴理論，關系模式可分成第一范式(1NF)第二范式(2NF)第三范式(3NF)Boyce-Codd范式(BCNF)這幾種范式的要求一個比一個嚴格，它們之間的聯(lián)系為：

BCNF

3NF2NF1NF滿足BCNF范式的關系一定滿足3NF范式，滿足3NF范式的關系一定滿足2NF范式，滿足2NF范式的關系一定滿足1NF范式。第一范式(1NF)——碼

定義5.16

如果一關系模式r(R)的每個屬性對應的域值都是不可分的(即原子的)，則稱r(R)屬于第一范式，記為r(R)1NF.第一范式的目標是：將基本數(shù)據(jù)劃分成稱為實體集或表的邏輯單元，當設計好每個實體后，需要為其指定主碼。studentNostudentNamesexbirthdayageaddressclassNoprovincecitystreet圖5-10非規(guī)范化的關系模式studentNostudentNamesexbirthdayageprovincecitystreetclassNo圖5-111NF規(guī)范化后的關系模式第二范式(2NF)——全部是碼

定義5.17

設有一關系模式r(R)，R。若包含在r(R)的某個候選碼中，則稱為主屬性，否則為非主屬性。在SCE關系中，屬性集{studentNo,courseNo}是SCE的唯一候選碼。因此，屬性studentNo和courseNo為主屬性，其余屬性為非主屬性。定義5.18

如果一個關系模式r(R)1NF，且所有非主屬性都完全函數(shù)依賴于r(R)的候選碼，則稱r(R)屬于第二范式，記為r(R)2NF。SCE中存在依賴關系studentNostudentName和courseNocourseName，即非主屬性studentName和courseName部分依賴于SCE的候選碼{studentNo,courseNo}，故SCE2NF。第二范式(2NF)——全部是碼

第二范式的目標：將只部分依賴于候選碼（即依賴于候選碼的部分屬性）的非主屬性移到其他表中。也就是說，在滿足第一范式的實體中，如果有復合候選碼(即多個屬性共同構成的候選碼)，那么所有非主屬性必須依賴于全部的候選碼，不允許依賴于部分的候選碼屬性。即不允許候選碼的一部分對非主屬性起決定作用：全部是碼違背2NF的模式，即存在非主屬性對候選碼的部分依賴，則可能導致例5.1所述的數(shù)據(jù)冗余及異常問題。第二范式(2NF)——全部是碼對于非2NF范式的關系模式，可通過分解進行規(guī)范化，以消除部分依賴。如將關系模式SCE分解為關系模式S、C和E。這樣在每個關系模式中，所有非主屬性對候選碼都是完全函數(shù)依賴，因此都屬于2NF范式。2NF范式雖然消除了由于非主屬性對候選碼的部分依賴所引起的冗余及各種異常，但并沒有排除傳遞依賴。因此，還需要對其進一步規(guī)范化。第三范式(3NF)第三范式的目標：去掉表中不直接依賴于候選碼的非主屬性.定義5.19

如果一個關系模式r(R)2NF，且所有非主屬性都直接函數(shù)依賴于r(R)的候選碼（即不存在非主屬性傳遞依賴于候選碼），則稱r(R)屬于第三范式，記為r(R)3NF.也就是說，在滿足2NF的實體中，非主屬性不能依賴于另一個非主屬性（即非主屬性只能直接依賴于候選碼）總之，所有的非主屬性應該直接依賴于(即不能存在傳遞依賴，這是3NF的要求)全部的候選碼(即必須完全依賴,不能存在部分依賴，這是2NF的要求)。第三范式(3NF)[例5.16]

r(R)=r(A,B,C,D)，函數(shù)依賴集F={AB→C,B→D}。r(R)的候選碼為AB，r(R)2NF?。因為函數(shù)依賴B→D中的決定屬性B只是候選碼的一部分，即D部分依賴于候選碼AB?？蓪(R)分解為r1(R1)=r1(A,B,C)、r2(R2)=r2(B,D)。r1(R1)的候選碼為AB，r2(R2)的候選碼為B。分解得到的r1(R1)和r2(R2)都屬于3NF范式。[例5.17]

r(R)=r(A,B,C)，函數(shù)依賴集F={A→B,B→C}。r(R)的候選碼為A，r(R)2NF，但r(R)3NF。因為函數(shù)依賴B→C中的決定屬性B不是候選碼?？蓪(R)分解為r1(R1)=r1(A,B)、r2(R2)=r2(B,C)。

r1(R1)的候選碼為A，r2(R2)的候選碼為B。則分解得到的r1(R1)和r2(R2)都屬于3NF范式。第三范式(3NF)[例5.18]

r(R)=r(A,B,C,D,E)，函數(shù)依賴集F={AB→C,B→D,C→E}。r(R)的候選碼為AB，r(R)2NF?。因為函數(shù)依賴B→D中的決定屬性B只是候選碼的一部分，即D部分依賴于候選碼AB。

r(R)分解為r1(R1)=r1(A,B,C)、r2(R2)=r2(B,D)、r3(R3)=r3(C,E)r1(R1)的候選碼為AB，r2(R2)的候選碼為B，r3(R3)的候選碼為C。它們都屬于3NF范式。[例5.19]

r(R)=r(A,B,C)，函數(shù)依賴集F={AB→C,C→A}.r(R)的候選碼為AB或BC，r(R)3NF。因為關系模式r(R)沒有非主屬性，也就不可能有非主屬性對候選碼的部分依賴和傳遞依賴。

87BCNF示例STC(S#,T#,C#)，語義：每位老師只教授一門課,每門課有若干教師,某一學生選定某門課,就對應一個固定的教師.T#C#，每位老師只教授一門課（S#，T#）C#（S#，C#）T#，某學生選定一門課，就對應一位老師（S#，T#），（S#，C#）為候選碼。思考

STC3NF？S#T#C#s1t1c1s2t2c2s3t3c2s3t1c1是由Boyce和Codd提出的,比3NF又進了一步,通常認為是修正的第三范式.88S#C#T#S#T#C#C#對碼的傳遞依賴C#對碼的部分依賴89BCNF不良特性插入異常：如果沒有學生選修某位老師的任課，則該老師擔任課程的信息就無法插入刪除異常：刪除學生選課信息，會刪除掉老師的任課信息更新異常：如果老師所教授的課程有所改動，則所有選修該老師課程的學生元組都要做改動數(shù)據(jù)冗余：每位學生都存儲了有關老師所教授的課程的信息癥由： 主屬性對碼的不良依賴S#T#C#s1t1c1s2t2c2s3t3c2s3t1c190BCNF定義關系模式R<U,F>中，對于屬性組X，Y，若XY且YX時X必含有碼，則R<U,F>BCNF

如STC？BCNFSTCBCNF，因為T#

C#，而T#不含有碼改造前：STC(S#,T#,C#)，改造后 將S分解為（S#，T#），（T#，C#）S#T#s1t1s2t2s3t3s3t1T#C#t1c1t2c2t3c291Boyce-Codd范式(BCNF)定義5.20

給定關系模式r(R)及函數(shù)依賴集F，若F+中的所有函數(shù)依賴

(R，R)至少滿足下列條件之一：是平凡函數(shù)依賴(即)；是r(R)的一個超碼(即+包含R的全部屬性)。即起決定作用的屬性必須是超碼！

則稱r(R)屬于Boyce-Codd范式，記為r(R)BCNF。換句話說，在關系模式r(R)中，如果F+中的每一個非平凡函數(shù)依賴的決定屬性集都包含候選碼，則r(R)BCNF。特別說明：為確定r(R)是否滿足BCNF范式，必須考慮F+而不是F中的每個依賴。從函數(shù)依賴角度可得出，一個滿足BCNF的關系模式必然滿足下列結論：（如果

非平凡，則是r(R)的一個超碼）所有非主屬性都完全函數(shù)依賴于每個候選碼；所有主屬性都完全函數(shù)依賴于每個不包含它的候選碼；沒有任何屬性完全函數(shù)依賴于非候選碼的任何一組屬性。BCNF范式排除了：任何屬性(包括主屬性和非主屬性)對候選碼的部分依賴和傳遞依賴；主屬性之間的傳遞依賴。Boyce-Codd范式(BCNF)從函數(shù)依賴角度可得出，一個滿足BCNF的關系模式必然滿足下列結論：（如果

非平凡，則是r(R)的一個超碼）所有非主屬性都完全函數(shù)依賴于每個候選碼；所有主屬性都完全函數(shù)依賴于每個不包含它的候選碼；沒有任何屬性完全函數(shù)依賴于非候選碼的任何一組屬性。BCNF范式排除了：任何屬性(包括主屬性和非主屬性)對候選碼的部分依賴和傳遞依賴；主屬性之間的傳遞依賴。Boyce-Codd范式(BCNF)候選碼A非主屬性1非主屬性2非主屬性k……候選碼BХХХBoyce-Codd范式判斷舉例[例5.20]

r(R)=r(A,B,C)，F(xiàn)={A→B,B→C}。r(R)的候選碼為A，r(R)BCNF，因為函數(shù)依賴B→C中的決定屬性B不是超碼。[例5.21]

r(R)=r(A,B,C)，F(xiàn)={AB→C,C→A}。r(R)的候選碼為AB或BC，r(R)BCNF，因為C→A的決定屬性C不是超碼。[例5.22]

r(R)=r(A,B,C)，F(xiàn)={AB→C,BC→A}。r(R)的候選碼為AB或BC，r(R)BCNF，因為兩個函數(shù)依賴中的決定屬性AB或BC都是r(R)的候選碼。Boyce-Codd范式存在問題對于非BCNF范式的關系模式，可通過分解進行規(guī)范化，以消除部分依賴和傳遞依賴。[例5.20]

(r(R)=r(A,B,C),F={A→B,B→C},候選碼為A)可分解為r1(R1)=r1(A,B)、r2(R2)

=r2(B,C)

(F1={A→B}、F2={B→C}

)或r1(R1)=r1(A,B)、r2(R2)

=r2(A,C)

(F1={A→B}、F2={A→C}

)顯然，這兩種分解得到的r1(R1)和r2(R2)都屬于BCNF范式。但是，后一種分解不是保持依賴分解。因此，滿足BCNF范式的模式分解，可能不是保持依賴分解。第三范式(3NF)——僅僅是碼定義5.21

給定關系模式r(R)及函數(shù)依賴集F，若對F+中的所有函數(shù)依賴→

(R,R)至少滿足下列條件之一：→是平凡函數(shù)依賴(即)；是r(R)的一個超碼(即+包含R的全部屬性)；-中的每個屬性是r(R)的候選碼的一部分(即主屬性)。則稱r(R)屬于第三范式，記為

r(R)3NF。3NF與BCNF范式的區(qū)別在于第3個條件：-中的每個屬性是r(R)的候選碼的一部分。放松之處：允許存在主屬性對候選碼的傳遞依賴和部分依賴。第三范式(3NF)——僅僅是碼定義5.21

給定關系模式r(R)及函數(shù)依賴集F，若對F+中的所有函數(shù)依賴→

(R,R)至少滿足下列條件之一：→是平凡函數(shù)依賴(即)；是r(R)的一個超碼(即+包含R的全部屬性)；-中的每個屬性是r(R)的候選碼的一部分(即主屬性)。則稱r(R)屬于第三范式，記為

r(R)3NF。3NF與BCNF范式的區(qū)別在于第3個條件：-中的每個屬性是r(R)的候選碼的一部分。放松之處：允許存在主屬性對候選碼的傳遞依賴和部分依賴。候選碼C候選碼B候選碼Aabc主屬性的傳遞依賴主屬性的部分依賴第三范式(3NF)——僅僅是碼注意：如果-中的每個屬性是r(R)的候選碼的一部分，那么中也一定包含候選碼的一部分，即不可能全是非主屬性(即中一定包含主屬性)。不妨假設∩

=，→是非平凡函數(shù)依賴，且不存在無關屬性。如果是候選碼，由于→，那么是超碼(包含候選碼)，因此中一定包含主屬性。否則，設是候選碼，有()+=R；由于→，那么()+=R，即是超碼(包含候選碼)

。由于是候選碼，即不能單獨構成候選碼，因此中一定包含主屬性。第三范式(3NF)——僅僅是碼注意：3NF的第3個條件不要求-中的每個屬性必須包含在r(R)的一個候選碼中。因此當r(R)有多個候選碼時，即-中的每個屬性可以包含在r(R)的不同候選碼中?？傊?，非主屬性對候選碼的部分依賴問題在2NF中解決了,而非主屬性對候選碼的傳遞依賴問題由3NF來解決！即不允許非主屬性起決定使用——僅僅是碼。[例5.23]

r(R)=r(A,B,C)，F(xiàn)={AB→C,C→A}。r(R)的候選碼為AB或BC，由[例5.19]和[例5.21]可知，r(R)3NF,但r(R)BCNF。

3NF與BCNF比較BCNF比3NF嚴格。BCNF要求所有的非平凡函數(shù)依賴中的是超碼，而3NF則放松了該約束，允許不是超碼。若關系模式屬于BCNF范式就一定屬于3N