授授课主主题第第17讲计划学划学时2第第6章章 关系数据理关系数据理论关系模关系模式分解的等价式分解的等价标准准教学目的教学目的和要求和要求1、掌握关系模式分解的两个等价、掌握关系模式分解的两个等价标准的算法准的算法2、理解分解、理解分解为3NF和和BCNF的两个算法的两个算法教学重点教学重点和和难点点关系模式分解的两个等价关系模式分解的两个等价标准的算法准的算法教学内容教学内容1、关系模式分解的等价、关系模式分解的等价标准准2、无、无损连接的定接的定义和性和性质3、分解具有保持函数依、分解具有保持函数依赖4、模式分解的算法、模式分解的算法教学教学过程程见课件件数据库系统概论17模式分解的等价标准消除非主属性对码的部分函数依赖消除非主属性对码的传递函数依赖消除函数依赖的决定因素是非码1NF2NF3NFBCNF关系模式的规范化，是通过对关系模式的分解实现的。分解的实质：“一事一表”，让一个关系只描述一个实体或联系，使关系单一化，以利于处理简单化。数据库系统概论17模式分解的等价标准规范化过程就是把一个关系模式分解为若干个关系模式，而且这种分解应该是可逆的。所谓可逆可逆，是要求模式的分解是没有信息丢失，并保证分解后产生的关系模式集合和原来的关系模式等价。如何对关系模式进行分解才能保证没有信息丢失呢？对于同一个关系模式可能有多种分解方案。下面的例子给出三种分解方案，如何判断哪种分解方案更好呢？6.4 6.4 关系模式的分解关系模式的分解数据库系统概论17模式分解的等价标准三种分解方案三种分解方案( (模式分解不唯一模式分解不唯一) )例：关系模式S(Sno,sdept,dean) 。何D2s3何D2s2罗D1s1deanSdept SnoF=Snosdept，sdeptdeanS1是哪个系的学生？何是哪个系的系主任呢？D1的系主任是谁呢？做连接snosdeptdeans1d1罗s1d1何s1d2罗s1d2何联接后问题没有得到解决，原因是没有保持函数依赖。第一种分解：SnoS1S2S3Sdeptd1d2dean罗何3NF数据库系统概论17模式分解的等价标准snosdeptdeanS1D1罗S2D2何S3D2何做自然连接分解后可以恢复原关系，但数据冗余问题没有得到解决，问题是丢失了函数依赖sdeptdean。D1的系主任是谁呢？何是哪个系的系主任呢？关系模式S(Sno,sdept,dean)， F=Snosdept，sdeptdean第二种分解：Sno sdeptS1 d1S2 d2S3 d2Sno deanS1 罗S2 何S3 何3NF数据库系统概论17模式分解的等价标准snosdeptdeanS1D1罗S2D2何S3D2何做自然连接问题得到了彻底解决，即不丢失信息，也减少了冗余。关系模式S(Sno,sdept,dean)， F=Snosdept，sdeptdean第三种分解：Sno sdeptS1 d1S2 d2S3 d2Sdept deand1 罗d2 何3NF数据库系统概论17模式分解的等价标准6.4.1 6.4.1 模式分解的等价标准模式分解的等价标准 上面例子中，每种分解方案得到的两个关系模式都属于3NF（实际上，也属于BCNF）。如何比较这三种分解方案的优劣呢？将一个关系模式分解为多个关系模式时，除了提高规范化程度外还需要什么别的考虑吗？常用的关系模式分解的等价标准有：l分解是具有无损连接性的；l分解是保持函数依赖的；l分解既要具有无损连接又要保持函数依赖两种。数据库系统概论17模式分解的等价标准(1)无损连接的定义 指的是对关系模式分解时，原关系模式下任一合法的关系实例在分解之后应能通过自然连接运算恢复起来。定义：设=R1，R2，Rk是关系模式R的一个分解，如果对于R的任一满足F的关系r都有 r=R1(r) R2(r) Rk(r)则称这个分解是满足依赖集F的无损连接。6.4.2 6.4.2 无损连接的定义和性质无损连接的定义和性质数据库系统概论17模式分解的等价标准(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不具有无损连接性。数据库系统概论17模式分解的等价标准(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中所有函数依赖都不能再修改表中的内容，且没有发现这样的行，则分解不具有无损连接性。数据库系统概论17模式分解的等价标准例：对给定的关系模式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所示。a5b54b53b52a1AEa5a4a3b42b41CDEa5b34b33a2b31BEb25b24b23a2a1ABb15a4b13b12a1ADEDCBARi表1-1数据库系统概论17模式分解的等价标准(3)根据CD，对上表进行处理，由于属性列C上的第1,2,3,5是相同的符号b13，而D列的1,2,3,5行中有a4，所以将D列的b24、b34、 b54改为相同的符号a4，修改后的表如表1-3所示。a5b54b13b52a1AEa5a4a3b42b41CDEa5b34b13a2b31BEb25b24b13a2a1ABb15a4b13b12a1ADEDCBARi表1-2a5a4b13b52a1AEa5a4a3b42b41CDEa5a4b13a2b31BEb25a4b13a2a1ABb15a4b13b12a1ADEDCBARi表1-3(4)根据DEC，对上表进行处理，由于属性列DE上的第3,4,5是相同的符号a4a5，而C列的3,4,5行中有a3，所以将C列的3、5行改为a3，修改后的表如表1-4所示。数据库系统概论17模式分解的等价标准(5)根据CEA，将属性列A上的第3、4行改为a1，修改后如表1-5所示。(6)通过上述更改，使得第3行为a1，a2，a3，a4，a5，算法终止，且具有无损连接性。a5a4a3b52a1AEa5a4a3b42b41CDEa5a4a3a2b31BEb25a4b13a2a1ABb15a4b13b12a1ADEDCBARi表1-4a5a4a3b52a1AEa5a4a3b42a1CDEa5a4a3a2a1BEb25a4b13a2a1ABb15a4b13b12a1ADEDCBARi表1-5数据库系统概论17模式分解的等价标准课堂练习：对给定的关系模式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具有无损连接性数据库系统概论17模式分解的等价标准6.4.3 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)，则称分解具有依赖保持性。数据库系统概论17模式分解的等价标准例：对给定的关系模式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也得以保持。 所以该分解具有依赖保持性。数据库系统概论17模式分解的等价标准前例：现有关系模式R(A,B,C)，其上的函数依赖集F=AB，CB，判断1=AB，AC， 2=AB，BC是否保持函数依赖。 第一种分解AB(F)=ABAC(F)=AB(F)AC(F)=ABF所以没有保持函数依赖第二种分解AB(F)=ABBC(F)=BCAB(F)BC(F)=F所以保持函数依赖数据库系统概论17模式分解的等价标准说明：(1)分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。它们两者之间是没有联系的。具有无损连接性的分解不一定保持函数依赖，保持函数依赖的不一定具有无损连接性。例如上一例题的二种分解，一种具有无损连接性但没有保持函数依赖，另一种不具有无损连接性但保持了函数依赖。 因此，关系模式的一个分解可能是保持函数依赖的，可能是具有无损连接的，也可能是既具有无损连接性又保持函数依赖的。(2)若要求分解既具有无损连接性，又保持函数依赖，则模式分解可以达到3NF，但不一定能达到BCNF。数据库系统概论17模式分解的等价标准6.4.3 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)输出。数据库系统概论17模式分解的等价标准例：对给定的关系模式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)判断其无损联接性如下表所示，由此可知具有无损连接性。数据库系统概论17模式分解的等价标准RiCTHRSGCSG a1a2b13b14a5a6CTa1a2b23b24b25b26THRa1a2a3a4b35b36HRC a1a2a3a4b45b46HSR a1a2a3a4a5a6(6)不执行(7)输出 =CSG，CT，THR，HRC，HSR数据库系统概论17模式分解的等价标准算法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)分解结束，输出。数据库系统概论17模式分解的等价标准例：对给定的关系模式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数据库系统概论17模式分解的等价标准方法二：解：R上只有一个候选码EC。因为ED，所以R 1NFR11(ED)，F11=ED，所以R11 BCNFR12(ABCE)，F12=EB， AB，ECA，所以R12 1NF分解F12，因为EBR121(EB)， F121=EB ，所以R121 BCNFR122(ACE)，F122=ECA，所以R122BCNF所以R分解为=ED，EB，ACE例：对给定的关系模式R(U,F)，U=A,B,C,D,E，F=AD，ED，DB，BCD， DCA，将其无损联接地分解为BCNF。由此可知，分解不是唯一的。数据库系统概论17模式分解的等价标准综合习题：1、对于关系模式R(A,B,C,D)，其上的函数依赖集为：F=AC，CA，BAC，DAC(1)计算(AD)+。(2)求F的最小函数依赖集Fm。(3)求R的码。(4)将R分解成满足3NF并具有无损连接性与保持依赖性。 (5)将R分解使其满足BCNF且具有无损连接性。数据库系统概论17模式分解的等价标准(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)ABCDACa1b12a3b14BAa1a2a3b24DAa1b32a3a4数据库系统概论17模式分解的等价标准(5)候选码DB。因为DA，所以R 1NFR11(DA)，F11=DA，所以R11 BCNFR12(BCD)，F12=DC， ，所以R12 1NF分解F12，因为DCR121(DC)， F121=DC ，所以R121 BCNFR122(DB)，全码，所以R122BCNF所以R分解为=DA，DC，DB其分解结果不唯一。数据库系统概论17模式分解的等价标准本讲小结1、关系模式分解的等价标准是具有无损连接和保持函数依赖。判断无损连接的测试方法表格法。判断保持函数依赖的方法是分解后的关系模式中函数依赖集是否和原F等价。2、掌握两个算法：无损连接和保持函数依赖分解为3NF、无损连接分解为BCNF数据库系统概论17模式分解的等价标准