本章的主要内容：数据库模式的超图表示无环数据库模式无环数据库模式例：R=CSTPY(课程，学号，教师，先修课，年份)F={CS→T,SP→Y,C→→P}数据库模式R={CST,SPY,CP}6.1数据库模式的超图表示6.1数据库模式的超图表示6.1数据库模式的超图表示6.1数据库模式的超图表示定义7设F=(N,E)是H=(N,E)的导出图，E1、E2E且f=E1∩E2。若N–f后的图比F具有更多的连通支数，称结点集f为F的关节集。若导出图H中不含关节集，称H是H的一个块。仅含一条边的块称是平凡的，否则是非平凡的。H1中有一个环：ABC,C,CED,E,AEF,A,ABCH3是一个无环超图，也是一个无环超图。定义9超图H中若存在一个边和点的序列S1,v1,S2,v2,…,Sm,vm,Sm+1,且满足：(1).v1,v2,…,vm是H中的不同结点；(2).S1,S2,…,Sm是H中的不同边且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，则称这样的序列为一个环。6.2.1无环数据库模式的特性:1.连接依赖与一组多值依赖等价。例:数据库模式S={ABC,BCD,CE,DE}求：R的一课连接树。2.唯一4NF分解定义12设属性集U和MVD集M，X→→Y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(X∩Y)。则称MVDS集M是无冲突的。例1：R=ABCDEFGM={AC→→B,CE→→D,AE→→F，D→→G}分解结果：{ABC，CED，AEC，AEF，DG}结果唯一。3.两两一致性蕴涵全体一致性定义13设R={R1,R2,…,Rk}，对应d={r1,r2,…,rk}。对d中的任一对关系ri和rj若ri(Ri∩Rj)=rj(Ri∩Rj)，称数据库d是两两一致的。若U=R1∪R2∪…∪Rn上存在泛关系r使得任意关系rid有ri=r[Ri],称d是全体一致的。r1(ABC)r2(AD)r3(BDE)2362737225829591(r1r3)r2或r1(r2r3)为单调连接。而(r1r2)r3为非单调的单调顺序连接表达式：(…((r1r2)r3)…rk)连接结果随着连接顺序执行呈单调增长趋势。定理1数据库模式R的下列条件是等价的。(1)R是一个无环超图。(2)R是一个封闭无环的超图。(3)连接依赖*[R]与一个无冲突的MVDS集等价。(4)R上的每个两两一致的数据库也是全体一致的。(5)R上的每个数据库都有一个完全归约。(6)R有一个连接树。(7)R有运行相交特性。(8)R有一个单调连接表达式。(9)R有一个顺序的单调连接表达式。(10)R有唯一的4NF分解。6.2.2Graham算法算法6.2.1判定一个数据库模式是否是无环的输入：数据库模式R={R1,R2,…,Rk}输出：若R是无环模式输出为true否则为falseGraham(R)(1).构造数据库模式R的对应超图H=(N，E)。(2).对H反复施加以下规则直到不能施加为止：rN规则：将仅出现在一条边中的结点从N中删除；rE规则：将包含在某条边中的边e从E中删除。(3).若H为空则输出true，否则输出false。例:设数据库模式R1={ABC,CDE,ACE,AEF}，R2={CST,SPY,CP}判定：R1和R2是否是无环数据库模式。引理1Graham算法不会破坏超图中原有的块。引理2Graham算法不会生成新的块。引理3任一化简的具有二条或二条以上边的无环超图至少含有二个节。节：含有孤立结点（结点仅在一条边中出现）的边。6.2.3无环数据库模式的设计定理3设M是一组多值依赖集，在M下生成的4NF数据库模式是无环的当且仅当M有一个无冲突的覆盖。无环数据库模式R的设计:无环数据库模式R的设计是一个对应超图的设计序列：H1,H2,…,Hn，H1=(N1,E1)，E1仅有一个超边，R=Hn。对1i<n，Hi=(Ni,Ei)，Hi+1=(Ni+1,Ei+1)，(Hi,Hi+1)称为一个设计步，超边eEi，Ni+1=Ni∪e,Ei+1=Ei∪e，e∩Ni称为连接结点集。若每个设计步满足规则：对Hi=(Ni,Ei)和Hi+1=(Ni∪e，Ei∪e)，若有eEi使得e∩Nie，则生成的数据库模式是无环的。例1