5第2講函數(shù)依賴公理體系-新省公開(kāi)課一等獎(jiǎng)全國(guó)示范課微課金獎(jiǎng)?wù)n件

第2講函數(shù)依賴公理體系講課人：

李朔Email:chn.nj.ls@2024/8/181南曉數(shù)信學(xué)院第1頁(yè)回想以下幾個(gè)主要概念X

YF邏輯蘊(yùn)涵X

YF閉包F＋,普通地有F

F＋。候選鍵2024/8/182南曉數(shù)信學(xué)院第2頁(yè)主要內(nèi)容阿姆斯特朗公理及推論X關(guān)于F閉包及其計(jì)算最小函數(shù)依賴集候選鍵求解方法2024/8/183南曉數(shù)信學(xué)院第3頁(yè)一、阿姆斯特朗公理及推論是一系列推理規(guī)則最早出現(xiàn)在1974年W.W.Armstrong論文里他人于1977年提出改進(jìn)形式F

=X→YF+侯選鍵X→Y在R中是否成立能從F導(dǎo)出全部X→Y推導(dǎo)工具？問(wèn)題引入：2024/8/184南曉數(shù)信學(xué)院第4頁(yè)1、阿姆斯特朗公理設(shè)相關(guān)系模式R(U,F)，U={A1,A2,…,An}是R屬性集，F(xiàn)是R屬性集U上FD集，X、Y、Z、W是U子集。阿姆斯特朗公理為：

A1自反律：若Y

X，則X

YA2增廣律：若X

Y，則XZ

YZA3傳遞律：若X

Y,Y

Z，則X

Z

2024/8/185南曉數(shù)信學(xué)院第5頁(yè)

Armstrong公理是正確。

方法：從函數(shù)依賴定義出發(fā)A1自反律：若Y

X，則X

Y(增廣律,傳遞律證實(shí)類似,P104)證：設(shè)u、v為r任意兩個(gè)元組。若u[X]=v[X]，則u和v在X任何子集上必定相等。由條件Y

X

，所以有：u[Y]=v[Y]，由u、v任意性，并依據(jù)函數(shù)依賴定義，可得X

Y。2、定理5.12024/8/186南曉數(shù)信學(xué)院第6頁(yè)3、阿姆斯特朗公理推論合并規(guī)則：若X

Y且X

Z，則X

YZ(增廣律)

分解規(guī)則：若X

Y，且Z

Y，則X

Z(自反律)

偽傳遞規(guī)則：若X

Y且WY

Z，則WX

Z增廣律傳遞律證：X

YWX→ZWX→WYWY→Z2024/8/187南曉數(shù)信學(xué)院第7頁(yè)例5.2簡(jiǎn)化版P105對(duì)關(guān)系模式R(A,B,C),依賴集F={C->A,AB->C},候選鍵為AB和CB,證實(shí)BC->ABC,AB->ABC證實(shí):已知有C->A,由增廣律可得BC->AB,又已知AB->C,由增廣律可得AB->ABC綜上由傳遞律可得BC->ABC2024/8/188南曉數(shù)信學(xué)院第8頁(yè)作用：將一個(gè)FD分解成若干個(gè)右邊是單屬性FD。用于確定關(guān)系主鍵。4、定理5.2

假如Ai(i=1,…,n)是關(guān)系模式R屬性,則X

A1A2…An成立充分必要條件是X

Ai(i=1,…,n)均成立。

2024/8/189南曉數(shù)信學(xué)院第9頁(yè)二、X關(guān)于F閉包及其計(jì)算例：已知關(guān)系模式R(A,B,C)，其函數(shù)依賴集為F={A→B，B→C}，求函數(shù)依賴集F閉包F+。(P103)

F+=A→

，AB→

，AC→

，ABC→

，B→

，C→

A→A，AB→A，AC→A，ABC→A，B→B，C→CA→B，AB→B，AC→B，ABC→B，B→C，A→C，AB→C，AC→C，ABC→C，B→BC，A→AB，AB→AB，AC→AB，ABC→AB，BC→

