第12講函數(shù)依賴的理論省公開課金獎全國賽課一等獎微課獲獎課件

第5章關(guān)系模式規(guī)范化設計——函數(shù)依賴理論數(shù)據(jù)庫原理與應用

11/53關(guān)系模式規(guī)范化設計所要處理問題什么是“好”關(guān)系數(shù)據(jù)模式怎樣評價一個好關(guān)系數(shù)據(jù)模式怎樣設計一個“好”關(guān)系數(shù)據(jù)模式22/53關(guān)系模式規(guī)范化設計主要內(nèi)容關(guān)系模式設計問題關(guān)系模式規(guī)范化基本概念和理論關(guān)系模式分解理論基礎(chǔ)和算法33/53回顧1NF2NF3NFBCNF去除非主屬性對于候選鍵部分函數(shù)依賴去除非主屬性對于候選鍵傳遞函數(shù)依賴去除主屬性對于候選鍵部分和傳遞函數(shù)依賴去除不被候選鍵所蘊涵非平凡多值依賴4NF－－－－消除決定原因非碼非平凡函數(shù)依賴44/53理論研究必要性對于應用所表示語義用一組函數(shù)依賴是否能充分表示模式屬性間約束關(guān)系，即得到一個給定關(guān)系模式完整函數(shù)依賴集F？能否將完整函數(shù)依賴集F縮小到一個可管理范圍?即找到一個遠遠小于F集合T，蘊含集合F全部函數(shù)依賴，則DBMS只要實現(xiàn)函數(shù)依賴集T，函數(shù)依賴集F中全部函數(shù)依賴便會自動實現(xiàn)。函數(shù)依賴理論55/53主要內(nèi)容Armstrong公理邏輯蘊含函數(shù)依賴集F閉包F+Armstrong公理推理規(guī)則屬性集閉包函數(shù)依賴集等價和最小函數(shù)依賴集候選碼及其求解方法函數(shù)依賴理論66/53【例】設相關(guān)系模式R（A，B，C），及其函數(shù)依賴集F={A→B，B→C}，判斷A→C是否成立。Armstrong公理解：對于關(guān)系模式R任一實例r任意元組ti、tj，i≠j，若ti[A]=tj[A]，依據(jù)函數(shù)依賴定義由A→B可推出ti[B]=tj[B]又由B→C可推出ti[C]=tj[C]所以，若ti[A]=tj[A]，可推出ti[C]=tj[C]依據(jù)函數(shù)依賴定義，則可得出A→C。77/53邏輯蘊含設F是關(guān)系模式R上函數(shù)依賴集，X→Y是R上一個函數(shù)依賴，若對于R每個滿足F關(guān)系r也滿足X→Y，則稱F邏輯蘊含X→Y記為：F┝X→Y。Armstrong公理88/53【例】R(學生學號，學生姓名，所在系，系主任，課程名稱，成績}，

F={學生學號→學生姓名，學生學號→所在系，所在系→系主任，（學生學號，課程名稱）→成績}Armstrong公理邏輯蘊含99/53【例】R(學生學號，學生姓名，所在系，系主任，課程名稱，成績}

F={學生學號→學生姓名，學生學號→所在系，所在系→系主任，（學生學號，課程名稱）→成績}Armstrong公理邏輯蘊含學生學號→學生學號,學生學號→系主任（學生學號，所在系）→學生學號（學生學號，所在系）→所在系（學生學號，課程名稱）→所在系（學生學號，所在系）→系主任（學生學號，課程名稱）→(學生學號，學生姓名，所在系，系主任，課程名稱，成績)1010/53函數(shù)依賴集F閉包F+F邏輯蘊含全部函數(shù)依賴集合稱為函數(shù)依賴集F閉包，并記為F+F+={X→Y│F┝X→Y}Armstrong公理1111/53Armstrong公理推理規(guī)則經(jīng)過推理規(guī)則，能夠從給定函數(shù)依賴中推出其所蘊含新函數(shù)依賴。假設U為關(guān)系模式R屬性集，F(xiàn)是U上函數(shù)依賴集，X、Y、Z是U任意子集，并采取把子集X、Y并集記為XY方式，對關(guān)系模式R<U，F(xiàn)>來說有以下推理規(guī)則：基本規(guī)則（3條）擴充規(guī)則（3條）Armstrong公理1212/53Armstrong公理推理規(guī)則基本規(guī)則Al.自反律（Reflexivity）

