1、第六章第六章 无环数据库模式无环数据库模式本章的主要内容：本章的主要内容：u 数据库模式的超图表示数据库模式的超图表示u 无无 环数据库模式环数据库模式u 无无 环数据库模式环数据库模式例：例：R=CSTPY (课程，学号，教师，先修课，年份课程，学号，教师，先修课，年份)F=CST,SPY,CP 数据库模式数据库模式R=CST,SPY,CP r(C S T P Y)C1 S1 t1 p1 y1 C1 S1 t1 P2 y2 C2 S1 t2 P3 y3 r1(C S T)r2(C P)r3(S P Y)C1 S1 t1 C1 P1 S1 p1 y1 C2 S1 t2 C1 P2 S1 P2
2、y2 C2 P3 S1 P3 y3要求：要求：查询教师查询教师t1所授课程的先修课。所授课程的先修课。T,P(Tt1(r1)r2);t1,p1;t1,p2 T,P(Tt1(r1)r3)t1,p1;t1,p2;t1,p36.1 6.1 数据库模式的超图表示数据库模式的超图表示6.1 6.1 数据库模式的超图表示数据库模式的超图表示 A B C D GFE数据库模式：数据库模式：ABCABC、CDECDE、AEFAEF、ACEACE、DG DG 6.1 6.1 数据库模式的超图表示数据库模式的超图表示定义定义1 一个超图一个超图H是一个二元组是一个二元组(N,E)，其中其中N是是图中结点的集合，图
3、中结点的集合，E是超边的集合，是超边的集合，E中的每条超边中的每条超边都是都是E的非空子集。如果的非空子集。如果H中不存在任一超边完全包中不存在任一超边完全包含在另一超边中，称含在另一超边中，称H为为化简超图化简超图，记为，记为RED(H)。定义定义2 若把数据库模式若把数据库模式R中的属性作为超图中的属性作为超图HR中的中的结点，结点，R中同一关系模式中的属性用一条超边表示，中同一关系模式中的属性用一条超边表示，则称则称HR为为数据库模式数据库模式R的超图的超图。6.1 6.1 数据库模式的超图表示数据库模式的超图表示 定义定义3 设超图设超图H=(N,E)，其中其中A和和B是是N中的结点，
4、中的结点，H中从中从A到到B的一条通路是一个边的序列的一条通路是一个边的序列E1,E2,EK,K 1,使得使得A E1，B EK，且且Ei Ei+1,1 i K,则称边序列则称边序列E1,E2,EK为从为从E1 到到EK的的通路通路。如果二个顶点或二条边之间。如果二个顶点或二条边之间有一条通路，则称他们是连通的。有一条通路，则称他们是连通的。若一个边集中的任一对若一个边集中的任一对边都是连通的，则称这些边集是连通的。边都是连通的，则称这些边集是连通的。6.1 6.1 数据库模式的超图表示数据库模式的超图表示定义定义4 设超图设超图H=(N,E)、H=(N,E)是超图是超图,若结点若结点NN，边
5、集边集E E，称称H 是是H的的子图子图。若对任意边若对任意边e E，eNE，则称则称H 是是H的的封闭子图封闭子图。若若NN，E=eN|e E，则称则称H 是是H的的导出图导出图。H1=(ABCDEIJK,ABC,BD,CDE,DEI,CIK,IJK)H1 A E C J B D I K 连通：ABC,BD,CDE 不连通：ABC,IJK A C EA C EB DB DA CA CB DB DC E JC E JD I KD I KH1是子图,封闭子图,导出图，H1是导出图(CD不是e的边)H1子图,不是封闭子图和导出图(CIK)定义定义7 设设F=(N,E)是是H=(N,E)的导出图的导
6、出图，E1、E2 E 且且f=E1E2。若若 N f 后的图比后的图比F具有更具有更多的连通支数，称结点集多的连通支数，称结点集f 为为F的的关节集关节集。若导出图若导出图H 中不含关节集，称中不含关节集，称H 是是H的一个的一个块块。仅含一条边的块称是仅含一条边的块称是平凡平凡的，否则是的，否则是 非平凡非平凡的。的。定义定义8 在超图在超图H中若不存在非平凡的块，称中若不存在非平凡的块，称H是无是无 环超图，环超图，否则为有否则为有 环超图。环超图。对应超图对应超图是无是无 环的数据库模式称为无环的数据库模式称为无 环数据库模式。环数据库模式。H1中有一个中有一个 环：环：ABC,C,CE
7、D,E,AEF,A,ABC H3是一个无是一个无 环超图，环超图，也是一个无也是一个无 环超图。环超图。EABCFDH1 ACEBDFH3 E ABCFDH2H1是无环超图ABC,CED,ACE,AEF，H2是有环超图ABC,CED,AEF，一个无一个无 环超图其子图可以有环超图其子图可以有 环，环，一个无一个无 环超图其子图不能有环超图其子图不能有 环。环。定义定义9 超图超图H中若存在一个边和点的序列中若存在一个边和点的序列 S1,v1,S2,v2,Sm,vm,Sm+1,且满足：且满足：(1).v1,v2,vm是是H中的不同结点；中的不同结点；(2).S1,S2,Sm 是是H中的不同边且中
8、的不同边且Sm+1=S1;(3).m 3，即序列中至少有三条不同的边；即序列中至少有三条不同的边；(4).vi Si Si+1，1 i m；(5).对所有对所有1 i,j m，j i,j i+1，vi Sj，则称这样的则称这样的序列为一个序列为一个 环。环。定义定义10 一个超图中若不存在任何一个超图中若不存在任何 环，则称该超图为无环，则称该超图为无 环超图，否则称为有环超图，否则称为有 环超图。如果一个数据库模式环超图。如果一个数据库模式R对应对应的超图是一个无的超图是一个无 环超图，则称该数据库模式环超图，则称该数据库模式R为无为无 环数据环数据库模式。库模式。6.2.1 无无 环数据库
9、模式的特性环数据库模式的特性:1.连接依赖与一组多值依赖等价。连接依赖与一组多值依赖等价。6.2 无无 环数据库模式环数据库模式定义11 设数据库模式R=R1,R2,Rk，R的连接树满足：(1)R中的每个Ri(1 i k)对应树的一个结点，结点用Ri的属性集表示；(2)R中的二个关系模式Ri和Rj(i j)若有公共属性则其对应结点间有一条边相连，并用该公共属性标识；(3)对于每一对关系模式Ri和Rj 对应的结点间存在唯一的一条通路，若属性A RiRj,则该条通路的每条边的标识中都含有A。ABCACEAEFCDEDGACAECED *R 对应的一组多值依赖对应的一组多值依赖:ACB，CED，AE
10、F，DG 例:设无环数据库模式 R=ABC,CDE,ACE,AEF,DG 求：R的一棵连接树。例例:数据库模式数据库模式 S=ABC,BCD,CE,DE 求：求：R的一课连接树。的一课连接树。A C E B DABCBCDCEDEBCCD 2.唯一唯一4NF分解分解定义定义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，D
11、EP(X)DEP(Y)DEP(XY)。则称则称MVDS集集M是是无冲突无冲突的。的。例例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 结果不唯一。结果不唯一。3.两两一致性蕴涵全体一致性两两一致性蕴涵全体一致性定义定义13 设设R=R1,R2,Rk，对应对应d=r1,r2,rk。对对 d 中的任一对关系中的任一对关系 ri 和和 rj 若若 ri(RiRj)=rj(RiRj)，称数据库称数据库d
12、是是两两一致两两一致的。的。若若U=R1R2Rn上存在泛关系上存在泛关系 r 使得任意关系使得任意关系ri d有有ri=r Ri,称称d是是全体一致全体一致的。的。r r1 1(A B A B)r)r2 2(B C D B C D)r)r3 3(C D A C D A)1 2 2 4 5 4 5 2 1 2 2 4 5 4 5 2 2 3 3 4 6 4 6 1 2 3 3 4 6 4 6 1 2 5 2 5 5 8 6 5 8 6 8 6 2 8 6 2 r1(A B C)r2(A D)r3(B D E)2 3 6 2 7 3 7 2 2 5 8 2 9 5 9 1(r1 r3)r 2 或或
13、r1 (r2 r 3)为单调连接。为单调连接。而而(r1 r2)r 3为非单调的为非单调的 4.单调顺序连接表达式单调顺序连接表达式 单调连接单调连接:连接过程中没有中间结果元组被丢失。连接过程中没有中间结果元组被丢失。单调连接表达式单调连接表达式:每个子表达式都是一致的。每个子表达式都是一致的。(r1 r2)(r3 r4)单调顺序连接表达式：单调顺序连接表达式：(r1 r2)r 3)r k )连接结果随着连接顺序执行呈单调增长趋势。连接结果随着连接顺序执行呈单调增长趋势。无无 环数据库模式环数据库模式有一个单调顺序连接表达式有一个单调顺序连接表达式定理定理1 数据库模式数据库模式R的下列条件
14、是等价的。的下列条件是等价的。(1)R是一个无是一个无 环超图。环超图。(2)R是一个封闭无环的超图。是一个封闭无环的超图。(3)连接依赖连接依赖*R与一个无冲突的与一个无冲突的MVDS集等价。集等价。(4)R上的每个两两一致的数据库也是全体一致的。上的每个两两一致的数据库也是全体一致的。(5)R上的每个数据库都有一个完全归约。上的每个数据库都有一个完全归约。(6)R有一个连接树。有一个连接树。(7)R有运行相交特性。有运行相交特性。(8)R有一个单调连接表达式。有一个单调连接表达式。(9)R有一个顺序的单调连接表达式。有一个顺序的单调连接表达式。(10)R有唯一的有唯一的4NF分解。分解。R
15、的每个封闭子超的每个封闭子超图都是无图都是无 环的。环的。归约后的结果关系归约后的结果关系是全体一致的是全体一致的在序列在序列R1,R2,RK中中,Ri与前面模式集并的交集包与前面模式集并的交集包含在前面某个模式中含在前面某个模式中6.2.2 Graham算法算法算法算法6.2.1 判定一个数据库模式是否是无判定一个数据库模式是否是无 环的环的输入：数据库模式输入：数据库模式R=R1,R2,Rk 输出：若输出：若R是无是无 环模式输出为环模式输出为true否则为否则为falseGraham(R)(1).构造数据库模式构造数据库模式R的对应超图的对应超图H=(N，E)。(2).对对H反复施加以下
16、规则直到不能施加为止：反复施加以下规则直到不能施加为止：rN规则规则：将仅出现在一条边中的结点从将仅出现在一条边中的结点从N中删除；中删除；rE规则：将包含在某条边中的边规则：将包含在某条边中的边e从从E中删除。中删除。(3).若若H为空则输出为空则输出true，否则输出否则输出false。例例:设数据库模式设数据库模式R1=ABC,CDE,ACE,AEF，R2=CST,SPY,CP判定：判定：R1和和R2是否是无是否是无 环数据库模式。环数据库模式。E ABCFDTSYCP R1 R2 引理引理1 Graham算法不会破坏超图中原有的块。算法不会破坏超图中原有的块。引理引理2 Graham算
17、法不会生成新的块。算法不会生成新的块。引理引理3 任一化简的具有二条或二条以上边的无任一化简的具有二条或二条以上边的无 环超图至环超图至少含有二个节。少含有二个节。节：节：含有孤立结点（结点仅在一条边中出现）的边。含有孤立结点（结点仅在一条边中出现）的边。定理定理2 若若R为无为无 环数据库模环数据库模式，式，当且仅当且仅当当Graham算法在算法在R上上是成功的。是成功的。6.2.3 无无 环数据库模式的设计环数据库模式的设计定理定理3 设设M是一组多值依赖集，在是一组多值依赖集，在M下生成的下生成的4NF数据库数据库模式是无模式是无 环的当且仅当环的当且仅当M有一个无冲突的覆盖。有一个无冲
18、突的覆盖。例：例：U=ABCDEF,M=AC B,CE D,AE F M是无冲突的，是无冲突的，4NF的数据库模式为：的数据库模式为：ABC,CDE,ACE,AEF 以上模式是无以上模式是无 环的。环的。定理定理4 设函数依赖和多值依赖集设函数依赖和多值依赖集D，在在D下生成的下生成的4NF数数据库模式是无据库模式是无 环的当且仅当环的当且仅当D有一个广义无冲突的覆盖。有一个广义无冲突的覆盖。无无 环数据库模式环数据库模式R的设计的设计:无无 环数据库模式环数据库模式R的设计是一个对应超图的设计序列：的设计是一个对应超图的设计序列：H1,H2,Hn，H1=(N1,E1)，E1仅有一个超边，仅有
19、一个超边，R=Hn。对对1 i n，Hi=(Ni,Ei)，Hi+1=(Ni+1,Ei+1)，(Hi,Hi+1)称为一称为一个设计步，超边个设计步，超边eEi，Ni+1=Nie,Ei+1=Eie，e Ni称为称为连接结点集。连接结点集。若每个设计步满足规则：对若每个设计步满足规则：对Hi=(Ni,Ei)和和Hi+1=(Nie，Eie)，若有若有e Ei使得使得e Ni e，则生成的数据库模式是无则生成的数据库模式是无 环的。环的。例例1：R=ABC，CDE，AEF，ACE，其生成序列：其生成序列：H1=ACE,ACE，H2=ABCE,ACE,ABC，H3=ABCDE,ACE,ABC，CDE，R=H4=ABCDEF,ACE,ABC，CDE，AEFR是无是无 环的。环的。例例2：R=CST,SPY,CP不是无不是无 环的。环的。H1=CST,CST，H2=CSTPY,CST,SPY，H3=CSTPY,CST,SPY,CP?
