3.5 关系模式的分解

在3.4节中，通过分解的方法消除了模式中的操作异常，减少和控制了数据冗余问题。要使关系模式的分解有意义，模式分解需要满足一些约束条件使分解不破坏原来的语义，即模式分解要符合无损连接和保持函数依赖的原则。本节主要讨论关系模式分解中的两个重要特性：保持信息的无损连接和保持函数依赖性。

（1）无损连接的分解

无损连接保证分解前后关系模式的信息不能丢失和增加，保持原有的信息不变。反映了模式分解的数据等价原则。如果不能保持无损连接性，那么在关系中就会出现错误的信息。

【定义3.17】设ρ={R1，R2，…，Rn}是R的一个分解，若对于任一R的关系实例r，都有r=π_R1（r）∞π_R2（r）∞…∞π_Rn（r）…则称该分解满足F的无损连接，简称无损分解；否则称为有损连接分解，简称有损分解。其中π_Rn（r）是r在关系模式Rn上的投影。

例如，有关系模式R（A，B，C）和具体关系r如表3-26（a）所示，其中R被分解的两个关系模式ρ={AB，AC}，r在这两个模式上的投影分别如表3-26（b）、表3-26（c）所示。显然r=r₁∞r₂，即分解ρ是无损连接分解。

如果是有损分解，则说明了分解后的关系做自然连接的结果比分解前的R反而增加了元组，它使原来关系中一些确定的信息变成不确定的信息，因此它是有害的错误信息，对做连接查询操作是极为不利的。

例如，有关系模式R（学号，课程号，成绩）和具体的关系r如表3-27（a）所示，R的一个分解为ρ={（学号，课程号），（学号，成绩）}，对应的两个关系r₁、r₂如表3-27（b）、表3-27（c）所示。此时r≠r₁∞r₂，如表3-27（d）所示，多出了两个元组（值加下划线的元组）。显然，这两个元组有悖于原来r中的元组，使原来元组值变成了不确定的信息。

将关系模式R分解成ρ={R1，R2，…，Rn}以后，如何判定该分解是否是无损连接分解？这是一个值得关心的问题。下面分别介绍判定是否具有无损连接分解的方法：判定表法。

【算法3.3】无损连接的测试。

输入：关系模式R=A₁，A₂，…，A_n，R上成立的函数依赖集F，R的一个分解ρ={R₁，R₂，…，R_k}。

输出：判断ρ相对于F是否具有无损连接特性。

方法：

1）构造一张k行n列的表格，每列对应一个属性A_j（l≤j≤n），每行对应一个模式R_i（1≤i≤k）。如果A_j在R_i中，那么在表格的第i行第j列处填上符号a_j，否则填上符号b_ij。

2）反复检查F的每一个函数依赖，并修改表格中的元素，其方法如下：

取F中的函数依赖X→Y，如果表格中有两行在X分量上相等，在Y分量上不相等，那修改Y，使这两行在Y分量上也相等。如果Y的分量中有一个是a_j，那么另一个也修改成a_j；如果没有a_j，那么用其中一个b_ij替换另一个符号（尽量把下标ij改成较小的数）。一直到表格不能修改为止（这个过程称为Chase过程）。

3）若修改到最后一张表格中有一行是全a，即a₁a₂…a_n，那么 ρ 相对于F是无损连接分解。

【例3-30】设R=ABCDE，R₁=AD，R₂=AB，R₃=BE，R₄=CDE，R₅=AE，设函数依赖是A→C，B→C，C→D，DE→C，CE→A。判断R分解成ρ={R₁，R₂，R₃，R₄，R₅}是否无损连接分解。

解：Chase过程的初始表如表3-28（a）所示。

根据A→C，对表3-27（a）进行处理，将b₁₃、b₂₃、b₅₂改成同一符号b₁₃，即b₁₃=b₂₃=b₅₂。然后考虑B→C，将b₃₃、b₁₃改成同一符号b₁₃。修改后的表格如表3-28（b）所示。

考虑C→D，根据上述修改原则，将第四列的b₂₄、b₃₄和b₅₄均改成a₄，其结果如表3-28（c）所示。考虑DE→C，根据修改原则将C所在列的第三、四和五行的元素改为a₃，其结果如表3-28（d）所示。

考虑CE→A，根据修改原则，将第一列的第三、四、五行的元素都改成a₁，其结果如表3-28（e）所示。

从表3-28（e）中可以看出，此时第三行已是全a行，因此R分解成ρ={R₁，R₂，R₃，R₄，R₅}是无损连接分解。