若Y

X

U，則X→Y為F所蘊含。A2.增廣律（Augmentation）若X→Y為F所蘊含，且Z

U，則XZ→YZ為F所蘊含。A3.傳遞律（Transitivity）若X→Y及Y→Z為F所蘊含，則X→Z為F所蘊含。Armstrong公理1313/53Armstrong公理推理規(guī)則擴充規(guī)則

合并規(guī)則由X→Y，X→Z，有X→YZ。（A2，A3）

偽傳遞規(guī)則由X→Y，WY→Z，有XW→Z。（A2，A3）

分解規(guī)則由X→Y及Z

Y，有X→Z。（A1，A3）Armstrong公理1414/53Armstrong公理推理規(guī)則依據(jù)合并規(guī)則和分解規(guī)則：引理1：

X→A1A2…Ak

成立充分必要條件是

X→Ai成立（i=l，2，…，k）Armstrong公理1515/53Armstrong公理推理規(guī)則Armstrong公理【例】設相關(guān)系R，它屬性集U={A,B,C,D,E,F}，R滿足以下函數(shù)依賴：

F={A→BC,B→E,CD→EF}，試證AD→F

證實：∵A→BC（已知）∴AD→BCD（增廣律）∵BCD→CD（自反律）∵CD→EF（已知）∴BCD→EF（傳遞律）∴AD→EF（傳遞律）∴AD→F（分解規(guī)則）1616/53Armstrong公理有效性從F中已經(jīng)有函數(shù)依賴關(guān)系利用Armstrong公理推出每一個函數(shù)依賴X→Y∈F+Armstrong公理完備性給定函數(shù)依賴集F,該函數(shù)依賴集所蘊含函數(shù)依賴，即F+中每一個函數(shù)依賴都能夠利用Armstrong公理推導出來。Armstrong公理推出全部函數(shù)依賴為真能夠推出全部函數(shù)依賴1717/53函數(shù)依賴集F閉包F+

Armstrong公理

【例】計算函數(shù)依賴集F={A→B,B→C}閉包F+

F中全部函數(shù)依賴都是其閉包中元素，即：A→B∈F+B→C∈F+依據(jù)自反規(guī)則，下述函數(shù)依賴(平凡)也是其閉包中元素A→AB→BC→CAB→AAB→BAB→ABAC→AAC→C

AC→ACBC→BBC→CBC→BCABC→A

ABC→B

ABC→CABC→ABABC→ACABC→BCABC→ABC1818/53函數(shù)依賴集F閉包F+Armstrong公理

【例】計算函數(shù)依賴集F={A→B,B→C}閉包F+

A→B,B→C及傳遞規(guī)則：A→C

A→B,A→C及合并規(guī)則：A→BC

A→B及增廣規(guī)則：A→ABAC→BCAC→ABC

B→C及增廣規(guī)則：AB→ACB→BCAB→ABC

A→C及增廣規(guī)則：A→ACAB→BC

A→BC及增廣規(guī)則：A→ABC

AB→B,B→C及傳遞規(guī)則：AB→C

AC→A,A→B及傳遞規(guī)則：AC→B……1919/53屬性集閉包設F是屬性集U上一組函數(shù)依賴，X

U，則屬性集X關(guān)于函數(shù)依賴集F閉包XＦ＋定義為：XF+={Ai|Ai

U且X→Ai可由F經(jīng)Armstrong公理導出}

即XF+={Ai|X→Ai∈F+，Ai

U}

XF+就是可由函數(shù)依賴集F經(jīng)Armstrong公理導出全部函數(shù)依賴于屬性集X全部屬性集合。

Armstrong公理2020/53屬性集閉包引理1：

X→A1A2…Ak

成立充分必要條件是

