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]成立。所以命题成立。 证毕