数据库——模式分解.ppt

习题讲解,最小依赖集,1）考查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，不能去掉,1 2 3 4 5,求解关系模式的候选码,属性分类L类：只出现在函数依赖的左边的属性R类：只出现在函数依赖的右边的属性N类：在函数依赖的两边均未出现的属性LR类：出现在函数依赖的两边的属性,求解关系模式的候选码,对于给定的关系模式R及其函数依赖集F如果X是L或N类属性，则X必为R的任一候选码的成员如果X是R类属性，则X必不在任何候选码中如果X是L和N类组成的属性组，且X+包含了全部属性，则X是R的唯一候选码,前例,例：关系模式CTHRSG,若最小依赖集为F=C T,HR C,CS G,HS R,HT R,候选关键字为HS？解：L、N类属性为HS，LR属性为CTR HS+=HS RCTG，包含全部属性，所以为唯一候选码,函数依赖图FDG用有向图表示的函数依赖，如,L或N类属性有E和C,LR类属性ADB，令X=EC,(EC)+=U,EC为R的唯一候选码。,对左边为单属性的函数依赖集求所有候选码,(1)求F的最小依赖集F(2)作出函数依赖图FDG(3)从FDG图中找出无入边的属性集X(4)察看FDG图中有无回路，若无，则输出X并结 束,否则进行下一步(5)从各独立回路中各取一个结点的属性与X组成一个候选码，重复取得所有可能的组合，即R的全部候选码,算法：对左边为多属性的函数依赖集求所有候选码,(1)将R所有属性分为L,R,N,LR四类，并令X代表L,N两类，令Y代表LR类。(2)求X+，若X+包含R全部属性，则X即为R的唯一候选码，结束，否则转下一步。(3)在Y中取一属性A，求(XA)+,若它包含R的全部属性，则转下一步，否则换一个属性重试，直至试完所有Y中的属性。(4)若已找出所有候选码，则结束，否则在Y中依次取两个、三个、，求它们的属性闭包，直至其闭包包含R的全部属性。,属于N-P完全问题(一类直观上难解可又找不出方法来证明它们的确难解的计算问题)多属性下求解候选码的充分条件,第六章 关系数据理论,6.1 数据依赖6.2 规范化6.3 数据依赖的公理系统6.4 模式的分解,6.4 模式的分解,把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的。只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义。,关系模式分解的标准,三种模式分解的等价定义 分解具有无损连接性 分解要保持函数依赖 分解既要保持函数依赖，又要具有无损连接性,模式的分解（续）,定义6.16 关系模式R的一个分解：=R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，Fi 为 F在 Ui 上的投影。定义6.17 函数依赖集合XY|XY F+XY Ui 的一个覆盖 Fi 叫作 F 在属性 Ui 上的投影,模式的分解（续）,定义6.16 关系模式R的一个分解：=R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，Fi 为 F在 Ui 上的投影。定义6.17 函数依赖集合XY|XY F+XY Ui 的一个覆盖 Fi 叫作 F 在属性 Ui 上的投影,模式的分解（续）,例:SL（Sno，Sdept，Sloc）F=SnoSdept,SdeptSloc,SnoSloc SL2NF 存在插入异常、删除异常、冗余度大和修改复杂等问题分解方法可以有多种。,模式的分解（续）,SL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 IS B 95005 PH B,模式的分解（续）,1.SL分解为下面三个关系模式：SN(Sno)SD(Sdept)SO(Sloc),分解后的关系为：,SN SD SO Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 PH 95005,模式的分解（续）,分解后的数据库丢失了许多信息 例如无法查询95001学生所在系或所在宿舍。如果分解后的关系可以通过自然连接恢复为原来的关系，那么这种分解就没有丢失信息,模式的分解（续）,2.SL分解为下面二个关系模式：NL(Sno,Sloc)DL(Sdept,Sloc)分解后的关系为：NL DL Sno Sloc 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,模式的分解（续）,NLDL比原来的SL关系多了3个元组 无法知道95002、95004、95005 究竟是哪个系的学生元组增加了，信息丢失了,第三种分解方法,3.将SL分解为下面二个关系模式：ND(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关系一样，因此没有丢失信息。,具有无损连接性的模式分解,关系模式R的一个分解=R1，R2，Rn,若R与R1、R2、Rn自然连接的结果相等，则称关系,模式R的这个分解具有无损连接性（Lossless join）具有无损连接性的分解保证不丢失信息无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题,模式的分解（续）,第三种分解方法具有无损连接性 问题:这种分解方法没有保持原关系中的函数依赖 SL中的函数依赖SdeptSloc，没有投影到关系模式ND、NL上,保持函数依赖的模式分解,设关系模式R被分解为若干个关系模式 R1，R2，Rn（其中U=U1U2Un，且不存在Ui Uj，Fi为F在Ui上的投影），若F所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖Fi所逻辑蕴含，则称关系模式R的这个分解是保持函数依赖的（Preserve dependency）。,保持函数依赖的模式分解,例 子,R(A,B,C),F=AB,C B分解1=(A,B,AB),(A,C)分解2=(A,B,AB),(B,C,C B)计算分解1,2中3个模式的闭包FAB：A+=AB,B+=B,AB+=AB,则对AB的分解有函数依赖ABAC：A+=A,C+=C,AC+=AC,则对AC的分解没有函数依赖BC：B+=B,C+=CB,BC+=BC,则对BC的分解只有函数依赖CB分解1：只有AB，显然，分解1不具有依赖保持性分解2：保留了所有函数依赖，具有依赖保持性,分析两种分解的依赖保持性？,第四种分解方法,SL（Sno，Sdept，Sloc）F=SnoSdept,SdeptSloc,SnoSloc将SL分解为下面二个关系模式：ND(Sno,Sdept)DL(Sdept,Sloc)这种分解方法就保持了函数依赖。,模式的分解（续）,如果一个分解具有无损连接性，则它能够保证不丢失信息。如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况。分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖。同样，保持函数依赖的分解也不一定具有无损连接性。,模式的分解（续）,第一种分解方法既不具有无损连接性，也未保持函 数依赖，它不是原关系模式的一个等价分解 SN(Sno)，SD(Sdept)，SO(Sloc)第二种分解方法保持了函数依赖，但不具有无损连 接性。NL(Sno,Sloc)，DL(Sdept,Sloc),SL（Sno，Sdept，Sloc）F=SnoSdept,SdeptSloc,SnoSloc,模式的分解（续）,第三种分解方法具有无损连接性，但未持函数依赖 ND(Sno,Sdept)，NL(Sno,Sloc)第四种分解方法既具有无损连接性，又保持了函数依赖 ND(Sno,Sdept)，DL(Sdept,Sloc),SL（Sno，Sdept，Sloc）F=SnoSdept,SdeptSloc,SnoSloc,分解算法,算法6.2 判别一个分解的无损连接性算法6.3（合成法）转换为3NF的保持函数依赖的分解。算法6.4 转换为3NF既有无损连接性又保持函数依赖的分解算法6.5 转换为BCNF的无损连接分解（分解法）算法6.6 达到4NF的具有无损连接性的分解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)判断分解是否为无损联接：如果通过修改，发现表中有一行变a1,a2,an,则分解是无损联接的，否则分解不具有无损联接性。,初始表：,最后结果：,R1,R2,R3,R1,R2,R3,1,2,2,例子：判断无损连接性,初始表：,最后结果：,R1,R2,R3,R1,R2,R3,1,2,2,简易方法：只画关注数据,判别一个分解的无损连接性,已知关系模式R(ABCDE)及函数依赖集F=AC,BC,CD,DEC,CEA 验证分解=R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE)是否为无损联接。,通过修改发现表中第三行元素变为a1,a2,an,分解是无损联接。,判别一个分解的无损连接性,定理：如果R的分解为r=R1，R2，F为R所满足的函数依赖集合，分解r具有无损联接性的充要条件是：R1 R2（R1R2）F+或R1 R2（R2R1）F+,模式的分解（续）,定义6.16 关系模式R的一个分解：=R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，Fi 为 F在 Ui 上的投影。定义6.17 函数依赖集合XY|XY F+XY Ui 的一个覆盖 Fi 叫作 F 在属性 Ui 上的投影,判别一个分解的无损连接性,关系模式R(A,B,C,D)函数依赖集F=AB,CD,=R1(AB)，R2(CD)，求R1,R2,并检验分解的无损联接性和分解的函数依赖保持性。解：F1=R1(F)=AB,F2=R2(F)=CD，分解为 R1(AB,AB),R2(CD,CD)U1U2=ABCD=,U1-U2=AB,U2-U1=CD,AB F+,CD F+,所以不是无损分解。,判别一个分解的无损连接性,例：设R=ABC，F=AB，则1=R1(AB)，R2(AC)和 2=R1(AB)，R3(BC)是否具有无损联接性。,判别一个分解的无损连接性,例 将R=(ABCD,AB,BC,BD,CA)分解为关于U1=AB，U2=ACD两个关系，求R1、R2，并检验分解的无损联接性和分解的函数依赖保持性。解：F1=R1(F)=AB,BA,F2=R2(F)=AC,CA,AD R1=(AB,AB,BA)R2=(ACD,AC,CA,AD)U1U2=ABACD=A,U1-U2=AB-ACD=B,ABF+,所以是无损连接分解；,（F1UF2)+=AB,BA,AC,CA,AD+AB,BC,BD,CA+=F+,所以是函数依赖保持性。,练习：,已知关系模式R(CITY,ST,ZIP),F=(CITY,ST)ZIP,ZIPCITY，以及R上的一个分解=R1,R2,R1=ST,ZIP,R2=CITY,ZIP，求R1,R2,并检验分解的无损联接性和分解的函数依赖保持性。答案 R1=(ST,ZIP,)R2=(CITY,ZIP,ZIPCITY)，是无损分解,但不具有函数依赖保持性。,(1)极小化处理F(2)如果R中的某些属性在F的所有依赖的左边和右边都不出现，那么这些属性可以从R中分出去，单独构成一个关系模式。(3)如果F中有一个依赖XA有XA=R，则=R，转(4)(4)对于F中每一个XA，构成一个关系模式XA，如果F有有XA1，XA2.XAn,则可以用模式XA1A2.An代替n个模式XA1,XA2.XAn;(5)分解结束。,算法6.3分解成3NF模式集（合成法）保持函数依赖,一般情况下，只要用F中所有函数依赖左右两边的属性组成各个关系子模式，函数依赖中不涉及的属性组成一个关系。,具有依赖保持性的3NF分解例子,例1：SL(Sno,Sdept,Sloc)F=SnoSdept,SdeptSloc,SnoSlocF=SnoSdept,SdeptSloc，因为去掉SnoSloc，Sno+=Sno Sdept Sloc,包含Sloc,则可去掉具有依赖保持性的3NF分解为Sno，Sdept和Sdept，Sloc例2：关系模式CTHRSG,若最小依赖集为F=C T,HR C,CS G,HS R,HT R具有依赖保持性的3NF分解为CT,CHR,CSG,HSR,HTR,分解成3NF模式（保持函数依赖又无损连接）,使用合成法将RU,F分解为=设X是R的码，令=R*X,FX 如有某个Ui，使得：X Ui，则从中去掉R*X,FX 即所求,例 子,例：关系模式CTHRSG,若最小依赖集为F=C T,HR C,CS G,HS R,HT R,候选关键字为HS如前例，具有依赖保持性的3NF分解为CT,CHR,CSG,HSR,HTR则具有无损连接和依赖保持性的3NF分解为CT,CHR,CSG,HSR,HTR,HSHS和HSR重复，则为CT,CHR,CSG,HSR,HTR,1、设U=A，B，C，D，E，F F=ABCDE,DEABC,ABD,EC,DEF 求最小依赖集，并使用算法分解到3NF解：F=ABCD，ABCE，DEA，DEB，DEC，ABD，EC，DEF ABD，ABCD 去掉ABCD 又 EC，DEC 去掉DEC Fm=ABCE,ABD,EC,DEA,DEB,DEF 其码：ABC，ABE，DE 按算法1得到：=R1ABCE，ABCE，R2（ABD，ABD），R3，R4,例 题,例 题,其中，(1)R3的属性包含在R1关系的属性中，去掉R3 R2的属性包含在R4关系的属性中，去掉R2；=R1ABCE，ABCE，R2（ABD，ABD），R3，R4(2)由于R*ABC，FABC，R*DE，FDE，R*ABE，FABE皆是中的某个Ui的子集，因此全部去掉。最终的分解为：=R1故上面的分解既保持函数依赖又无损连接。,分解成BCNF模式集的算法,无损联接分解成BCNF模式集的算法：(1)置初值=R;(2)如果中所有关系模式都是BCNF，则转(4);(3)如果中有一个关系模式S不是BCNF，则S中必能找到一个函数依赖集XA有X不是S的键，且A不属于X，设S1=XA，S2=S-A，用分解S1,S2代替S，转(2)；(4)分解结束。输出。Notice:重点在于(3)步，判断哪个关系不是BCNF，并找到X和A。,分成BCNF,设关系模式R，R的函数依赖关系F=AD，ED，DB，BCD，DCA请将该关系分解到BCNF。解：找到候选键：ED ECDC.(1)DCA ECA.(2)DB DCBCB ECB.(3)由(1)(2)(3)得ECABD EC为键，这里关系键仅有一个(在右边有E和C未出现键中必包含EC为键)主属性EC,非主属性A,B,D。,分成BCNF（无损）,直接分解到BCNF AD，A BCE R1(AD)，R2(ABCE)在R2中 EB 分解：R21(EB)，R22(EAC)R分解为R1(AD)，R2(EB)，R3(EAC)分解不是唯一的。,分解算法,解P196 图5.11若要求分解具有无损连接性，那么模式分解一定能够达到4NF。若要求分解保持函数依赖，那么模式分解一定能够达到3NF，但不一定能够达到BCNF。若要求分解既具有无损连接性，又保持函数依赖，则模式分解一定能够达到3NF，但不一定能够达到BCNF。,泛关系假设,“假设已知一个模式S，它仅由单个关系模式组成，问题是要设计一个模式SD，它与S等价，但在某些方面更好一些”。从一个关系模式出发，而不是从一组关系模式出发实行分解。“等价”的定义也是一组关系模式与一个关系模式的“等价”。,小结(续),规范化理论为数据库设计提供了理论的指南和工具也仅仅是指南和工具并不是规范化程度越高，模式就越好必须结合应用环境和现实世界的具体情况合理地选择数据库模式,综合习题,下面给出一个数据集，判断它是否可直接作为关系数据库中的关系，若不行，则改造成为尽可能好的并能作为关系数据库中关系的形式，同时说明进行这种改造的理由。,解答,下面给出的关系R为第几范式？是否存在操作异常？若存在，则将其分解为高一级范式。分解完成的高级范式中是否可以避免分解前关系中存在的操作异常？,解答,答：它为1NF。因为该关系的候选关键字为（工程号，材料号），而非主属性（开工日期和完工日期）部分函数依赖于候选关键字的子集工程号，即：（工程号，材料号）p 开工日期（工程号，材料号）p 完工日期 所以它不是2NF。它存在操作异常。如果工程项目确定后，若暂时未用到材料，则该工程的数据因缺少关键字的一部分（材料号）而不能进入到数据库中，出现插入异常。若某工程下马，则删去该工程的操作也可能丢失材料方面的信息。将其中的部分函数依赖分解为一个独立的关系，则产生如下的两个2NF关系子模式：,分解后，新工程确定后，尽管还未用到材料，该工程数据可在关系R2中插入。删除某工程数据时，仅对关系R2操作，不会丢失材料方面的信息。,