判断模式分解是否为无损连接的方法

【方法步骤】

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

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

A1 A2 … An
R1<U1 , F1>
R2<U2 , F2>
…
Rk<Uk , Fk>

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

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

【例题】

题目：

设关系模式R（U，F），其中：U= {A，B，C，D，E } ，F={A→B，DE→B，CB→E，E→A，B→D}。（ D ）为关系模式R的候选关键字。分解（ D ）是无损连接，并保持函数依赖的。

问题1选项

​ A.AB B.DE C.DB D.CE

问题2选项

​ A.ρ={ R1(AC)，R2(ED)，R3(B)} B.ρ={ R1(AC)，R2(E)，R3(DB)}

​ C.ρ={ R1(AC)，R2(ED)，R3(AB)} D.ρ={ R1(ABC)，R2(ED)，R3(ACE)}

解析：

第一空：由于B、E、A、D都能被推出来，所以候选关键字中一定包含C。所以选D。

第二空：解析如下👇

​ 1、一般关系中只有一个关键字都是有损的。

​ 2、注意F中的关系并不是只能用一次，可以反复使用。

这里我们以正确答案 D 为例来判断说明是否为无损连接的具体过程：

  1. 构造一个初始的 i 行 j 列 的二维表，若 “属性” 属于 “模式” 中的属性，则填 aj，否则填 bij。

    A B C D E
    R1（ABC） a1 a2 a3 b14 b15
    R2（ED） b21 b22 b23 a4 a5
    R3（ACE） a1 b32 a3 b34 a5

  2. 根据 A→B ，对上表进行处理，由于属性列 A上第1、3行相同均为a1，所以将属性列 B 上的 a2、b32 改为同一个符号 a2（这里有有 a2 于是就改为 a2）。

    A B C D E
    R1（ABC） a1 a2 a3 b14 b15
    R2（ED） b21 b22 b23 a4 a5
    R3（ACE） a1 a2 a3 b34 a5

  3. 根据 DE→B ，对上表进行处理，由于属性列 DE 上没有相同的列所以这里不做处理。

  4. 根据 CB→E ，对上表进行处理，由于属性列 CB上第1、3行相同均为 a2 a3，所以将属性列 E 上的 a5、b15 改为同一个符号 a5（这里有有 a5 于是就改为 a5）。

    A B C D E
    R1（ABC） a1 a2 a3 b14 a5
    R2（ED） b21 b22 b23 a4 a5
    R3（ACE） a1 a2 a3 b34 a5

  5. 根据 E→A ，对上表进行处理，由于属性列 E 上第1、2、3行相同均为 a5，所以将属性列 A 上的 a1、b21 、a1改为同一个符号 a1（这里有有 a1 于是就改为 a1）。

    A B C D E
    R1（ABC） a1 a2 a3 b14 a5
    R2（ED） a1 b22 b23 a4 a5
    R3（ACE） a1 a2 a3 b34 a5

  6. 根据 B→D ，对上表进行处理，由于属性列 B 上第1、3行相同均为 a2，所以将属性列 D 上的 b14 、b34 改为同一个符号 b14 （取行号最小值）。

    A B C D E
    R1（ABC） a1 a2 a3 b14 a5
    R2（ED） a1 b22 b23 a4 a5
    R3（ACE） a1 a2 a3 b14 a5

  7. 再根据 A→B (前面已经用过，F中的依赖关系是可以重复使用的)，对上表进行处理，由于属性列 A上第1、2、3行相同均为a1，所以将属性列 B 上的 a2、b22、a2 改为同一个符号 a2。

    A B C D E
    R1（ABC） a1 a2 a3 b14 a5
    R2（ED） a1 a2 b23 a4 a5
    R3（ACE） a1 a2 a3 b14 a5

  8. 根据 B→D ，对上表进行处理，由于属性列 B 上第1、2、3行相同均为 a2，所以将属性列 D 上的 b14 、a4、b14 改为同一个符号 a4。

    A B C D E
    R1（ABC） a1 a2 a3 a4 a5
    R2（ED） a1 a2 b23 a4 a5
    R3（ACE） a1 a2 a3 a4 a5

  9. 最终，第1、3行成为a1a2a3a4a5。所以 D.ρ={ R1(ABC)，R2(ED)，R3(ACE)} 分解具有无损连接性。

【参考博客】https://www.cnblogs.com/bewolf/p/4443730.html