狂学数据库之关系模式分解算法

关系模式的分解

将一个关系模式 R<U，F>分解为若干个关系模式 R1<U1，F1>，R2<U2，F2>，…，Rn<Un， Fn>（其中 U=U1∪U2∪…∪Un，且不存在 Ui⊈Uj，Ri为 F 在 Ui上的投影）,意味着相应将存储在一个二维表 t 中的数据分散到若干个二维表 t1，t2，…，tn中去(其中 ti 是 t 在属性集 Ui 上的投影)。则称ρ ={ R1，R2，…，Rk}为关系模式 R 的一个分解。

关系模式的规范化过程是通过对关系模式的分解来实现的，但是把低一级的关系模式分 解为若干个高一级的关系模式的方法并不是唯一的。在这些分解方法中，只有能够保证分解后的关系模式与原关系模式等价的方法才有意义。

关系模式分解等价性的三个判定准则：(1)分解具有“无损连接性”。(2)分解要“保持函数依赖”。 (3)分解既要“保持函数依赖”，又要具有“无损连接性”。 

无损连接分解

若将一个关系模式分解为两个关系模式，比较容易判别分解是否具有无损连接性。然而，若将一个关系模式分解为三个或更多个关系模式，要判别分解是否具有无损连接性需要比较复杂的算法。
下面将对于分解为两个模式的情况，可以采用以下特殊的判定准则。

二项分解定理：
关系模式 R(U，F)的一个分解ρ={R1(U1，F1)，R2(U2，F2)}
具有无损连接性的充分必要的条件是 U1∩U2→U1-U2∈F+ 或 U1∩U2→U2-U1∈F+
例子：

将给定的关系模式 R(U,F),U= {A,B,C,D},F={A→B,B→C,A→D}, 有如下两个分解： ρ1={ ABC,ACD} ρ2={ ABD,BC} 并检验这两个分解的无损连接性
. 解：可根据无损连接充分必要条件判断本题：(1)因为 ABC∩ACD =CABC-ACD=BACD-ABC=D 所以 C→B不属于F+ ，C→D不属于F+ 故ρ1为有损连接. (2)因为 ABD∩ABC=A   ABD-ABC=D ABC-ABD=C 所以 A→D∈F+ 故ρ2为无损连接. 注意：尽管 A→C不属于F+,但根据无损连接充分必要条件只要满足一个即可,故ρ2为无损 连接.

检验算法：
输入：关系模式 R(A1,A2,…,An),函数依赖集 F,分解ρ={R1,R2,…,Rk}.
输出：确定ρ是否具有无损连接性.
方法
(1)构造一个 k 行 n 列的表,第 i 行对应于关系模式 Ri,第 j 列对应于属性 Aj.如果 Aj∈Ri, 则在第 i 行第 j 列上放符号 aj,否则放符号 bij. (2)重复考察 F 中的每一个函数依赖,并修改表中的元素.其方法如下：取 F 中一个函 数依赖 X→Y,在 X 的分量中寻找相同的行,然后将这些行中 Y 的分量改为相同的符号, 如果其中有 aj,则将 bij改为 aj；若其中无 aj,则全部改为 bij(i 是这些行的行号最小值). (3)如果发现表中某一行变成了 a1,a2,…,an,则分解ρ具有无损连接性；如果 F 中所 有函数依赖都不能再修改表中的内容,且没有发现这样的行,则分解ρ不具有无损连接性.

例子

设 关 系 模 式 R(G,H,L,M,O),F={GL→O,O→M,G→H,H→M}, 判 断 分 解 ρ={R1(GHL),R2(MO),R3(GLO) }是否为无损连接。
二维表如下：

修改后的表为：

修改后的表可以看出第一行出现了 a1、a2、a3、a4、a5，所以该分解具有无损连接性。

保持函数依赖的分解

保持函数依赖的分解是指在模式的分解过程中函数依赖不能丢失的特性，及模式分解不 能破坏原来的语义。
从定义看出,保持函数依赖的分解就是指 ：当一个关系模式 R 分解后,无语义丢失, 且经过分解后,原模式 R 的函数依赖关系,都分散在分解后的子模式中

判定过程：

设 R(U，F)是一个关系模式，其中 U 是它的全体属性集，F 是它的一个函数依赖集，Z 包含于 U， 则把 F+在 Z 中的所有函数依赖的集合称为 F 在 Z 上的投影，记为Πz(F)，即
Πz(F)={X→Y|(X→Y∈F+)且( XY 包含于Z)}
设关系模式 R 的一个分解⍴={ R1，R2，…，Rk}，F 是 R 的函数依赖集，如果 F 等价于分解各关系的并集，则称分解ρ具有函数依赖保持性

例子：

设关系模式 R={CITY, STREET, POSTALCODE）表示各城市街道的邮政编 号，其中属性分别表示城市名、街道名和邮政编号，F={(CITY, STREET)→POSTALCODE， POSTALCODE→CITY)}。如果将 R 分解成⍴={R1，R2}，其中 R1={STREET, POSTALCODE}， R2={CITY, POSTALCODE}。判断这个分解是否保持无损连接性和函数依赖性。
解：根据无损连接充分必要条件，由于 R1∩R2=POSTALCODE, R2-R1=CITY, POSTALCODE→CITY 所以这个分解是无损连接。
又根据函数依赖定义F1=ΠR1(F)= 空集 ,F2= ΠR2  (F)={ POSTALCODE→CITY}
F1∪F2={ POSTALCODE→CITY }≠F 所以这个分解不保持函数依赖性

总结案例

试分析下列分解是否具有无损连接性和函数依赖保持性。
(1)设关系模式 S1 (A，B，C)，函数依赖集为 F1={A→B}在 R 上成立，ρ1={AB，AC}
(2)设关系模式 S2 (A，B，C)，函数依赖集为 F2={A→C，B→C}在 R 上成立，ρ2={AB， AC}
(3)设关系模式 S3 (A，B，C)，函数依赖集为 F3={A→B，B→C}在 R 上成立，ρ3={AC， BC}
解: (1)令 R1=AB，R2=AC 因为( R1∩R2)→R1-R2 即 A→B，所以ρ1 相对于 F1 是无损连接。 又因为ПAB(F1)∪ПAC (F1)={A→B}与 F1 等价，所以ρ1 相对于 F1 是保持函数依赖的分 解。

(2)令 R1=AB，R2=AC 因为( R1∩R2)→R2-R1 即 A→C，所以ρ2 相对于 F2 是无损连接。 又因为ПAB(F2)∪ПAC (F2)={A→C}与 F2 不等价，丢失了 B→C，所以ρ2 相对于 F2 不保 持函数依赖。

(3)令 R1=AC，R2=BC 因为(R1∩R2)=C，R1-R2=A，R2-R1=B，C→A 和 C→B 均不成立，所以ρ3 相对于 F3 不是无损连接。 又因为ПAC(F3)∪ПBC (F3)={B→C)与 F3 不等价，丢失了 A→B 所以ρ3 相对于 F3 不保持 函数依赖。