模式的分解.PPTVIP

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