备战软考数据库:8.7 范式

范式可用来衡量关系模式的好坏。

不同范式之间的关系:5NFsubseteq 4NFsubseteq BCNF subseteq{3NF}subseteq 2NF subseteq 1NF

第一范式 1NF

  • 如果关系模式R的每个关系r的属性值都是不可分的原子值,则称R1NF

第二范式 2NF

  • 对于函数依赖Wrightarrow A,如果存在Xsubset WXrightarrow A成立,则称Wrightarrow A是局部依赖(A局部依赖于W);否则则称为完全依赖。
  • 如果A是关系模式R候选键中的属性,则称AR的主属性,否则称为非主属性。
  • 对于一个1NF的关系模式R,若每个非主属性都完全依赖于候选键,则称R2NF
  • 第二范式关系模式R中不存在对关键码局部依赖的非主属性

例:R(text{S#,C#,SCORE,T#,TITLE})中属性分别为:学生学号,选修课程的编号,成绩,任课教师工号,教师职称。

  • R上有两个函数依赖(text{S#,C#})rightarrow(text{T#,TITLE})text{C#}rightarrow(text{T#,TITLE}),前者为局部依赖,因此R不是2NF
  • 分解R为:
    R_1(text{C#,T#,TITLE})
    R_2(text{S#,C#,SCORE})
    则消除了局部依赖,并且R_1R_2都是2NF

分解成2NF的方法:

  • 设关系模式R(U)主键W,R上函数依赖为Xrightarrow Z,Zsubset W并且Z是非主属性,即Wrightarrow Z是一个局部依赖,应将R分解为如下两个模式:
  1. R_1(XZ)主键为X
  2. R_2(Y)其中Y=U-Z,主键为W,外键为X
  • R_1,R_2仍然不是2NF则继续上述过程

第三范式 3NF

  • Xrightarrow Y,Yrightarrow A,且Ynrightarrow X,Anotin Y则称Xrightarrow A是传递依赖(A传递依赖于X
  • 若关系模式R1NF,且每个非主属性都不传递依赖于R的候选键,则称R3NF
  • 不满足3NF的关系模式中必然存在非主属性对关键码的传递依赖
  • 如果R3NFR一定是2NF
  • 另一种等价定义:
    F是关系模式R的函数依赖集,若F中每个非平凡的函数依赖Xrightarrow Y,都有:XR的超键或Y的每个属性都是主属性,则称R3NF

示例,上面2NF例子中的两个关系:

  • R_1(text{C#,T#,TITLE})不一定是3NF,因为如果text{C#}rightarrow T,Trightarrow text{TITLE},则text{C#}rightarrowtext{TITLE}是一个传递依赖。
  • R_2(text{S#,C#,SCORE})3NF
  • 若将上述模式分解为:
  1. R_2(text{S#,C#,SCORE})
  2. R_{11}(text{T#,TITLE})
  3. R_{12}(text{C#,T#})
  • 则三个关系模式都是3NF

分解成3NF的方法:

  • 设关系模式R(U),主键为W,R上存在函数依赖Xrightarrow Z,且Z是非主属性,Znsubseteq XX不是候选键,,Wrightarrow Z就是一个传递依赖,此时应该分解R为:
  1. R_1(XZ),主键为X
  2. R_2(Y),其中Y=U-Z,主键W外键是X
  • R_1,R_2仍然不是3NF则继续上述过程

分解成3NF模式集的合成算法(Bernstein)(无损且保持函数依赖):

  1. 对于关系模式RR上的函数依赖集F,求出F的最小依赖集,将最小依赖集中左边相同的函数依赖用合并性合并起来。
  2. 最小依赖集中,每个函数依赖Xrightarrow Y构成一个模式XY
  3. 在构成的模式集中,若每个模式都不包含R的候选键,则将候选键作为一个模式放入到模式集中

BC范式 BCNF

  • 如果关系模式R1NF,并且每个属性都不传递依赖于R的候选键,则称RBCNF
  • 另一种定义:
    F是关系模式R的函数依赖集,若对于F中任意非平凡的函数依赖Xrightarrow Y都有XR的超键,则称RBCNF
  • 若非平凡的函数依赖Xrightarrow Y不包含超键,则Y必须传递依赖于候选键,因此R将不是BCNF

示例,关系模式:R(text{B#,BNAME,AUTHOR})属性分别代表书号,书名,作者名。

  • 若规定每个书号对应一个书名,不同的书号可以有相同的书名,每本书可以有多个作者,但是每个作者参与编写的书名不能相同。
  • 上述规定对应的函数依赖为:
    text{B#}rightarrow text{BNAME}
    (AUTHOR,BNMAE)rightarrow text{B#}
  • 则关系R中所有属性都是主属性,即R3NF,但是BNAME传递依赖于(AUTHOR,BNAME)应此不是BCNF
  • 应该将上述关系分解为:
    R_1(text{B#,BNAME})
    R_2(AUTHOR,BNAME)
    R_1,R_2均为BCNF

分解为BCNF模式集的分解方法:

无损分解法,能保证把R无损分解成rho,但不保证能保持函数依赖

  • 对于关系模式R的分解rho( 初始时rho=R),若rho中存在关系模式R_i相对于pi_{R_i}(F)不是BCNF,则应该将R_i分解为XYR_i-Y两个模式,重复上述过程直至每一个模式都是BCNF

多值依赖(Multi Valued Dependency):

  • U是关系模式R的属性集,X,YU的子集,Z=R-X-Y,小写的xyz表示属性集XYZ的值。对于R的任意关系r,在r中存在元组(x,y_1,z_1)(x,y_2,z_2)也就存在元组(x,y_2,z_1)x,y_1,z_2,那么称多值依赖Xrightarrow rightarrow Y在关系R上成立

推理规则:

  1. 自反性(reflexivity):
    Ysubseteq X subseteq U,则Xrightarrow YR上成立
  2. 增广性(augmentation):
    Xrightarrow YR上成立,且Zsubseteq U,则XZrightarrow YZR上成立
  3. 传递性(transitivity):
    Xrightarrow YYrightarrow ZR上成立,则Xrightarrow ZR上也成立
  4. 补规则(Complementation):
    Xrightarrow rightarrow YXrightarrow rightarrow (U-XY)
  5. 增广性:
    Xrightarrow rightarrow YVsubseteq W subseteq UWXrightarrow VY
  6.  传递性:
    Xrightarrow rightarrow Y,Yrightarrow rightarrow ZXrightarrow rightarrow (Z-Y)
  7. 复制性(Replication):
    Xrightarrow Y,则Xrightarrow rightarrow Y
  8. 结合性(Coalescence Rule):
    Xrightarrow rightarrow Y,W rightarrow Z并且Zsubseteq Y,Wcap Y=emptyset则:Xrightarrow Z
  9. 并规则:
    Xrightarrow rightarrow Y,Xrightarrow rightarrow ZXrightarrow rightarrow YZ
  10. 交规则:
    Xrightarrow rightarrow Y,Xrightarrow rightarrow ZXrightarrow rightarrow Ycap Z
  11. 差规则:
    Xrightarrow rightarrow Y,Xrightarrow rightarrow ZXrightarrow rightarrow Y-Z,Xrightarrow rightarrow Z-Y
  12. 伪传递:
    Xrightarrow rightarrow Y,WYrightarrow rightarrow ZWXrightarrow rightarrow Z-WY
  13. 混合传递:
    Xrightarrow rightarrow Y,XYrightarrow rightarrow ZXrightarrow rightarrow Z-Y

第四范式4NF

  • D是关系模式R上成立的函数依赖和多值依赖集合,若D中每个非平凡的多值依赖Xrightarrow rightarrow Y都是R的超键,则称R4NF

无损分解成4NF的方法:

  • 对于关系模式R的分解rho初始时R=rho,如果rho中有一个关系R_i不是4NF,则应将其分解成XYR_i-Y两个模式,如此循环。

联接依赖(Join Dependency):

  • U是关系模式R的属性集,R_1,dots,R_nU的子集,并且满足U=R_1cup R_2cup dots cup R_n,rho=left{R_1,R_2,dots,R_nright}R的一个分解。
    如果对于R的每一个关系r都有m_{rho}(r)=r那么称联接依赖在关系模式R上成立,记为*(R_1,dots,R_n)

第五范式5NF

  • 如果关系模式R中每个联接依赖均由R的候选键蕴涵,则称R5NF

 

Leave a Reply

Your email address will not be published. Required fields are marked *