数据库闭包怎么计算？

已知关系模式R<U，F>，其中

U={A，B，C，D，E}；

F={AB→C，B→D，C→E，EC→B，AC→B}。

求（AB）F+ 。

解 设X（0）=AB；

(1)计算X（1）: 逐一的扫描F集合中各个函数依赖，

找左部为A，B或AB的函数依赖。得到两个：

AB→C，B→D。

于是X（1）=AB∪CD=ABCD。

(2)因为X（0）≠ X（1） ，所以再找出左部为ABCD子集的那些函数依赖，又得到AB→C，B→D， C→E，AC→B，

于是X（2）=X（1）∪BCDE=ABCDE。

(3)因为X（2）=U，算法终止

所以（AB）F+ =ABCDE。

求属性集X（X  U）关于U上的函数依

赖集F 的闭包XF+

输入：X，F

输出：XF+

步骤：

（1）令X（0）=X，i=0

（2）求B，这里B = { A |( V)(  W)(V→WF

∧V  X（i）∧A W)}；

（3）X（i+1）=B∪X（i）

（4）判断X（i+1）= X （i）吗?

（5）若相等或X（i）=U , 则X（i）就是XF+ ,

算法终止。

（6）若否，则 i=i+l，返回第（2）步。

对于算法6.l， 令ai =|X（i）|，{ai }形成一个步长大

于1的严格递增的序列，序列的上界是 | U |，因

此该算法最多 |U| - |X| 次循环就会终止。

计算属性集闭包X+的算法如下：

输入：X，F

输出：

X+

　迭代算法的步骤：

①

选取X+的初始值为X

，即X+＝{X}；

②

计算X+，

X+＝{XZ}

，其中Z要满足如下条件：

YX+，且F中存在一函数依赖Y→Z。实际上就是以X+中的属性子集作为函数依赖的决定因素，在F中搜索函数依赖集，找到函数依赖的被决定属性Z放到X+中。

③

判断：如果X+没有变化？或X+等于U？则X+就是所求的结果，算法终止。否则转②。

　因为U是有穷的，所以上述迭代过程经过有限步骤之后就会终止。

方法：warshall法，即运行n次，每次使得MR[n][i],MR[i][n]都为1时使得MR[i][j]为1,否则还是为MR[i][j]。

传递闭包的计算过程一般可以用Warshell算法描述：

For 每个节点i Do

For 每个节点j Do

If j能到i Then

For 每个节点k Do

a[j, k] := a[j, k] Or ( a[j, i] And a[ i, k] )

其中a数组为布尔数组，用来描述两个节点是否相连，可以看做一个无权图的邻接矩阵。算法过程跟Floyd很相似，三重循环，枚举每个中间节点。不过传递闭包只需要求出两个节点是否相连，而不用求其间的最短路径长。

传递性：对于一个节点i，如果j能到i，i能到k，那么j就能到k。求传递闭包，就是把图中所有满足这样传递性的节点都弄出来，计算完成后，就知道任意两个节点之间是否相连。

传递闭包的定义：R’是R（不具有传递性质）变动最少的步骤得到的具有传递性质的关系。

扩展资料

算法实例：

#include<stdio.h>

#define

N

10

int

judge(int

k,int

i,int

j)

{

if(i==1

&&

j==1){

return

1

}

return

k

}

void

warShall(int

MR[N][N],int

n)

{

for(int

k=0k<nk++){

for(int

i=0i<ni++){

for(int

j=0j<nj++){

if(i!=k

||

j!=k){

MR[i][j]=judge(MR[i][j],MR[k][j],MR[i][k])

}

}

}

}

}

int

main()

{

int

MR[10][10]

int

mul

scanf("%d",&mul)

for(int

i=0i<muli++){

for(int

j=0j<mulj++){

scanf("%d",&MR[i][j])

}

}

printf("求传递闭包为:\n")

warShall(MR,mul)

for(int

i=0i<muli++){

for(int

j=0j<mulj++){

printf("%d

",MR[i][j])

}

printf("\n")

}

return

0

}

运行结果：

参考资料：百度百科-传递闭包

---