Boyce-Codd Normal Form (BCNF)

Boyce-Codd Normal Form是Third Normal Form 的一种扩展，因此有时候也被称为3.5范式。

在讲BCNF之前，我们需要知道许多其他的一些概念，下面一一叙述，别怕，很简单的。

1.functional dependency（函数依赖）

它的定义如下：

if two tuples of R agree on all of the attributes A₁A₂A₃…A_n(i.e., the tuples have the same values in their respective componets for each of these attributes), then they must also agree on all of another list of attributes B₁B₂B₃…B_n. So, we write this FD formally as:

$A_1A_2A_3...A_n \rightarrow B_1B_2B_3...B_n-------------- ①$

也就是说，假如对任意两个元组在A₁A₂A₃…A_n属性的取值相同，那么他们俩在B₁B₂B₃…B_n属性的取值也肯定相同，那么我们就称①式子为一个FD。

举个很简答的例子，为了减少数据的冗余，我们希望在一个叫StuInfo的表中，只有学生的id和name字段，那么对任何两个记录，只要id是相同的，那么姓名也必定相同，那么这个id→name就是一个FD（函数依赖).

FD的性质：

假设X，Y，Z都是relation R上的一些属性。

Reflexivity（自反性）: 如果 Y 是X的子集, 那么 X → Y. 例如：X= {ID, NAME} and Y={ID}，显然， X → Y是正确的。
Augmentation（这个我真不知道怎么翻译）: If X → Y, then XZ → YZ. 也就是说在FD的左右两边同时加上相同的属性，新的FD也是成立的。
Transitivity（传递性）: If X → Y and Y → Z, then X → Z.
Splitting/Combining Rule（分解/合并规则）：如果 A₁A₂A₃…A_n →B₁B₂B₃…B_n，那么A₁A₂A₃…A_n →B₁，A₁A₂A₃…A_n →B₂，… A₁A₂A₃…A_n →B_n都是对的，这就是split啦，反过来就是combine了。
Attribute Closure(属性的闭包): 所有由A决定的属性的集合叫做A的闭包，记为A⁺.

另：如果 Y 是X的子集, 那么 X → Y我们称为trivial FD（平凡FD）；反正，如果Y不是X的子集，那么我们称之为non-trivial FD（非平凡FD）

2.Keys of Relations（关系的keys）

定义如下：

如果一个属性的集合{A₁A₂A₃…A_n}是一个relation的key，那么这些属性也决定了整个relation上的所以attributes的取值。

这样可能显得有点抽象，继续采用上面StuInfo的例子，如果只有学生的id和name字段，且存在id→name的FD，那么显然id这个属性（也可以说是只有一个元素的集合）就决定了StuInfo这个relation的所以属性的取值；如果还有一个hobby的字段，那么{id}就不是这个relation的key了，对，{id，hobby}就可以是key了。既然{id，hobby}是key，那{id，name，hobby}也肯定是一个字段了，于是又引申出minimal key和superkey的概念了。

minimal key
当一个key的属性不能再减少时，它就是一个minimal key了。
superkey
包含minimal key的任何属性集合都叫做superkey。

是的，我们上面的例子中，{id，hobby}，{id，name，hobby}都是key，并且{id，name}是minimal key，{id，name，hobby}是superkey。

3. Closure of Attributes（属性的闭包）

在讲到FD的性质的时候，我们提到了属性的闭包这个概念，下面我换个方法，先举例子，再写定义。
继续StuInfo这个relation，现在有id，name，birthday，university，u_city，u_country这些属性，还有以下FDs：

$id \rightarrow name,birthday， university \rightarrow u\_city， u\_city \rightarrow u\_country$

ok，那么id的闭包就是{id，name}了，university的闭包就是{u_city，u_country}了，看一眼你大概知道是怎么操作得来的吧？

算法：计算属性集合的闭包
输入：待求属性集合A={A1A2A3...An}，所有给定的FD集合S
输出：A的闭包

1. 如果必要，对S中的每个FD，将它的右边全部根据split规则分解成右边只有一个属性的FD。
2. 初始化X=A，X最终会是我们要求的闭包
3. 重复以下过程：
			对所有B1B2B3...Bn→C的FD，
			其中B1B2B3...Bn都在X中，但是C不在X中，直到再也找不到这样的C。
		
		由于属性个数是有限的，所有以上步骤肯定是可以在有限步骤内完成的。
4. 返回X，它就是A的闭包。

呼。。。终于可以讲BCNF了，其实它就两句话：

Rules for BCNF

一个relation满足BCNF，它必须满足以下条件：

它必须满足 Third Normal Form.
对任意non-trivial(非平凡的)FD A → B, A 必须是个superkey。

Example

假设一个schema如下：

$\{title,year,studioName,president,presAddr\}$

有以下FD：

$title , year \rightarrow studioName ② \\ studioNamer \rightarrow president ③ \\ president \rightarrow presAddr ④ \\$

从以上我们可以得知，只有{title，year}是这个relation的key，可以简单推导验证。那么②是满足BCNF的（它的左边就是一个key)，可是③④就都违反了BCNF的第二个条件了，所以上面这个relation就说明设计存在问题，会导致数据冗余。怎么办？别急，有一个叫做BCNF Decomposition的算法，它可以帮助我们将不满足规则的relation分解成两个或多个relations，使得它们各自满足BCNF。

BCNF Decomposition algorithm
输入：给定原始relation R0，所有给定的FD原始集合S0.
输出：两个或多个relations，使得它们各自满足BCNF

1. 检查R0是否满足BCNF条件，如果满足，直接返回R0。

2. 找到任意一条违反BCNF的FD，X→Y，使用属性集合的闭包算法，计算X的闭包X+。
令R1=X+，R2包含两部分，一部分是X，另一部分是在R中但不在X+中的属性。

3. 根据R1和R2对原始FD集合S0运用projection算法进行“分割”，对应记作S1和S2。

4. 递归地对R1和R2调用本算法，直到所有relations都满足BCNF。

关于步骤3中说的的projection算法，我就不再叙述了，给个==> 链接 <==，很简单的。

以上就是关于BCNF的主要内容了，当然BCNF也有一个shortcoming，以后会陆续更新，如果理解不当，还请留言指出！

reference：

【1】 A First Course in Database System , UJeffrey D.llman, Jennifer Widom,Stanford University

Andy
2018-9-25 23:02

Boyce-Codd Normal Form（BCNF）