Functional-Dependency Theory

SQL for judging FDs

Closure of a Set of Functional Dependencies

The set of all functional dependencies logically implied by F is the closure of F, which is denoted as F+. It is the set of all functional dependencies that can be inferred from F using Armstrong’s axioms.

Armstrong’s Axioms

Armstrong’s axioms are a set of rules used to infer all the functional dependencies in a relational database. They are sound (i.e., they only produce valid dependencies) and complete (i.e., they can produce all valid dependencies).

1. Reflexivity: If Y is a subset of X, then X → Y holds.
2. Augmentation: If X → Y holds, then XZ → YZ holds for any Z.
3. Transitivity: If X → Y and Y → Z hold, then X → Z holds.

Additional Rules

1. Union: If X → Y and X → Z hold, then X → YZ holds.
2. Decomposition: If X → YZ holds, then X → Y and X → Z hold.
3. Pseudotransitivity: If X → Y and YZ → W hold, then XZ → W holds. （可由先argumentation和transitivity推导出）

属性集闭包

属性集X在函数依赖集F下的闭包，记为X+，是指在F中可以由X推导出的所有属性的集合。 计算X+的算法：

1. 初始化X+为X。
2. 重复以下步骤，直到X+不再变化：
   • 对于F中的每个函数依赖A → B，如果A是X+的子集，则将B添加到X+中。

例子

设有关系R(A, B, C, D)和函数依赖集F = {A → B, B → C}，计算属性集A的闭包A+：

1. 初始化A+ = {A}。
2. 应用A → B，因为A是A+的子集，添加B到A+，得到A+ = {A, B}。
3. 应用B → C，因为B是A+的子集，添加C到 A+，得到A+ = {A, B, C}。
4. 没有更多的函数依赖可以应用，算法终止。 最终，A+ = {A, B, C}。

Canonical Cover【最简函数依赖集】

函数依赖集F的规范覆盖（Canonical Cover），记为Fc，是一个等价于F的最小函数依赖集。 A canonical cover for F is a set of dependencies Fc such that:

1. F logically implies all dependencies in Fc
2. Fc logically implies all dependencies in F

(F+ = Fc+)

3. no functional dependency in Fc contains an extraneous attribute
4. each left side of functional dependency in Fc is unique. That is, there are no two dependencies in Fc, with the same left side i.e. X → Y and X → Z cannot both be in Fc

计算规范覆盖的步骤

1
2
3
4

do{
    1、使用Union rule结合右侧
    2、去除Fc中的冗余属性
}while(Fc不变)

例子

F、F+、Fc

Extraneous Attributes（冗余属性）

在函数依赖X → Y中，如果存在属性A ∈ X，使得在去掉A后，X - {A} → Y仍然成立，则称A是冗余属性。

例子

设有函数依赖集F = {AB → C, A → B}，检查属性A在AB → C中是否冗余：

1. 计算B的闭包B+：
   • 初始化B+ = {B}。
   • 没有函数依赖可以应用，B+ = {B}。
2. 检查是否B+包含C：
   • B+不包含C，因此A不是冗余属性。 最终，属性A在AB → C中不是冗余属性。

对于右端冗余属性的检查： 在函数依赖X → Y中，如果存在属性B ∈ Y，使得在去掉B后，X → Y - {B}仍然成立，则称B是冗余属性。

移除左端冗余属性，得到更强的函数依赖【所需左端前提条件更少】

移除右端冗余属性，得到更弱的函数依赖【结论更少】

一个依赖关系under F的意思是可以从F中推导出该依赖关系

Dependency Preservation（依赖保持）

在关系模式分解中，如果分解后的每个子模式的函数依赖集的联合能够推导出原始模式的所有函数依赖，则称该分解是依赖保持的。

与holds on的区别在于， holds on是指某个具体的关系实例满足某个函数依赖， 而dependency preservation是指分解后的模式在所有可能的关系实例中都能保持原始模式的函数依赖。

Fi：

7.5 Algorithms for Decomposition Using Functional Dependencies

本节内容 BCNF

• Testing for BCNF /判断关系模式是否是BCNF
• Testing Decomposition for BCNF/ 判断分解后的子模式是否是BCNF
• BCNF decomposition algorithm/将关系模式分解为BCNF的方法

3NF

• Testing for 3NF
• 3NF decomposition algorithm
• Comparison of BCNF and 3NF

Testing for BCNF

To check if a non-trivial dependency $\alpha$ causes a violation of BCNF

1. compute $\alpha^+$ (the attribute closure of $\alpha$), and
2. verify that it includes all attributes of R, that is, $\alpha$ is a superkey of R.

Simplified but Incorrect test: To check if a relation schema R is in BCNF, it suffices to check only the dependencies in the given set F for violation of BCNF, rather than checking all dependencies in F+.

If none of the dependencies in F causes a violation of BCNF, then none of the dependencies in F+ will cause a violation of BCNF either.

However, simplified test using only F is incorrect when testing a relation in a decomposition of R

