数据库——模式分解.ppt

《数据库——模式分解.ppt》由会员分享，可在线阅读，更多相关《数据库——模式分解.ppt（67页珍藏版）》请在优知文库上搜索。

1、习题讲解等价与使得真子集有赖中不存在这样的函数依等价与使得赖中不存在这样的函数依仅含一个属性中任一函数依赖的右部FAZAXFZXAXFAXFFAXFF,) 3(,)2() 1 (最小依赖集的最小函数依赖集求,ACCACBABBAF1）考查AB，去掉它，计算A+=AC，不包含B，不能去掉2）考查 B A，去掉它，计算BB C A，包含A，可去掉它3）考查 B C，去掉它，计算BB，不包含C，不能去掉4）考查A C，去掉它，计算AA B C，包含C，可去掉它5）考查 C A，去掉它，计算CC，不包含A，不能去掉,21ACCBABBAFACCBBAF1 2 3 4 5求解关系模式的候选码 属性分类

2、L类：只出现在函数依赖的左边的属性 R类：只出现在函数依赖的右边的属性 N类：在函数依赖的两边均未出现的属性 LR类：出现在函数依赖的两边的属性求解关系模式的候选码 对于给定的关系模式R及其函数依赖集F 如果X是L或N类属性，则X必为R的任一候选码的成员 如果X是R类属性，则X必不在任何候选码中 如果X是L和N类组成的属性组，且X+包含了全部属性，则X是R的唯一候选码前例n 例：关系模式CTHRSG, 若最小依赖集为F=C T, HR C,CS G,HS R,HT R, 候选关键字为HS？n 解： L、N类属性为HS，LR属性为CTR HS+=HS RCTG，包含全部属性，所以为唯一候选码n

3、函数依赖图FDG 用有向图表示的函数依赖，如XY即X Y,ADCDBCBDDEDAFL L或或N N类属性有类属性有E E和和C, LRC, LR类属性类属性ADBADB，令，令X=EC,(EC)X=EC,(EC)+ +=U,EC=U,EC为为R R的唯一候选码。的唯一候选码。对对左边为单属性左边为单属性的函数依赖集求所有候选码的函数依赖集求所有候选码(1) 求F的最小依赖集F(2) 作出函数依赖图FDG(3) 从FDG图中找出无入边的属性集X(4) 察看FDG图中有无回路，若无，则输出X并结 束,否则进行下一步(5) 从各中各取一个结点的属性与X组成一个候选码，重复取得所有可能的组合，即R的

4、全部候选码所有的候选码求F),(ABCDER已知IBOQSD已知,),(DSQIOBBIFIBOQSDR和所有的候选码求 FISFF候选码为, 和所有的候选码求已知,),(FWXZWYZWYXWYYWFXYWZR和所有的候选码求已知,),(FIQQOOBBIDSFSDBIOQRZXWZYXWYYWF唯一的候选码为,SQSOSBSIFF,候选码为ZWYXSDIBOQ算法：对左边为多属性的函数依赖集求所有候选码 (1) 将R所有属性分为L,R,N,LR四类，并令X代表L,N两类，令Y代表LR类。(2) 求X+，若X+包含R全部属性，则X即为R的唯一候选码，结束，否则转下一步。(3) 在Y中取一属性

5、A，求(XA)+,若它包含R的全部属性，则转下一步，否则换一个属性重试，直至试完所有Y中的属性。(4) 若已找出所有候选码，则结束，否则在Y中依次取两个、三个、，求它们的属性闭包，直至其闭包包含R的全部属性。n 属于N-P完全问题 (一类直观上难解可又找不出方法来证明它们的确难解的计算问题)n 多属性下求解候选码的充分条件第六章 关系数据理论6.1 数据依赖6.2 规范化6.3 数据依赖的公理系统6.4 模式的分解模式的分解6.4 模式的分解n 把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一并不是唯一的。n 只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义。UUU

6、URRUUUURURURURKKKKK.,.,.,)(),.,(),()(21112211的属性集合，的子集，分别是都是，其中：分解关系模式分解的标准三种模式分解的等价定义 分解具有无损连接性 分解要保持函数依赖 分解既要保持函数依赖，又要具有无损连接性模式的分解（续）关系模式R的一个分解：= R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，F Fi i 为为 F F在在 U Ui i 上的投影。上的投影。函数依赖集合XY | XY F+XY Ui 的一个覆盖 Fi 叫作 F F 在属性在属性 UiUi 上的投影上的投影模式的分解（续）关系模式R的一个分解：= R1，R2，Rn U=

7、U1U2Un，且不存在 Ui Uj，F Fi i 为为 F F在在 U Ui i 上的投影。上的投影。函数依赖集合XY | XY F+XY Ui 的一个覆盖 Fi 叫作 F F 在属性在属性 UiUi 上的投影上的投影模式的分解（续）n 例: SL（Sno， Sdept， Sloc） F= SnoSdept,SdeptSloc,SnoSloc SL2NF n 存在插入异常、删除异常、冗余度大和修改复杂等问题n 分解方法可以有多种 。模式的分解（续）SL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 IS B 95005 PH B 模

8、式的分解（续）1. SL分解为下面三个关系模式： SN(Sno) SD(Sdept) SO(Sloc)分解后的关系为： Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 PH 95005 模式的分解（续）n 分解后的数据库丢失了许多信息丢失了许多信息n 例如无法查询95001学生所在系或所在宿舍。n 如果分解后的关系可以通过自然连接恢复为原来的关系，那么这种分解就没有丢失信息丢失信息模式的分解（续）2. SL分解为下面二个关系模式： NL(Sno, Sloc) DL(Sdept, Sloc)分解后的关系为： NL DL Sno Sloc

9、 Sdept Sloc 95001 A CS A 95002 B IS B 95003 C MA C 95004 B PH B 95005 B 模式的分解（续）NL DL Sno Sloc Sdept 95001 A CS 95002 B IS 95002 B PH 95003 C MA 95004 B IS 95004 B PH 95005 B IS 95005 B PH 模式的分解（续）n NLDL比原来的SL关系多了3个元组 无法知道95002、95004、95005 究竟是哪个系的学生n 元组增加了，信息丢失了元组增加了，信息丢失了第三种分解方法3. 将SL分解为下面二个关系模式： N

10、D(Sno, Sdept) NL(Sno, Sloc) 分解后的关系为： 模式的分解（续）ND NL Sno Sdept Sno Sloc 95001 CS 95001 A 95002 IS 95002 B 95003 MA 95003 C 95004 IS 95004 B 95005 PH 95005 B 模式的分解（续） ND NL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 CS A 95005 PH B 与SL关系一样，因此没有丢失信息。具有无损连接性的模式分解n 关系模式R的一个分解 = R1，R2， ，Rn,若R与R1

11、、R2、Rn自然连接的结果相等，则称关系,模式R的这个分解具有无损连接性无损连接性（Lossless join）n 具有无损连接性的分解保证不丢失信息n 无损连接性不一定能解决插入异常、删除异常、修改复杂、数不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题据冗余等问题为无损连接分解（则分解自然连接即可还原若),.,)( ,.22211121KKKKFURFURFURRRRR模式的分解（续） 第三种分解方法具有无损连接性 问题: 这种分解方法没有保持原关系中的函数依赖 SL中的函数依赖SdeptSloc， 没有投影到关系模式ND、NL上 保持函数依赖的模式分解设关系模式R被分解为若干个关

12、系模式 R1，R2，Rn （其中U=U1U2Un，且不存在Ui Uj，Fi为F在Ui上的投影），若F所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖Fi所逻辑蕴含，则称关系模式R的这个分解是保持函数依赖的保持函数依赖的（Preserve dependency）。保持函数依赖的模式分解依赖性具有保持函数价的，即前后的函数依赖集是等解若两者相等，则表示分和分别求解，（的一个分解为设,)(),.,1222111ikiKKKFFFURFURFURFUR例 子n R(A,B,C), F=AB, C B 分解1=(A,B,AB), (A,C) 分解2=(A,B, AB), (B,C, C B

13、)n 计算分解1,2中3个模式的闭包F AB：A+=AB,B+=B,AB+=AB, 则对AB的分解有函数依赖AB AC：A+=A,C+=C,AC+=AC, 则对AC的分解没有函数依赖 BC：B+=B,C+=CB,BC+=BC, 则对BC的分解只有函数依赖CBn 分解1：只有AB，显然，分解1不具有依赖保持性n 分解2：保留了所有函数依赖，具有依赖保持性第四种分解方法n SL（Sno， Sdept， Sloc） F= SnoSdept,SdeptSloc,SnoSlocn 将SL分解为下面二个关系模式： ND(Sno, Sdept) DL(Sdept, Sloc) 这种分解方法就保持了函数依赖。

