数据库 第六章 模式的分解(续).ppt

第一条说明r在p上的投影连接映射后的元组只会膨胀，不会变少。第二条说明直接投影的结果与先拆开来再连接再投影的结果一致。第三条说明无论进行多少次分解后，再连接的结果都是一致的。 结论告诉我们，一个实例经过投影，连接之后，其结果可能产生元组膨胀，即元组增多，本节开头部分的引例恰好也说明了这个事实。 我们并不希望类似的情况发生，因为它在多个表进行连接操作时出现了本身不存在的元组，产生了数据异常，这对保持数据的正确性是有害的。因此，我们需要对表间连接的情况进行分析，以便降低产生数据异常的可能性。为此，我们先引入以下的概念。 无损分解的定义 定义6.18 p={ R1U1,F1，R2U2,F2，…，RkUk,Fk}是RU,F的一个分解 若对R中的任何一个关系r均有r= mp(r)成立，则称分解p具有无损连接性。 无损分解的判定算法 算法6.2 判断一个分解的无损连接性设p={ R1U1,F1，R2U2,F2，…，RkUk,Fk}是RU,F的一个分解，U={A1, A2 ,…,An}, F={FD1, FD1 ,…,FDp} 1.建立一个n列k行的表，每列对应一个属性，每行对应分解中的一个关系模式。若属性Aj属于Ui ，则在j列i行的交叉处天上aj ,否则填上bij; * 人们从不同的角度去观察问题，对“等价”的概念形成了三种不同的定义： 这三个定义是实行分解的三条不同的准则。按照不同的分解准则，模式所能达到的分离程度各不相同，各种范式就是对分离程度的测度。 这一节要讨论的问题是： （1）“无损连接性”和“保持函数依赖”的含义是什么？如何判断？ （2）对于不同的分解等价定义，究竟能达到何种程度的分离，即分离后的关系模式是第几范式。 （3）如何实现分离，即给出分解的算法。 * 在引理1.3.3中，第一条说明r在p上的投影连接映射后的元组只会膨胀，不会变少。第二条说明直接投影的结果与先拆开来再连接再投影的结果一致。第三条说明无论进行多少次分解后，再连接的结果都是一致的。 引理1.3.3的结论告诉我们，一个实例经过投影，连接之后，其结果可能产生元组膨胀，即元组增多，本节开头部分的引例恰好也说明了这个事实。 我们并不希望类似例1.3.11的情况发生，因为它在多个表进行连接操作时出现了本身不存在的元组，产生了数据异常，这对保持数据的正确性是有害的。因此，我们需要对表间连接的情况进行分析，以便降低产生数据异常的可能性。为此，我们先引入以下的概念。 * 用word执行算法步骤 * R*〈X，Fx〉显然属于3NF，而τ保持函数依赖也很显然，只要判定τ的无损连接性就行了。 由于τ中必某关系模式R（T）的属性组T≧X。由于X是R〈U，F〉的码，任取U-T中的属性B，必存在某个i，使B∈T(i)（按算法6.1）。对i施行归纳法可以证明由算法6.2，表中关系模式R（T）所在的行一定可成为a1,a2,…an。τ的无损连接性得证 3）要证明具有无损边接性，也就是要证明ChaseF（T）有一全a行。我们利用求（K）的算法加以证明。 由于K是码，全部属性都可被码推出，所有属性最终都将被加入到（K）之中。设U—K中的属性加入到（K）中的次序为A1，A2，…An。现在按加入的次序进行归纳，追逐表T中K所在行最终将变成全a。 归纳基础：当i=0时，[K]为全a。 归纳假设：i=j—1时，[KA1A2…Aj—1]为全a。 归纳推广：当i=j时，假设Aj由某个XiAj加入到（K），其中上求的算法可知在之中，对应于行， 全a。而由假设行上KA1A2…Aj—1为全a，上XiAj进行追逐，则必为a。 故而[KA1A2……Aj]为全a行，结论得证。 * 分解为第四范式是否保持函数依赖？ U={A，B，C，D}，F={AB→C，C→D}， U＇={A，B，C}，F＇={AB→C，C→B} 这是一个自顶向下的算法。它自然地形成一棵对R〈U，F〉的二叉分解树。应当指出，R〈U，F〉的分解树不一定是唯一的。这与步骤（3）中具体选定的X→A有关。 算法6.5最初ρ={R〈U，F〉}令，显然ρ是无损连接分解，而以后的分解则由下面的引理6.5保证了它的无损连接性。 数据库系统原理 An Introduction to Database System 第六章 关系数据理论 第六章 关系数据理论 6.1 数据依赖 6.2 规范化 6.3 数据依赖的公理系统 6.4 模式的分解 6.4 模式的分解 把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的 只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义 模式的分解（续） 定义6.16 关系模式RU,F的一个分解： ρ={ R1U1,F1，R2U2,F2，…，RnUn,Fn} U=U1∪U2∪…∪Un，且不存在