数据库 规范覆盖的计算、多值依赖

(1)F中每个FD的右部只含一个属性。函数依赖集的最小覆盖定义

:设F

是R(U)上的FD集，如果F满足以下三个条件：(2)F中无多余FD。即不存在XA,满足F与F－{XA}等价。(3)F中每个FD的左部都不含多余属性。即不存在XA，X有真子集Z，满足：F与(F－{XA})∪{ZA}等价。则称F为最小依赖集或最小覆盖。则对应的规范覆盖为：Fc={}。例：设最小覆盖为：Fm={C→B,

B→A,C→D,A→E,B→D},将最小覆盖中左部相同的FD合并成一个后得到的FD集称为规范覆盖。C→BD,B→AD,A→E函数依赖集的最小覆盖(1)

用分解规则将F中的每个FD右部分解为单属性。如何计算FD集F的最小覆盖？分三步：F(F-{XY})∪{XAi|i=1,2,…,k

}。对每个XYF,若Y=A1A2…Ak(k≥2),则置：(2)

删除F中多余的FD。对每个XAF,令G=F-{XA},若AXG＋,则置FG。因：由AXG＋可得XA，故F中的XA多余。(3)

删除F中每个FD左部的多余属性。对每个XAF,设X=B1B2…Bm(m≥2),逐个考查Bi(i=1..m):若A(X-Bi)F＋,因：由A(X-Bi)F＋可得(X-Bi)A，故XA中Bi是多余属性。则置F(F-{XA})∪{(X-Bi)A}。F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→B,CB→E}例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆盖(1)用分解规则将F中的每个FD右部分解为单属性。(2)删除F中多余的FD。G={

C→B,

B→A,C→D,C→A,AC→D,CB→B,CB→E}(AC)G+={A,C,…}，∵A(AC)G＋，∴置FG

。函数依赖集的最小覆盖函数依赖集的最小覆盖F={

C→B,

B→A,C→D,C→A,AC→D,CB→B,CB→E}G={

B→A,C→D,C→A,AC→D,CB→B,CB→E}CG+={}，∴F不变

。,DC,A∵BCG＋，例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆盖(1)用分解规则将F中的每个FD右部分解为单属性。(2)删除F中多余的FD。函数依赖集的最小覆盖F={

C→B,

B→A,C→D,C→A,AC→D,CB→B,CB→E}例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆盖BG+={B}，∴F不变

。∵ABG＋，G={

C→B,C→D,C→A,AC→D,CB→B,CB→E}(1)用分解规则将F中的每个FD右部分解为单属性。(2)删除F中多余的FD。函数依赖集的最小覆盖例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆盖F={

C→B,

B→A,C→D,C→A,AC→D,CB→B,CB→E}G={

C→B,B→A,C→A,AC→D,CB→B,CB→E}CG+={}，∴置FG

。,BC,A∵DCG＋，,D,E(1)用分解规则将F中的每个FD右部分解为单属性。(2)删除F中多余的FD。函数依赖集的最小覆盖例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆盖F={

C→B,

B→A,C→A,AC→D,CB→B,CB→E}G={

C→B,B→A,AC→D,CB→B,CB→E}CG+={}，∴置FG

。,BC,A∵ACG＋，,D,E(1)用分解规则将F中的每个FD右部分解为单属性。(2)删除F中多余的FD。函数依赖集的最小覆盖例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆盖A,CF={

C→B,

B→A,AC→D,CB→B,CB→E}G={

C→B,B→A,

CB→B,CB→E}(AC)G+={}，∴F不变

。,B,E∵D(AC)G+

，(1)用分解规则将F中的每个FD右部分解为单属性。(2)删除F中多余的FD。函数依赖集的最小覆盖例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆盖(CB)G+={}，C,B,…F={

C→B,

B→A,AC→D,CB→B,CB→E}G={

C→B,B→A,AC→D,CB→E}∴置FG

。∵B(CB)G+，(1)用分解规则将F中的每个FD右部分解为单属性。(2)删除F中多余的FD。函数依赖集的最小覆盖例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆盖(CB)G+={}，C,BF={

C→B,

B→A,AC→D,

CB→E}G={

C→B,B→A,AC→D

}∴F不变

。,A,D∵E(CB)G+，(1)用分解规则将F中的每个FD右部分解为单属性。(2)删除F中多余的FD。函数依赖集的最小覆盖例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆盖F={

C→B,

B→A,AC→D,

CB→E}(3)删除F中每个FD左部的多余属性。F={

C→B,

B→A,AC→D,

CB→E

}CF+={}，C∴A是多余属性，删去。,B,A∵DCF+，,D,E

C→D,(1)用分解规则将F中的每个FD右部分解为单属性。(2)删除F中多余的FD。函数依赖集的最小覆盖例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆盖F={

C→B,

B→A,AC→D,

CB→E}F={

C→B,

B→A,AC→D,

CB→E

}(1)用分解规则将F中的每个FD右部分解为单属性。(2)删除F中多余的FD。