X→Ai成立（i=l，2，…，k）Armstrong公理引理2：

設F為屬性集U上一組函數(shù)依賴，X、Y

U，X→Y能由F依據(jù)Armstrong公理導出充分必要條件是Y

XF+2121/53屬性集閉包引理2：設F為屬性集U上一組函數(shù)依賴，X、Y

U，X→Y能由F依據(jù)Armstrong公理導出充分必要條件是Y

XF+Armstrong公理用途：將判定X→Y是否能由F依據(jù)Armstrong公理導出問題，就轉(zhuǎn)化為求出XF+，判定Y是否為XF+子集問題。2222/53屬性集閉包

Armstrong公理算法1

求XF+一個算法。輸入：屬性集X和函數(shù)依賴集F。輸出：XF+算法：XF+:=X;repeatoldXF+:=XF+;foreachfunctionaldependencyY→ZinFdoifY

XF+thenXF+:=XF+∪Z;until(oldXF+=XF+）2323/53屬性集閉包

Armstrong公理【例】設F={(f1)B→CD,(f2)AD→E,(f3)B→A}，計算{B}F+

解：{B}F+

={B}第一遍循環(huán)

1）X={B}F

+={B}2）f1決定原因是{B}F+一個子集，所以{B}F+={B}F+∪{C,D}={B,C,D}3）f2決定原因不是{B}F+子集,所以f2不影響此次循環(huán)計算結(jié)果4）f3決定原因是{B}F+一個子集，所以{B}F+={B}F+∪{A}={A,B,C,D}5）X≠{B}F+,返回開始執(zhí)行第二遍循環(huán)2424/53屬性集閉包

Armstrong公理【例】設F={(f1)B→CD,(f2)AD→E,(f3)B→A}，計算{B}F+

第二遍循環(huán)1）X={B}F+={A,B,C,D}2）f1、f2、f3決定原因均是{B}F+子集,所以{B}F+={B}F+∪{C,D}∪{A}∪{E}={A,B,C,D,E}3）X≠{B}F+,返回開始執(zhí)行第三遍循環(huán)2525/53屬性集閉包

Armstrong公理【例】設F={(f1)B→CD,(f2)AD→E,(f3)B→A}，計算{B}F+第三遍循環(huán)

1）X={B}F+={A,B,C,D,E}2）F中全部函數(shù)依賴都已處理過（其依賴原因都已經(jīng)被并入到{B}F+中）3）所以在此次循環(huán)中X={B}F+，算法執(zhí)行結(jié)束返回結(jié)果{B}F+=ABCDE2626/53屬性集閉包

Armstrong公理【例】F={A→BC，E→CF，B→E，CD→EF}，求(AB)F+解：X（0）=AB;∵A→BC,B→E，∴X（1）=AB∪BC∪E=ABCE又∵A→BC、B→E和E→CF∴X（2）=ABCE∪BC∪E∪CF=ABCEF又∵A→BC、B→E、E→CF，則X（3）=ABCEF∪BC∪E∪CF=ABCEFX（3）=X（2）

∴(AB)F+=ABCEF2727/53函數(shù)依賴集等價和最小函數(shù)依賴集定義：設F、G為兩個函數(shù)依賴集，若F+=G+，則稱F和G是等價，也可稱F和G相互覆蓋。

引理：

F+=G+充分必要條件是F?G+，G?F+。Armstrong公理

要判定F?G+

，只需逐一對F中函數(shù)依賴X→Y，考查Y是否屬于XＧ＋就行了。2828/53函數(shù)依賴集等價和最小函數(shù)依賴集定義：

函數(shù)依賴集F當且僅當滿足以下條件時，稱為最小函數(shù)依賴集，或極小函數(shù)依賴集，或最小覆蓋。1）F中每個函數(shù)依賴右部為單一屬性。（右部不可約）2）F中不存在這么函數(shù)依賴X→A，使得F-{X→A}與F等價。3）F中不存在這么函數(shù)依賴X→A，使得Z?X，且F-{X→A}∪{Z→A}與F等價。（左部不可約）Armstrong公理引理：

任一函數(shù)依賴集F總能夠為一右部恒為單屬性函數(shù)依賴集所覆蓋。2929/53函數(shù)依賴集等價和最小函數(shù)依賴集定理：

每一個函數(shù)依賴集F都等價于一個最小函數(shù)依賴集Fm。Armstrong公理3030/53函數(shù)依賴集等價和最小函數(shù)依賴集Armstrong公理進行結(jié)構(gòu)性證實：

1）對F中每個函數(shù)依賴X→Y，若Y=A1A2…Ak，k≥2，則用{X→Aj|j=1,2,…,k}來取代X→Y。2）對F中每個函數(shù)依賴X→A，令G=F-{X→A}，若A∈XG+

，說明X→A為F-{X→A}所蘊含，F(xiàn)與F-{X→A}等價，則從F中去掉此函數(shù)依賴X→A。3）對F中每個函數(shù)依賴X→A，設X=B1B2…Bk，對每個Bi（i=1,2,…,k）若A∈(X-Bi)F+

，說明(X-Bi)→A為F所蘊含，函數(shù)依賴X→A是左部可約，F(xiàn)與F-{X→A}∪{(X-Bi)→A}等價，則以X-Bi取代X。3131/53Armstrong公理函數(shù)依賴集等價和最小函數(shù)依賴集【例】設F={A→BC,B→AC,C→A},求Fm。1)函數(shù)依賴右邊屬性單一化