，A→AC，AB→AC，AC→AC，ABC→AC，BC→B，A→BC，AB→BC，AC→BC，ABC→BC，BC→C，A→ABC，AB→ABC，AC→ABC，ABC→ABC，BC→BC，2024/8/1810南曉數(shù)信學(xué)院第10頁(yè)1、X關(guān)于F閉包設(shè)相關(guān)系模式R(U,F)和屬性集U={A1,A2,…,An}子集X。則稱全部用阿姆斯特朗公理從F推導(dǎo)出函數(shù)依賴X→Ai屬性Ai組成集合稱為X關(guān)于F閉包，記為XF+，通常簡(jiǎn)記為X+。即

XF+={Ai|用公理從F推出X→Ai}集合元素對(duì)比F+和X+2024/8/1811南曉數(shù)信學(xué)院第11頁(yè)設(shè)相關(guān)系模式R(U，F(xiàn))，U={A1,A2,…,An}是R屬性集，F(xiàn)是R屬性集U上函數(shù)依賴集，X、Y是U子集，則

X

Y能用Armstrong公理從F導(dǎo)出

Y

X＋。該定理把判定X

Y是否能由F依據(jù)Armstrong公理導(dǎo)出問(wèn)題

求出X＋，判定Y是否為X＋子集問(wèn)題。2、定理5.32024/8/1812南曉數(shù)信學(xué)院第12頁(yè)算法5.1

求屬性集X關(guān)于函數(shù)依賴集F閉包X＋輸入：關(guān)系模式R全部屬性集U,U上函數(shù)依賴集F，U子集X。輸出：X關(guān)于F閉包X＋。計(jì)算方法：3、X關(guān)于F閉包X＋計(jì)算2024/8/1813南曉數(shù)信學(xué)院第13頁(yè)（1）X(0)=X。（2）從F中找出滿足條件V

X(i)全部函數(shù)依賴V→W，并把全部V→W中屬性W組成集合記為Z；也即從F中找出那些其決定原因是X(i)子集函數(shù)依賴，并把由全部這么依賴被決定原因組成集合記為Z。（3）若Z

X(i)，則轉(zhuǎn)（5）。(當(dāng)X(i)只決定自己時(shí))（4）不然，X(i+1)=X(i)Z，并轉(zhuǎn)（2）。(傳遞律)（5）停頓計(jì)算，輸出X(i)，即為X+。3、X關(guān)于F閉包X＋計(jì)算（續(xù)）2024/8/1814南曉數(shù)信學(xué)院第14頁(yè)例5.4已知R(U),U={A,B,C,D,E,G}，R上FD集F={AB→C,C→A,BC→D,ACD→B，D→EG,BE→C,CG→BD,CE→AG}，X=BD，求X＋，BD→A是否成立？(1)X（0）=BD。({B}、{D}、{B，D}）(2)X（1）=BDEG（{B}、{D}、{E}、{G}、{B、D}…2n-1個(gè)子集)(3)X（2）=BCDEG(4)X（3）=ABCDEGX＋=ABCDEGA∈BD＋，故BD→A成立4、舉例Z=EGBD=X(0)2024/8/1815南曉數(shù)信學(xué)院第15頁(yè)一個(gè)函數(shù)依賴集F閉包F＋通常包含很多函數(shù)依賴，有些函數(shù)依賴是無(wú)意義，如平凡函數(shù)依賴，還有一些是能夠推導(dǎo)出，即無(wú)關(guān)函數(shù)依賴。假如將每一個(gè)函數(shù)依賴看作是對(duì)關(guān)系一個(gè)約束，要檢驗(yàn)F＋中每一個(gè)函數(shù)依賴對(duì)應(yīng)約束，顯然是一件很繁重任務(wù)。假如能找出一個(gè)與F等價(jià)、包含較少數(shù)目函數(shù)依賴函數(shù)依賴集G，則能夠簡(jiǎn)化此工作。最小函數(shù)依賴集概念由此而提出。三、最小函數(shù)依賴集2024/8/1816南曉數(shù)信學(xué)院第16頁(yè)

