关系数据库设计理论(5) 关系模式的规范化

时间:2022-01-12 11:34:30

   关系数据库设计理论(5)   关系模式的规范化一、范式

 

        关系模式满足的确定约束条件称为范式,根据满足约束条件的级别不同,
    范式由低到高分为1NF,2NF,3NF,BCNF,4NF,5NF等。

        不同的级别范式性质不同

       关系模式的规范化:把一个低一级的关系模式分解为高一级关系模式的过程。

关系数据库设计理论(5)   关系模式的规范化

 


  关系数据库设计理论(5)   关系模式的规范化二、概念


    1、第一范式(1NF)

           关系模式的所有域为简单域,其元素(即属性)不可再分,
       是属性项而不是属性组。

      
4.5.1:

关系数据库设计理论(5)   关系模式的规范化

       4.5.2:工资(工号,姓名,工资(基本工资,年绩津贴,煤电补贴))

      △ 不满足1NF的关系称为非规范化关系。
      △ 关系数据模型不能存储上两个例子(非规范化关系),
         在关系数据库中不允许非规范化关系的存在。
      △ 转化方法:
       (1) A1,A2,A3,…,Ak1,Ak2,…,An
       (2) 工资(工号,姓名,基本工资,津贴,奖金)

    2、第二范式2NF):

           给定关系模式R及其上的函数依赖集F,
       如果R的任何一个非主属性都完全依赖于它的每一个侯选关键字,
       则称R是第二范式,简记为2NF。

       △ 若关系模型H包含的每一关系模式都是2NF的,则称该关系模型是2NF的。
       △ 2NF∈1NF

      
例4.5.3:
           SCT(SNO,CNO,CN,GRADE,TNAME,BDATE,SALARY)
           F={SNO,CNO→GRADE
           CNO→CN,CNO→TNAME
           TNAME→BDATE,TNAME→SALARY} 非2NF

       存在问题:1.数据冗余;2.插入,删除异常 3.修改麻烦。 

       原因:非主属性部分依赖于侯选关键字,
             关键字是一个元组区别其它元组的依赖,
             同时也是一个元组赖以存在的依据。

       分解为:SC (SNO,CNO,GRADE),CT(CNO,CN,TNAME,BDATE,SALARY)

      
4.5.4:
           R=(ABCD,{AB→C,C→D})

       答案:R为2NF


     3、第三范式3NF

          给定关系模式R及其上的函数依赖集F,
      如果R的任何一个非主属性都不传递依赖于它的任何一个侯选关键字,
      则称R是第三范式,简记为3NF。

      △ 若关系模型H包含的每一关系模式都是3NF的,则称该关系模型是3NF的。
      △ 定理:一个3NF的关系(模式)必定是2NF的(3NF∈2NF∈1NF) 。 

      证明:如果一个关系(模式)不是2NF的,那么必有非主属性Aj
        候选关键字X和X的真子集Y存在,使得Y→Aj。由于Aj是非主属性,
        故Aj-(XY)≠Φ,Y是X的真子集,所以Y关系数据库设计理论(5)   关系模式的规范化X,
        这样在该关系模式上就存在非主属性Aj传递依赖候选关键字X(X→Y→Aj),
        所以它不是3NF的,证毕。

     
4.5.4:CT(CNO,TNAME,BDATE,SALARY)

        解:不能存放不开课的教师
教师信息和课程数一样多。

      原因:传递函数依赖
           R={City,St,Zip}
           F={(City,St)→Zip,Zip→City} 3NF
           CT(CNO,TNAME, BDATE, SALARY)非3NF

      分解为:C(CNO,CNAME,TNAME), T(TNAME,BDATE,SALARY) 3NF

     4、BCNF改进的3NF

            给定关系模式R及其上的函数依赖集F,如果R的任意两个子集X、Y,
        当非平凡函数依赖X→Y为F所蕴涵,则决定因素X中
        必含有侯选关键字或X为超关键字,则称R是Boyde/Codd范式,
        简记为BCNF。

        BCNF的内涵:
         (1)非主属性对关键字完全函数依赖
         (2)主属性对不含它的关键字完全函数依赖
         (3)没有属性完全函数依赖于一组非主属性
         (4)主属性不传递依赖于任何一个侯选关键字
         (5)非主属性不传递依赖于任何一个侯选关键字

      △ 定理: BCNF满足3NF (BCNF∈3NF∈2NF∈1NF)

        反证法:
            R∈BCNF,但R∈BCNF
        设存在非主属性A,关键字X以及属性组Y,使得X→Y,Y→X,Y→A,
        由BCNF有Y→A,则Y为关键字,于是有Y→X,这与Y关系数据库设计理论(5)   关系模式的规范化X矛盾。

     
