判断一个分解具有无损连接性的算法.ppt

《判断一个分解具有无损连接性的算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、判断一个分解具有无损连接性的算法算法的输入：关系模式R(A1,A2,…,An),R上的函数依赖集F,R的一个分解={R1,R2,…,Rk}算法的输出：true或false算法LOSSLESSTEST(R,F,)构造一个k行n列的二维表T，第i行对应于关系模式Ri，第j列对应于属性Aj，令tij={aj若AjRibij若AjRic1:=truedowhilec1{c1:=false;for每一个XYFdofor每一对ti,tkTdoifti[X]=tk[X]andti[Y]tk[Y]then{EQUY(ti,tk);c1=true}};for任一个tTdo{if

2、t=a1a2..anthenreturn(true)}return(false)EQUY(ti,tk)是使ti,tk两个元组的Y值相等的子处理过程，处理原则如下：若ti[Y]与tj[Y]有一个为aj则将另一个也改为aj否则，tk[Y]=ti[Y]假定i

3、2b15b24b25b34b31b54b52b42b41由AC,做的修改ABCDER1R2R3a1a3a2a1b23R4R5a5a4a2a4a1a5a5b13b33b53b12b15b24b25b34b31b54b52b42b41b13b13由CD做的修改ABCDER1R2R3a1a3a2a1b13R4R5a5a4a2a4a1a5a5b13b13b13b12b15b24b25b34b31b54b52b42b41a4a4a4结果二维表ABCDER1R2R3a1a3a2a1R4R5a5a4a2a4a1a5a5b12b15b25b52b42a3a3a3a3a1a1a4a4a4算法

4、输出true是无损的定理：关系模式R(U)，分解为={R(U1),R(U2)}是无损连接的当且仅当U1U2U1-U2或U1U2U2-U1