第六章习题解答.doc

例：求FABDAC，CBE，ADBF，BE的最小函数依赖集Fm注意：当在函数依赖已经改变的地方开始一个新步骤时，重写函数依赖集很重要，这样可以在下一步中方便引用。第一步对F中的函数依赖运用分解原则来创建一个等价函数依赖集H，该集合中每一个函数依赖的右部是单个属性：HABDA，ABDC，CB，CE，ADB，ADF，BE第二步考察每一个函数依赖是否是必须的，去除非必要的函数依赖（1） ABDA是平凡的函数依赖，所以显然是非必要的函数依赖，因此去除。保留在H中的函数依赖是HABDC，CB，CE，ADB，ADF，BE（2） 考察ABDC，去掉此函数依赖将会得到新的函数依赖集JCB，CE，ADB，ADF，BE。如果ABDC是非必要的，则C(ABD)J。(ABD)J=ABDFE，不包含C，因此ABDC是必要的函数依赖，不能去掉。HABDC，CB，CE，ADB，ADF，BE（3） 考察CB，JABDC，CE，ADB，ADF，BE。(C)J=CE，不包含B，因此CB是必要的函数依赖，保留在H中。（4） 考察CE，JABDC，CB，ADB，ADF，BE。(C)J=CBE，包含E，因此是不必要的，去除后得到的函数依赖集为HABDC，CB，ADB，ADF，BE（5） 同理考察函数依赖、和，最后得到的函数依赖集为HABDC，CB，ADB，ADF，BE。为了第三步方便引用，我们进行重新编号：HABDC，CB，ADB， ADF， BE。第三步考察每一个左部为多个属性的函数依赖，看左部的每个属性是否是必须的，能否用更小的属性集替代原有的属性集。首先从函数依赖ABDC开始。（1） 去除A？如果A可以去除，那么可得到新的函数依赖集JBDC，CB，ADB， ADF， BE。去掉A后BD在J上的闭包将比在H下函数决定更多的属性，如果(BD)J(BD)H（或者C(BD)H），则说明去掉A得到的函数依赖集和原有的函数依赖集是等价的，可以用BDC替换ABDC。(BD)HBDE，不包含C，所以A不能去掉。（2） 去掉B？JADC，CB，ADB， ADF， BE。（3） 去掉D？JAC，CB，ADB， ADF， BE。因为H的函数依赖集在第三步发生了改变，因此我们需要回到第二步。最后得到的函数依赖集为H=ADC， CB， ADF， BE1. 设有关系模式R(A,B,C,D,E ,F,G,H,I,J),其上的函数依赖集F=AB C, ADE, B F, FGH, DIJ问R的候选码是什么？将R先分解成2NF关系，然后再分解成3NF关系。解：因为AB为只在左部出现的属性，又ABABCDEFGHIJ，因此AB是R唯一的候选码。其中，A和B为主属性，C、D、E、F、G、H、I和J都是非主属性，因为ADE，存在非主属性对码的部分函数依赖，因此R1NF。将R先分解成2NF关系，我们可将R分解为：R1（A，D，E，I，J）F1= A DE， DIJ R2（B，F，G，H）F2= B F, FGHR3（A，B，C）F3= ABCR1 和R2中分别存在着非主属性对码传递函数依赖，A D， DIJ和B F, FGH，因此R1 和R23NF。若要满足3NF，则我们可以将R1 和R2进一步分解，以去除非主属性对码的传递函数依赖。R1可分解为R4（A，D，E）和R5（D，I，J）R2可分解为R6（B，F）和R7（F，G，H）R可分解为r R3，R4，R5，R6，R7解：判断关系模式属于第几范式，首先要求解出关系的（候选）码。根据码的求解理论，我们先将属性分为4类：L类属性（只在最新函数依赖集左边出现的属性）：Book_title, AuthornameR类属性（只在右边出现的属性）：Publisher, Listprice, Author-affilN类属性（两边均为出现的属性）：LR类属性（左右两边都出现的属性）：Book_typeL类属性必是任一候选码的组成属性，因此候选码必包含属性Book_title和 Authorname。因为（Book_title, Authorname）+=（Book_title, Authorname，Publisher, Listprice, Author-affil，Book_type）=U，所以（Book_title, Authorname）是唯一候选码。Book_title, Authorname是主属性，其余属性是非主属性。因为存在非主属性对码的部分函数依赖，如（Book_title, Authorname）publisher，因此BOOK1NF。分解方法有多种，下面将逐一解释说明：（同学们只要选择其中一种解法即可）方法一：转换为3NF保持函数依赖的分解（P191算法6.3）第1步，对函数依赖集进行极小化处理，得到最小函数依赖集F=Book_title Publisher， Book_title Booke_type，Book_typeListprice，AuthornameAuthor_affil第2步，将F中函数依赖按相同左部原则分组，可分为3组：F1=Book_title Publisher， Book_title Booke_type F2= Book_typeListprice F3= AuthornameAuthor_affil第3步，每一组函数依赖所涉及全部属性组成分解后的一个关系模式，因此我们会分解得到3个关系模式（，）R1（Book_title ，Publisher，Booke_type），R1上函数依赖集为F1=Book_title Publisher， Book_title Booke_type R2（Book_type，Listprice ），R上函数依赖集为F2= Book_typeListprice R3（Authorname，Author_affil），R上函数依赖集为F3= AuthornameAuthor_affil方法二：转换为3NF既有无损连接性又保持函数依赖的分解（P191算法6.4）根据算法可得到一个分解，（见方法一）的码为（Book_title, Authorname），因为不存在（Book_title, Authorname）（，）因此在.算法分解的基础上增加一张表(Book_title, Authorname)分解结果为：，R1（Book_title ，Publisher，Booke_type），F1=Book_title Publisher， Book_title Booke_type R2（Book_type，Listprice ），F2= Book_typeListprice R3（Authorname，Author_affil），F3= AuthornameAuthor_affil(Book_title, Authorname)，F=方法三：转换为的无损连接分解（P19算法6.）BCNF要求每一个非平凡的函数依赖必含有码，因为函数依赖Book_title （Publisher， Booke_type），Book_typeListprice，AuthornameAuthor_affil左部都不含候选码，所以BCNF不属于BCNF。从不符合BCNF的函数依赖中选取一个，如Book_typeListprice进行分解，则可分解为两张表：R1（Book_type，Listprice ），F1= Book_typeListprice 和 R2（Book_title, Authorname，Publisher, Author-affil，Book_type），F2=Book_title （Publisher，Booke_type），AuthornameAuthor_affil R2不属于BCNF，同理，可选取不符合BCNF的函数依赖进行分解。如果根据Book_title （Publisher，Booke_type）进行分解，则R2可进一步分解为：R21 (Book_title,，Publisher，Booke_type) ，F21=Book_title （Publisher，Booke_type）R22(Authorname， Author-affil ，Book_title) ，F22= AuthornameAuthor_affil 同理，因为R22中的函数依赖AuthornameAuthor_affil左部不含有候选码，所以R22不属于BCNF。根据AuthornameAuthor_affil对R22分解，可分解为：R221(Authorname， Author-affil) ，F221= AuthornameAuthor_affil R222(Book_title ，Authorname) ，F222=经过整理后，可得到一个分解，R1（Book_type，Listprice ），F1= Book_typeListprice R2（Book_title ，Publisher，Booke_type），F2=Book_title Publisher， Book_title Booke_type R3（Authorname，Author_affil），F3= AuthornameAuthor_affil(Book_title, Authorname)，F=（由于BOOK中有多个函数依赖不符合BCNF，因选取次序不同得到的分解结果可能有多个）方法四：由于BOOK存在非主属性对码的部分函数依赖，在分解中去掉部分函数依赖。BOOK的码为(Book_title, Authorname)，因此通常分解为3张表，第1张表的码是Book_title，表中包含Book_title和由它函数决定的所有属性；第2张表的码是Authorname，表中包含Authorname和由它函数决定的所有属性；第3张表的码是(Book_title, Authorname)，表中包含属性Book_title和Authorname，以及由（Book_title, Authorname）共同函数决定的属性，分解，R1（Book_title ，Publisher，Booke_type，Listprice），F1=Book_title Publisher， Book_title Booke_type， Book_typeListprice R2（Authorname，Author_affil），F2= AuthornameAuthor_affil分解后的R1和R2均达到2NF。进一步分析，R1存在非主属性对码的传递函数依赖，所以不属于3NF，需再进行分解。去掉传递函数依赖后，R1可分解为：R11（Book_title ，Publisher，Booke_type），F11=Book_title Publisher， Book_title Booke_type R12（Booke_type，Listprice），F12= Book_typeListprice 分解后的关系模式均达到BCNF，停止分解。分解结果，R1（Book_title ，Publisher，Booke_type），F1=Book_title Publisher， Book_title Booke_type R2（Booke_type，Listprice），F2= Book_typeListprice R3（Authorname，Author_affil），F3= AuthornameAuthor_affil2. 设有关系模式R(A,B,C,D),其上的函数依赖集F=A C, CA, BAC, DAC 计算(AD)+ 求F的最小函数依赖集Fm 求R的码 将R分解为满足3NF且保持函数依赖 将R分解为满足3NF并具有无损连接性和保持函数依赖 将R分解为满足BCNF且具有无损连接性解：（1）令X=AD，X(0)=AD， X(1)=ADC，X(2)=ADC，故(AD)+ADC(2)第一步：将F中的函数依赖右部属性单一化：H= A C, CA, BA, BC, DA, DC 第二步：去掉不必要的函数依赖考察A C，若A C是不必要的依赖，则H= CA, BA, BC, DA, DC ，计算AH+，AH+A，不包含C，所以A C是必要的函数依赖，我们保留在H中。H= A C, CA, BA, BC, DA, DC 考察C A，若C A是不必要的依赖，则H=AC, BA, BC, DA, DC ，计算CH+，CH+C，不包含A，所以C A也是必要的函数依赖，我们保留在H中。H= A C, CA, BA, BC, DA, DC 考察B A，若B A是不必要的依赖，则H=AC, CA, BC, DA, DC ，计算BH+，BH+BCA，包含A，所以B A是不必要的函数依赖，我们可以除掉，则H= A C, CA, BC, DA, DC 考察B C，若B C是不必要的依赖，则H=AC, CA, DA, DC ，计算BH+，BH+B，不包含C，所以B A是必要的函数依赖，我们保留在H中， H= A C, CA, BC, DA, DC 同理，DA是不必要的函数依赖，H= A C, CA, BC, DC 第三步：因为H中所有函数依赖左部均为单一属性，所以H即为最小函数依赖集：HMin= A C, CA, BC, DC （注意：最小函数依赖并不是唯一的，求解的次序不同，得到的最小函数依赖集可能不同。大家也可能得到另一个解HMin= A C, CA, BA, DA ）(3) 因为BD在F中所以函数依赖的右部均为出现，所以候选关键字中一定含有BD，又BD在F上的闭包(BD)F+ABCD，包含所有的属性，所以BD是R的唯一候选关键字。(4) 将（2）中求得的最小函数依赖集按相同左部的原则分为三组：F1= A C F2= CA F3= BC F4= DC 则按分解为满足3NF且保持函数依赖的算法可知，