函数依赖公理体系.ppt

单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,第2讲 函数依赖的公理体系,,主要内容,,阿姆斯特朗公理及推论,,X,关于,F,的闭包及其计算,,最小函数依赖集,,候选键的求解方法,,,一、阿姆斯特朗公理及推论,是一系列推理规则,,最早出现在,1974,年,的论文里,,他人与,1977,年提出改进形式,F,,=X→Y,F,+,侯选键,X→Y,在,R,中是否成立,能从,F,导出的所有,X→Y,推导工具？,问题引入：,,,1,、,阿姆斯特朗,公理,设有关系模式,R(U,F),，,U={A,1,,A,2,,…,A,n,},是,R,的属性集，,F,是,R,的属性集,U,上的,FD,集，,X,、,Y,、,Z,、,W,是,U,的子集阿姆斯特朗,公理为：,,,A1,自反律,：若,Y,,X,，则,X,,Y,,A2,增广律,：若,X,,Y,，则,XZ,,YZ,,A3,传递律,：若,X,,Y,Y,,Z,，则,X,,Z,,,,,Armstrong公理是正确的方法,：,从函数依赖的定义出发,,A1,自反律,：,若,Y,,X,，则,X,,Y,,证：,设,u,、,v,为,r,的任意两个元组。

若,u[X]=v[X],，则,u,和,v,在,X,的任何子集上必然相等由条件,Y,,X,,，所以有：,u[Y]=v[Y],，,,由,u,、,v,的任意性，并根据函数依赖的定义，可得,X,,Y,2,、,定理5.1,,,,3,、,阿姆斯特朗,公理的推论,合并规则,：若,X,,Y,且,X,,Z,，则,X,,YZ,,,分解规则,：若,X,,Y,，且,Z,,Y,，则,X,,Z,,,伪传递规则,：若,X,,Y,且,WY,,Z,，则,WX,,Z,增广律,传递律,证：,X,,Y,WX→Z,WX→WY,WY→Z,,,作用：,将一个,FD,分解成若干个右边是单属性的,FD,用于确定关系的主键4,、,定理,5.2,,如果,A,i,(i=1,…,n),是关系模式,R,的属性,,,则,X,,A,1,A,2,…A,n,成立的充分必要条件是,X,,A,i,(i=,,1,…,n),均成立二、,X,关于,F,的闭包及其计算,例：已知关系模式,R(A,B,C),，其函数依赖集为,F={A→B,，,B→C},，求函数依赖集,F,的闭包,F,+,F,+,=,A→,,，,AB→,,,，,AC→,,,，,ABC→,,,，,B→,,,，,C→,,,A→ A,，,AB→ A,，,AC→ A,，,ABC→ A,，,B→ B,，,C→ C,,A→ 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,，,,,1,、,X,关于,F,的闭包,设有关系模式,R(U,F),和属性集,U={A,1,,A,2,,…,A,n,},的子集,X,。

则称所有用阿姆斯特朗公理从,F,推导出的函数依赖,X,→A,i,的属性,A,i,组成的集合称为,X,关于,F,的闭包，记为,X,F,+,，通常简记为,X,+,即,,,X,F,+,={A,i,|,用公理从,F,推出的,X,→A,i,},集合元素,对比,F,+,和,X,+,,,设有关系模式,R(U,，,F),，,U={A,1,,A,2,,…,A,n,}是R的属性集，F,是,R,的属性集,U,上的函数依赖集，,X,、,Y,是,U,的子集，则,,,X,,Y,能用,Armstrong,公理从,F,导出,,Y,,X,＋,该定理把判定,X,,Y,是否能由,F,根据,Armstrong,公理导出的问题,,,求出,X,＋,，判定,Y,是否为,X,＋,的子集的问题2,、,定理,5.3,,,算法,5.1,,求属性集,X,关于函数依赖集,F,的闭包,X,＋,,输入：,,关系模式,R,的全部属性集,U,U,上的函数依赖集,F,，,U,的子集,X,输出：,,X,关于,F,的闭包,X,＋,计算方法：,,3,、,X,关于,F,的闭包,X,＋,的,计算,,,（,1,）,X,(0),=X,2,）从,F,中找出满足条件,V,,X,(i),的所有函数依赖,V→W,，并把所有的,V→W,中的属性,W,组成的集合记为,Z,；也即从,F,中找出那些其决定因素是,X,(i),的子集的函数依赖，并把由所有这样的依赖的被决定因素组成的集合记为,Z,。

