每个二元关系是如何BCNF的



因此,作为任务的一部分,我必须证明任何具有两个属性的关系都在BCNF中。

根据我的理解,如果一个关系具有第三范式,并且一个非键属性在功能上决定了键属性,那么它就违反了BCNF。

假设我的关系由两个属性A1、A2 组成

场景1(只有一个功能依赖项)

A1 -> A2 (so A1 is the key, and A2 does not FD A1 : so no violation)

也是如此

A2 -> A1

但是如果

A1->A2 and A2->A1

这里的键可以是A1或A2。而另一个非关键属性在功能上决定了关键。

在每个函数依赖项中,X -> YXY是属性集。当XY是空集1时,这需要特别注意。因此,在只有两个属性A1A2的示例中,我们有所有可能的非平凡依赖项:

1. {} -> {A1}
2. {} -> {A2}
3. {} -> {A1 A2}
4. {A1} -> {A2}
5. {A2} -> {A1}

所有其他可能的依赖关系都是平凡依赖关系,即右集是左集的子集(例如{A1} -> {}{} -> {}{A1} -> {A1}{A1 A2} -> {A1}等)。我们知道这些依赖关系总是成立的,所以在正规形式的定义中不考虑它们。

1.当从依赖关系中排除空集时,定理成立

考虑依赖项4和5。我们有四种可能的情况:

1. Only 4 holds, so we have: {A1} -> {A2}

这意味着{A1}是候选密钥(因为从{A1} -> {A2}我们可以导出{A1}->{A1 A2}),并且满足BCNF条件,因为每个依赖项都有一个超级密钥作为行列式;

2. Only 5 holds, so we have: {A2} -> {A1}

与之前的情况相同,仅交换A1A2的角色;

3. Neither 4 nor 5 hold (no functional dependencies),

因此形式上满足BCNF(因为没有依赖关系违反BCNF);最后:

4. both hold, so we have {A1} -> {A2} and {A2} -> {A1}

在这种情况下,关系也在BCNF中,因为{A1}{A2}都是候选密钥,因为它们确定了所有属性(简单地将上面的1和2放在一起)。

2.当我们允许函数依赖中的空集时,该定理不成立

考虑一个关系式R(A1, A2),带有依赖的覆盖F

F = { {}-> {A1} }

通过回顾函数依赖的定义,{} -> {A1}的含义是列A1具有常数值。所以我们有两列的关系,其中一列的值总是相同的。在这种情况下,唯一的候选密钥是{A2},因为{A2}+ = {A1 A2},而{A1 A2}是超级密钥,并且该关系不在BCNF中,因为非平凡函数依赖性({} -> {A1})具有不是超级密钥的行列式。


1注意,在有关该主题的科学文献中(以及在数据库书籍中),函数依赖中空集的可能性有时被明确排除(例如,参见:Tsou,Don Min和Patrick C.Fischer。"将关系方案分解为Boyce Codd范式"。ACM SIGACT新闻14,第3期(1982年7月1日):23-29。https://doi.org/10.1145/990511.990513),而有时它是允许的,或者不讨论。

For any relation to be in BCNF, the following must holds.
X → Y is a trivial functional dependency (Y ⊆ X).
X is a superkey for schema R

此处的维基百科链接

For Example, there is a relation R = {A,B} with two attributes. 
The only possible (non-trivial) FD's are {A}->{B} and {B}->{A}. 
So, there are four possible cases:
1. No FD's holds in R. {C.K = AB}, Since it is an all key relation it's always in BCNF.
2. Only A->B holds. In this case {C.K = A} and relation satisfies BCNF.
3. Only B->A holds. In this case {C.K = B} and relation satisfies BCNF.
4. Both A->B and B->A holds. In this case there are two keys {CK = A and B} and
   relation satisfies BCNF.
Hence, every Binary Relation (A relation with two attributes) is always in BCNF!

要证明具有两个属性的任何关系都在BCNF中。Boyce-Codd范式规则:

如果R处于第三范式,则关系R处于BCNF中,并且对于每个FD,LHS都是超级密钥

所以如果A1和A2是唯一的属性:A1->A2和A2->A1作为函数依赖项,那么在这两个函数依赖项中,左边是一个超级键。满足BCNF的条件。

最新更新