关系数据库_2.pptVIP

关系模式的分解算法 算法：（达到4NF无损连接分解算法） 给定关系模式RU , F ， ⒈令? = {RU , F} ⒉检查?中各关系模式是否属于4NF，若是，则 算法终止。 ⒊设? 中RiUi , Fi不属于4NF， 则存在非平凡多值依赖X??A，X不是Ri的码， 则XA是Ri的真子集，将Ri分解为?={S1，S1}， 其中US1 = XA， US2 = Ui ? {A} 以?代替Ri ，返回到⒉ 关系模式的分解算法 示例：U={A，B，C，D，E，G} F={A??BCG，B?AC，C?G} ⒈U1={A，E，D} U2={A，B，C，G} , F2={A??BCG，B?AC，C?G} ⒉U1={A，E，D} U2={C，G} , F2={C?G} U3={A，B，C}, F3={B?AC} 关系模式的分解算法 示例：U=(S#，P#，C#)， F={(S#，C#)?P#, P#?C#} 不属于BCNF，分解为 U1=(S#，P#)， U2=(P#，C#)，F2={P#?C#} 丢失了函数依赖(S#，C#)?P#，原来一个学生选修一门课程时，只能对应一个老师；在新的关系模式下现在一个学生选修一门课程时，可能会对应多个老师。 关系模式的分解算法 保持函数依赖的分解 定义 若F+ = ( ? Fi)+， 则称R U , F 的分解 ? = {R1U1 , F1 , … , RnUn , Fn}保持函数依赖。 如表（职工，级别，工资）的分解， 分解一：（职工，工资），（工资，级别） 丢失函数依赖，级别?工资 分解二：（职工，级别），（工资，级别） 保持函数依赖。 关系模式的分解算法 如何判断分解保持函数依赖？ 回忆： F+ = ( Fi)+ ? F ? ( Fi )+， Fi ? F+ 如对于{ABC，{A?B , B?C}}的分解{AB, {A?B}，AC, {A?C}} 思考：B?C?{A?B， A?C}+ ? 检验：C? ？ 关系模式的分解算法 结论：若要求分解保持函数依赖，那么分解后的模式总可以达到3NF，但不一定能达到BCNF。 算法：（达到3NF且保持函数依赖的分解） ⒈求F的正则覆盖FC 。 ⒉找出不在FC中出现的属性，将它们构成一个关 系模式，并从U中去掉它们(剩余属性仍记为U)。 ⒊若有X?A? FC ，且XA=U， 则={R}，算法终止。 关系模式的分解算法 ⒋对FC按具有相同左部的原则进行分组（设为k 组），每一组函数依赖所涉及的属性全体为Ui， 令Fi为FC在Ui上的投影，则? = {R1U1 , F1 , … , RkUk , Fk}是RU , F的一个保持函数依赖的 分解，并且每个RiUi , Fi ?3NF。 关系模式的分解算法 示例 U={S#，SD，MN，C#，G} F={S#?SD，S#?MN，SD?MN，(S#,C#)?G} ⒈FC={S#?SD，SD?MN ，(S#,C#)?G} ⒉分组 {(S#，SD)，S#?SD} {(SD，MN)，SD?MN} {(S#，C#，G)， (S#,C#)?G} A B C 1 1 1 2 1 1 2 2 1 A C 1 1 2 1 B C 1 1 2 1 A B C 1 1 1 1 2 1 2 1 1 2 2 1 关系模式的分解算法 示例：R（ABC；A?C，B?C） ⒈按保持无损连接分解 码为AB，分解为{AC；A?C}，{AB}。 丢失了函数依赖B?C。 ⒉按保持函数依赖分解 进行分组，{AC；A?C}，{BC；B?C}。 分解是有损的。 关系模式的分解算法 算法：（达到3NF且同时保持无损连接与函数依赖的分解） 设? = {R1U1 , F1 , … , RkUk , Fk}是RU , F的一个保持函数依赖的3NF分解。 设X为RU , F的码， 若有某个Ui，X ? Ui，则?即为所求， 否则令τ = ?∪{R? X，FX，τ即为所求。 关系模式的分解算法 示例： 求R（ABC；A?C，B?C）的保持无损连接和函数依赖的3NF分解。 ⒈按保持函数依赖分解 进行分组， ?={{AC；A?C}，{BC；B?C}}。 ⒉码为AB τ = ?∪{AB} 最后的分解为： {{AC；A?C}，{BC；B?C}，{AB}} * * 数据库模式的好坏和关系中各属性间的依赖关系有