定義5.5設(shè)F和G是兩個(gè)函數(shù)依賴集，假如F＋＝G＋，則稱F和G等價(jià)。假如F和G等價(jià)，則稱F覆蓋G，同時(shí)也稱G覆蓋F。1、函數(shù)依賴集等價(jià)與覆蓋2024/8/1817南曉數(shù)信學(xué)院第17頁(yè)定理5.4F＋＝G＋充要條件是F

G＋和G

F＋。F＋=G＋FG＋X→Y全部

F

G＋定理G

F＋F

G＋,F＋

(G＋)+=G＋同理有G

F＋,G＋

(F＋)+=F＋定理意義:P107不計(jì)算F+與G+,只通求Xg+來(lái)判斷F

G＋,XF+來(lái)判斷G

F＋2024/8/1818南曉數(shù)信學(xué)院第18頁(yè)作用：任一函數(shù)依賴集都可轉(zhuǎn)化成由右端只有單一屬性依賴組成集合。該結(jié)論是最小函數(shù)依賴集基礎(chǔ)。推論每一個(gè)函數(shù)依賴集F都被其右端只有一個(gè)屬性函數(shù)依賴組成依賴集G所覆蓋。(即F與G等價(jià),證實(shí)略,P107,注意更正書上印刷錯(cuò)誤)2024/8/1819南曉數(shù)信學(xué)院第19頁(yè)回想以下幾個(gè)主要概念1.Armstrong公理系統(tǒng):自反律,增廣律,傳遞律合并規(guī)則,分解規(guī)則,偽傳遞規(guī)則2.F+和XF+3.函數(shù)依賴集等價(jià)與覆蓋4.最小函數(shù)依賴集2024/8/1820南曉數(shù)信學(xué)院第20頁(yè)滿足以下條件函數(shù)依賴集F稱為最小函數(shù)依賴集。①F中每一個(gè)FD右端都是單個(gè)屬性；②對(duì)F中任何FD:X

A，F(xiàn)-{X

A}不等價(jià)于F；③對(duì)F中任何FD:X

A和X任何真子集Z，(F-{X

A})∪{Z

A}不等價(jià)于F。2、最小函數(shù)依賴集F沒(méi)有多出FD每個(gè)FD左端無(wú)多出屬性2024/8/1821南曉數(shù)信學(xué)院第21頁(yè)求解方法（1）用分解規(guī)則將F中全部函數(shù)依賴分解成右端為單個(gè)屬性函數(shù)依賴；Armstrong公理推論分解規(guī)則：若X

Y，且Z

Y，則X

Z2024/8/1822南曉數(shù)信學(xué)院第22頁(yè)求解方法（續(xù)一）（2）去掉F中冗余函數(shù)依賴對(duì)于F中任一FD：X

Y①G=F-{X

Y}；②求X關(guān)于G閉包XG+；③看XG+是否包含Y。假如XG+包含Y，則在G中邏輯蘊(yùn)涵X

Y，說(shuō)明X

Y是多出函數(shù)依賴，所以F=G；假如X+不包含Y，則保留X

Y。2024/8/1823南曉數(shù)信學(xué)院第23頁(yè)求解方法（續(xù)二）（3）去掉左端多出屬性對(duì)于F中左端是非單屬性函數(shù)依賴（XY

A），假設(shè)要判斷Y是否是多出屬性

②

求X關(guān)于F閉包XF+；

③

假如A不屬于XF+，則X

A不在F+中，說(shuō)明Y不是多出屬性，接著判別X是否是多出屬性；假如A屬于XF+，則說(shuō)明Y是多出屬性，F(xiàn)=G。(①G=(F-{XY

A})∪{X

A}；)2024/8/1824南曉數(shù)信學(xué)院第24頁(yè)AB

