是否为无损连接

方法一：无损连接定理

关系模式R(U，F)的一个分解，ρ={R1<U1,F1>,R2<U2,F2>}具有无损连接的充分必要条件是：

U1∩U2→U1-U2 €F+ 或U1∩U2→U2 -U1€F+

方法二：算法

ρ={R1<U1,F1>,R2<U2,F2>,…,Rk<Uk,Fk>}是关系模式R<U,F>的一个分解，U={A1,A2,…,An}，F={FD1,FD2,…,FDp}，并设F是一个最小依赖集，记FDi为Xi→Alj，其步骤如下：

① 建立一张n列k行的表，每一列对应一个属性，每一行对应分解中的一个关系模式。若属性Aj Ui，则在j列i行上真上aj，否则填上bij；

② 对于每一个FDi做如下操作：找到Xi所对应的列中具有相同符号的那些行。考察这些行中li列的元素，若其中有aj，则全部改为aj，否则全部改为bmli，m是这些行的行号最小值。

如果在某次更改后，有一行成为：a1,a2,…,an，则算法终止。且分解ρ具有无损连接性，否则不具有无损连接性。

对F中p个FD逐一进行一次这样的处理，称为对F的一次扫描。

③ 比较扫描前后，表有无变化，如有变化，则返回第② 步，否则算法终止。如果发生循环，那么前次扫描至少应使该表减少一个符号，表中符号有限，因此，循环必然终止。

举例1： 已知R<U,F>，U={A,B,C}，F={A→B}，如下的两个分解：

① ρ1={AB,BC}

② ρ2={AB,AC}

判断这两个分解是否具有无损连接性。

①因为AB∩BC=B，AB-BC=A，BC-AB=C

所以B→A ¢F+，B→C ¢ F+

故ρ1是有损连接。

② 因为AB∩AC=A，AB-AC=B，AC-AB=C

所以A→B €F+，A→C ¢F+

故ρ2是无损连接。

举例2： 已知R<U,F>，U={A,B,C,D,E}，F={A→C,B→C,C→D,DE→C,CE→A}，R的一个分解为R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，判断这个分解是否具有无损连接性。

① 构造一个初始的二维表，若“属性”属于“模式”中的属性，则填aj，否则填bij

② 根据A→C，对上表进行处理，由于属性列A上第1、2、5行相同均为a1，所以将属性列C上的b13、b23、b53改为同一个符号b13（取行号最小值）。

③ 根据B→C，对上表进行处理，由于属性列B上第2、3行相同均为a2，所以将属性列C上的b13、b33改为同一个符号b13（取行号最小值）。

④ 根据C→D，对上表进行处理，由于属性列C上第1、2、3、5行相同均为b13，所以将属性列D上的值均改为同一个符号a4。

⑤ 根据DE→C，对上表进行处理，由于属性列DE上第3、4、5行相同均为a4a5，所以将属性列C上的值均改为同一个符号a3。

⑥ 根据CE→A，对上表进行处理，由于属性列CE上第3、4、5行相同均为a3a5，所以将属性列A上的值均改为同一个符号a1。

⑦ 通过上述的修改，使第三行成为a1a2a3a4a5，则算法终止。且分解具有无损连接性。

是否保持函数依赖

方法一：算法
对于关系模式R(U,F), 设P = {R1(U1,F1) , R2(U2,F2) , … , Rn(Un,Fn)}是R的一个分解，若F+ = （UFi)+ ，则称分解P是保持函数依赖。 注：U：并集

例：R ={A，B，C，D，E}，F = {B → A ， D → A ， A → E , AC → B}，判断分解P ={R1（ABCE） ， R2（CD）}是否保持函数依赖

解：
首先，我们需要将R1和R2的函数依赖F1，F2找到。
显然有 F1 = {B → A ，A → E ， AC → B} ，F2 = { }
注：这样就找全了吗？其实不然，在这一步中最容易漏掉部分函数依赖，比如传递依赖等关系会因为F的分组而丢失。
因此，在这一步，我的习惯是计算一下左边属性的闭包 B+ ={B,A,E} 显然 B 和 E存在传递依赖 即 B → E，同理 D+={D，A，E} ，发现D+没有C，即D推不出C A+={A，E} (AC)+ = {A ,C , B, E}，显然 AC → A ， AC→ E
综上，F1 更新为 F1 = {B → A ，A → E ， AC → B， B → E，AC → A ， AC→ E}
F2依旧是空集
令 G = F1 ∪ F2 = {B → A ，A → E ， AC → B， B → E，AC → A ， AC→ E}
我们检查一下F中的函数依赖，是否在G中全部都出现，如果出现，则算法结束，保持函数依赖 发现，D → A 不在G中，此时，我们需要计算元素D在G下的闭包
显然，D+ ={D} 不包含A，因此该分解不保持函数依赖。
注：如果D+ ={D ,A }，包含了A，则该分解保持函数依赖.

首先了解一下几个概念：

1）把一个关系模式分解成若干个关系模式的过程，称为关系模式的分解。

2）把低一级的关系模式分解为若干个高一级的关系模式的方法不是唯一的。

3）只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义。

对于第一句话，为什么需要分解关系模式？因为原来的关系模式可能造成数据冗余或

给数据库带来潜在的不一致性。对于第二句话，根据不同语义，分解的原则也不尽相

同，所以方法肯定是不唯一的，譬如U={A,B,C}，根据不同原则（随便你自己定），

