模式分解的无损连接性之深入剖析

1. 无损连接分解的形式定义

　　无损连接分解的形式定义如下：设R是一个关系模式，F是R上的一个函数依赖(FD)集。R分解成数据库模式δ={R1,……,Rk}。如果对R中每一个满足F的关系r都有下式成立：

　　那么称分解δ相对于F是“无损连接分解”，否则称为“损失连接分解”。其中表示自然连接。

　　从上述形式定义中可知，若直接根据定义来判断某个分解是否具有无损连接性，那么就得“对R中每一个满足F的关系r”进行测试，看是否满足上面的等式，这显然不可操作，因为“对R中每一个满足F的关系r”进行测试就意味着“对R中所有满足F的关系r”进行测试，显然是不可能的。这里所说的“关系”就是指一张具体的表。

　　因此，必须寻求其它的可操作性方法来判别分解的无损连接性。

　　2. 无损连接分解的普通判别方法——表格法

　　设关系模式R=A1,…,An，R上成立的FD集F，R的一个分解p={R1,…,Rk}。无损连接分解的判断步骤如下：

　　(1)构造一张k行n列的表格，每列对应一个属性Aj(1≤j≤n)，每行对应一个模式Ri(1≤i≤k)。如果Aj在Ri中，那么在表格的第i行第j列处填上符号aj，否则填上符号bij。

　　(2)把表格看成模式R的一个关系，反复检查F中每个FD在表格中是否成立，若不成立，则修改表格中的元素。修改方法如下：对于F中一个FD：X→Y，如果表格中有两行在X分量上相等，在Y分量上不相等，那么把这两行在Y分量上改成相等。如果Y的分量中有一个是aj，那么另一个也改成aj;如果没有aj，那么用其中的一个bij替换另一个(尽量把ij改成较小的数，亦即取i值较小的那个)。

　　若在修改的过程中，发现表格中有一行全是a，即a1,a2,…,an，那么可立即断定p相对于F是无损连接分解，此时不必再继续修改。若经过多次修改直到表格不能修改之后，发现表格中不存在有一行全是a的情况，那么分解就是有损的。特别要注意，这里有个循环反复修改的过程，因为一次修改可能导致表格能继续修改。

　　修改过程中要特别注意，若某个bij被改动，那么它所在列的所有bij都需要做相应的改动。为了明确这一点，举例说明。例如，我们根据FD“H→I”、“ K→L”来修改表格之前时的表格如表1所示(已经过多次修改，非初始表，空的单元表示省略)：

　　表1

H
I
J
K
L

R1

b12


b35

R2
a1
a2

a4
b25

R3
a1
b12

a4
b35

R4

b12


b35

　　R2、R3所在行的H分量都为a1，根据FD“H→I”，需要修改这两行对应的I分量，而R2所在行的I分量为a2，因此，要将R3所在行的I分量b12修改为a2，注意到，R1、R4所在行的H分量也为b12，因此，这两行对应的I分量也必须修改为a2。R2、R3所在行的K分量都为a4，根据FD“K→L”，需要修改这两行对应的L分量，于是将R3所在行的L分量b35修改为较小的b25，同时注意到，R1、R4所在行的L分量也为b35，因此，这两行对应的L分量也必须修改为b25。修改后的表格如表2所示：

　　表2

H
I
J
K
L

R1

a2


b25

R2
a1
a2

a4
b25

R3
a1
a2

a4
b25

R4

a2


b25

　　【例题】(软件设计师2002年上午试题38)

　　设关系模式 R为 R(H,I,J,K,L)，R上的一个函数依赖集为 F={H→J,J→K,I→J,JL→H}，分解 (38) 是无损连接的。

　　供选择的答案：

　　(38) A. p={HK，HI，IJ，JKL，HL} B. p={HIL，IKL，IJL}

　　C. p={HJ，IK，HL} D. p={HI，JK，HL}

　　试题分析：

　　根据上述判断方法，我们列出选项B(分解成三个关系模式R1(HIL)、R2(IKL)、R3(IJL) )的初始表如表3所示：

　　表3 选项B的初始表

H I J K L
HIL a1 a2 b13 b14 a5
IKL b21 a2 b23 a4 a5
IJL b31 a2 a3 b34 a5

　　对于函数依赖集中的H→J、J→K对表3进行处理，由于属性列H和属性列J上无相同的元素，所以无法修改。但对于I→J在属性列I上对应的1、2、3行上全为a2元素，所以，将属性列J的第一行b13和第二行b23改为a3。