规范化无损分解及保持函数依赖

1、设R是一个关系模式，F是R上的一个FD集。R分解成数据库模式 。如果对R中满足F的每一个关系r，都有kRR,1，那么称相对于F是“无损分解”，否则称“损失分解”。R=R1(r) R2(r) Rk(r)无损分解（1)构建一张k行n列的表格，每列对应一个属性 ，每行对应一个模式 。如果 在 中，那么在表格的第i行第j列处填上符号 ，否则填上 。nj1AjKi1RijAiRjaijb关系模式 ，F是R上成立的函数依赖集， 是R的一个分解。判断相对于F是否具有无损分解特征。1nRAA1,kRR例：设关系模式R（ABCD），R分解成 。如果R上成立的函数依赖集 ，那么相对于 是否无损分解？如果R上成立的

2、函数依赖集 呢？,AB BC CD1F2,FAB CD1,FBA CDA B C DABBCCD121 31 42 1232 43 13 234a a b bb a a bb b a a无损分解的测试方法（2)把表格看成模式R的一个关系，反复检查F中每个FD在表格中是否成立，若不成立，则修改表格中的值。修改方法如下： 对于F中一个FD ，如果表格中有两行在X值上相等，在Y值上不相等，那么把这两行在Y值上也改成相等的值。如果Y值中有一个是 ，那么另一个也改成 ；如果没有 ，那么用其中一个 替换另一个值（尽量把下标ij改成较小的数）。一直到表格不能修改为止。YX jaiajaijbA B C DA

3、BBCCD121 31 412343 13 234a a b ba a a ab b a a（3)若修改的最后一张表格中有一行全是a，即 ，那么称相对于F是无损分解，否则称有损分解。n21aaa所以相对与 ，R分解成是无损分解。1F无损分解的测试方法相对于 ，Chase过程如下：2FA B C DABBCCD121 31 42 1232 43 13 234a a b bb a a bb b a aA B C DABBCCD121 31 42 12343 13 234a a b bb a a ab b a a此时表格(b)中没有一行是全a行，因此相对于 ，R分解成是损失分解。(a)(b)2F无损

4、分解的测试方法定义：定义：设F是属性集U上的FD集，Z是U的子集，F在Z上的投影用 表示，定义为： Fz +FXY|XYF ,XYZz且定义：定义：设 是R的一个分解，F是R上的FD集，如果有 ，那么称分解为保持函数依赖集F。kRR,1， 1kRi=1F |=F 1kRi=1F |=F 1kRi=1F|=F 1+k+Ri=1F=F保持函数依赖情况有：保持函数依赖的分解具有无损连接性的模式分解v关系模式R的一个分解 = R1，R2， ，Rn 若R与R1、R2、Rn自然连接的结果相等，则称关系模式R的这个分解具有无损连接性（Lossless join）v具有无损连接性的分解保证不丢失信息v无损连接

5、性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题保持函数依赖的模式分解设关系模式R被分解为若干个关系模式R1，R2，Rn （其中U=U1U2Un，且不存在Ui Uj，Fi为F在Ui上的投影），若F所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖Fi所逻辑蕴含，则称关系模式R的这个分解是保持函数依赖的（Preserve dependency）模式设计数据等价依赖等价无损分解依赖闭包相等例：例：关系模式R(ABC), 是R的一个分解。试分析分别在 情况下，是否具有无损分解和保持FD的分解特性。= AB,AC1234F=AB,F =AC,BC,F =BA,F =CB,BA模式分解与模式等价问题分解成分解成3NF3NF模式集既无损模式集既无损又保持函数依赖的方法又保持函数依赖的方法 对于关系模式R和R上成立的FD集F，先求出F的最小依赖集，然后再把最小依赖集中那些左部相同的FD用合并性合并起来。 对最小依赖集中每个FD XY去构成一个模式XY。 在构成的模式集中，如果