资源描述:
《函数依赖逻辑蕴涵》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、一、函数依赖的逻辑蕴涵定义:设有关系模式R(U)及其函数依赖集F,如果对于R的任一个满足F的关系r函数依赖X→Y都成立,则称F逻辑蕴涵X→Y,或称X→Y可以由F推出。例:关系模式R=(A,B,C),函数依赖集F={A→B,B→C},F逻辑蕴涵A→C。证:设u,v为r中任意两个元组: 若A→C不成立,则有u[A]=v[A],而u[C]≠v[C] 而且A→B,B→C,知 u[A]=v[A],u[B]=v[B],u[C]=v[C], 即若u[A]=v[A]则u[C]=v[C],和假设矛盾。
2、 故F逻辑蕴涵A→C。满足F依赖集的所有元组都函数依赖X→Y(X→Y不属于F集),则称F逻辑蕴涵X→Y(X→Y由F依赖集中所有依赖关系推断而出)二、Armstrong公理1、定理:若U为关系模式R的属性全集,F为U上的一组函数依赖,设X、Y、Z、W均为R的子集,对R(U,F)有: F1(自反性):若X≥Y(表X包含Y),则X→Y为F所蕴涵;(F1':X→X) F2(增广性):若X→Y为F所蕴涵,则XZ→YZ为F所蕴涵;(F2':XZ→Y) F3(传递性):若X→Y,Y→Z
3、为F所蕴涵,则X→Z为F所蕴涵; F4(伪增性):若X→Y,W≥Z(表W包含Z)为F所蕴涵,则XW→YZ为F所蕴涵; F5(伪传性):若X→Y,YW→Z为F所蕴涵,则XW→Z为F所蕴涵; F6(合成性):若X→Y,X→Z为F所蕴涵,则X→YZ为F所蕴涵; F7(分解性):若X→Y,Z≤Y(表Z包含于Y)为F所蕴涵,则X→Z为F所蕴涵。 函数依赖推理规则F1∽F7都是正确的。2、Armstrong公理:推理规则F1、F2、F3合称Armstrong公理;F4∽
4、F7可由F1、F2、F3推得,是Armstrong公理的推论部分。三、函数依赖的闭包 定义:若F为关系模式R(U)的函数依赖集,我们把F以及所有被F逻辑蕴涵的函数依赖的集合称为F的闭包,记为F+。即:F+={X→Y
5、X→Y∈F∨“应用Armstong公理从F中导出的任何X→Y”} △F包含于F+,如果F=F+,则F为函数依赖的一个完备集。 △规定:若X为U的子集,X→Φ属于F+。 例:R=ABC,F={A→B,B→C},求F+ 解:F+={A→Φ,AB→Φ,AC→Φ,ABC→Φ
6、,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,
7、AC→ABC,ABC→A,BC→BC} 例:已知关系模式R中 U={A,B,C,D,E,G}, F={AB→C,C→A,BC→D,ACD→B,D→EG,BE→C,CG→BD,CE→AG},判断BD→AC是否属于F+ 解:由D→EG知D→E,BD→BE …① 又知BE→C,C→A所以BE→A,BE→AC…② 由①、②知,BD→AC,所以BD→AC被F所蕴涵,即BD→AC属于F+ 例:已知关系模式R中
8、 U={A,B,C,E,H,P,G}, F={AC→PE,PG→A,B→CE,A→P,GA→B,GC→A,PAB→G,AE→GB,ABCP→H},证明BG→HE属于F+ 证:由B→CE知B→C,B→E,BG→GC …① 又知GC→A,A→P所以BG→A,BG→ABCP…② 又ABCP→H,由①、②知BG→HE,所以BG→HE被F所蕴涵, 即BG→HE属于F+四、属性集闭包 1、定义:若F为关系模式R(U)的函数依赖集,X是U
9、的子集,则由Armstrong公理推导出的所有X→Ai所形成的属性集例:设R=ABC,F={A→B,B→C}当X分别为A,B,C是求X+。解:当X=A时,X+=ABC 当X=B时,X+=BC 当X=C时,X+=C*X代表的属性集可以决定的属性集(包括本身)2、定理:当且仅当Y属于X+时,X→Y能根据Armstron公理由F导出。证:设Y=A1,A2,…,An ①充分条件:当Y属于X+时,对于每个i,X→Ai