3,）若,Z,,X,(i),，则转（,5,）4,）否则，,X,(i+1),=X,(i),Z,，并转（,2,）5,）停止计算，输出,X,(i),，即为,X,+,3,、,X,关于,F,的闭包,X,＋,的计算（续）,,,,例,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,2)X,（,1,）,=BDEG,,(3)X,（,2,）,=BCDEG,,(4)X,（,3,）,=ABCDEG,X,＋,=ABCDEG,A∈BD,＋,，故,BD→A,成立,4,、举例,,Z=EG BD=X,(0),,,一个函数依赖集,F,的闭包,F,＋,通常包含很多函数依赖，有些函数依赖是无意义的，如平凡的函数依赖，还有一些是可以推导出的，即无关的函数依赖如果将每一个函数依赖看作是对关系的一个约束，要检查,F,＋,中的每一个函数依赖对应的约束，显然是一件很繁重的任务如果能找出一个与,F,等价的、包含较少数目函数依赖的函数依赖集,G,，则可以简化此工作。

最小函数依赖集的概念由此而提出三、最小函数依赖集,,,,定义,5.5,,设,F,和,G,是两个函数依赖集，如果,F,＋,＝,G,＋,，则称,F,和,G,等价如果,F,和,G,等价，则称,F,覆盖,G,，同时也称,G,覆盖,F,1,、,函数依赖集的等价与覆盖,,,定理,5.7,F,＋,＝,G,＋,的充要条件是,F,,G,＋,和,G,,F,＋,F,＋,=,G,＋,F,G,＋,X,→,Y,所有,,F,,G,＋,定理,G,,F,＋,X,→,Y,能否由,G,根据公理导出？,Y,,X,G,+,,？,,,作用：,任一函数依赖集都可转化成由右端只有单一属性的依赖组成的集合该结论是最小函数依赖集的基础推论,每一个函数依赖集,F,都被其,右端只有一个属性,的函数依赖组成的依赖集,G,所覆盖满足下列条件的函数依赖集,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,左端无多余的属性,,,求解方法,（,1,）用分解规则将,F,中的所有函数依赖分解成右端为单个属性的函数依赖；,Armstrong,公理的推论,,分解规则：,若,X,,Y,，且,Z,,Y,，则,X,,Z,,,求解方法（续一）,（,2,）去掉,F,中冗余的函数依赖,,对于,F,中任一,FD,：,X,,Y,,① G = F-{X,,Y},；,,②,求,X,关于,G,的闭包,X,G,+,；,,③,看,X,G,+,是否包含,Y,。

如果,X,G,+,包含,Y,，则在,G,中逻辑蕴涵,X,,Y,，说明,X,,Y,是多余的函数依赖，所以,F=G,；如果,X,+,不包含,Y,，则保留,X,,Y,求解方法,（续二）,（,3,）去掉左端多余的属性,,对于,F,中左端是非单属性的函数依赖（,XY,,A,），假设要判断,Y,是否是多余的属性,,① G = (F-{XY,,A})∪{X,,A},；,,②,求,X,关于,F,的闭包,X,F,+,；,,③,如果,A,不属于,X,F,+,，则,X,,A,不在,F,+,中，说明,Y,不是多余的属性，接着判别,X,是否是多余的属性；如果,A,属于,X,F,+,，则说明,Y,是多余的属性，,F=G,AB,,C,，,C,,A,，,BC,,D,，,,ACD,,B,，,D,,EG,，,BE,,C,，,,CG,,BD,，,CE,,AG,F=,AB,,C,，,C,,A,，,BC,,D,，,ACD,,B,,,D,,E,D,,G,，,BE,,C,，,CG,,B,，,,CG,,D,，,CE,,A,CE,,G,① F,1,=,例,5.5,：求函数依赖集,F,的最小函数依赖集,,,,,法,1,：,3,、举例,,,② F,21,=,AB,,C,，,C,,A,，,BC,,D,，,ACD,,B,,,D,,E,D,,G,，,BE,,C,，,CG,,B,，,,CG,,D,，,CE,,A,CE,,G,① F,1,=,AB,,C,，,C,,A,，,BC,,D,，,ACD,,B,，,D,,E,，,D,,G,，,BE,,C,，,CG,,D,，,CE,,A,CE,,G,3,、举例（续一）,例,5.5,：求函数依赖集,F,的最小函数依赖集,,,② F,22,=,AB,,C,，,C,,A,，,BC,,D,，,ACD,,B,,,D,,E,D,,G,，,BE,,C,，,CG,,D,，,CE,,A,CE,,G,② F,21,=,AB,,C,，,C,,A,，,BC,,D,，,ACD,,B,，,D,,E,，,D,,G,，,BE,,C,，,CG,,D,，,CE,,G,3,、举例（续二）,例,5.5,：求函数依赖集,F,的最小函数依赖集,,,AB,,C,，,C,,A,，,BC,,D,，,ACD,,B,，,D,,E,，,D,,G,，,BE,,C,，,CG,,D,，,CE,,G,② F,22,=,③ F,3,=,AB,,C,，,C,,A,，,BC,,D,，,,CD,,B,，,D,,E,，,D,,G,，,,BE,,C,，,CG,,D,，,CE,,G,3,、举例（续三）,例,5.5,：求函数依赖集,F,的最小函数依赖集,,,② F,21,=,AB,,C,，,C,,A,，,BC,,D,，,,D,,E,，,D,,G,，,BE,,C,，,,CG,,B,，,CE,,G,AB,,C,，,C,,A,，,BC,,D,，,ACD,,B,,,D,,E,D,,G,，,BE,,C,，,CG,,B,,CG,,D,，,CE,,A,CE,,G,① F,1,=,3,、举例（续四）,例,5.5,：求函数依赖集,F,的最小函数依赖集,,法,2,：,,,四、候选键的求解方法,1,、属性分类,,对于给定的关系,R,（,U,）和函数依赖集,F,，可将其属性分为,4,类：,,① L,类：仅出现在,F,的函数依赖,左部,的属性；,,② R,类：仅出现在,F,的函数依赖,右部,的属性；,,③ N,类：在,F,的,FD,左右两边均,未,出现,的属性；,,④ LR,类：在,F,的,FD,左右两边均出现,的属性。