（2）保持函数依赖的分解

保持依赖性分解是关系模式分解的另一个分解特性，分解后的关系不能破坏原来的函数依赖（不能破坏原来的语义），即保持分解前后原有的函数依赖依然成立。保持依赖反映了模式分解的依赖等价原则。

例：成绩（学号，课程名，教师姓名，成绩）

函数依赖集：

分解为：学-课-教（学号，课程名，成绩）、学-教（学号，教师姓名）

丢失函数依赖：教师姓名→课程名，不能体现一个教师只开一门课的语义。

【定义3.18】设F是关系模式R（U）上的FD集，Z⊆U，F在Z上的投影用π_Z（F）表示，定义为

π_Z（F）={X→Y|X→Y∈F⁺，X，Y⊆Z}

【定义3.19】设R的一个分解ρ={R₁，R₂，…，R_n}，F是R上的依赖集，如果F等价于U=π_R1（F）∪π_R2（F）∪…∪π_Rk（F），则称分解ρ具有依赖保持性。

由于U⊆F，即U⁺⊆F⁺必成立，所以只要判断F⁺⊆U⁺是否成立即可。具体方法：

对F中有而G中无的每个X→Y，求X相对于函数依赖集U的闭包，如果所有的Y，都有，则称分解具有依赖保持性，如果存在某个Y，有，则分解不具依赖保持性。

【例3-31】设关系模式R{A，B，C，D，E}，F={A→B，B→C，C→D，D→A}是依赖集，ρ={AB，BC，CD}是R的一个分解，判断该分解是否具有依赖保持性。

解：因为

π_AB（F）={A→B，B→A}

π_BC（F）={B→C，C→B}

π_CD（F）={C→D，D→C}

U=π_AB（F）∪π_BC（F）∪π_CD（F）={A→B，B→A，B→C，C→B，C→D，D→C}

从中可以看到，A→B，B→C，C→D均得以保持，对于D→A，由于，所以，该分解具有依赖保持性。

注意：一个无损连接不一定具有依赖保持性，同样，一个依赖保持性分解不一定具有无损连接。

思考：设R{A，B，C}，F={A→B，C→B}是依赖集，判断分解ρ1（AB，AC），ρ2（AB，BC）是否具有无损连接性和依赖保持性？

（3）模式分解的算法

范式和分解是数据库设计中两个重要的概念和技术，模式规范化的手段是分解，将模式分解成3NF和BCNF后是否一定能保证分解都具有无损连接性和保持函数依赖性呢？研究的结论是：若要求分解既具有无损连接又具有保持依赖保持性，则分解总可以达到3NF。

对于分解成BCNF模式集合，只存在无损连接性，不保持函数依赖性。本节介绍这三种算法。

【算法3.4】把一个关系模式分解为3NF，使它具有依赖保持性。

输入：关系模式R和R的最小依赖集Fm。

输出：R的一个分解 ρ={R₁，R₂，…，R_k}，R_i（i=1，2，…，k）为3NF，ρ具有无损连接性和依赖保持性。

方法：

1）如果Fm中有一依赖X→A，且XA=R，则输出，转4）。

2）如果R中某些属性与F中所有依赖的左右部都无关，则将它们构成关系模式，从R中将它们分出去。

3）对于Fm中的每一个X_i→A_i，都构成一个关系子模式R=X_iA_i。

4）停止分解，输出ρ。

【例3-32】：设有关系模式R＜U，F＞，U={C，T，H，R，S，G}，F={CS→G，C→T，TH→R，HR→C，HS→R}，将其保持依赖性分解为3NF。

解：

求出F的最小依赖集F_m={CS→G，C→T，TH→R，HR→C，HS→R}，使用【算法3.4】：

1）不满足条件。

2）不满足条件。

3）R₁=CSG，R₂=CT，R₃=THR，R₄=HRC，R₅=HSR。

4）ρ={CSG，CT，THR，HRC，HSR}。

【算法3.5】把一个关系模式分解为3NF，使它既具有无损连接性又具有依赖保持性。

输入：关系模式R和R的最小依赖集Fm。

输出：R的一个分解 ρ={R₁，R₂，…，R_k}，R_i（i=1，2，…，k）为3NF，ρ具有无损连接性和依赖保持性。

方法：

1）根据【算法3.5】求出依赖保持性分解ρ={R₁，R₂，…，R_k}。

2）判断ρ是否具有无损连接性，若是，则转4）。

3）令ρ=ρ∪{X}，其中X是候选码。

4）输出ρ。

