函数依赖闭包求关系模式的候选关键字

前端之家收集整理的这篇文章主要介绍了函数依赖闭包求关系模式的候选关键字前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

函数依赖闭包

'函数依赖闭包专门用来求关系模式的候选关键字'

设关系模式R{A,B,C,D,E,F},其上函数依赖集F={(A,B)->E,(A,C)->F,D)->B,B->C,C->D}

--首先是观察那个属性集最有可能是候选关键字(其实就是用函数依赖闭包算法进行观察)

--经观察,首先定下候选关键字为(A,D)然后验证如下:

1、(A,D)0=(AD)

2、由(A,D)中的(AD)包含于(A,D)0=(AD)得:
(A,D)0=(AD) =>(A,D)1=AD∪B=ABD

3、由(A,B),B 中的(AB),B 均包含于(A,D)1=ABD得:
(A,D)1=ABD =>(A,D)2=ABD∪E∪C=ABCDE

4、由(A,C),C 中的(AC),C 均包含于(A,D)2=ABCDE得:
(A,C->D,D)2=ABCDE =>(A,D)3=ABCDE∪F∪D=ABCDEF

5、由于(A,D)3=ABCDEF已经包含了关系模式 R 的所有属性集!所以(A,D)就是关系模式 R 的候选关键字


'下面是有关“函数依赖闭包”的专业解说'


函数依赖闭包


一、函数依赖的逻辑蕴涵

定义:设有关系模式R(U)及其函数依赖集F,如果对于R的任一个满足F的关系r函数依赖X→Y都成立,则称F逻辑蕴涵X→Y,或称X→Y可以由F推出。

例:关系模式 R=(A,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集),则称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所蕴涵;

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|X→Y∈F∨“应用Armstong公理从F中导出的任何X→Y”}

△ F包含于F+,如果F=F+,则F为函数依赖的一个完备集。
△ 规定:若X为U的子集,X→Φ 属于F+。

例:R=ABC,F={A→B,求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,
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,BC→BC}

例:已知关系模式R中
U={A,B,C,D,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,
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的子集,则由Armstrong公理推导出的所有X→Ai所形成的属性

例:设R=ABC,B→C}当X分别为A,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可由公理导出。
再用合并规则可得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+中依次查找左边包含于X+的属性,把其右边的对应属性并到X中)

(3)算法实现
输入:关系模式R的子集X,R上的函数依赖集F。
输出:X关于F的闭包X+

算法伪语言描述:

Closure(X,F)
{
olds=Φ; news=X; G=F;
while (olds!=news)
{
olds=news;
for (G中的每个函数依赖W→Z)
{
if (news包含W)
{
news=news∪Z;
从G中删除函数依赖W→Z;
}
}
}
return news;
}


例:已知关系模式R中
U={A,B,C,D,
F={AB→C,
求(BD)+,判断BD→AC是否属于F+

解:X+=BDEGCA
结论:(BD)+=ABCDEG,BD→AC可由F导出,即BD→AC属于F+

例:已知关系模式R中
U={A,B,C,E,
F={AC→PE,
证明BG→HE属于F+

证:因为,(BG)+ =ABCEHPG,
所以BG→HE可由F导出,即BG→HE属于F+

4、结论
判定函数依赖X→Y是否能由F导出的问题,可转化为求X+并判定Y是否是X+子集的问题。
即求闭包问题可转化为求属性集问题。
判定给定函数依赖X→Y是否蕴涵于函数依赖集F算法实现:

输入:函数依赖集合F,函数依赖X→Y
输出:若X→Y∈F+输出真,否则输出

算法伪语言描述:
number(F,X→Y)
{ if (Y包含于close(X,F))
return 真
else
return 假
}

{Ai|i=1,…}称为X对于F的闭包,记为X+。

原文链接:https://www.f2er.com/javaschema/287591.html

猜你在找的设计模式相关文章