14、 模式的分解（续）n 如果一个分解具有无损连接性无损连接性，则它能够保证不丢失信息。n 如果一个分解保持了函数依赖函数依赖，则它可以减轻或解决各种异常情况。n 分解具有无损连接性和分解保持函数依赖是两个互相独立的互相独立的标准标准。n 具有无损连接性的分解不一定能够保持函数依赖。同样，保持函数依赖的分解也不一定具有无损连接性。模式的分解（续） 第一种分解方法既不具有无损连接性，也未保持函 数依赖，它不是原关系模式的一个等价分解 SN(Sno)， SD(Sdept)， SO(Sloc) 第二种分解方法保持了函数依赖，但不具有无损连 接性。 NL(Sno, Sloc)， DL(Sdept, Slo

15、c)SLSL（SnoSno， SdeptSdept， SlocSloc）F= F= SnoSdept,SdeptSloc,SnoSlocSnoSdept,SdeptSloc,SnoSloc 模式的分解（续）第三种分解方法具有无损连接性，但未持函数依赖 ND(Sno, Sdept)， NL(Sno, Sloc)第四种分解方法既具有无损连接性，又保持了函数依赖 ND(Sno, Sdept)， DL(Sdept, Sloc)SL（Sno， Sdept， Sloc）F= SnoSdept,SdeptSloc,SnoSloc分解算法n 算法6.2 判别一个分解的无损连接性n 算法6.3 （合成法）转换为

16、3NF的保持函数依赖的分解。n 算法6.4 转换为3NF既有无损连接性又保持函数依赖的分解n 算法6.5 转换为BCNF的无损连接分解（分解法）n 算法6.6 达到4NF的具有无损连接性的分n 解P196 图5 .11判别一个分解的无损连接性算法6.2(1)构造初始表： 构造一个k行n列的初始表，其中每列对应于R的一个属性，每行用于表示分解后的一个模式组成。 如果属性Aj属于关系模式Ri, 则在表的第一i行第j列置符号aj，否则置符号bij 。(2)根据F中的函数依赖修改表内容： 考察F中的每个函数依赖XY,在属性组X所在的那些列上寻找具有相同符号的行，如果找到这样的两行或更多的行， 则修改这些行，则使这些行上属性组Y所在的列上元素相同。 修改规则是：如果y所在的要修改的行中有一个为aj， 则这些元素均变成aj；否则改动为bmj（其中m为这些行的最小行号）。 判别一个分解的无损连接性 注意：若某个bij被改动，则该列中凡是与bij相同的符号均做相同的改动。 循环地对F中的函数依赖进行逐个处理，直到发现表中有一行 变为a1,a2,an或不能再被修改为止。 (3)判断分解是否为无损联接：