【例3-33】设有关系模式R＜U，F＞，U={C，T，H，R，S，G}，F={CS→G，C→T，TH→R，HR→C，HS→R}，将其无损连接和保持依赖性分解为3NF。

解：

1）由上例求出依赖保持性分解：

ρ={CSG，CT，THR，HRC，HSR}。

2）判断其无损连接性，若是，则转4）。

3）不执行。

4）输出ρ={CSG，CT，THR，HRC，HSR}。

【算法3.6】把一个关系模式无损分解为BCNF。

输入：关系模式R和R的依赖集F。

输出：R的无损分解ρ={R₁，R₂，…，R_k}。

方法：

1）令ρ=（R）。

2）如果ρ中所有模式都是BCNF，则转4）。

3）如果ρ中有一个关系模式S不是BCNF，则S中必能找到一个函数依赖X→A，有X不是R的候选键，且A不属于X，设S1=XA，S2=S-A，用分解{S1，S2}代替S，转2）。

4）分解结束，输出ρ。

【例3-34】设有关系模式R＜U，F＞，U={C，T，H，R，S，G}，F={CS→G，C→T，TH→R，HR→C，HS→R}，将其无损连接分解为BCNF。

解：

R上只有一个候选键HS。

1）令ρ={CTHRSG}。

2）ρ中的关系模式不是BCNF。

3）考虑CS→G，这个函数依赖不满足BCNF条件，将CTHRSG分解为CSG和CTHRS。

CSG已是BCNF，CTHRS不是BCNF，进一步分解。选择C→T，把CTHRS分解为CT和CHRS。

CT已是BCNF，CHRS不是BCNF，进一步分解。选择HS→R，把CHRS分解为HRS和CHS。

这时，HRS和CHS均为BCNF。

4）ρ={CSG，CT，HRC，CHS}。

注意：

● 进行模式分解时，除考虑数据等价和依赖等价以外，还要考虑效率。

● 当对DB的操作主要是查询时，为提高查询效率，可保留适当的数据冗余，让关系模式中的属性多些，而不把模式分解得太小，否则为了查询一些数据，常常要做大量的连接运算，把多个关系模式连在一起才能从中找到相关的数据。

● 在设计DB时，为减少冗余，节省空间，把关系模式一再分解，到使用DB时，为查询相关数据，把关系模式一再连接，花费大量时间，会得不偿失。

● 因此，保留适量冗余，达到以空间换时间的目的，也是模式分解的重要原则。

在关系数据库中，对关系模式的基本要求是满足1NF，在此基础上，为了消除关系模式中存在的插入异常、删除异常、更新异常和数据冗余等问题，人们寻求解决这些问题的方法，这就是规范化的目的。

规范化的基本思想是逐步消除数据依赖中不合适的部分，使模式中的各关系模式达到某种程度的“分离”。让一个关系描述一个概念、一个实体或实体间的一种联系，若多于一个概念就把它“分离”出去，因此所谓规范化实质上是概念的单一化。

关系模式的规范化过程是通过对关系模式的分解来实现的，把低一级的关系模式分解为若干高一级的关系模式，对关系模式进一步规范化，使之逐步达到2NF、3NF、4NF和5NF。各种规范化之间的关系为：

5NF⊆4NF⊆BCNF⊆3NF⊆2NF⊆1NF。

关系规范化的递进过程如图3-6所示。

一般来说，规范化程度越高，分解就越细，所得数据库的数据冗余就越小，且更新异常也可相对减少。但是，如果某一关系经过数据大量加载后主要用于检索，那么，即使它是一个低范式的关系，也不要去追求高范式而将其不断进行分解，因为在检索时，会通过多个关系的自然连接才能获得全部信息，从而降低了数据的检索效率。数据库设计满足的范式越高，其数据处理的开销也越大。

因此，规范化的基本原则是：由低到高，逐步规范，权衡利弊，适可而止。通常以满足第三范式为基本要求。

把一个非规范化的数据结构转换成第三范式，一般经过以下几步。

1）把该结构分解成若干属于第一范式的关系。

2）对那些存在组合码，且有非主属性部分函数依赖的关系必须继续分解，使所得关系都属于第二范式。

3）若关系中有非主属性传递依赖于码，则继续分解之，使得关系都属于第三范式。

事实上，规范化理论是在与SQL编程语言结合时产生的。关系理论的基本原则指出，数据库被规范化后，其中的任何数据子集都可以用基本的SQL操作获取，这就是规范化的重要性所在。数据库不进行规范化，就必须通过编写大量复杂代码来查询数据。规范化规则在关系建模和关系对象建模中同等重要。