函数依赖的逻辑蕴涵

《函数依赖的逻辑蕴涵》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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]，和假设矛盾。故F逻辑蕴涵A→C。满足F依赖集的所有元组都函数依赖X→Y（X→Y不属于F集），

2、则称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为F所蕴涵，则X→Z为F所蕴涵；F4(伪增性)：若X→Y，W≥Z(表W包含Z）为F所蕴涵，则XW→YZ为F所蕴涵；F5(伪传性):若X→Y，YW→Z为F所蕴涵,则XW→Z为F所蕴涵

3、；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∽F7可由F1、F2、F3推得，是Armstrong公理的推论部分。三、函数依赖的闭包　定义：若F为关系模式R(U)的函数依赖集，我们把F以及所有被F逻辑蕴涵的函数依赖的集合称为F的闭包，记为F+。即：F+={X→Y

4、X→Y∈F∨“应用Armstong公理从F中导出的任何X→Y”}△F包含于F+，

5、如果F=F+，则F为函数依赖的一个完备集。△规定：若X为U的子集，X→Φ属于F+。例：R=ABC,F={A→B,B→C},求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,AB

6、C→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中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→

7、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的子集，则由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

8、①充分条件：当Y属于X+时,对于每个i,X→Ai可由公理导出。再用合并规则可得X→Y。②必要条件：若X→Y能够由公理导出,则根据分解规,X→Ai(i=1,2,…,n)成立，所以Y属于X+。3、计算X+(1)算法依据：若F为关系模式R(U)的函数依赖集,X,Z,W是U的子集,对于任意的Z→W∈F,若X≥Z（表X包含Z）,则X→XW。(2)算法：a.令X+=X;b.在F中依次查找每个没有被标记的函数依赖，若“左边属性集”包含于X+，则令X+=X+∪“右边属性集”,为被访问过的函数依赖设置访问标记。c.反复执行b直到X+不改变为止。（先令X+等于本身，然后在F+中依次

9、查找左边包含于X+的属性