证明:通过3NF Synthesis(第三正规式合成)得到的每个子关系皆为第三正规式

通过3NF Synthesis算法,我们可以获得多个子关系,而每个子关系皆为第三正规式,以下证明了为什么每个子关系皆为第三正规式。

首先,根据第三正规式合成之算法,先得获得Minimal Cover(最小覆盖),然后每个子关系,都是由最小覆盖中的每一个关系X->Y中的X Union Y构成。如果发现有子关系比过去或未来的任一子关系小,则将其抹去。

最难理解的情况是,比如说我们根据X->Y获得了XY,根据M->N获得了MN,我们发现MN是XY之子集。所以这个子关系便是:

XY, {X->Y, M->N}

所以XY > MN,所以M必然不是XY的superkey。而X必然是一个candidate key,这是根据最小覆盖的定义得到的。

如果N是X的一部分,那么万事大吉。但如果N不是X的一部分呢?

我的结论是,这种情况不可能会发生。

因为,如果N不是X的一部分,那么N必须是Y的一部分,否则N不属于XY。所以我们可以把这个子关系改写成:

XNK,{X->NK, M->N},其中NK=Y

假设X<M,那么M->N不可能还存在,会在生成最小覆盖的时候被去掉。否则{X->NK, M->N} = {X-> N, X->K, M-> N}中M->N含有多余的attribute 。

假设M<=X,那么X->NK不可能还存在,会在生成最小覆盖的时候被去掉。否则 {X->NK, M->N} = {X-> N, X->K, M-> N}中X->N含有多余的attribute。

发表评论

电子邮件地址不会被公开。 必填项已用*标注