4.5.6:
             R={S,T,J}
             F={T→J,ST→J,SJ→T}非BCNF
             C(CNO,CNAME,TNAME),T(TNAME,BDATE,SALARY)  BCNF

      分解为:ST(S,T), TJ(T,J)

     5、总结:
         3NF→BCNF:消除主属性对侯选关键字的部分和传递函数依赖
         2NF→3NF :消除非主属性对侯选关键字的传递函数依赖
         1NF→2NF :消除非主属性对侯选关键字的部分函数依赖

     6、规范化的基本思想
            逐步消除不合适的函数依赖,使数据库中的各个关系模式
        达到某种程度的分离。


关系数据库设计理论(5)   关系模式的规范化

 


  关系数据库设计理论(5)   关系模式的规范化三、分解算法


     1、分解的基本要求

           分解后的关系模式与分解前的关系模式等价,
       即分解必须具有无损联接和函数依赖保持性。

     2、目前分解算法的研究结论

      (1) 若要求分解具有无损联接性,那么分解一定可以达到BCNF。
      (2) 若要求分解保持函数依赖,那么分解可以达到3NF,
          但不一定能达到BCNF。
      (3) 若要求分解既保持函数依赖,又具有无损联接性,
          那么分解可以达到3NF,但不一定能达到BCNF。

     3、面向BCNF且具有无损联接性的分解(算法1)

      输入:关系模式R及其函数依赖集F。
      输出:R的一个无损联接分解,其中每一个子关系模式都满足
              F在其上投影的BCNF。

      算法实现:
             反复运用逐步分解定理,逐步分解关系模式R,
         使得每次分解都具有无损联接性,而且
         每次分解出来的子关系模式至少有一个是BCNF的,
           即:
          1)置初值ρ={R};
          2)检查ρ中的关系模式,如果均属BCNF,则转4);
          3)在ρ中找出不属于BCNF的关系模式S,那么必有X→A∈F+
             (A不包含于X),且X不是S的关键字。因此XA必不包含
             S的全部属性。把S分解为{S1,S2},其中S1=XA,S2=(S-A)X,
             并以{S1,S2}代替ρ中的S,返回2)
          4)终止分解,输出ρ。

      定理:算法1正确

      证明:在上述算法的第3)步,

       ⑴由于S1∩S2=X,S1-S2=A,而且满足X→A∈F,
         S分解为{S1,S2}具有无损联接性。
       ⑵由于R中的属性有限,S1和S2所包含的属性个数都有比S少,
         所以经过有限次迭代,算法一定终止,ρ的每一个关系模式都满足BCNF,
         由于每步分解都具有无损联接性,最后分解当然是无损联接的。

     
4.5.7:
          R=(ABCD,{BC→A}),分解R使分解后的关系达到BCNF且具有无损联接性。

      答案:R1=(ABC, {BC→A}), R2=(BCD, {Ф})

     
