3-3-2
来源:百度文库 编辑:神马文学网 时间:2024/10/02 20:24:55
3.3.1 关系模式的分解
1.定义
(2)一般把上述的R称为泛关系模式,R对应的当前值称为泛关系。数据库模式ρ对应的当前值称为数据库实例,它是由数据库模式中的每一个关系模式的当前值组成。我们用σ=<r1,…,rk>表示。
2.模式分解示意图
3.模式分解的两个问题
(1)σ和r是否等价,即是否表示同样的数据。这个问题用“无损分解”特性表示。
(2)在模式R上有一个FD集F,在ρ的每一个模式Ri上有一个FD集Fi,那么{F1,…,Fk}与F是否等价。这个问题用“保持依赖”特性表示。 3.3.2 无损分解
1.无损分解和损失分解的例子
(1)设有关系模式R(ABC),分解成ρ={ AB,AC }。
(2)无损分解的例子
(3)损失分解的例子
2.寄生元组
3.无损分解的定义
(2)其中符号πRi(r)表示关系r在模式Ri属性上的投影。r的投影连接表达式πR1(r)
4.说明
①先存在r(泛关系)的情况下,再去谈论分解,这是关系数据库理论中著名的“泛关系假设”(universal relation assumption)。
②如果谈论模式分解时,先不提泛关系r的存在性,而先说存在一个数据库实例σ〈r1,…,rk〉,再设
5.定义
(1)在无泛关系假设时,对两个关系进行自然连接中被丢失的元组称为悬挂元组。
(2)悬挂元组是造成两个关系不存在泛关系的原因。
6.实例
(1)设关系模式R(ABC)分解成ρ={AB,BC}。
(2)关系r1和r2不存在泛关系。
(3)显然πBC(r1
(4)这里r2中元组(b2c2)就是一个悬挂元组,由于它的存在,使得r1和r2不存在泛关系r。 3.3.3 模式分解的优缺点
1.模式分解的优点
(1)模式分解能消除数据冗余和操作异常现象。
(2)在分解了的数据库中可以存储悬挂元组,存储泛关系中无法存储的信息。
2.模式分解的缺点
(1)分解以后,检索操作需要做笛卡儿积或连接操作,这将付出时间代价。
(2)在有泛关系假设时,对数据库中关系进行自然连接时,可能产生寄生元组,即损失了信息。在无泛关系假设时,由于数据库中可能存在悬挂元组,就有可能不存在泛关系。 3.3.4 无损分解的测试方法
1.无损分解的测试算法
(1)输入:关系模式R=A1…An,F是R上成立的函数依赖集,ρ={ R1,…,Rk }是R的一个分解。
(2)输出:判断ρ相对于F是否具有无损分解特性。
(3)方法:
①构造一张k行n列的表格,每列对应一个属性Aj(1≤j≤n),每行对应一个模式Ri(1≤i≤k)。如果Aj在Ri中,那么在表格的第i行第j列处填上符号aj,否则填上bij。
②把表格看成模式R的一个关系,反复检查F中每个FD在表格中是否成立,若不成立,则修改表格中的值。修改方法如下:
对于F中一个函数依赖X→Y,如果表格中有两行在X值上相等,在Y值上不相等,那么把这两行在Y值上也改成相等的值。如果Y值中有一个是aj,那么另一个也改成aj;如果没有aj,那么用其中一个bij替换另一个值(尽量把下标ij改成较小的数)。一直到表格不能修改为止。这个过程称为chase(追踪)过程。
③若修改的最后一张表格中有一行是全a,即a1a2…an,那么称ρ相对于F是无损分解,否则称损失分解。
2.实例
(1)问题
设关系模式R(ABCD),R分解成ρ={AB,BC,CD}。如果R上成立的函数依赖集F1={B→A,C→D},那么ρ相对于F1是否无损分解?如果R上成立的函数依赖集F2={A→B,C→D}呢?
(2)求解
①相对于F1,chase过程的示意图
据B→A,可把b21改成a1;据C→D,可把b24改成a4。此时第二行已是全a行,因此相对于F1,R分解成ρ是无损分解。
②相对于F2,chase过程的示意图
据C→D,可把b24改成a4;据A→B,不能修改表格。此时表格没有一行是全a行,因此相对于F2,R分解成ρ是损失分解。
3.Chase的机理
①在chase过程中,如果把b改成a,则表示可以从其他模式和已知的FD使得该模式可以增加一个属性。如果改成另一个bij,表示模式相应关系中该属性值虽然还没有,但其值应与其他关系中的值相等。
②当最后一张表格中存在一行全a时,这行表示的模式中可以包含R的所有属性,也就回到原来的表格,即mρ(r) = r。因此,分解是无损分解。
③当最后一张表格中,不存在全a行时,也就是回不到原来的表格,即mρ(r) ≠ r。因此,分解是损失分解。 3.3.5 保持函数依赖的分解
1.定义
(2)设ρ={R1,…,Rk}是R的一个分解,F是R上的FD集,如果有
2.说明
①从定义1可知F
②根据定义1,测试一个分解是否保持FD,比较可行的方法是逐步验证F中每个FD是否被
③如果F的投影不蕴涵F,而我们又用ρ={R1,…,Rk}表达R,很可能会找到一个数据库实例σ满足投影后的依赖,但不满足F。对σ的更新也有可能使r违反FD。
3.实例
(1)设关系模式R(T#,TITLE,SALARY)的属性分别表示教师的工号、职称和工资。如果规定每个教师只有一个职称,并且每个职称只有一个工资数目,那么R上的FD有T#→TITLE和TITLE→SALARY。
(2)如果R分解成ρ={R1,R2},其中R1={T#,TITLE},R2={T#,SALARY},可以验证这个分解是无损分解。
(3)R1上FD是F1={T#→TITLE},R2上的FD是F2={T#→SALARY}。但从这两个FD推导不出在R上成立的函数依赖TITLE→SALARY,因此分解ρ把TITLE→SALARY丢失了,即ρ不保持F。
(4)表(a)和(b)是两个关系r1和r2,(c)是r1
4.小结
如果某个分解能保持FD集,那么在数据输入或更新时,只要每个关系模式本身的FD约束被满足,就可以确保整个数据库中数据的语义完整性不受破坏。显然这是一种良好的特性。 3.3.6 模式分解与模式等价问题
1.关系模式分解的两个特性
(1)无损分解
(2)依赖等价
2.数据库模式的等价问题
(1)数据等价
①数据等价是指两个数据库实例应表示同样的信息内容,用“无损分解”衡量。
②如果是无损分解,那么对泛关系反复的投影和连接都不会丢失信息。
(2)依赖等价
①依赖等价是指两个数据库模式应有相同的依赖集闭包。
②在依赖集闭包相等情况下,数据的语义是不会出差错的。
3.小结
(1)违反数据等价或依赖等价的分解很难说是一个好的模式设计。
(2)但是要同时达到无损分解和保持FD的分解也不是一件容易的事情,需要认真对待。
(3)从下例可以看出分解的无损分解与保持FD的分解两个特性之间没有必然的联系。
4.实例
(1)问题
○设关系模式R(ABC),ρ={AB,AC}是R的一个分解。试分析分别在F1={A→B},F2={A→C,B→C},F3={B→A},F4={C→B,B→A}情况下,ρ是否具有无损分解和保持FD的分解特性。
(2)解答:
①相对于F1={A→B},分解ρ是无损分解且保持FD的分解。
②相对于F2={A→C,B→C},分解ρ是无损分解,但不保持FD集。因为B→C丢失了。
③相对于F3={B→A},分解ρ是损失分解但保持FD集的分解。
④相对于F4={C→B,B→A},分解ρ是损失分解且不保持FD集的分解(丢失了C→B)。