5第2讲函数依赖公理体系-新省公开课一等奖全国示范课微课金奖课件

第2讲函数依赖公理体系讲课人：

李朔Email:chn.nj.ls@2024/8/181南晓数信学院第1页回想以下几个主要概念X

YF逻辑蕴涵X

YF闭包F＋,普通地有F

F＋。候选键2024/8/182南晓数信学院第2页主要内容阿姆斯特朗公理及推论X关于F闭包及其计算最小函数依赖集候选键求解方法2024/8/183南晓数信学院第3页一、阿姆斯特朗公理及推论是一系列推理规则最早出现在1974年W.W.Armstrong论文里他人于1977年提出改进形式F

=X→YF+侯选键X→Y在R中是否成立能从F导出全部X→Y推导工具？问题引入：2024/8/184南晓数信学院第4页1、阿姆斯特朗公理设相关系模式R(U,F)，U={A1,A2,…,An}是R属性集，F是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南晓数信学院第5页

Armstrong公理是正确。

方法：从函数依赖定义出发A1自反律：若Y

X，则X

Y(增广律,传递律证实类似,P104)证：设u、v为r任意两个元组。若u[X]=v[X]，则u和v在X任何子集上必定相等。由条件Y

X

，所以有：u[Y]=v[Y]，由u、v任意性，并依据函数依赖定义，可得X

Y。2、定理5.12024/8/186南晓数信学院第6页3、阿姆斯特朗公理推论合并规则：若X

Y且X

Z，则X

YZ(增广律)

分解规则：若X

Y，且Z

Y，则X

Z(自反律)

伪传递规则：若X

Y且WY

Z，则WX

Z增广律传递律证：X

YWX→ZWX→WYWY→Z2024/8/187南晓数信学院第7页例5.2简化版P105对关系模式R(A,B,C),依赖集F={C->A,AB->C},候选键为AB和CB,证实BC->ABC,AB->ABC证实:已知有C->A,由增广律可得BC->AB,又已知AB->C,由增广律可得AB->ABC综上由传递律可得BC->ABC2024/8/188南晓数信学院第8页作用：将一个FD分解成若干个右边是单属性FD。用于确定关系主键。4、定理5.2

假如Ai(i=1,…,n)是关系模式R属性,则X

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

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

2024/8/189南晓数信学院第9页二、X关于F闭包及其计算例：已知关系模式R(A,B,C)，其函数依赖集为F={A→B，B→C}，求函数依赖集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南晓数信学院第10页1、X关于F闭包设相关系模式R(U,F)和属性集U={A1,A2,…,An}子集X。则称全部用阿姆斯特朗公理从F推导出函数依赖X→Ai属性Ai组成集合称为X关于F闭包，记为XF+，通常简记为X+。即

XF+={Ai|用公理从F推出X→Ai}集合元素对比F+和X+2024/8/1811南晓数信学院第11页设相关系模式R(U，F)，U={A1,A2,…,An}是R属性集，F是R属性集U上函数依赖集，X、Y是U子集，则

X

Y能用Armstrong公理从F导出

Y

X＋。该定理把判定X

Y是否能由F依据Armstrong公理导出问题

求出X＋，判定Y是否为X＋子集问题。2、定理5.32024/8/1812南晓数信学院第12页算法5.1

求属性集X关于函数依赖集F闭包X＋输入：关系模式R全部属性集U,U上函数依赖集F，U子集X。输出：X关于F闭包X＋。计算方法：3、X关于F闭包X＋计算2024/8/1813南晓数信学院第13页（1）X(0)=X。（2）从F中找出满足条件V

X(i)全部函数依赖V→W，并把全部V→W中属性W组成集合记为Z；也即从F中找出那些其决定原因是X(i)子集函数依赖，并把由全部这么依赖被决定原因组成集合记为Z。（3）若Z

X(i)，则转（5）。(当X(i)只决定自己时)（4）不然，X(i+1)=X(i)Z，并转（2）。(传递律)（5）停顿计算，输出X(i)，即为X+。3、X关于F闭包X＋计算（续）2024/8/1814南晓数信学院第14页例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个子集)(3)X（2）=BCDEG(4)X（3）=ABCDEGX＋=ABCDEGA∈BD＋，故BD→A成立4、举例Z=EGBD=X(0)2024/8/1815南晓数信学院第15页一个函数依赖集F闭包F＋通常包含很多函数依赖，有些函数依赖是无意义，如平凡函数依赖，还有一些是能够推导出，即无关函数依赖。假如将每一个函数依赖看作是对关系一个约束，要检验F＋中每一个函数依赖对应约束，显然是一件很繁重任务。假如能找出一个与F等价、包含较少数目函数依赖函数依赖集G，则能够简化此工作。最小函数依赖集概念由此而提出。三、最小函数依赖集2024/8/1816南晓数信学院第16页

