Boyce-Codd Normal Form(BCNF)

Posted by 刘知安 on 2018-11-15
文章目录
  1. Boyce-Codd Normal Form (BCNF)
    1. 1.functional dependency(函数依赖)
    2. 2.Keys of Relations(关系的keys)
    3. 3. Closure of Attributes(属性的闭包)
  • Rules for BCNF
  • Example
  • reference:
  • Boyce-Codd Normal Form (BCNF)

    Boyce-Codd Normal FormThird Normal Form 的一种扩展,因此有时候也被称为3.5范式

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

    1.functional dependency(函数依赖)

    它的定义如下:

    if two tuples of R agree on all of the attributes A1A2A3…An(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 B1B2B3…Bn. So, we write this FD formally as:

    也就是说,假如对任意两个元组在A1A2A3…An属性的取值相同,那么他们俩在B1B2B3…Bn属性的取值也肯定相同,那么我们就称①式子为一个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(分解/合并规则):如果 A1A2A3…An →B1B2B3…Bn,那么A1A2A3…An →B1,A1A2A3…An →B2,… A1A2A3…An →Bn都是对的,这就是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)

    定义如下:

    如果一个属性的集合{A1A2A3…An}是一个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 keysuperkey的概念了。

    • 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:

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    算法:计算属性集合的闭包
    输入:待求属性集合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如下:

    有以下FD:

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    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