2024年软考软件设计师模式分解的无损连接性之深入剖析.doc

模式分解的无损连接性之深入剖析
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
　　【例题】(软件设计师上午试题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。修改后如表4所示：
【例题】(表4 选项B的中间表

H
I
J
K
L
HIL
a1
a2
a3
b14
a5
IKL
b21
a2
a3
a4
a5
IJL
b31
a2
a3
b34
a5
　　对于函数依赖集中的JL→H在属性列J和L上对应的1、2、3行上为a3、a5元素，因此，将属性列H的第二行b21和第三行b31改为a1。修改后如表5所示：
　　表5 选项B的成果表

H
I
J
K
L
HIL
a1
a2
a3
b14
a5
IKL
a1
a2
a3
a4
a5
IJL
a1
a2
a3
b34
a5
　　从表5能够看出，第二行为a1、a2、a3、a4、a5，因此分解p是无损的。
　　有一个特殊情况要注意：分解后的各个关系模式两两均无公共属性。因为是模式分解，那么任一一个分解后的关系模式覆盖的属性集不也许是分解前的整个所有属性U，因此初始表中不存在全是a的行。又注意到，分解后的各个关系模式两两均无公共属性，表白任两行在任一列上都没有相同的分量，这导致整个表格无法修改，保持初始状态。而初始状态不存在全是a的行，因此这种特殊情况的分解是有损的。
　　例如，函数依赖集合FD，将关系模式R(ABCDEF)分解成R1(AB)、R2(CDE)、R3(F)，那么这种分解肯定是有损的。考试中也许遇到这种情况，那么一眼就能够判断出成果，从而节约了时间。
　　3. 无损连接分解的快捷判别措施
　　首先要申明，这种快捷措施是有前提的，前提就是分解后的关系模式只有两个。其内容为：
　　设ρ={R1，R2｝是R的一个分解，F是R上的FD集，那么分解ρ相对于F是无损分解的充足必要条件是：(R1∩R2)→(R1–R2)或(R1∩R2)→(R2–R1)。这个“或”字很重要，这里表示(R1∩R2)→(R1–R2)、(R1∩R2)→(R2–R1)中只要有一个成立就行。这里的求交和相减运算的对象是关系模式的属性。
　　【例题】
　　关系模式R(U，F)，其中U={W,X,Y,Z},F={WX→Y,W→X, X→Z,Y→W}。那么下列分解中是无损分解的是 。
　　供选择的答案：
　　A.p={R1(WY),R2(XZ)} B.p={R1(WZ),R2(XY)}
　　C.p={R1(WXY),R2(XZ)} D.p={R1(WX),R2(YZ)}
　　试题分析：
　　A选项，R1∩R2为空，肯定不满足条件。
　　B选项，R1∩R2为空，肯定不满足条件。
　　C选项，R1∩R2={X}，R1-R2={WY}，R2-R1={Z}，依照函数依赖集，X→Z成立，因此满足条件。
　　D选项，R1∩R2为空，肯定不满足条件。
　　4. 总结
　　模式分解无损性判别的源泉仍然是一般的表格法。这种快捷措施只不过是依照这种表格法推断出来的而已，是它的一个特列。不过这种快捷措施却往往非常有用。
软件设计师上午试题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。修改后如表4所示：