定义5.5设F和G是两个函数依赖集，假如F＋＝G＋，则称F和G等价。假如F和G等价，则称F覆盖G，同时也称G覆盖F。1、函数依赖集等价与覆盖2024/8/1817南晓数信学院第17页定理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不计算F+与G+,只通求Xg+来判断F

G＋,XF+来判断G

F＋2024/8/1818南晓数信学院第18页作用：任一函数依赖集都可转化成由右端只有单一属性依赖组成集合。该结论是最小函数依赖集基础。推论每一个函数依赖集F都被其右端只有一个属性函数依赖组成依赖集G所覆盖。(即F与G等价,证实略,P107,注意更正书上印刷错误)2024/8/1819南晓数信学院第19页回想以下几个主要概念1.Armstrong公理系统:自反律,增广律,传递律合并规则,分解规则,伪传递规则2.F+和XF+3.函数依赖集等价与覆盖4.最小函数依赖集2024/8/1820南晓数信学院第20页满足以下条件函数依赖集F称为最小函数依赖集。①F中每一个FD右端都是单个属性；②对F中任何FD:X

A，F-{X

A}不等价于F；③对F中任何FD:X

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

A})∪{Z

A}不等价于F。2、最小函数依赖集F没有多出FD每个FD左端无多出属性2024/8/1821南晓数信学院第21页求解方法（1）用分解规则将F中全部函数依赖分解成右端为单个属性函数依赖；Armstrong公理推论分解规则：若X

Y，且Z

Y，则X

Z2024/8/1822南晓数信学院第22页求解方法（续一）（2）去掉F中冗余函数依赖对于F中任一FD：X

Y①G=F-{X

Y}；②求X关于G闭包XG+；③看XG+是否包含Y。假如XG+包含Y，则在G中逻辑蕴涵X

Y，说明X

Y是多出函数依赖，所以F=G；假如X+不包含Y，则保留X

Y。2024/8/1823南晓数信学院第23页求解方法（续二）（3）去掉左端多出属性对于F中左端是非单属性函数依赖（XY

A），假设要判断Y是否是多出属性

②

求X关于F闭包XF+；

③

假如A不属于XF+，则X

A不在F+中，说明Y不是多出属性，接着判别X是否是多出属性；假如A属于XF+，则说明Y是多出属性，F=G。(①G=(F-{XY

A})∪{X

A}；)2024/8/1824南晓数信学院第24页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：求函数依赖集F最小函数依赖集法1：（步骤一：分解规则）3、举例2024/8/1825南晓数信学院第25页②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、举例（续一）例5.5：求函数依赖集F最小函数依赖集(步骤二：去掉F中冗余函数依赖,看XG+是否包含Y）2024/8/1826南晓数信学院第26页②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、举例（续二）例5.5：求函数依赖集F最小函数依赖集(步骤二：去掉F中冗余函数依赖看XG+是否包含Y

）2024/8/1827南晓数信学院第27页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、举例（续三）例5.5：求函数依赖集F最小函数依赖集步骤三：去掉左端多出属性X关于F闭包XF+,看余下属性是否仍能决定右边2024/8/1828南晓数信学院第28页②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、举例（续四）例5.5：求函数依赖集F最小函数依赖集法2：（步骤一：分解规则）步骤二：去掉F中冗余函数依赖步骤三：去掉左端多出属性2024/8/1829南晓数信学院第29页四、候选键求解方法1、属性分类对于给定关系R（U）和函数依赖集F，可将其属性分为4类：①L类：仅出现在F函数依赖左部属性；②R类：仅出现在F函数依赖右部属性；③N类：在FFD左右两边均未出现属性；④LR类：在FFD左右两边均出现属性。2024/8/1830南晓数信学院第30页四、候选键求解方法2、快速求解候选键一个充分条件（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南晓数信学院第31页四、候选键求解方法3、候选键普通求解方法①将全部属性分为L、R、N和LR四类，并令X代表L和N类，Y代表LR类；②求XF+：若XF+