无损联接分解
本文出自 “李驥平” 博客，請務必保留此出處
?
?
http://fsjoy.blog.51cto.com/318484/137130
?
?
?
?
定義：無損聯接分解是將一個關系模式分解成若干個關系模式后，通過自然聯接和投影等運算仍能還原到原來的關系模式，則稱這種分解為無損聯接分解。
?
?
??
?
?
例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 ? | a1 ? | b12 ? | b13 ? | a4 ? | b15 ? |
| BC ? | b21 ? | a2 ? | a3 ? | b24 ? | b25 ? |
| BE ? | b31 ? | a2 ? | b33 ? | b34 ? | a5 ? |
| CDE ? | b41 ? | b42 ? | a3 ? | a4 ? | a5 ? |
| AE ? | a1 ? | b52 ? | b53 ? | b54 ? | a5 ? |
表1
?
?
(A B C D E是關系R的屬性， AD, BC, BE, CDE, AE 是分解之后每一個關系對應的屬性集)
?
?
?
?
填表的過程：
?
?
當橫豎相交的時候，如果在分解關系中存在對應列的單個的屬性（譬如第一列第一行AD與A相交的單元格，AD含有A，就填寫a1），則填寫a下標 ， 下標就是單元格對應所在的列號。否則填寫b下標， 下標是單元格對應所在的行列號。
?
?
填寫之后的初始表就是表1所示
?
?
2.根據依賴關系修改原始表：
?
?
對于依賴關系A->C，看A列中有兩行a1是相等的（第一行和第五行），所以在C列中對應的兩行也應該相等，但是看到這兩行都是b（b13，b53），所以將這個b都換成b13（上面的較小的標）
?
?
?
?
|
? | A ? | B ? | C ? | D ? | E ? |
| AD ? | a1 ? | b12 ? | b13 ? | a4 ? | b15 ? |
| BC ? | b21 ? | a2 ? | a3 ? | b24 ? | b25 ? |
| BE ? | b31 ? | a2 ? | b33 ? | b34 ? | a5 ? |
| CDE ? | b41 ? | b42 ? | a3 ? | a4 ? | a5 ? |
| AE ? | a1 ? | b52 ? | b53àb13 ? | b54 ? | a5 ? |
對于依賴BàC, 同樣的道理，看B這一列中，第二行和第三行都是a2,那么對C這一列同樣的操作，但是看到C這一列中第二行是a3，那么就將第三行改成a3，優先級比b要高。
?
?
|
? | A ? | B ? | C ? | D ? | E ? |
| AD ? | a1 ? | b12 ? | b13 ? | a4 ? | b15 ? |
| BC ? | b21 ? | a2 ? | a3 ? | b24 ? | b25 ? |
| BE ? | b31 ? | a2 ? | b33àa3 ? | b34 ? | a5 ? |
| CDE ? | b41 ? | b42 ? | a3 ? | a4 ? | a5 ? |
| AE ? | a1 ? | b52 ? | b13 ? | b54 ? | a5 ? |
?
?
對依賴CàD，C列的1，5行相等，D的1，5行也應該相等，D的第1行有a，所以b54換成a4；另外C列的2，3，4行也相等，D的2，3，4行也應該相等，D的第4行有a，所以將對應的行都換成a4
?
?
|
? | A ? | B ? | C ? | D ? | E ? |
| AD ? | a1 ? | b12 ? | b13 ? | a4 ? | b15 ? |
| BC ? | b21 ? | a2 ? | a3 ? | b24àa4 ? | b25 ? |
| BE ? | b31 ? | a2 ? | a3 ? | b34àa4 ? | a5 ? |
| CDE ? | b41 ? | b42 ? | a3 ? | a4 ? | a5 ? |
| AE ? | a1 ? | b52 ? | b13 ? | b54àa4 ? | a5 ? |
?
?
?
?
對于DEàC, DE公共的相等的行是3，4，5行，對應C的3，4，5行也應該相等，故將C列的兩個的b13換成a3，所以表格經過這個函數依賴關系，就是：
?
?
|
? | A ? | B ? | C ? | D ? | E ? |
| AD ? | a1 ? | b12 ? | b13àa3 ? | a4 ? | b15 ? |
| BC ? | b21 ? | a2 ? | a3 ? | a4 ? | b25 ? |
| BE ? | b31 ? | a2 ? | a3 ? | a4 ? | a5 ? |
| CDE ? | b41 ? | b42 ? | a3 ? | a4 ? | a5 ? |
| AE ? | a1 ? | b52 ? | b13àa3 ? | a4 ? | a5 ? |
?
?
?
?
對于CEàA, CE的公共行是3，4，5行，所以將A的3，4，5行也對應相等，因為A列的第五行含有a1，所以將3，4行的b31,b41都換成a1
?
?
?
?
?
最終得到的表格就是：
?
?
?
?
?
?
?
?最后，我們從表格里看到對于DE行來說，都是a，所以得出結論，題中的分解是無損聯接分解
?
?
?
?
?
********************
?
?
?
?
?
無損分解的一個簡便的判別方法（適用于分解成2個關系的情況）
?
?
?
?
?
譬如：
?
?
有關系R=ABC, 依賴關系{A-->B}那么下面哪個是無損分解：
?
?
?
?
?
A. {R1(AB),R2(AC)}
?
?
B.{R1(AB),R3(BC)}
?
?
?
?
?
首先看選項A，R1∩R2=A，R1-R2=B，R1U R2-->(R1-R2).所以它是無損分解
?
?
選項B， R1∩R2=B, R1-R2=A, R2-R1=C,
?
?
所以它不是無損分解
?
?
?
?
?
那么這里快速判斷無損分解的方法就是
?
?
對兩個集合先求集合的∩，然后求集合的差(2個集合有兩個差的結果)
?
?
如果集合的∩-->集合的差（得到差結果的任意一個）成立那么就是無損分解
?
?
本文出自 “李驥平” 博客，請務必保留此出處http://fsjoy.blog.51cto.com/318484/137130
?
?
本文出自 51CTO.COM技術博客
?
?
?
轉載于:https://www.cnblogs.com/xyjblog/archive/2010/11/21/1883487.html
總結
- 上一篇： Python PIL : import
- 下一篇： 处理2D图像和纹理——显示文字