【文档说明】无环数据库模式课件.ppt，共(26)页，178.501 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-92534.html

以下为本文档部分文字说明：

第六章无环数据库模式本章的主要内容：数据库模式的超图表示无环数据库模式无环数据库模式例：R=CSTPY(课程，学号，教师，先修课，年份)F={CS→T,SP→Y,C→→P}数据库模式R={CST,SPY,C

P}r(CSTPY)C1S1t1p1y1C1S1t1P2y2C2S1t2P3y3r1(CST)r2(CP)r3(SPY)C1S1t1C1P1S1p1y1C2S1t2C1P2S1P2y2C2P3S1P3y3要求：查询教师t1所授课程的先修课。T,P(T＝t1(r1)r2);{t1,

p1};{t1,p2}T,P(T＝t1(r1)r3){t1,p1};{t1,p2};{t1,p3}6.1数据库模式的超图表示6.1数据库模式的超图表示ABCDGFE数据库模式：ABC、CDE、AEF、ACE、DG6.1数据库模式的超图表示定

义1一个超图H是一个二元组(N,E)，其中N是图中结点的集合，E是超边的集合，E中的每条超边都是E的非空子集。如果H中不存在任一超边完全包含在另一超边中，称H为化简超图，记为RED(H)。定义2若把数据

库模式R中的属性作为超图HR中的结点，R中同一关系模式中的属性用一条超边表示，则称HR为数据库模式R的超图。6.1数据库模式的超图表示定义3设超图H=(N,E)，其中A和B是N中的结点，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数据库模式的超图表示定义4设超图H=(N,E)、H=(N,E)是超图,若结点

NN，边集EE，称H是H的子图。若对任意边eE，e∩NE，则称H是H的封闭子图。若NN，E={e∩N|eE}，则称H是H的导出图。H1=(ABCDEIJK,{ABC,BD,CDE,DEI,CIK,IJK})H1AECJBDIK连通

：ABC,BD,CDE不连通：ABC,IJKACEBDACBDCEJDIKH1是子图,封闭子图,导出图，H1是导出图(CD不是e的边)H1子图,不是封闭子图和导出图(CIK)定义7设F=(N,E)是H=(N,E)的导出图，

E1、E2E且f=E1∩E2。若N–f后的图比F具有更多的连通支数，称结点集f为F的关节集。若导出图H中不含关节集，称H是H的一个块。仅含一条边的块称是平凡的，否则是非平凡的。定义8在超图H中若不存在非平凡的块，称H是无环超图，否则为有环超图。对应超图是无环的

数据库模式称为无环数据库模式。H1中有一个环：ABC,C,CED,E,AEF,A,ABCH3是一个无环超图，也是一个无环超图。EABCFDH1ACEBDFH3EABCFDH2H1是无环超图{ABC,CED,ACE,AEF}，H

2是有环超图{ABC,CED,AEF}，一个无环超图其子图可以有环，一个无环超图其子图不能有环。定义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，则称这样的序列为一个环。定义10一个超图中若不存在任何环，则称

该超图为无环超图，否则称为有环超图。如果一个数据库模式R对应的超图是一个无环超图，则称该数据库模式R为无环数据库模式。6.2.1无环数据库模式的特性: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Ri∩Rj,则该条通路的每条边的标识中都含有A。ABCACEAEFCDEDGACAECED*[R]对应的一组多值依赖:{AC→→

B，CE→→D，AE→→F，D→→G}例:设无环数据库模式R={ABC,CDE,ACE,AEF,DG}求：R的一棵连接树。例:数据库模式S={ABC,BCD,CE,DE}求：R的一课连接树。ACEBDABCBCDCEDEBCCD2.唯一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)。则称MV

DS集M是无冲突的。例1：R=ABCDEFGM={AC→→B,CE→→D,AE→→F，D→→G}分解结果：{ABC，CED，AEC，AEF，DG}结果唯一。例2：R=ABCDEM={AB→→C,CE→→B}分解结

果：R1={ABC，ABDE}R2={BCE，ACDE}结果不唯一。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(AB)r2(BCD)r3(CDA)122454522334646125586862r1(ABC)r2(AD)r3(BDE)236

2737225829591(r1r3)r2或r1(r2r3)为单调连接。而(r1r2)r3为非单调的4.单调顺序连接表达式单调连接:连接过程中没有中间结果元组被丢失。单调连接表达式:每个子表达式都是一致的。(r1r2)(r3r4)单调顺序连接表达式

：(…((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分解。R的每个封闭子超图都是无环的。归约后的结果关系是全体一致的在序列R1,R2,…,RK中,Ri与前面模式集并的交集包含在前面某个模式中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

是否是无环数据库模式。EABCFDTSYCPR1R2引理1Graham算法不会破坏超图中原有的块。引理2Graham算法不会生成新的块。引理3任一化简的具有二条或二条以上边的无环超图至少含有二个节。节：含有孤立结点（结点仅在一条边中出

现）的边。定理2若R为无环数据库模式，当且仅当Graham算法在R上是成功的。6.2.3无环数据库模式的设计定理3设M是一组多值依赖集，在M下生成的4NF数据库模式是无环的当且仅当M有一个无冲突的覆盖。例：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仅有一个超边，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：R={ABC，CDE，AEF，ACE}，其生成序列：H1={ACE,{ACE}}，H2={ABCE,{ACE,ABC}}，H3={ABCDE,{ACE,ABC，CDE}}，R=H

4={ABCDEF,{ACE,ABC，CDE，AEF}}R是无环的。例2：R={CST,SPY,CP}不是无环的。H1={CST,{CST}}，H2={CSTPY,{CST,SPY}}，H3={CSTPY,{CST,SPY,CP}}??