F={A→B,A→C,B→A,B→C,C→A}2)去掉冗余函數(shù)依賴判斷A→B是否冗余：G1={A→C,B→A,B→C,C→A}AＧ1＋=AC,B不屬于AＧ1

＋，A→B不冗余；判斷A→C是否冗余：G2={A→B,B→A,B→C,C→A}AＧ2

＋=ABC，C∈AＧ2

＋，A→C冗余

F={A→B,B→A,B→C,C→A}；3232/53Armstrong公理函數(shù)依賴集等價和最小函數(shù)依賴集【例(續(xù))】設F={A→BC,B→AC,C→A},求Fm。判斷B→A是否冗余：G3={A→B,B→C,C→A}BＧ3

＋=ABC，A∈BＧ3

＋，B→A冗余

F={A→B,B→C,C→A}；判斷B→C是否冗余：G4={A→B,C→A}

BＧ4

＋=B，C不屬于BＧ4

＋，B→C不冗余；判斷C→A是否冗余：G5={A→B,B→C}

CＧ5

＋=C，A不屬于CＧ5

＋，C→A不冗余。

3333/53Armstrong公理函數(shù)依賴集等價和最小函數(shù)依賴集【例(續(xù))】設F={A→BC,B→AC,C→A},求Fm。

3)因為例中函數(shù)依賴決定原因均為單屬性，因而不需要第三步檢驗，上述結(jié)果就是最小函數(shù)依賴集。

Fm＝{A→B,B→C,C→A}3434/53Armstrong公理函數(shù)依賴集等價和最小函數(shù)依賴集【例】函數(shù)依賴集F={AB→C,A→B,B→A}，求Fm。解：1）全部函數(shù)依賴右部均為單屬性，此步完成。

2）去掉冗余函數(shù)依賴，按前例方法，經(jīng)過檢驗，函數(shù)依賴集仍為F；

3）去掉各函數(shù)依賴左部冗余屬性。

本題只需考慮AB→C。3535/53Armstrong公理函數(shù)依賴集等價和最小函數(shù)依賴集【例】函數(shù)依賴集F={AB→C,A→B,B→A}，求Fm。解：方法1：在決定原因中去掉B,若C∈AF+,則以A→C代替AB→C。求得AF+＝ABC,∵C∈AF+,∴Fm＝{A→C,A→B,B→A};方法2：在決定原因中去掉A,若C∈BF+,則以B→C代替AB→C。求得BF+＝ABC,∵C∈BF+

∴Fm＝{B→C,A→B,B→A};最小函數(shù)依賴集不是唯一3636/53主要內(nèi)容Armstrong公理邏輯蘊含函數(shù)依賴集F閉包F+