四、候选键的求解方法,2,、快速求解候选键的一个充分条件,,（,1,）若,X,是,L,类属性，则,X,必为,R,的某一候选键的成员；,,（,2,）若,X,是,L,类属性，且,X,＋,包含了,R,的全部属性，则,X,必为,R,的,唯一,候选键；,,（,3,）若,X,是,R,类属性，则,X,不是任一候选键的成员；,,（,4,）若,X,是,N,类属性，则,X,必包含在,R,的某一候选键中；,,（,5,）若,X,是,R,的,N,类属性和,L,类属性组成的属性集，且,X,＋,包含了,R,的全部属性，则,X,是,R,的,唯一,候选键四、候选键的求解方法,3,、候选键的一般求解方法,,① 将所有属性分为,L,、,R,、,N,和,LR,四类，并令,X,代表,L,和,N,类，,Y,代表,LR,类；,,② 求,X,F,+,：若,X,F,+,包含了,R,的全部属性，则,X,是,R,的唯一候选键，转⑧；,,③ 在,Y,中取一属性,A,，并求,(XA),F,+,：若,(XA),F,+,包含了,R,的全部属性，则,XA,为的一个候选键；,,④ 重复③，直到,Y,中的属性依次取完为止；,,⑤ 从,Y,中除去所有已成为主属性的属性,A,；,,,四、候选键的求解方法,3,、候选键的一般求解法,,⑥ 在剩余的属性中依次取两个属性、三个属性，,…,，将其记为集合,B,，并求,(XB),F,+,：若,(XB),F,+,包含了,R,的全部属性，且,自身不包含已求出的候选键,，则,XB,为,R,的一个候选键；,,⑦ 重复⑥，直到,Y,中的属性按⑥的组合依次取完为止；,,⑧ 输出候选键，算法结束。

R的候选键,：,A,、,E,、,BC,和,CD,四、候选键的求解方法,3,、候选键的一般求解法,,例,:,设有关系模式,R,（,A,B,C,D,E,），,R,的函数依赖集,F,＝,{A,,BC,CD,,E,B,,D,E,,A},，求,R,的所有候选键均为,LR,类,,,令,Y=ABCDE,A,+,=ABCDE E,+,=ABCDE,,BC,+,=ABCDE CD,+,=ABCDE,,,,X→Y,是否能从,F,导出,Armstrong,公理,,及推论,小结,Y,X,+,求,X,+,求最小,FD,集,FD,右边,,单属性,无多余,FD,FD,左边,,无多余属性,F,+,=G,+,候选键,L,类、,N,类、,LR,类,,,。