C，C

A，BC

D，ACD

B，D

EG，BE

C，CG

BD，CE

AGF=AB

C，C

A，BC

D，ACD

B,D

E,D

G，BE

C，CG

B，CG

D，CE

A,CE

G①F1=例5.5：求函數(shù)依賴集F最小函數(shù)依賴集法1：（步驟一：分解規(guī)則）3、舉例2024/8/1825南曉數(shù)信學(xué)院第25頁(yè)②F21=AB

C，C

A，BC

D，ACD

B,D

E,D

G，BE

C，CG

B，CG

D，CE

A,CE

G①F1=AB

C，C

A，BC

D，ACD

B,D

E，D

G，BE

C，CG

D，CE

A,CE

G3、舉例（續(xù)一）例5.5：求函數(shù)依賴集F最小函數(shù)依賴集(步驟二：去掉F中冗余函數(shù)依賴,看XG+是否包含Y）2024/8/1826南曉數(shù)信學(xué)院第26頁(yè)②F22=AB

C，C

A，BC

D，ACD

B,D

E,D

G，BE

C，CG

D，CE

A,CE

G②F21=AB

C，C

A，BC

D，ACD

B，D

E，D

G，BE

C，CG

D，CE

G3、舉例（續(xù)二）例5.5：求函數(shù)依賴集F最小函數(shù)依賴集(步驟二：去掉F中冗余函數(shù)依賴看XG+是否包含Y

）2024/8/1827南曉數(shù)信學(xué)院第27頁(yè)AB

C，C

A，BC

D，ACD

B，D

E，D

G，BE

C，CG

D，CE

G②F22=③F3=AB

C，C

A，BC

D，CD

B，D

E，D

G，BE

C，CG

D，CE

G3、舉例（續(xù)三）例5.5：求函數(shù)依賴集F最小函數(shù)依賴集步驟三：去掉左端多出屬性X關(guān)于F閉包XF+,看余下屬性是否仍能決定右邊2024/8/1828南曉數(shù)信學(xué)院第28頁(yè)②F21=AB

C，C

A，BC

D，D

E，D

G，BE

C，CG

B，CE

GAB

C，C

A，BC

D，ACD

B,D

E,D

G，BE

C，CG

BCG

D，CE

A,CE

G①F1=3、舉例（續(xù)四）例5.5：求函數(shù)依賴集F最小函數(shù)依賴集法2：（步驟一：分解規(guī)則）步驟二：去掉F中冗余函數(shù)依賴步驟三：去掉左端多出屬性2024/8/1829南曉數(shù)信學(xué)院第29頁(yè)四、候選鍵求解方法1、屬性分類對(duì)于給定關(guān)系R（U）和函數(shù)依賴集F，可將其屬性分為4類：①L類：僅出現(xiàn)在F函數(shù)依賴左部屬性；②R類：僅出現(xiàn)在F函數(shù)依賴右部屬性；③N類：在FFD左右兩邊均未出現(xiàn)屬性；④LR類：在FFD左右兩邊均出現(xiàn)屬性。2024/8/1830南曉數(shù)信學(xué)院第30頁(yè)四、候選鍵求解方法2、快速求解候選鍵一個(gè)充分條件（1）若X是L類屬性，則X必為R某一候選鍵組員；（2）若X是L類屬性，且X＋包含了R全部屬性，則X必為R唯一候選鍵；（3）若X是R類屬性，則X不是任一候選鍵組員；（4）若X是N類屬性，則X必包含在R某一候選鍵中；（5）若X是RN類屬性和L類屬性組成屬性集，且X＋包含了R全部屬性，則X是R唯一候選鍵。2024/8/1831南曉數(shù)信學(xué)院第31頁(yè)四、候選鍵求解方法3、候選鍵普通求解方法①將全部屬性分為L(zhǎng)、R、N和LR四類，并令X代表L和N類，Y代表LR類；②求XF+：若XF+