S6.02 Armstrong公理体系
1 §6.02 Armstrong公理体系
● ·产生：为从已知的相关性集合F, 推出F+的其它相关性.人们总结 了很多推理规则。1974年， w.w.Armstrong!归纳建立了函数相关性推理系， 叫Armstrong公理体系。 一.FD公理体系 ·把关系记为R(U,F) 其中U一R的属性集，F一U上的一个函 数依赖集，有如下三条函数相关性公理 2
2 • 产生: 为从已知的相关性集合F, 推出F +的其它相关性.人们总结 了很多推理规则。1974年, w.w.Armstrong归纳建立了函数相关性推理系， 叫 Armstrong公理体系。 一.FD公理体系 • 把关系记为R ( U,F ) 其中 U — R 的属性集 , F — U上的一个函 数依赖集.有如下三条函数相关性公理 :
公理一：自反性公理 (Reflexivity) 若YcXcU则X一Y 证明：因YcX,令Z=X-Y,令Yz表示(YUz), 于是：=YZ。设r为框架R的任一具体关系， t、s为r的两个元组 因：t[X]=t[YZ]=t[Y]t[Z] s [X]=s [YZ]=s [Y]s [Z] 若t[X]=s[X]时，必有t[Y]=s[Y] 即 YcXU时，X一Y。 证毕
3 公理一 : 自反性公理 (Reflexivity) 若YXU 则 X Y 证明 : 因YX , 令Z=X-Y,令YZ表示 (YZ)， 于是 :X=YZ。设 r 为框架 R 的任一具体关系， t、s 为 r 的两个元组 因: t [X] = t [YZ] = t [Y] t [Z] s [X] = s [YZ] = s [Y] s [Z] 若 t [X] = s [X] 时, 必有t [Y] = s [Y] 即 YXU 时,X Y 。 证毕
公理二：增广性公理 (Augmentat i on) 若X一Y为F蕴含，且ZsU, 则XZ一YZ亦为F蕴含。 证明：设r为R(U,F)的任一具体关系，t、s 为r的两个任意元组。 若t[XZ]=s[XZ],则有t[X]=s[X],t[Z]=s[Z]。 另由X一Y,只要t[X]=s[X],就有t[Y] =s[Y] 故只要有：t[XZ]=s [XZ] 必有：t[Yz]=s[YZ].证毕 4 ☒
4 公理二 : 增广性公理 (Augmentation) 若X Y为F蕴含, 且ZU, 则 XZ YZ亦为F蕴含。 证明: 设 r 为R(U,F)的任一具体关系, t 、s 为 r 的两个任意元组。 若t[XZ]=s[XZ], 则有t [X]=s[X], t[Z]=s[Z]。 另由X Y, 只要t [X] = s [X] , 就有t [Y] = s [Y] 故只要有: t [XZ] = s [XZ] , 必有: t [YZ] = s [YZ].证毕
公理三：传递性 若X一Y,且Y一Z为F蕴含， 则X一Z亦为F蕴含。 证明：由X一Y,若：t[X]=u[X], 必有：t[Y]=u[Y]; 由Y一Z,若：t[Y]=u[Y] 必有：t[Z]=u[Z]; 故：若X一Y,且Y一Z为F蕴含， 则只要：t[X]=u[X]成立， 必有：t[Z]=u[Z]成立。所以命题成立。 证毕
5 公理三 : 传递性 若X Y, 且Y Z为F蕴含, 则X Z亦为F蕴含。 证明:由X Y，若：t[X]= u[X]， 必有：t[Y]= u[Y]； 由Y Z，若：t[Y]= u[Y]， 必有：t[Z]= u[Z]； 故：若X Y, 且Y Z为F蕴含， 则只要：t[X]= u[X]成立， 必有：t[Z]= u[Z]成立。所以命题成立。 证毕
根据上述三条公理，可以很容易 证明下述三条推理规则： 1.合并规则： 由X一Z,X一Y,则X一YZ 2.伪传递规则： 由X一Y,Y一Z,则必有XW一Z 3.分解规则： 由X一Y,且ZsY,有X一Z 6
6 根据上述三条公理,可以很容易 证明下述三条推理规则 : 1.合并规则: 由 X Z, X Y,则 X YZ 2.伪传递规则: 由X Y, WY Z,则必有XW Z 3.分解规则: 由X Y, 且 Z Y,有X Z
二.X 定义：设有关系框架R(B1,B2,,Bx)其属性 集合为U=B1,,Bk,X是U的一个子集，F 是基于关系框架R的一个函数相关性集合 令X=[B,|只用公理一至三可以从F导出 XB(i=1,,k)]. 则X+定义为x基 于关系框架R关于F的闭包 7
7 二.X + 定义:设有关系框架R (B1,B2,…,BK)其属性 集合为U=B1,…,BK, X是U的一个子集, F 是基于关系框架R的一个函数相关性集合. 令X +=[Bi |只用公理一 至 三可以从F导出 X Bi (i=1,…,k)]. 则X +定义为x基 于关系框架R关于F的闭包
例： 设有关系框架R(A,B,C), 函数相关性集合F={A一B,B一C 则有：当X=A时，X=ABC 当X=B时，X=BC 当X=C时，X=C 8
8 例: 设有关系框架R(A, B, C), 函数相关性集合F={A B, B C} 则有: 当X=A时, X +=ABC 当X=B时, X +=BC 当X=C时, X +=C
主.The minimum set of Functional Dependence (最小函数相关性集合) 对于任何一个函数相关性集合F,总希望用 一个与之等价的最小函数相关性集合表示它。 定义：如果一个函数相关性集合F,满足下列 条件，称为最小函数相关性集合，记为Fmin 1,Fmin中每一个函数相关性的依赖属性集 均为单个属性
9 三.The minimum set of Functional Dependence （最小函数相关性集合） 对于任何一个函数相关性集合F, 总希望用 一个与之等价的最小函数相关性集合表示它。 定义:如果一个函数相关性集合F, 满足下列 条件,称为最小函数相关性集合,记为F min: 1. F min中每一个函数相关性的依赖属性集 均为单个属性
Fmin中不存在相关性X一AJ,使 min-X一A与Fmin等价。 3.F min中不存在相关性集合X,一AJ和X的真 子集，使min-X一Aj}U[Z一AJ与F min等价. 例：分析F1,F2,F3, 是否最小相关性集合 AD-BC A-D A F BE一 C B A F3= AD C H F2= A B 一D 10
10 2. F min中不存在相关性X AJ ,使 F min -{X AJ }与F min等价。 3. F min中不存在相关性集合X AJ和X的真 子集,使F min -{X AJ } {Z AJ}与 F min等价. 例: 分析F1, F2, F3, 是否最小相关性集合 AD BC A D A C F= BE C B A F3= AD B C H F2= A C C D B D D A D C