4.5.8:
          无损联接地将CTHRSG分解为一组BCNF的关系模式,
      其中:C表示课程,T表示教师,H表示时间,R表示教室,
            S表示学生,G表示成绩。
      函数依赖集F及其所反映的语义分别为:
          C→T 每门课程仅有一位教师担任。
         HT→R 在任一时间,一个教师只能在一个教室上课。
         HR→C 在任一时间,每个教室只能上一门课。
         HS→R 在任一时间,每个学生只能在一个教室听课。
         CS→G 每个学生学习一门课程只有一个成绩。

      解:1) 关系模式CTHRSG侯选关键字为:HS;
             由CS不包含侯选关键字,CS→G,
             分解CTHRSG为CSG和CTHRS,并求得CSG和CTHRS上函数依赖最小集:
             F11=πCSG(F) ={ CS→G }
             F12=πCTHRS(F)={HS→R,HT→R,C→T,HR→C}
             CSR(CSG,{CS→G})(BCNF)
             CTHRS(CTHRS,{HS→R,HT→R,C→T,HR→C})
             ρ={CSG, CTHRS}
          2) 关系模式CTHRS侯选关键字为:HS;
             由C不包含侯选关键字,C→T,
             分解CT为CSG和CHRS,并求得CT和CHRS上函数依赖最小集:
             CT(CT,{C→T})(BCNF)
             CHRS(CHRS,{HS→R,HT→R,HR→C})
             ρ={CSG,CT, CHRS}
          3) 关系模式CHRS侯选关键字为:HS;
             由HR不包含侯选关键字,HC→R,
             分解CT为CSG和CHRS,并求得CT和CHRS上函数依赖最小集:
             CHR(CH,{HC→R,HR→C})(BCNF)
             CHS(HS,{HS→C})(BCNF)
          4) ρ={CSG,CT,CHR,CHS}

 

关系数据库设计理论(5)   关系模式的规范化

图4.5.1 算法分解树

      算法1:存在两个问题:
  第一、分解结果不唯一
  例:最后一次分解时如果选择HR→C,
      则分解的最终结果为
        CSG、CT、HRC和HRS。
      所以分解要结合语义和实际应用
      来考虑。
  第二、分解不保证是保持函数依赖的
  例:TH→R未能保持,在分解后各模式的
     函数依赖的并集中没有逻辑蕴涵
     TH→R。


       4、面向3NF且保持函数依赖的分解(算法2)

         输入:关系模式R及其上的最小函数依赖集F。
         输出:R的保持函数依赖的分解,其中每一个关系模式是关于F在其上投影的3NF。

         算法实现:
             1)如果R中存在一些不在F中出现的属性,
               则将它们单独构成一个关系模式,并从模式R中消去;
             2)如果F中有一个函数依赖X→A,且XA=R,则R不用分解,
               算法终止;
             3)对F中的每一个函数依赖X→A,构造一个关系模式XA。
               如果X→A1,X→A2,…,X→An均属于F,则构造一个关系模式XA1A2…An

         定理:算法2正确(证明略)

        
4.5.9:分解算法1例2关系模式CTHRSG,要保持函数依赖达到3NF。

         解:关系模式CTHRSG的最小函数依赖集F={C→T,CS→G,HR→C,
             HS→R,TH→R}。该模式可以保持函数依赖地分解为如下一
             组3NF的关系模式:ρ={CT,CSG,CHR,HSR,HRT}。

      5、面向3NF既有无损联接性又保持函数依赖的分解(算法3)

         输入:关系模式R及其上的最小函数依赖集F。
         输出:R的具有无损联接性及保持函数依赖的分解,
              其中每一个关系模式均为3NF。

         算法实现:
            1) 按算法2对关系模式R进行分解,设结果为σ={R1,R2,…,Rk};
            2) X是R的关键字,τ=σ∪{X}是R的一个分解。
            3) 求τ式的最小集合(当Ri≤Rj∈τ时,消去Ri)。

         定理:算法3正确
              设X是R的关键字,则τ=σ∪{X}是R的一个分解,
          且所有的关系模式均满足3NF,同时具有无损联接性和保持函数依赖性。
          由于σ中全部模式均为3NF,X中属性之间不存在传递和部分函数依赖,
          即X也是3NF的。分解τ具有无损联接性可以无损联接性检验算法验证。
          由于X为R的关键字,表中模式X所对应的行,应用修改规则处理后,
          将变成全部由а组成。

       
4.5.10:
                将算法1例2的关系模式CTHRSG分解为一组3NF的关系模式,
            要求分解既具有无损联接性又保持函数依赖。

        解:在算法2例中得σ={CT,CSG,CHR,HSR,HRT},
            而HS是原模式的关键字,所以τ={CT,CSG,CHR,HSR,HRT,HS}。
            由于HS是模式HSR的一个子集,所以
            消去HS后的分解{CT,CSG,CHR,HSR,HRT}
            就是具有无损联接性和保持函数依赖性的分解,
            且其中每一个模式均为3NF。