database_无损联接分解

本文出自 “李骥平” 博客&＃xff0c;请务必保留此出处

http://fsjoy.blog.51cto.com/318484/137130

 

定义&＃xff1a;无损联接分解是将一个关系模式分解成若干个关系模式后&＃xff0c;通过自然联接和投影等运算仍能还原到原来的关系模式&＃xff0c;则称这种分解为无损联接分解。

  

例1&＃xff1a;关系模式&＃xff1a;成绩&＃xff08;学号&＃xff0c;姓名&＃xff0c;课程号&＃xff0c;课程名&＃xff0c;分数&＃xff09;

函数依赖&＃xff1a;学号->姓名&＃xff0c;课程号->课程名&＃xff0c; &＃xff08;学号&＃xff0c;课程号&＃xff09;->分数

若将其分解为下面三个关系模式&＃xff1a;

 

成绩&＃xff08;学号&＃xff0c;课程号&＃xff0c;分数&＃xff09;

学生&＃xff08;学号&＃xff0c;姓名&＃xff09;

课程&＃xff08;课程号&＃xff0c;课程名&＃xff09;

问&＃xff0c;这样的分解是无损分解么&＃xff1f;

----

由于&＃xff1a;学号->姓名&＃xff0c;所以&＃xff1a;

成绩&＃xff08;学号&＃xff0c;课程号&＃xff0c;分数&＃xff0c;姓名&＃xff09;

由于&＃xff1a;课程号->课程名&＃xff0c;所以&＃xff1a;

成绩&＃xff08;学号&＃xff0c;课程号&＃xff0c;分数&＃xff0c;姓名&＃xff0c;课程名&＃xff09;

 

所以这个例子是无损分解

 

例2&＃xff1a;设R&＃61;ABCDE, R1&＃61;AD,R2&＃61;BC,R3&＃61;BE,R4&＃61;CDE, R5&＃61;AE, 设函数依赖&＃xff1a;

A->C, B->C, C->D, DE->C, CE->A. 判断R分解成

 

ρ&＃61;{R1,  R2,  R3,  R4,  R5}是否无损联接分解&＃xff1f;

 

解&＃xff1a;

这样的题要通过画表的方法来解&＃xff0c;首先&＃xff0c;原始表&＃xff1a;

 

表1

(A B C D E是关系R的属性&＃xff0c; AD, BC, BE, CDE, AE 是分解之后每一个关系对应的属性集)

 

填表的过程&＃xff1a;

当横竖相交的时候&＃xff0c;如果在分解关系中存在对应列的单个的属性&＃xff08;譬如第一列第一行AD与A相交的单元格&＃xff0c;AD含有A&＃xff0c;就填写a₁&＃xff09;&＃xff0c;则填写a_下标 &＃xff0c; 下标就是单元格对应所在的列号。否则填写b_下标&＃xff0c; 下标是单元格对应所在的行列号。

填写之后的初始表就是表1所示

2.根据依赖关系修改原始表&＃xff1a;

对于依赖关系A->C&＃xff0c;看A列中有两行a₁是相等的&＃xff08;第一行和第五行&＃xff09;&＃xff0c;所以在C列中对应的两行也应该相等&＃xff0c;但是看到这两行都是b&＃xff08;b₁₃&＃xff0c;b₅₃&＃xff09;&＃xff0c;所以将这个b都换成b₁₃&＃xff08;上面的较小的标&＃xff09;

 

对于依赖BàC, 同样的道理&＃xff0c;看B这一列中&＃xff0c;第二行和第三行都是a₂,那么对C这一列同样的操作&＃xff0c;但是看到C这一列中第二行是a₃&＃xff0c;那么就将第三行改成a₃&＃xff0c;优先级比b要高。

 

对依赖CàD&＃xff0c;C列的1&＃xff0c;5行相等&＃xff0c;D的1&＃xff0c;5行也应该相等&＃xff0c;D的第1行有a&＃xff0c;所以b₅₄换成a₄&＃xff1b;另外C列的2&＃xff0c;3&＃xff0c;4行也相等&＃xff0c;D的2&＃xff0c;3&＃xff0c;4行也应该相等&＃xff0c;D的第4行有a&＃xff0c;所以将对应的行都换成a₄

 

 

对于DEàC, DE公共的相等的行是3&＃xff0c;4&＃xff0c;5行&＃xff0c;对应C的3&＃xff0c;4&＃xff0c;5行也应该相等&＃xff0c;故将C列的两个的b₁₃换成a₃&＃xff0c;所以表格经过这个函数依赖关系&＃xff0c;就是&＃xff1a;

 

 

对于CEàA, CE的公共行是3&＃xff0c;4&＃xff0c;5行&＃xff0c;所以将A的3&＃xff0c;4&＃xff0c;5行也对应相等&＃xff0c;因为A列的第五行含有a₁&＃xff0c;所以将3&＃xff0c;4行的b₃₁,b₄₁都换成_a1

 

最终得到的表格就是&＃xff1a;

 

 最后&＃xff0c;我们从表格里看到对于DE行来说&＃xff0c;都是a&＃xff0c;所以得出结论&＃xff0c;题中的分解是无损联接分解

 

********************

 

无损分解的一个简便的判别方法&＃xff08;适用于分解成2个关系的情况&＃xff09;

 

譬如&＃xff1a;

有关系R&＃61;ABC, 依赖关系{A-->B}那么下面哪个是无损分解&＃xff1a;

 

A. {R₁(AB),R₂(AC)}

B.{R₁(AB),R₃(BC)}

 

首先看选项A&＃xff0c;R₁∩R₂&＃61;A&＃xff0c;R₁-R₂&＃61;B&＃xff0c;R₁U R₂-->(R₁-R₂).所以它是无损分解

选项B&＃xff0c; R₁∩R₂&＃61;B, R₁-R₂&＃61;A, R₂-R₁&＃61;C,

所以它不是无损分解

 

那么这里快速判断无损分解的方法就是

对两个集合先求集合的∩&＃xff0c;然后求集合的差(2个集合有两个差的结果)

如果集合的∩-->集合的差&＃xff08;得到差结果的任意一个&＃xff09;成立那么就是无损分解

本文出自 “李骥平” 博客&＃xff0c;请务必保留此出处http://fsjoy.blog.51cto.com/318484/137130

本文出自 51CTO.COM技术博客