3-3-3

3.3.1 关系模式的分解
1.定义
　　(1)设有关系模式R(U)，属性集为U，R1、…、Rk都是U的子集，并且有R1∪R2∪…∪Rk＝U。关系模式R1、…、Rk的集合用ρ表示，ρ=｛R1，…，Rk｝。用ρ代替R的过程称为关系模式的分解。这里ρ称为R的一个分解，也称为数据库模式。
　　(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.寄生元组
　　在泛关系模式R分解成数据库模式ρ={R1，…，Rk}时，泛关系r在ρ的每一模式Ri（1≤i≤n）上投影后再连接起来，比原来r中多出来的元组，称为“寄生元组”（Spurious Tuple）或额外元组。实际上，寄生元组表示着错误的信息。
3.无损分解的定义
　　(1)设R是一个关系模式，F是R上的一个FD集。R分解成数据库模式ρ=｛ R1，…，Rk ｝。如果对R中满足F的每一个关系r，都有r=π_R1（r）π_R2（r） … π_Rk（r），那么称分解ρ相对于F是“无损连接分解”（lossless join decomposition），简称为“无损分解”，否则称为“损失分解”（lossy decomposition）。
　　(2)其中符号π_Ri(r)表示关系r在模式Ri属性上的投影。r的投影连接表达式π_R1(r)…π_Rk(r) 用符号m_ρ(r)表示，即m_ρ(r)=π_Ri(r)。

4.说明
　　 ①先存在r（泛关系）的情况下，再去谈论分解，这是关系数据库理论中著名的“泛关系假设”（universal relation assumption）。
　　 ②如果谈论模式分解时，先不提泛关系r的存在性，而先说存在一个数据库实例σ〈r1，…，rk〉，再设π_ri(r)=s，那么π_Ri(s)就未必与ri相等了。原因就是这些ri中可能有“悬挂”元组（dangling tuple，破坏泛关系存在的元组）。
5.定义
(1)在无泛关系假设时，对两个关系进行自然连接中被丢失的元组称为悬挂元组。
(2)悬挂元组是造成两个关系不存在泛关系的原因。
6.实例

(1)设关系模式R（ABC）分解成ρ=｛AB，BC｝。
(2)关系r1和r2不存在泛关系。
(3)显然π_BC（r1r2）≠r2。
(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.定义
　　(1)设F是属性集U上的FD集，Z是U的子集，F在Z上的投影用π_Z（F）表示，定义为π_Z（F）=｛X→Y | X→Y∈F⁺，且XYZ｝
　　(2)设ρ=｛R1，…，Rk｝是R的一个分解，F是R上的FD集，如果有π_Ri(F) F，那么称分解ρ保持函数依赖集F。

2.说明
　　 ①从定义1可知Fπ_Ri(F)，从定义2可知π_Ri(F)F，因此，在分解ρ保持函数依赖情况下有(π_Ri(F))⁺=F⁺。
　　 ②根据定义1，测试一个分解是否保持FD，比较可行的方法是逐步验证F中每个FD是否被π_Ri(F) 逻辑蕴涵。
　　 ③如果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）是r1r2。r1和r2分别满足F1和F2。但r1r2违反了TITLE→SALARY。
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)。