可能分成（A,B）（A,C）也可能分成（B,C）（A,C）。对于第三句话，则是本文所要

讲的内容。

为了保证分解后的关系模式与原关系模式等价，我们要判定 1）分解后形成的行的关

系模式中是否为无损连接  2）是否保持函数依赖

一、无损连接的判定：

1）如果分解后的的关系模式是形如{U1，U2}这，里面只有两个，那很好做，就判断

       或 是否成立，成立的话肯定是

      无损连接。

2）如果是两个以上{U1，U2，U3....}这种，那就比较麻烦了，比如，有属性集，

ABCDEF，存在这样的函数依赖集{A->BC , CD->E , B->D , BE->F , EF->A},然后有

这样的分解{ABC , BD , BEF}。

例如：

设U1=ABC，U2=BD，U3=BEF，根据提供的函数依赖集，我们可得U1存在这样的

函数依赖A->BC，U2上的函数依赖是 B->D， U3的函数依赖是BE->F。

1）于是可构造这样的表格。

2）各自判断A,B,C,D,E,F是否有在G列的函数依赖中，如果有记为ai，i表示第几列，否

则记为bji，表示第j行第i列

如：

这样我们可得到图：

 3)接下来是关键的，如果我们经过一系列变换得到有一行是这样的排序

{a1,a2,a3,a4,a5,a6...}，即不存在bji，那我们就认为，该分解是无损连接。

 4）变换过程：为了方便，我们可以按A->BC， B->D，BE->F这个顺序来（随你喜

欢）。

第一遍，根据A->BC，我们知道主健是能唯一标识一个元组的，也就是说如果

A中存在着两个属性值是相同的，毫无疑问，他们推出的BC的值肯定也是相同的。从

表格中我们遍历A列，没有发现有相同的属性组，那就跳过。

第二遍， 根据B->D，因为B列属性值相同，那我们修改D列。修改时遵照这样的一个

规则，如果D中有ai这样的值，那么宣布修改为ai，如果没有，修改成该列的第一行的

第一个值。从表格中我们可以发现D中有a4，那么修改后变成：

第三遍，根据BE->F，找一组BE相同的值，发现不存在，即不存在类似

{a1,a2,a3,a4,a5,a6}这样的序列，即该分解不是无损连接分解。

二、是否保持函数依赖？

这个的判断方法就比较简单了，还是这道题，有属性集，ABCDEF，存在这样

的函数依赖集{A->BC , CD->E , B->D , BE->F , EF->A},然后有这样的分解

{ABC , BD , BEF}。

设U1=ABC，A->BC，U2=BD，B->D ，U3=BEF，BE->F ，即我们不能推出 CD->E 

，EF->A，所以也不具有保持函数依赖的特性。

保持依赖的判断。 

如果F上的每一个函数依赖都在其分解后的某一个关系上成立，则这个分解是保持依赖的（充分条件）。 

如果上述判断失败，并不能断言分解不是保持依赖的，因为上面只是充分条件，还要使用下面的通用方法来做进一步判断。 

过程表述如下： 

对F上的每一个α→β使用下面的过程：

result:=α; 
while(result改变)do 
for each 分解后的Ri 
t=(result∩Ri)+ ∩Ri 
result=result∪t

例1：考虑关系模式R（A，B，C，D）分解｛R1（A，B），R2（BC），R3（C，D）｝，

函数依赖集F=｛A→B，B→C，C→D，D→A}

显然，AB包含于R1，BC包含于R2，CD包含于R3。因此，只需要验证是否有D→A呗分解p所保持。为此，我们使用算法。

首先，result=｛D｝进入 repeat循环，当i=1时不改变，因为｛D｝U（（｛D｝∩｛A，B｝）+∩｛A，B｝）仍是｛D｝。

同样方法，当i=2时Z不变。然而，i=3时，我们得到

result=｛D｝U（（｛D｝∩{C，D｝）+∩{C,D｝

=｛D｝U（｛D｝+∩｛C，D｝)=｛D｝U（｛A，B，C，D｝∩｛C，D｝）

=｛C，D}

再次执行 repeat的循环体，当i=2时产生result=｛B，C，D｝而第三遍，当i=1时置result为｛A，B，C，D｝。此后，T不再改变。这样，result=｛A，B，C，D}它包含A，因此，D→A被分解所保持。从而是保持函数依赖的分解。

例2：已知R<U,F>，U={A,B,C,D,E}，F={A→C,B→C,C→D,DE→C,CE→A}，R的一个分解为R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，判断这个分解是否具有函数依赖性。

先看F中每一个函数依赖，R4有C->D,DE->C。A->C,B->C,CE->A。这三个函数依赖分解模式里均未能覆盖。

开始使用算法进行检测：

首先对于A->C，result = A，（A）+ = ACD ，T=AD，result=AD，result改变，进入下一个循环：result = AD,（ABD）+ = ABCD ，t=AB，result=ABD。

result改变：result = ABD, （ABD）+ = ABCDE, t=BE，result=ABDE。

result改变：result = ABDE，（ABCD）+=ABCDE，t=CDE，result=ABCDE。

result改变：（从这一步就能看出来，保持了函数依赖了，因为已经包含C了）result = ABCDE，（ABCDE）+=ABCDE,t=AE，result=ABCDE。

result未改变。退出循环。、由于result=ABCDE，包含了C，所以分解保持函数依赖。