Armstrong公理推理規(guī)則屬性集閉包函數(shù)依賴集等價和最小函數(shù)依賴集候選鍵及其求解方法

函數(shù)依賴理論3737/53候選鍵概念在關(guān)系模式R（U，F(xiàn)）中，假如屬性集K滿足KU，K為關(guān)系模式R候選鍵。

候選鍵及其求解方法怎樣判斷？3838/53候選鍵求解方法方法一：在關(guān)系模式R（U，F(xiàn)）中，K

U，利用Armstrong公理中推導規(guī)則，從已知函數(shù)依賴集F中推導得到以下函數(shù)依賴關(guān)系，則K為候選鍵。

K→U，且不存在K真子集K’→U候選鍵及其求解方法3939/53【例1】R(A,B,C,D)，F(xiàn)={B→D,AB→C}，求解R候選鍵。候選碼及其求解方法解：由B→D利用增廣規(guī)則可得：AB→AD………….(1)

由(1),AB→C及合并規(guī)則可得:AB→ACD…………(2)

由(2)利用增廣規(guī)則可得：AB→ABCD因為不存在A→ABCD和B→ABCD，則AB為候選鍵。AB是否是唯一候選鍵？4040/53候選鍵求解方法方法二：在關(guān)系模式R（U，F(xiàn)）中，K

U，依據(jù)候選鍵定義及屬性集閉包概念，假如K滿足下面兩個條件，則K為候選鍵：KF+=U對于K任意一個真子集K’，都有K’F

+≠U

候選碼及其求解方法4141/53【例1】R(A,B,C,D)，F(xiàn)={B→D,AB→C}，求解R候選鍵。候選碼及其求解方法解：驗證方法一候選鍵是否是AB，因為：{A}F+={A}≠{A,B,C,D}{B}F+={B,D}≠{A,B,C,D}{AB}F+={A,B,C,D}

所以AB是關(guān)系模式R一個候選鍵。AB是否是唯一候選鍵？4242/53【例2】設相關(guān)系模式R(U,F)，U={A,B,C,D}，F(xiàn)={A→B，B→C}，求解R全部候選碼。候選碼及其求解方法解：

AF+={ABC},BF+={BC},CF+={C},DF+={D}(AB)F+=(AC)F+={ABC},(AD)F+={ABCD},

(BC)F+={BC},(BD)F+={BCD},(CD)F+={CD}(ABC)F+={ABC},(BCD)F+={BCD}

(ACD)F+=(ABD)F+={ABCD}

故R只有一個候選碼AD4343/53算法：尋找關(guān)系模式R(U,F)某一候選鍵K候選碼及其求解方法1.setK:=U;2.foreachattributeAinK{compute(K–A)F+;if(K–A)F+containsalltheattributesinU,then{setK:=K–{A};}}4444/53【例2】設相關(guān)系模式R(U,F)，U={A,B,C,D}，F(xiàn)={A→B，B→C}，求解R全部候選碼。候選碼及其求解方法解：

K={A,B,C,D}∵{K–A}F+={B,C,D}≠U∴該候選鍵中必定含有屬性A∵{K–B}F+={A,B,C,D}=U∴K=K–B={A,C,D}∵{K–C}F+={A,B,C,D}=U∴K=K–C={A,D}∵{K–D}F+={A,B,C}≠U∴該候選鍵中必定含有屬性D最終得到該關(guān)系候選鍵{A,D}AD是否是唯一候選鍵？4545/53【例3】利用算法尋找候選鍵。模式R(U,F)，U={A,B,C,D}，F(xiàn)={A→C,CD→B}。候選碼及其求解方法解：K={A,B,C,D}∵{K–A}F+={B,C,D}≠U∴該候選鍵中必定含有屬性A∵{K–B}F+={A,B,C,D}=U∴K=K–B={A,C,D}∵{K–C}F+={A,B,C,D}=U∴K=K–C={A,B,D}∵{K–D}F+={A,C}≠U∴該候選鍵中必定含有屬性D最終得到該關(guān)系一個候選鍵{A,D}