1 1 1 2 2 2 k k k
}
2018/10/5
11
判断无损连接的算法
算法6.2 判断一个分解的无损连接性 {R1 U1, F1 , R2 U2 , F2 ,..., Rk Uk , Fk是 }R<U，F〉的一 个分解，U={A1，A2，…，An}，F={FD1，FD2，…， FDm}，这里我们设F是一个极小依赖集，记FDi为 Xi→Ali。 （1）建立一张n列k行的表。一列对应一个属 性，一行对应一个分解后的模式；在i行j列中的空白 处，若属性Aj属于Ui，则填上aj，否则填上bij。
2018/10/5
8
6.4.2.1 分解的“无损连接性”
我们先来定义几个符号： 分解： {R1 U1, F1 , R2 U2 , F2 ,..., Rk Uk , Fk } 其中r是R<U，F>的一个关系。 再定义： m = （ r ） Ri 也就是说 是r在各个模式分解上的投 m 影的连接。
2018/10/5 3
本小节要讨论的内容
• “无损连接性”和“保持函数依赖”的含 义； • 对于这三种角度的分解可以达到的分离程 度，即可以达到第几范式； • 对于这几种分离的分解算法；
下面用一个实际分解的例子来引出本小 节的内容。
2018/10/5 4
一个分解实例
例4：一个关系模式R<U，F>，其中U={Sno，Sdept， Mn}，F={Sno→Sdept，Sdept →Mn}。 如果我们把它分解成：
我们从r1，r2和r3这三个关系中已经不能回 答“某个学生在哪个系学习”了，显然这样的分 解是失败的。这是由于失去了关原来的关系。 而我们把r1，r2和r3做自然连接（它们的笛卡 尔积）后，我们得到的是一个具有4*4*4=64行的 没有实际意义的关系表。不能恢复表5.3所示的 含义了。
7
一个分解实例（续3）
我们来看一个比较好的分解：
3 {R 我们按这种模式分解后的关系通过自然连接是 1 {Sno, Sdept},{Sno Sdept} , R2 {Sdept , Mn},{Sdept Mn} }
可以恢复到原来的关系的，同时，我们可以显然的 发现在原关系模式中的函数依赖在新的关系模式中 都存在，因此，这次分解既保证了“无损连接特 性”，又“保持了函数依赖”。 下面我们用形式化的概念来描述“无损连接性” 和“保持函数依赖性”。
我们可以对照课本表6.5和分解的办法，我们可以把表6.5 分解成了三个关系： r1={S1，S2，S3，S4} r2={D1，D2，D3} r3={张五，李四，王一}
1 {R1 Sno, , R2 Sdept, , R3 Mn, }
2018/10/5
5
一个分解实例（续）
2018/10/5 13
判断无损连接的算法（续2）
对F中的m个FD逐一进行一次这样的处置， 称为对F的一次扫描。 （3）比较扫描前后表的变化，若有则转到第 （2）步，否则算法终止。 如果发生循环，那么前次扫描至少应使该表 减少一个符号，表中符号有限，因此循环必然终 止。 定理6.4：若修改结束后的表格中有一行全 是a，即a1，a2，…，an，那么该模式分解是无 损连接分解。 下面我们用两个例子来解释一下。
2018/10/5
9
其中：r是R的一个关系； ri= （r）是Ri的一个关系； Ri 则有：
m
与r以及ri的关系
(1)r m (r ) (2)若s m (r ), 则 Ri ( s ) ri (3)m (m (r )) m (r )
2018/10/5 10
无损连接的定义
2018/10/5
12
判断无损连接的算法（续）
（2）对于每一个FDi做如下的操作：取 F中的函数依赖X→Y，如果表格中有两行在X 分量上相等，在Y分量上不相等，那么修改Y 分量上的值，使这两行在Y分量上也相等，修 改时分两种情况：
① 如果Y的分量上有一个是aj，那么另外一个 也修改正aj。 ② 如果Y的分量上没有aj，那么下标i较小的那 个bij替换其他的符号。
2018/10/5 6
一个分解实例（续2）
分解2：
这种分解通过自然连接后是可以恢复原 来的关系的，但是我们发现在原来的关系模 式的F中有函数依赖Sdept→Mn，而在分解后 的关系模式中不存在了。 因此，关系模式的分解就要求具有“保 持函数依赖”的特性才好。
2018/10/5
2 {R1 {Sno, Sdept},{Sno Sdept} , R2 {Sno, Mn},{Sno Mn} }
其中 U U i并且没有Ui U j ,1 i, j n, Fi是F在Ui上的投影
i 1 n
定义6.17： Fi是指函数依赖集合{X→Y∣ X→Y∈F+∧XY是Ui的子集}的一个覆盖。
2018/10/5 2
6.4.1 模式分解的三个定义
对于每一个分解是多种多样的，但是分 解后的模式应该与原模式是等价的。 那么怎么衡量分解的等价呢？从不同的 角度可以分为三种： • 分解要具有“无损连接性” • 分解要“保持函数依赖” • 分解既要“保持函数依赖”，又要具有 “无损连接性”
数据库原理
第六章第四节 模式的分解
2018/10/5
1
定义6.16 模式分解
在对函数依赖的基本性质了解之后，可以具体地 来讨论模式的分解了。 定义6.16：关系模式R（U，F）的一个分解是指： {R1 U1, F1 , R2 U2 , F2 ,..., Rn Un , Fn }
定义6.18 {R U , F , R U , F ,..., R U , F 是R<U，F>的一个分解，若对R<U，F>的任 何一个关系r均有r= （rm ）成立，则称这个分 解具有无损连接性。 也就是说：把分解后的关系做自然连接 后可以恢复成原来的关系就可以了。 那么用什么样的数学法子来判断呢？