1、第六章 无环数据库模式,本章的主要内容：数据库模式的超图表示无环数据库模式无环数据库模式,例： R=CSTPY (课程，学号，教师，先修课，年份)F=CST, SPY, CP 数据库模式R=CST, SPY, CP,r (C S T P Y )C1 S1 t1 p1 y1C1 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 y1C2 S1 t2 C1 P2 S1 P2 y2 C2 P3 S1 P3 y3,6.1 数据库模式的超图表示,6.1 数据库模式的超图表示,数据库模式： ABC、CD
2、E、AEF、ACE、DG,6.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, K1, 使得AE1，BEK，且Ei Ei+1 , 1 i K, 则称
3、边序列E1, E2, , EK为从E1 到EK的通路。如果二个顶点或二条边之间有一条通路，则称他们是连通的。若一个边集中的任一对边都是连通的，则称这些边集是连通的。,6.1 数据库模式的超图表示,定义4 设超图H=(N, E)、H=(N, E)是超图, 若结点NN，边集E E，称H是H的子图。若对任意边eE，eNE，则称H是H的封闭子图。 若NN，E=eN| eE，则称H是H的导出图。,H1 =(ABCDEIJK,ABC, BD, CDE,DEI,CIK,IJK),H1是子图,封闭子图,导出图， H1是导出图(CD不是e的边) H1子图,不是封闭子图和导出图(CIK),定义7 设F=( N,
4、E)是H=(N, E)的导出图，E1、E2 E且f =E1E2。若 N f 后的图比F具有更多的连通支数，称结点集f 为F的关节集。若导出图H中不含关节集，称H是H的一个块。仅含一条边的块称是平凡的，否则是 非平凡的。,定义8 在超图H中若不存在非平凡的块，称H是无环超图， 否则为有环超图。 对应超图是无环的数据库模式称为无环数据库模式。,H1中有一个环：ABC, C, CED, E, AEF, A, ABC H3是一个无环超图，也是一个无环超图。,H1是无环超图ABC, CED, ACE, AEF ， H2是有环超图ABC, CED, AEF ，,一个无环超图其子图可以有环， 一个无环超图其
5、子图不能有环。,定义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). 对所有1i , j m，j i, j i+1，viSj，则称这样的序列为一个环。,定义10 一个超图中若不存在任何环，则称该超图为无环超图，否则称为有环超图。如果一个数据库模式R对应的超图是一个无环超图，则称该数据库模式R为无环数据库模式。,6
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 RiRj, 则该条通路的每条边的标识中都含有A。,*R 对应的一组多值依赖: ACB，CED，AEF，DG,例: 设无环数据库模式R= ABC, CDE, ACE, AE
7、F, DG 求：R的一棵连接树。,例: 数据库模式 S = ABC, BCD, CE, DE 求：R的一课连接树。,2. 唯一4NF分解 定义12 设属性集U 和 MVD 集 M，XY M，W U。若A、B W而使得A Y，B UXY，则称X Y分裂W。若多值依赖集M 满足：(1). M中每个MVD都不分裂其他MVD的左部;(2). M中任意二个MVD的左部属性集X和Y，DEP(X)DEP(Y) DEP(XY)。则称MVDS集M是无冲突的。,例1： R=ABCDEFG M=ACB, CED, AEF，DG 分解结果：ABC，CED，AEC， AEF， DG结果唯一。,例2： R=ABCDE M
8、=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是两两一致的。 若U= R1R2Rn上存在泛关系 r 使得任意关系 ri d有ri = r Ri, 称d是全体一致的。,r1( A B ) r2( B C D ) r3( C D A )1 2 2 4 5 4 5 22 3 3 4 6 4 6 12 5 5 8 6 8 6 2,4. 单调顺序连接表达式,单调
9、连接: 连接过程中没有中间结果元组被丢失。,无环数据库模式有一个单调顺序连接表达式,定理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与前面模式集并
10、的交集包含在前面某个模式中,6.2.2 Graham算法 算法6.2.1 判定一个数据库模式是否是无环的 输入：数据库模式R=R1, R2,Rk 输出：若R是无环模式输出为true否则为false Graham(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是否是无环数据库模式
11、。,引理1 Graham算法不会破坏超图中原有的块。 引理2 Graham算法不会生成新的块。 引理3 任一化简的具有二条或二条以上边的无环超图至少含有二个节。节： 含有孤立结点（结点仅在一条边中出现）的边。,定理2 若R为无环数据库模式，当且仅当Graham算法在R上是成功的。,6.2.3 无环数据库模式的设计 定理3 设M是一组多值依赖集，在M下生成的4NF数据库模式是无环的当且仅当M有一个无冲突的覆盖。,例：U=ABCDEF, M=AC B, CE D, AE FM是无冲突的，4NF的数据库模式为：ABC, CDE, ACE, AEF以上模式是无 环的。,定理4 设函数依赖和多值依赖集D
12、，在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)称为一个设计步，超边eEi，Ni+1 =Nie, Ei+1=Eie，eNi称为连接结点集。若每个设计步满足规则：对Hi = (Ni , Ei)和Hi+1=( Nie，Eie)，若有eEi使得eNi 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，AEF R是无环的。,例2： R= CST, SPY, CP不是无环的。H1=CST, CST，H2=CSTPY, CST, SPY，H3=CSTPY, CST, SPY, CP ?,