也就是说判断BCNF可以使用F作为充分条件，因为F无违例说明F+也无违例，但是判断子模式（a decomposition of R）只用F是错的！！！

Testing Decomposition for BCNF

Note:

• the restriction of F to Ri 的意思是： 将函数依赖集F中的所有函数依赖限制在子模式Ri上，即只保留那些在Ri中有效的函数依赖。 举例子： 设有关系模式R(A, B, C)和函数依赖集F = {A → B, B → C}，将R分解为子模式R1(A, B)和R2(B, C)。 the restriction of F to R1是{A → B}，因为B → C在R1中无效。

测试由R分解后的子模式Ri是否BCNF，不能仅凭R上的F，应该采用F+

Decomposition Algorithm for BCNF

1. 检查关系模式R是否是BCNF。如果是，则返回R作为分解结果。（to determine whether or not Ri is in BCNF, the restriction of F to Ri and the candidate keys of Ri need to be computed）

2. 如果R不是BCNF，找到一个违反BCNF的函数依赖X → Y，其中X不是R的超键。

3. 将R分解为两个子模式R1和R2：

   • R1 = X ∪ Y
   • R2 = R - Y + X

4. 递归地对R1和R2应用步骤1-3，直到所有子模式都是BCNF。

Note:

• 3中R1的意思是包含X和Y的所有属性的子模式，R2的意思是R中去掉Y属性后再加上X属性的子模式
• 该算法可能不会产生依赖保持的分解。
• 该算法确保每个子模式都是BCNF。

BCNF分解不保证依赖保持

Testing for 3NF

Need to check only FDs in F, no checking all FDs in F+.

Step1. Use attribute closure to check for each dependency $\alpha$, if $\alpha$ is a superkey

检查每个函数依赖左端是否为超键

Step2. If $\alpha$ is not a superkey, we have to verify if each attribute in $\beta$ is contained in a candidate key of R

如果左端不是超键，检查右端属性是否包含在某个候选键中

This test is rather more expensive, since it involve finding all candidate keys

Testing for 3NF has been shown to be NP-hard!

Interestingly, decomposition into third normal form (described shortly) can be done in polynomial time

Decomposition Algorithm for 3NF

为什么需要3NF分解算法？ 因为BCNF分解不保证依赖保持，而3NF分解算法可以保证依赖保持。

算法步骤：

1. 计算函数依赖集F的规范覆盖Fc。
2. 对于Fc中的每个函数依赖X → Y，创建一个子模式R_i = X ∪ Y。
3. 如果没有子模式包含R的候选键，则添加一个子模式R_k，该子模式包含R的一个候选键。
4. 返回所有子模式作为分解结果。

Note:

• 只要有一个候选键包含在第2步构造出的某个子模式Ri中，就无需在第3步中，为候选键单独构造子模式。 任意挑选R的一个候选键【只需挑选一个】，对该候选健单独构造一个关系模式；无需考虑全部候选键!!!

Example of 3NF Decomposition 设有关系模式R(A, B, C, D)和函数依赖集F = {A → B, B → C}，应用3NF分解算法：

1. 计算规范覆盖Fc = {A → B, B → C}。
2. 创建子模式：
   • R1 = {A, B}（对应A → B）
   • R2 = {B, C}（对应B → C） （R1、R2都是BCNF）
3. R的候选键是{A, D}，没有子模式包含它，因此添加R3 = {A, D}。
4. 返回子模式R1, R2, R3作为分解结果。

对比记忆BCNF和3NF算法

3NF合成：依赖于一个预先处理好的、最小化的规范覆盖Fc来“合成”模式。Fc是它的输入。

BCNF分解：是一个递归的、基于验证的分解过程，它直接使用当前模式上成立的函数依赖（来自原始F或其投影）来指导分解。它不关心F是否最小化。

因此，计算BCNF分解一般不需要计算Fc。

Appendix 7-1 Computing Candidate Keys

计算候选键的步骤：

step1. 将R的所有属性分为四类：

• L类：仅出现在F中函数依赖左部的属性
• R类：仅出现在F中函数依赖右部的属性
• N类：在F中函数依赖左右两边均未出现的属性
• LR类：在F中函数依赖左右两边均出现的属性 令X_set=L类 ∪ N类，Y_set=LR类

step2. 求X_set +，

• 如果X_set+ =R，则X_set为R的唯一候选键，转step5；否则转step3

step3.

• 在Y_set中取一属性A，求(X_set ∪ A)+，若它包含了R的所有属性，则转step4; 否则，调换一属性反复进行这一过程，直到试完所有Y_set中的属性

step4.

• 如果已找出所有的候选键，则转step5; 否则，在Y_set中依此取两个、三个，…，求其属性闭包，直至其闭包包含R的所有的属性

step5. 停止，输出结果

最后，为什么需要4NF

在某些情况下，关系模式可能存在多值依赖（MVD），这会导致数据冗余和更新异常。4NF通过消除非平凡的多值依赖，进一步规范化关系模式，从而提高数据的完整性和一致性。

考题类型

判断最高范式 计算候选键，从BCNF向下找