分解算法

在前一节中，我们通过小例子讨论了分解及其类型。在实际世界中，数据库模式过于庞大，难以处理。因此，它需要能够生成适当数据库的算法。

在这里，我们将通过函数依赖来了解两种不同范式的分解算法，它们是

• 分解到 BCNF
• 分解到 3NF

使用函数依赖的分解旨在保持依赖性和无损分解。

让我们详细讨论一下。

分解到 BCNF

在将 BCNF 分解算法应用于给定关系之前，有必要测试该关系是否处于 Boyce-Codd 范式。测试后，如果发现给定关系不在 BCNF 中，我们可以进一步分解它以创建 BCNF 中的关系。

如果给定的关系模式 R 满足 BCNF 规则，则需要测试以下情况。

情况 1：检查并测试，如果非平凡依赖 α -> β 违反 BCNF 规则，则计算 α⁺，即 α 的属性闭包。同时，验证 α⁺ 是否包含给定关系 R 的所有属性。这意味着它应该是关系 R 的超键。

情况 2：如果给定的关系 R 处于 BCNF 中，则无需测试 F⁺ 中的所有依赖项。它仅需要确定并检查 BCNF 测试所提供的依赖集 F 中的依赖项。这是因为如果 F 中的任何依赖项未违反 BCNF，那么 F⁺ 中的任何依赖项也不会违反 BCNF。

注意：当关系被分解时，情况 2 不起作用。这意味着在测试给定关系 R 时，我们无法检查 F 的依赖性是否会导致 BCNF 违反。

BCNF 分解算法

如果给定的关系 R 由于不在 BCNF 中而被分解为多个关系 R₁、R₂、…、R_n，则使用此算法。因此，

对于关系 R_i 中的每个属性子集 α，我们需要检查 α⁺（α 在 F 下的属性闭包）要么包含关系 R_i 的所有属性，要么不包含 R_i-α 的任何属性。

result={R};
done=false;
compute F+;
while (not done) do
	if (there is a schema Ri in result that is not in BCNF)
		then begin
			let α->β be a nontrivial functional dependency that holds 
			on Ri such that α->Ri is not in F+, and α ꓵ β= ø;
			result=(result-Ri) U (Ri-β) U (α,β);
		end
		else done=true;

注意：如果 Ri 中的某些属性集 α 违反算法中指定的条件，在这种情况下，请考虑函数依赖 α->( α⁺ - α) ꓵ R_i。此类依赖项可能存在于 F⁺ 依赖项中。

此算法用于将给定的关系 R 分解为多个分解器。此算法使用显示 BCNF 违反的依赖项来执行关系 R 的分解。因此，此类算法不仅生成 BCNF 中的关系 R 的分解器，而且还是无损分解。这意味着在将给定的关系 R 分解为 R₁、R₂ 等时不会发生数据丢失……

BCNF 分解算法的运行时间与初始关系模式 R 的大小呈指数关系。因此，此算法的一个缺点是它可能会不必要地分解给定的关系 R，即过度规范化关系。尽管 BCNF 和 4NF 的分解算法相似，但有一个区别。第四范式处理多值依赖，而 BCNF 处理函数依赖。多值依赖有助于减少一些数据重复，而函数依赖无法理解这一点。

多值依赖与函数依赖的区别

两者之间的区别在于，函数依赖会排除某些元组不出现在关系中，而多值依赖则不会。这意味着多值依赖不会排除或废除某些元组。相反，它要求特定形式的其他元组存在于关系中。由于这种差异，多值依赖也称为元组生成依赖，函数依赖称为等值生成依赖。

分解到 3NF

3NF 的分解算法通过显式为规范覆盖中的每个依赖项构建模式来确保依赖项的保留。它保证至少有一个模式必须持有一个被分解项的候选键，这反过来又确保生成的分解是无损分解。

3NF 分解算法

let Fc be a canonical cover for F; 
i=0;
for each functional dependency α->β in Fc
	i = i+1;
R = αβ;
If none of the schemas Rj, j=1,2,…I holds a candidate key for R 
Then
	i = i+1;
	Ri= any candidate key for R;
/* Optionally, remove the repetitive relations*/
Repeat
	If any schema Rj is contained in another schema Rk
 Then
/* Delete Rj */
Rj = Ri;
i = i-1;
until no more Rjs can be deleted
return (R1, R2, . . .  ,Ri)

这里，R 是给定的关系，F 是给定的函数依赖集，其中 F_c 维护规范覆盖。R₁、R₂、...、R_i 是给定关系 R 的分解部分。因此，此算法既保留了依赖项，又生成了关系 R 的无损分解。

3NF 算法也称为3NF 合成算法。之所以这样称呼，是因为范式处理依赖集，并且它不是通过反复分解初始模式，而是一次添加一个模式。

3NF 分解算法的缺点

• 分解算法的结果不是唯一的，因为一组函数依赖可以有多个规范覆盖。
• 在某些情况下，算法的结果取决于它考虑 F_c 中依赖项的顺序。
• 即使给定的关系已经处于第三范式，它也可能分解关系。