软考数据库-无损联接分解

时间：2015-12-16 19:23:32 阅读：287 评论：0 收藏：0 [点我收藏+]

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

可还原

例1：关系模式：成绩（学号，姓名，课程号，课程名，分数）

函数依赖：学号->姓名，课程号->课程名，（学号，课程号）->分数

若将其分解为下面三个关系模式：

成绩（学号，课程号，分数）

学生（学号，姓名）

课程（课程号，课程名）

问，这样的分解是无损分解么？

----

由于：学号->姓名，所以：

成绩（学号，课程号，分数，姓名）

由于：课程号->课程名，所以：

成绩（学号，课程号，分数，姓名，课程名）

所以这个例子是无损分解

例2：设R=ABCDE, R1=AD,R2=BC,R3=BE,R4=CDE, R5=AE, 设函数依赖：

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

ρ={R1, R2, R3, R4, R5}是否无损联接分解？

解：

这样的题要通过画表的方法来解，首先，原始表：

	A	B	C	D	E
AD	a₁	b₁₂	b₁₃	a₄	b₁₅
BC	b₂₁	a₂	a₃	b₂₄	b₂₅
BE	b₃₁	a₂	b₃₃	b₃₄	a₅
CDE	b₄₁	b₄₂	a₃	a₄	a₅
AE	a₁	b₅₂	b₅₃	b₅₄	a₅

表1

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

填表的过程：

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

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

2.根据依赖关系修改原始表：

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

	A	B	C	D	E
AD	a₁	b₁₂	b₁₃	a₄	b₁₅
BC	b₂₁	a₂	a₃	b₂₄	b₂₅
BE	b₃₁	a₂	b₃₃	b₃₄	a₅
CDE	b₄₁	b₄₂	a₃	a₄	a₅
AE	a₁	b₅₂	b₅₃àb₁₃	b₅₄	a₅

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

	A	B	C	D	E
AD	a₁	b₁₂	b₁₃	a₄	b₁₅
BC	b₂₁	a₂	a₃	b₂₄	b₂₅
BE	b₃₁	a₂	b₃₃àa₃	b₃₄	a₅
CDE	b₄₁	b₄₂	a₃	a₄	a₅
AE	a₁	b₅₂	b₁₃	b₅₄	a₅

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

	A	B	C	D	E
AD	a₁	b₁₂	b₁₃	a₄	b₁₅
BC	b₂₁	a₂	a₃	b₂₄àa₄	b₂₅
BE	b₃₁	a₂	a₃	b₃₄àa₄	a₅
CDE	b₄₁	b₄₂	a₃	a₄	a₅
AE	a₁	b₅₂	b₁₃	b₅₄àa₄	a₅

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

	A	B	C	D	E
AD	a₁	b₁₂	b₁₃àa₃	a₄	b₁₅
BC	b₂₁	a₂	a₃	a₄	b₂₅
BE	b₃₁	a₂	a₃	a₄	a₅
CDE	b₄₁	b₄₂	a₃	a₄	a₅
AE	a₁	b₅₂	b₁₃àa₃	a₄	a₅

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

最终得到的表格就是：

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

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

无损分解的一个简便的判别方法（适用于分解成2个关系的情况）

譬如：

有关系R=ABC, 依赖关系{A-->B}那么下面哪个是无损分解：

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

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

首先看选项A，R₁∩R₂=A，R₁-R₂=B，R₁U R₂-->(R₁-R₂).所以它是无损分解

选项B， R₁∩R₂=B, R₁-R₂=A, R₂-R₁=C,

所以它不是无损分解

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

对两个集合先求集合的∩，然后求集合的差(2个集合有两个差的结果)

如果集合的∩-->集合的差（得到差结果的任意一个）成立那么就是无损分解

其它问题请加我的微信:x7993794, 可加入我的软考数据库微信群一起讨论

（本文出自 “李骥平” 博客）

软考数据库-无损联接分解

原文：http://www.cnblogs.com/fredx/p/5052026.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)