华中科技大学数据库课件第06章-关系数据理论-3

©2011by1AnIntroductiontoDatabaseSystem6.1问题的提出6.2函数依赖6.3函数依赖的公理系统6.4关系模式的规范化6.5关系模式的分解6.6小结第6章关系数据理论©2011by2AnIntroductiontoDatabaseSystem6.5.1模式分解的定义6.5.2模式分解中的问题6.5.3无损连接分解6.5.4保持函数依赖的分解6.5.5关系模式的分解算法6.5关系模式的分解©2011by3AnIntroductiontoDatabaseSystem定义6.17设有关系模式RU,F,称用ρ={R1U1,F1，R2U2,F2，…，RnUn,Fn}代替R的过程为R模式的分解，ρ称为R的一个分解，这里Ui和Fi必须同时满足：U=U1∪U2∪…∪UnUi与Uj可以相交,但不允许UiUj或UjUi,i≠j,i,j=1,2,…nFi是F在Ui上的投影(也可记作∏Ri(F))6.5关系模式的分解©2011by4AnIntroductiontoDatabaseSystem定义6.18函数依赖集合{X→Y|X→YF+∧XYUi}的一个覆盖Fi叫作F在属性Ui上的投影设有RU,F,U={A,B,C,D},F={A→B,C→D}(R最高为几范式?)ρ1:R1(A,B,C),R2(C,D),F在R1,R2上的投影是什么?F1={A→B},F2={C→D}(R1最高为几范式?R2呢?)6.5关系模式的分解©2011by5AnIntroductiontoDatabaseSystem设有RU,F,U={A,B,C},F={A→B,B→C}(R最高为几范式?)ρ1:R1(A,B),R2(A,C),F在R1,R2上的投影是什么?F1={A→B},F2={A→C}(R1最高为几范式?R2呢?)6.5关系模式的分解©2011by6AnIntroductiontoDatabaseSystemSCD(Sno,Sname,Age,Dept,Mn,Cno,Score)F={sno→*,Dept→Mn,(sno,cno)→score}分解ρ1={SD,SC}:SD(Sno,Sname,Age,Dept,Mn),F1={sno→*,dept→Mn}SC(Sno,Cno,Score),F2={(sno,cno)→score}分解ρ2={S,D,SC}:S(Sno,Sname,Age,Dept),F1={sno→(sname,age,dept)}D(Dept,Mn),F2={dept→Mn}SC(Sno,Cno,Score),F3={(sno,cno)→score}6.5关系模式的分解©2011by7AnIntroductiontoDatabaseSystem6.5.1模式分解的定义6.5.2模式分解中的问题6.5.3无损连接分解6.5.4保持函数依赖的分解6.5.5关系模式的分解算法6.5关系模式的分解©2011by8AnIntroductiontoDatabaseSystem把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义无损连接性保持函数依赖既保持函数依赖，又无损连接6.5关系模式的分解©2011by9AnIntroductiontoDatabaseSystem6.5关系模式的分解A学生B学院C院长赵计算机王钱计算机王孙机械张李软件王{AB,BC}(A,B):(学生,学院)(A,C):(学生,院长)(A,C):(学生,院长)(B,C):(学院,院长)(A,B):(学生,学院)(B,C):(学院,院长)©2011by10AnIntroductiontoDatabaseSystem6.5关系模式的分解AC院长赵王钱王孙张李王{AC}B学院C院长计算机王机械张软件王{BC}=ABC赵计算机王赵软件王钱计算机王钱软件王孙机械张李计算机王李软件王多出违背事实的元组有损连接的分解{AB,BC}©2011by11AnIntroductiontoDatabaseSystem6.5关系模式的分解AB学院赵计算机钱计算机孙机械李软件周计算机{AB}AC院长赵王钱王孙张李王周江{AC}=A学生B学院C院长赵计算机王钱计算机王孙机械张李软件王周计算机江插入违反BC:不保持FD的分解{AB,BC}©2011by12AnIntroductiontoDatabaseSystem6.5关系模式的分解AB学院赵计算机钱计算机孙机械李软件{AB}B学院C院长赵王钱王孙张李王{BC}=A学生B学院C院长赵计算机王钱计算机王孙机械张李软件王无损连接，且保持FD{AB,BC}©2011by13AnIntroductiontoDatabaseSystem6.5.1模式分解的定义6.5.2模式分解中的问题6.5.3无损连接分解6.5.4保持函数依赖的分解6.5.5关系模式的分解算法6.5关系模式的分解©2011by14AnIntroductiontoDatabaseSystem定义6.19关系模式RU,F的一个分解ρ={R1U1,F1，R2U2,F2，…，RnUn,Fn}若R与R1、R2、…、Rn自然连接的结果相等，则称关系模式R的这个分解ρ具有无损连接性（Losslessjoin）。具有无损连接性的分解保证不丢失信息无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题6.5关系模式的分解©2011by15AnIntroductiontoDatabaseSystem算法6.2判别一个分解是否具有无损连接性U={A1,A2,…,An}={R1U1,F1,R2U2,F2,…,RkUk,Fk}1.建立一个n列k行的矩阵TB={Cij|若AjUi,Cij=aj,否则Cij=bij}6.5关系模式的分解A1A2…AnU1…CijUk©2011by16AnIntroductiontoDatabaseSystem算法6.2(续)2.对F中每一个函数依赖XY，若TB中存在元组t1，t2，使得t1[X]=t2[X]，t1[Y]≠t2[Y]，则对每一个AiY：①若t1[Ai],t2[Ai]中有一个等于aj,则另一个也改为aj；②若①不成立,则取t1[Ai]=t2[Ai](t2的行号小于t1)。(即Ai列上，只要其中有一个aj则全改为aj,否则全改为行号最小的即一列的值)6.5关系模式的分解©2011by17AnIntroductiontoDatabaseSystem算法6.2(续)3.反复执行2,直至：①TB中出现一行为a1,a2,…,an的一行。②TB不再发生变化,且没有一行为a1,…,an。在①情况下，为无损分解，否则为有损分解。定理6.4为无损连接的分解当且仅当是算法5.2终止时,表中有一行为a1,…,an。6.5关系模式的分解©2011by18AnIntroductiontoDatabaseSystem【例6.17】U={A,B,C,D,E},F={ABC,CD,DE},={(A,B,C),(C,D),(D,E)}，判断分解是否具有无损连接性。6.5关系模式的分解ABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5ABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5ABCABCDEABCa1a2a3a4b15CDb21b22a3a4b25DEb31b32b33a4a5CDABCDEABCa1a2a3a4a5CDb21b22a3a4a5DEb31b32b33a4a5DE©2011by19AnIntroductiontoDatabaseSystem【别解】U={A,B,C,D,E},F={ABC,CD,DE},={(A,B,C),(C,D),(D,E)}，判断分解是否具有无损连接性。6.5关系模式的分解ABCDEABCa1a2a3CDa3a4DEa4a5ABCDEABCa1a2a3CDa3a4DEa4a5ABCABCDEABCa1a2a3a4CDa3a4DEa4a5CDABCDEABCa1a2a3a4a5CDa3a4a5DEa4a5DE©2011by20AnIntroductiontoDatabaseSystem【例6.18】U={A,B,C,D,E},F={AC,BC,CD,DEC,CEA},={AD,AB,BE,CDE,AE},判断分解是否无损连接。6.5关系模式的分解ABCDEADa1a4ABa1a2BEa2a5CDEa3a4a5AEa1a5ACBCCDDECCEAb13b13a1a1a3a4a4a4b13b13a3无损连接©2011by21AnIntroductiontoDatabaseSystem定理6.5RU,F的一个分解无损连接={R1U1,F1,R2U2,F2}具有无损连接性的充要条件是：U1∩U2→U1-U2∈F+或U1∩U2→U2-U1∈F+6.5关系模式的分解©2011by22AnIntroductiontoDatabaseSystem证明借助算法6.2,将R的属性分成三部分,…6.5关系模式的分解U1∩U2U1-U2U2-U1U1aa…aaa…abb…bU2aa…abb…baa…a(1)充分性如有U1∩U2→U1-U2,则U2行(U1-U2)列全改为a,于是U2行全为a.分解具有无损连接性;同理,…(2)必要性如是无损连接，则必有一行全a，…©2011by23AnIntroductiontoDatabaseSystem【例6.19】RU,F,U={A,B,C},F={A→B}的两个分解：(1)1={R1(A,B),R2(A,C)}(2)2={R1(A,B),R2(B,C)}问两分解具有无损连接性吗?解:(1)AB∩AC=A,AB-AC=B,A→B∈F+,故分解1具有无损连接性。(2)AB∩BC=B,AB-BC=A,BC-AB=C.无论B→A，还是B→C都不在F+中，所以分解2不具有无损连接性。6.5关系模式的分解©2011by24AnIntroductiontoDatabaseSystem【例6.20】RU,F,U={A,B,C},F={A→B,C→B}的分解：(1)1={AC,BC}(2)2={AB,BC}问两分解具有无损连接性吗?解:(1)AC∩BC=C,AC-BC=A,BC-AC=B,C→B∈F+,故分解1具有无损连接性。(2)AB∩BC=B,AB-BC=A,BC-AB=C.无论B→A，还是B→C都不在F+中，所以分解2不具有无损连接性。6.5关系模式的分解©2011by25AnIntroductiontoDatabaseSystem【例6.21】RU,F,U={A,B,C,D,E,F},F={A→B,C→F,E→A,CE→D}的分解：={ABE,CDEF}问分解具有无损连接性吗?解:ABE∩CDEF=E,ABE-CDEF=AB,E→AB∈F+(为什么?).故分解具有无损连接性。思考：R的候选码是什么？它最高是几范式？分解后的两个关系模式又是几范式?6.5关系模式的分解©2011by26AnIntroductiontoDatabaseSystem6.5.1模式分解的定义6.5.2模式分解中的问题6.5.3无损连接分解6.5.4保持函数依赖的分解6.5.5关系模式的分解算法6.5关系模式的分解©2011by27AnIntroductiontoDatabaseSystem定义6.20关系模式RU,F的一个ρ={R1U1,F1，R2U2,F2，…，RnUn,Fn}若F与F1∪F2∪…∪Fn等价则称分解ρ保持函数依赖。(Fi是F在Ui上的投影)引理6.4F+=G+FG+，