C→D,BF+={}，B∴C不是多余属性，保留。,A∵EBF+，(3)删除F中每个FD左部的多余属性。函数依赖集的最小覆盖例:

求F={AC→A,C→B,

B→A,C→D,C→A,AC→D,CB→BE}的最小覆盖F={

C→B,

B→A,AC→D,

CB→E}F={

C→B,

B→A,AC→D,

CB→E

}(1)用分解规则将F中的每个FD右部分解为单属性。(2)删除F中多余的FD。

C→D,(3)删除F中每个FD左部的多余属性。CF+={}，C∴B是多余属性，删去。,B,A∵ECF+，,D,EC→EF的规范覆盖为：Fc={}最后得到F的最小覆盖为：Fm={C→B,

B→A,C→D,C→E},B→AC→BDE多值依赖在函数依赖范畴内，BCNF已经非常完美。但是属于BCNF的关系模式仍可能存在问题。例如：假设多个教师上同一门课程，使用同一套参考书：注意：

TC不成立，因为一个教师可以上多门课。

BC不成立，因为参考书可以跨课程交叉使用。数学分析高等代数微分方程数学邓军陈斯物理李平王强邓军普通物理微分方程用关系模式Teach(C,T,B)表示。课程教师参考书F={}，候选码为CTB,即全码，所以Teach∈BCNF否则：候选码是TBTeach∈2NF

TBC是部分依赖Teach关系存在以下4个问题：Teach(C,T,B)存在的问题数据冗余大：有多少教师上同一门课，参考书就重复多少次;(2)更新异常：改某一门课的参考书需要修改该课的所有记录;(3)插入异常:

某门课增加一个教师，该课有多少参考书就需要插入多少个元组;(4)删除异常:删除某门课的一本参考书，该课程有多少教师就要删除多少元组。原因：对于每一门课，Teach表中都存储了T和B的笛卡尔积,即下列条件对每门课x都成立：TeachCTB数学数学数学数学数学数学物理物理物理物理物理物理…邓军邓军邓军陈斯陈斯陈斯李平李平王强王强邓军邓军…数学分析高等代数微分方程数学分析高等代数微分方程普通物理微分方程普通物理微分方程普通物理微分方程…PT,B(sC=x(Teach))=PT

(sC=x(Teach))×PB(sC=x(Teach))由此引出多值依赖的定义：R(U)UXYZrXYZ………………………设R(U)是U上的关系模式，定义(多值依赖)：X,Y,ZU,且Z=U-X-Y,若对R(U)的任意关系r，都有：以及r在X属性组上的任意值x,成立，PY,Z(sX=x(r))=PY

(sX=x(r))×PZ(sX=x(r))xx说明：则称X多值确定Y或Y多值依赖于X，记作XY。条件必须对R(U)的所有可能关系在X属性组上的所有可能值都成立,只要在某个可能值上条件不成立，则:XY不成立。R(U)UXYZrXYZ………………………………设R(U)是U上的关系模式，多值依赖的另一个定义：X,Y,ZU,且Z=U-X-Y,若R的任意关系r满足:那么(x,y2,z1)和(x,y1,z2)也是r的元组，只要(x,y1,z1)和(x,y2,z2)是r的元组,说明：则称多值依赖XY在R(U)上成立。两种定义是等价的：xy1

z1xy2

z2xy2

z1xy1

z2y1

z1y2

z2y2

z1y1

z2y1y2z1z2=×多值依赖的性质(1)对称性：若XY，则XU-X-Y(即Z)证明:PY,Z(sX=x(r))=PY

(sX=x(r))×PZ(sX=x(r))成立，必有PZ,Y(sX=x(r))=PZ

(sX=x(r))×PY(sX=x(r))成立。(2)传递性：若XY，YZ,则XZ-Y证明非常复杂，大大超出了本课程的范围。(3)复制性：若XY,则XY。rXYZ………x…xy…yz1…zk………XY:若X上的分量相等，则Y上的分量相等。PY,Z(.)PY

(.)PZ(.)yz1…yzkyz1…zk×=×=证明：所以XY多值依赖的性质(1)对称性：若XY，则XU-X-Y(即Z)证明:PY,Z(sX=x(r))=PY

(sX=x(r))×PZ(sX=x(r))成立，必有PZ,Y(sX=x(r))=PZ

(sX=x(r))×PY(sX=x(r))成立。(2)传递性：若XY，YZ,则XZ-Y证明非常复杂，大大超出了本课程的范围。(3)复制性：若XY,则XY。(4)并规则：若XY,XZ,则XYZ。(5)交规则：若XY,XZ,则XY∩Z。(6)差规则：若XY,XZ,