,第六章 无环数据库模式,第六章 无环数据库模式,1,本章的主要内容：,数据库模式的超图表示,无,环数据库模式,无,环数据库模式,本章的主要内容：,例：,R=CSTPY (,课程，学号，教师，先修课，年份),F=CST,SPY,CP,数据库模式,R=CST,SPY,CP,r,(C S T P Y),C,1,S,1,t,1,p,1,y,1,C,1,S,1,t,1,P,2,y,2,C,2,S,1,t,2,P,3,y,3,r,1,(,C S T,)r,2,(,C P,)r,3,(,S P Y,),C,1,S,1,t,1,C,1,P,1,S,1,p,1,y,1,C,2,S,1,t,2,C,1,P,2,S,1,P,2,y,2,C,2,P,3,S,1,P,3,y,3,要求：,查询教师,t,1,所授课程的先修课。,T,P,(,Tt1,(r,1,)r,2,);t,1,p,1,;t,1,p,2,T,P,(,Tt1,(r,1,)r,3,)t,1,p,1,;t,1,p,2,;t,1,p,3,6.1 数据库模式的超图表示,例：R=CSTPY (课程，学号，教师，先,6.1 数据库模式的超图表示,A B C,D G,F,E,数据库模式：,ABC、CDE、AEF、ACE、DG,6.1 数据库模式的超图表示 A,6.1 数据库模式的超图表示,定义1 一个超图,H,是一个二元组(,N,E)，,其中,N,是图中结点的集合，,E,是超边的集合，,E,中的每条超边都是,E,的非空子集。如果,H,中不存在任一超边完全包含在另一超边中，称,H,为,化简超图,，记为,RED(H)。,定义2 若把数据库模式,R,中的属性作为超图,H,R,中的结点，,R,中同一关系模式中的属性用一条超边表示，则称,H,R,为,数据库模式,R,的超图,。,6.1 数据库模式的超图表示定义1 一个超图H,6.1 数据库模式的超图表示,定义3 设超图,H=(N,E)，,其中,A,和,B,是,N,中的结点，,H,中从,A,到,B,的一条通路是一个边的序列,E,1,E,2,E,K,K,1,使得,A,E,1,，B,E,K,，,且,E,i,E,i+1,1 i K,则称边序列,E,1,E,2,E,K,为从,E,1,到,E,K,的,通路,。如果二个顶点或二条边之间有一条通路，则称他们是连通的。,若一个边集中的任一对边都是连通的，则称这些边集是连通的。,6.1 数据库模式的超图表示 定义3,6.1 数据库模式的超图表示,定义4 设超图,H=(N,E)、H,=(N,E,),是超图,若结点,N,N，,边集,E,E，,称,H,是,H,的,子图,。,若对任意边,e,E，eN,E,，,则称,H,是,H,的,封闭子图,。,若,N,N，E,=eN,|e,E，,则称,H,是,H,的,导出图,。,6.1 数据库模式的超图表示定义4 设超图H=,H,1,=,(,ABCDEIJK,ABC,BD,CDE,DEI,CIK,IJK,),H,1,A,E,C,J,B D I K,连通：,ABC,BD,CDE,不连通：,ABC,IJK,A C E,B D,A C,B D,C E J,D I K,H,1,是子图,封闭子图,导出图，,H,1,是导出图(,CD,不是,e,的边),H,1,子图,不是封闭子图和导出图(,CIK,),H1=(ABCDEIJK,连通：ABC,B,定义7,设,F=(N,E,),是,H=(N,E),的导出图,，,E,1,、,E,2,E,且,f=E,1,E,2,。,若,N,f,后的图比,F,具有更多的连通支数，称结点集,f,为,F,的,关节集,。,若导出图,H,中不含关节集，称,H,是,H,的一个,块,。仅含一条边的块称是,平凡,的，否则是,非平凡,的。,定义8,在超图,H,中若不存在非平凡的块，称,H,是无,环超图，否则为有,环超图。对应超图是无,环的数据库模式称为无,环数据库模式。,定义7 设F=(N,E,H,1,中有一个,环：,ABC,C,CED,E,AEF,A,ABC,H,3,是一个无,环超图，,也是一个无,环超图。,E,A,B,C,F,D,H,1,A,C,E,B,D,F,H,3,E,A,B,C,F,D,H,2,H,1,是无,环超图,ABC,CED,ACE,AEF，,H,2,是有,环超图,ABC,CED,AEF，,一个无,环超图其子图可以有,环，,一个无,环超图其子图不能有,环。,H1中有一个环：EABCFDH1 ACEBDFH3 E,定义9,超图,H,中若存在一个边和点的序列,S,1,v,1,S,2,v,2,S,m,v,m,S,m+1,且满足：,(1).,v,1,v,2,v,m,是,H,中的不同结点；,(2).,S,1,S,2,S,m,是,H,中的不同边且,S,m+1,=S,1,;,(3).m,3，,即序列中至少有三条不同的边；,(4).,v,i,S,i,S,i+1,，1,i,m；,(5).,对所有1,i,j,m，j,i,j,i+1，v,i,S,j,，,则称这样的序列为一个,环。,定义10,一个超图中若不存在任何,环，则称该超图为无,环超图，否则称为有,环超图。如果一个数据库模式,R,对应的超图是一个无,环超图，则称该数据库模式,R,为无,环数据库模式。,定义9 超图H中若存在一个边和点的序列 S1,6.2.1 无,环数据库模式的特性:,1.连接依赖与一组多值依赖等价。,6.2 无,环数据库模式,定义11 设数据库模式,R=R,1,R,2,R,k,，R,的连接树满足：,(1),R,中的每个,R,i,(1,i,k),对应树的一个结点，结点用,R,i,的属性集表示；,(2),R,中的二个关系模式,R,i,和,R,j,(i,j),若有公共属性则其对应结点间有一条边相连，并用该公共属性标识；,(3)对于每一对关系模式,R,i,和,R,j,对应的结点间存在唯一的一条通路，若属性,A,R,i,R,j,则该条通路的每条边的标识中都含有,A。,6.2.1 无环数据库模式的特性:6.2 无环数,ABC,ACE,AEF,CDE,DG,AC,AE,CE,D,*,R,对应的一组多值依赖:,ACB，CED，,AEF，DG,例:设无,环数据库模式,R,=ABC,CDE,ACE,AEF,DG,求：,R,的一棵连接树。,ABCACEAEFCDEDGACAECED *R 对,例:数据库模式,S,=ABC,BCD,CE,DE,求：,R,的一课连接树。,A C E,B D,ABC,BCD,CE,DE,BC,C,D,例:数据库模式 S=ABC,BCD,CE,DE,2.唯一4,NF,分解,定义12 设属性集,U,和,MVD,集,M，XY,M，W,U。,若,A、B,W,而使得,A,Y，B,U,XY，,则称,X,Y,分裂,W,。,若多值依赖集,M,满足：,(1).,M,中每个,MVD,都不分裂其他,MVD,的左部;,(2).,M,中任意二个,MVD,的左部属性集,X,和,Y，,DEP(X)DEP(Y),DEP(XY)。,则称,MVD,S,集,M,是,无冲突,的。,2.唯一4NF分解,例1：,R=ABCDEFG,M=ACB,CED,AEF，DG,分解结果：,ABC，CED，AEC，AEF，DG,结果唯一。,例2：,R=ABCDE M=ABC,CEB,分解结果：,R1=ABC，ABDE,R2=BCE，ACDE,结果不唯一。,例1：R=ABCDEFG 例2：R=A,3.两两一致性蕴涵全体一致性,定义13 设,R=R,1,R,2,R,k,，,对应,d=r,1,r,2,r,k,。,对,d,中的任一对关系,r,i,和,r,j,若,r,i,(R,i,R,j,)=r,j,(R,i,R,j,)，,称数据库,d,是,两两一致,的。,若,U=R,1,R,2,R,n,上存在泛关系,r,使得任意关系,r,i,d,有,r,i,=r R,i,称,d,是,全体一致,的。,r,1,(,A B,)r,2,(,B C D,)r,3,(,C D A,),1 2 2 4 5 4 5 2,2 3 3 4 6 4 6 1,2 5,5 8 6,8 6 2,3.两两一致性蕴涵全体一致性 r1(,r,1,(,A B C,)r,2,(,A D,)r,3,(,B D E,),2 3 6 2 7 3 7 2,2 5 8,2 9,5 9 1,(r,1,r,3,),r,2,或,r,1,(r,2,r,3,),为单调连接。,而(,r,1,r,2,),r,3,为非单调的,4.单调顺序连接表达式,单调连接:,连接过程中没有中间结果元组被丢失。,单调连接表达式:,每个子表达式都是一致的。,(,r,1,r,2,),(,r,3,r,4,),4.单调顺序连接表达式 单调连接:,单调顺序连接表达式：,(,r,1,r,2,)r,3,),r,k,),连接结果随着连接顺序执行呈单调增长趋势。,无,环数据库模式,有一个单调顺序连接表达式,单调顺序连接表达式：无环数据库模式有一个单调顺序连接表达式,定理1 数据库模式,R,的下列条件是等价的。,(1),R,是一个无环超图。,(2),R,是一个封闭无环的超图。,(3)连接依赖,*,R,与一个无冲突的,MVD,S,集等价。,(4),R,上的每个两两一致的数据库也是全体一致的。,(5),R,上的每个数据库都有一个完全归约。,(6),R,有一个连接树。,(7),R,有运行相交特性。,(8),R,有一个单调连接表达式。,(9),R,有一个顺序的单调连接表达式。,(10),R,有唯一的4,NF,分解。,R,的每个封闭子超图都是无环的。,归约后的结果关系是全体一致的,在序列,R,1,R,2,R,K,中,R,i,与前面模式集并的交集包含在前面某个模式中,定理1 数据库模式R的下列条件是等价的。R的每个封,6.2.2,Graham,算法,算法6.2.1 判定一个数据库模式是否是无,环的,输入：数据库模式,R=R,1,R,2,R,k,输出：若,R,是无,环模式输出为,true,否则为,false,Graham(R),(1).,构造数据库模式,R,的对应超图,H=(N，E)。,(2).,对,H,反复施加以下规则直到不能施加为止：,rN,规则,：,将仅出现在一条边中的结点从,N,中删除；,rE,规则：将包含在某条边中的边,e,从,E,中删除。,(3).若,H,为空则输出,true，,否则输出,false。,6.2.2 Graham算法,例:设数据库模式,R,1,=ABC,CDE,ACE,AEF，,R,2,=CST,SPY,CP,判定：,R,1,和,R,2,是否是无,环数据库模式。,E,A,B,C,F,D,T,S,Y,C,P,R,1,R,2,例:设数据库模式R1=ABC,CDE,ACE,引理1,Graham,算法不会破坏超图中原有的块。,引理2,Graham,算法不会生成新的块。,引理3 任一化简的具有二条或二条以上边的无,环超图至少含有二个节。,节：,含有孤立结点（结点仅在一条边中出现）的边。,定理2 若,R,为无,环数据库模,式，,当且仅,当,Graham,算法在,R,上,是成功的。,引理1 Graham算法不会破坏超图中原有的块。定理2,6.2.3 无,环数据库模式的设计,定理3 设,M,是一组多值依赖集，在,M,下生成的4,NF,数据库模式是无,环的当且仅当,M,有一个无冲突的覆盖。,例：,U=ABCDEF,M=AC,B,CE D,AE F,M,是无冲突的，4,NF,的数据库模式为：,ABC,CDE,ACE,AEF,以上模式是无,环的。,定理4 设函数依赖和多值依赖集,D，,在,D,下生成的4,NF,数据库模式是无,环的当且仅当,D,有一个广义无冲突的覆盖。,6.2.3 无环数据库模式的设计,无,环数据库模式,R,的设计:,无,环数据库模式,R,的设计是一个对应超图的设计序列：,H,1,H,2,H,n,，H,1,=(N,1,E,1,)，E,1,仅有一个超边，,R=H,n,。,对,1,i n,，H,i,=(N,i,E,i,)，H,i+1,=(N,i+1,E,i+1,)，(H,i,H,i+1,),称为一个设