数据库系统概论17模式分解的等价标准.ppt

消除非主属性对码的部分函数依赖 消除非主属性对码的传递函数依赖 消除函数依赖的决定因素是非码,1NF 2NF 3NF BCNF,关系模式的规范化，是通过对关系模式的分解实现的。 分解的实质： “一事一表”，让一个关系只描述一个实体或联系，使关系单一化，以利于处理简单化。,规范化过程就是把一个关系模式分解为若干个关系模式，而且这种分解应该是可逆的。所谓可逆，是要求模式的分解是没有信息丢失，并保证分解后产生的关系模式集合和原来的关系模式等价。 如何对关系模式进行分解才能保证没有信息丢失呢？ 对于同一个关系模式可能有多种分解方案。下面的例子给出三种分解方案，如何判断哪种分解方案更好呢？,6.4 关系模式的分解,三种分解方案(模式分解不唯一),S1是哪个系的学生？ 何是哪个系的系主任呢？ D1的系主任是谁呢？,做连接,联接后问题没有得到解决，原因是没有保持函数依赖。,做自然连接,分解后可以恢复原关系，但数据冗余问题没有得到解决，问题是丢失了函数依赖sdeptdean。,D1的系主任是谁呢？ 何是哪个系的系主任呢？,做自然连接,问题得到了彻底解决，即不丢失信息，也减少了冗余。,6.4.1 模式分解的等价标准,上面例子中，每种分解方案得到的两个关系模式都属于3NF（实际上，也属于BCNF）。如何比较这三种分解方案的优劣呢？将一个关系模式分解为多个关系模式时，除了提高规范化程度外还需要什么别的考虑吗？ 常用的关系模式分解的等价标准有： 分解是具有无损连接性的； 分解是保持函数依赖的； 分解既要具有无损连接又要保持函数依赖两种。,(1)无损连接的定义 指的是对关系模式分解时，原关系模式下任一合法的关系实例在分解之后应能通过自然连接运算恢复起来。 定义：设=R1，R2，Rk是关系模式R的一个分解，如果对于R的任一满足F的关系r都有 r=R1(r) R2(r) Rk(r) 则称这个分解是满足依赖集F的无损连接。,6.4.2 无损连接的定义和性质,(2)验证无损连接的充要条件 如果R的分解为=R1，R2，F为R所满足的函数依赖集合，则分解具有无损连接性的充分必要条件为 R1R2(R1-R2)F+ 或R1R2(R2-R1)F+,例：现有关系模式R(A,B,C)，函数依赖集F=AB，CB，判断1=AB，AC， 2=AB，BC是否具有无损连接性。,解： ABAC=A AB-AC=B ABF+ 所以：1具有无损连接性。,解： ABBC=B AB-BC=A BC-AB=C BA或BCF+ 所以：2不具有无损连接性。,(3)无损连接的测试方法-表格法（算法6.2,P189） 算法：检验无损连接性。 输入：关系模式R(A1,A2,An)，它的函数依赖集F以及分解=R1，R2，Rk。 输出：确定是否具有无损连接性。 方法： 构造一个k行n列的表，第i行对应于关系模式Ri，第j列对应于属性Aj。如果AjRi，则在第i行第j列上放符号aj，否则放符号bij。 逐个检查F中的每一个函数依赖，并修改表中的元素。其方式如下：取F中一个函数依赖XY，在X的分量中寻找相同的行，然后将这些行中Y的分量改为相同的符号，如果其中有aj，则将bij改为aj；若无aj，则改为bij(i是这些行的行号最小值)。 这样反复进行，如果发现某一行变成了a1,a2,，ak，则分解具有无损连接性；如果F中所有函数依赖都不能再修改表中的内容，且没有发现这样的行，则分解不具有无损连接性。,例：对给定的关系模式R(U,F)，U=A,B,C,D,E，F=AC，BC，CD，DEC，CEA，有如下的分解： =AD，AB，BE，CDE，AE，判断分解是否无损。,解： (1)构造一个初始的二维表，如下表1-1所示。,(2)根据AC，对上表进行处理，由于属性列A上的第1,2,5行是相同的符号a1，而C列的1,2,5行没有a1，所以将C列的b13、b23、 b53改为相同的符号b13。又根据BC将C列的b13、b33改为同一符号b13，修改后的表如表1-2所示。,(3)根据CD，对上表进行处理，由于属性列C上的第1,2,3,5是相同的符号b13，而D列的1,2,3,5行中有a4，所以将D列的b24、b34、 b54改为相同的符号a4，修改后的表如表1-3所示。,(4)根据DEC，对上表进行处理，由于属性列DE上的第3,4,5是相同的符号a4a5，而C列的3,4,5行中有a3，所以将C列的3、5行改为a3，修改后的表如表1-4所示。,(5)根据CEA，将属性列A上的第3、4行改为a1，修改后如表1-5所示。,(6)通过上述更改，使得第3行为a1，a2，a3，a4，a5，算法终止，且具有无损连接性。,课堂练习：对给定的关系模式R(U,F)，U=U,V,W,X,Y,Z，F=UV，WZ，YU，WYX，现如下的分解： (1)1=WZ，VY，WXY，UV (2)2=UVY,WXYZ 判断上述分解是否具有无损连接性。,结果： 1不具有无损连接性 2具有无损连接性,6.4.3 分解保持函数依赖,定义：设有关系模式R，F是R的函数依赖集，Z是R的一个属性集合，则称Z所涉及到的F+中所有函数依赖为F在Z上的投影，记为Z(F)，有 Z(F)=XY| XYF+且XYZ 定义：设有关系模式R的一个分解=R1，R2，Rk，F是R的依赖集，如果F等价于R1(F) R2(F) Rk(F)，则称分解具有依赖保持性。,例：对给定的关系模式R(U,F)，U=A,B,C,D，F=AB，BC，CD，DA，判断关系模式R的分解=AB，BC，CD是否具有函数依赖保持性。,解： AB(F)=AB,BA BC(F)=BC,CB CD(F)=CD,DC AB(F)BC(F) CD(F)=AB，BA，BC，CB， CD，DC 从中可以看到， AB，BC，CD均得以保持。 又因为D+=ABCD，A D+，所以DA也得以保持。 所以该分解具有依赖保持性。,前例：现有关系模式R(A,B,C)，其上的函数依赖集F=AB，CB，判断1=AB，AC， 2=AB，BC是否保持函数依赖。,第一种分解 AB(F)=AB AC(F)= AB(F)AC(F)=ABF 所以没有保持函数依赖,第二种分解 AB(F)=AB BC(F)=BC AB(F)BC(F)=F 所以保持函数依赖,说明： (1)分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。它们两者之间是没有联系的。具有无损连接性的分解不一定保持函数依赖，保持函数依赖的不一定具有无损连接性。例如上一例题的二种分解，一种具有无损连接性但没有保持函数依赖，另一种不具有无损连接性但保持了函数依赖。 因此，关系模式的一个分解可能是保持函数依赖的，可能是具有无损连接的，也可能是既具有无损连接性又保持函数依赖的。 (2)若要求分解既具有无损连接性，又保持函数依赖，则模式分解可以达到3NF，但不一定能达到BCNF。,6.4.3 模式分解的算法 算法1、把一个关系模式分解为3NF，使它具有无损连接性又具有依赖保持性。 输入：关系模式R和R的最小依赖集Fm 输出：R的一个分解=R1，R2，Rk，Ri为3NF(i=1，k)， 具有无损联接性和依赖保持性。 方法： (1)如果Fm中只有一依赖XA，且XA=R，则输出=(R),则转(4)。 (2)如果R中某些属性与F中所有依赖的左边和右边都无关（N类属性），则将它们构成关系模式，R中将它们分出去。 (3)对于Fm中的每一个XiAi，都构成一个关系子模式Ri=XiAi。 (4)停止分解， =R1，R2，Rk (5)判定是否具有无损连接性，若是，转(7)，若不是，转（6） (6)令= X，其中X是R的候选码。 (7)输出。,例：对给定的关系模式R(U,F)，U=C,T,H,R,S,G，F=CSG，CT，THR，HRC， HSR，将其无损连接性和依赖保持性分解为3NF。,解：求出F的最小依赖集，Fm= CSG，CT，THR，HRC， HSR (1)不满足条件 (2)不满足条件 (3)R1=CSG，R2=CT，R3=THR，R4=HRC，R5=HSR (4) =CSG，CT，THR，HRC，HSR (5)判断其无损联接性如下表所示，由此可知具有无损连接性。,(6)不执行 (7)输出 =CSG，CT，THR，HRC，HSR,算法2：把关系模式无损分解成BCNF（但没要求保持函数依赖） 输入：关系模式R和函数依赖集F 输出：R的一个无损分解=R1，R2，Rk。 方法： (1)令=(R) 。 (2)如果中所有模式都是BCNF，则转(4)。 (3)如果中有一个关系模式S不是BCNF，则S中必能找到一个函数依赖XA，且X不是S的候选码，A不属于X，设S1=XA，S2=S-A，则分解S1，S2代替S，转(2)。 (4)分解结束，输出。,例：对给定的关系模式R(U,F)，U=A,B,C,D,E，F=AD，ED，DB，BCD， DCA，将其无损联接地分解为BCNF。,方法一： 解：R只有一个候选码EC。 (1)令=R(U，F)； (2) 中不是所有的模式都是BCNF，转(3); (3) 考虑AD，这个函数依赖不满足BCNF范式的条件(A不包含候选码EC)，所以将其分解为R1(AD)、R2(ABCE)。计算R1和R2的最小函数依赖集分别为：F1=AD，F2=EB，AB，。 (因为R1已是BCNF，进一步分解R2) (4)考虑EB，把R2分解为R21(EB)、R22(ACE)。计算R21和R22的最小函数依赖集分别为：F21=EB，F22=CEA。 (R21已是BCNF，R22也是BCNF) 所以F分解为：=AD，EB，ACE,方法二： 解：R上只有一个候选码EC。 因为ED，所以R 1NF R11(ED)，F11=ED，所以R11 BCNF R12(ABCE)，F12=EB， AB，ECA，所以R12 1NF 分解F12，因为EB R121(EB)， F121=EB ，所以R121 BCNF R122(ACE)，F122=ECA，所以R122BCNF 所以R分解为=ED，EB，ACE,例：对给定的关系模式R(U,F)，U=A,B,C,D,E，F=AD，ED，DB，BCD， DCA，将其无损联接地分解为BCNF。,由此可知，分解不是唯一的。,综合习题：,1、对于关系模式R(A,B,C,D)，其上的函数依赖集为： F=AC，CA，BAC，DAC (1)计算(AD)+。 (2)求F的最小函数依赖集Fm。 (3)求R的码。 (4)将R分解成满足3NF并具有无损连接性与保持依赖性。 (5)将R分解使其满足BCNF且具有无损连接性。,(1)(AD)+=ADC (2)Fm=AC，CA， BA， DA 或者Fm=AC，CA， BA， DC Fm=AC，CA， BC， DA Fm=AC，CA， BC， DC (3)码为DB (4) 1=(AC,BA,DA) 不具有无损连接性，所以=(AC,BA,DA,DB),(5)候选码DB。 因为DA，所以R 1NF R11(DA)，F11=DA，所以R11 BCNF R