第二步，把原始关系模式分解成两个属性重迭的关系模式，一个模式包含了违背BCNF的函数依赖的所有属性，另一个模式包含了依赖左边以及未包含在该依赖中的所有属性
第三步，判断新关系模式是否满足BCNF。如果不满足则继续重复上述步骤进行分解
关系模式分解的目的是解决数据冗余的问题，但要考虑多方面的问题。如原关系模式中信息是否丢失，函数依赖关系是否保持等，要研究这方面的问题就要涉及关系模式分解算法的具体准则。
关系模式的分解算法中有以下几方面的准则：（（1)若要求分解具有无损连接性，则模式分解一定可以达到第四范式（4NF）。
（2）若要求分解保持函数依赖性，则模式分解可以达到第三范式（3NF），但不一定能达到巴斯−科德范式（BCNF）。
（3）若要求分解既具有无损连接性，又保持函数依赖性，则模式分解可以达到第三范式（3NF），但不一定能达到巴斯−科德范式（BCNF）。
1.二元分解的无损连接性判断二元分解是关系模式分解中最简单的一种分解方式。二元分解是将原关系模式分解成两个子关系模式。如将关系模式R分解成关系模式集ρ，ρ中包含两个关模式R1、R2，即ρ={R1，R2}，则ρ是R的二元分解。
当关系模式分解是最简单的二元分解（ρ={R1
数据依赖的公理系统逻辑蕴含
定义5.11 对于满足一组函数依赖 F 的关系模式R <U，F>，其任何一个关系r，若函数依
赖X→Y都成立, 则称F逻辑蕴含X →Y。
一、Armstrong公理系统：
关系模式R <U，F >来说有以下的推理规则：
Al.自反律（Reflexivity）：若Y≤X≤U，则X →Y为F所蕴含。
A2.增广律（Augmentation）：若X→Y为F所蕴含，且Z≤U，则XZ→YZ为F所蕴含。
A3.传递律（Transitivity）：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。
注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F。
定理 5.l Armstrong推理规则是正确的
证明：
(1)自反律:若Y∈X∈U，则X →Y为F所蕴含
证: 设Y∈X∈U 对R <U，F>的任一关系r中的任意两个元组t，s：
若t[X]=s[X]，由于Y≤X，有t[y]=s[y]，
所以X→Y成立，自反律得证
(2)增广律: 若X→Y为F所蕴含，且Z∈U，则XZ→YZ 为F所蕴含。
证：设X→Y为F所蕴含，且Z∈U。设R<U，F>的任一关系r中任意的两个元组t,s；
若t[XZ]=s[XZ]，则有t[X]=s[X]和t[Z]=s[Z]；
由X→Y，于是有t[Y]=s[Y]，所以t[YZ]=s[YZ]；
所以XZ→YZ为F所蕴含，增广律得证。
(3) 传递律：若X→Y及Y→Z为F所蕴含，则X→Z为 F所蕴含。
证：设X→Y及Y→Z为F所蕴含。对R<U，F>的任一关系 r中的任意两个元组 t,s。
若t[X]=s[X]，由于X→Y，有 t[Y]=s[Y]；再由Y→Z，有t[Z]=s[Z]；
所以X→Z为F所蕴含，传递律得证。
二、导出规则
1.根据A1，A2，A3这三条推理规则可以得到下面三条推理规则：
合并规则：由X→Y，X→Z，有X→YZ。（A2， A3）
伪传递规则：由X→Y，WY→Z，有XW→Z。（A2， A3）
分解规则：由X→Y及 Z≤Y，有X→Z。（A1， A3）
2.根据合并规则和分解规则，可得引理5.1
引理5.l X→A1 A2…Ak成立的充分必要条件是X→Ai成立（i=l，2，…，k）。
三、函数依赖闭包
定义5.l2 在关系模式R<U，F>中为F所逻辑蕴含的函数依赖的全体叫作F的闭包,记为F+。
定义5.13 设F为属性集U上的一组函数依赖，X≤U， XF+ ={ A|X→A能由F 根据
Armstrong公理导出}，XF+称为属性集X关于函数依赖集F 的闭包。
引理5.2 设F为属性集U上的一组函数依赖，X，Y≤U，X→Y能由F 根据Armstrong公理导
出的充分必要条件是Y≤XF+。
用途：将判定X→Y是否能由F根据Armstrong公理导出的问题， 就转化为求出XF+ ，判定
Y是否为XF+的子集的问题。
算法5.l 求属性集X（X≤U）关于U上的函数依赖集F 的闭包XF+
输入：X，F
输出：XF+
步骤：
（1）令X（0）=X，i=0
(2）求B，这里B = { A |(ヨV)(ヨW)(V→W∈F∧V≤X（i）∧A∈W)}；
（3）X（i+1）=B∪X（i）
（4）判断X（i+1）= X （i）吗?
（5）若相等或X（i）=U , 则X（i）就是XF+ , 算法终止。
（6）若否，则 i=i+l，返回第（2）步。
对于算法5.l， 令ai =|X（i）|，{ai }形成一个步长大于1的严格增的序列，序列的上
界是 | U |，因此该算法最多|U| - |X| 次循环就会终止。
[例1] 已知关系模式R<U，F>，其中U={A，B，C，D，E}；F={AB→C，B→D，C→E，
EC→B，AC→B}。求（AB）F+ 。
解 设X（0）=AB；
(1)计算X（1）: 逐一的扫描F集合中各个函数依赖，找左部为A，B或AB的函数依赖。
得到两个：AB→C，B→D，于是X（1）=AB∪CD=ABCD。
(2)因为X（0）≠ X（1） ，所以再找出左部为ABCD子集的那些函数依赖，又得到
AB→C，B→D， C→E，AC→B，于是X（2）=X（1）∪BCDE=ABCDE。
(3)因为X（2）=U，算法终止，所以（AB）F+ =ABCDE。
四、Armstrong公理系统的有效性与完备性
有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中
/* Armstrong正确
完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来
/* Armstrong公理够用，完全
完备性：所有不能用Armstrong公理推导出来f, 都不为真。
若 f 不能用Armstrong公理推导出来， f∈ F+
有效性与完备性的证明（略）
Armstrong公理的完备性及有效性说明:
“蕴含” == “导出” 等价的概念；
F+ ==由F出发借助Armstrong公理导出的函数依赖的集合五、函数依赖集等价
定义5.14 如果G+=F+，就说函数依赖集F覆盖G(F是G的覆盖，或G是F的覆盖)或F与G等价。
引理5.3 F+ = G+ 的充分必要条件是F≤G+ ，和G≤F+
证: 必要性显然，只证充分性。
（1）若F≤G+ ，则XF+≤XG++ 。
（2）任取X→Y∈F+ 则有 Y≤XF+≤XG++ 。
所以X→Y∈(G+）+= G+。即F+≤G+。
（3）同理可证G+≤F+ ，所以F+ = G+。
六、最小依赖集
定义5.15 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依
赖集或最小覆盖。
(1) F中任一函数依赖的右部仅含有一个属性。
(2) F中不存在这样的函数依赖X→A，使得F与F-{X→A}等价。
(3) F中不存在这样的函数依赖X→A，X有真子集Z使得F-{X→A}∪{Z→A}与F等价。
[例2] 对于5.l节中的关系模式S<U，F>，其中：U={ SNO，SDEPT，MN，CNAME，G }，
F={ SNO→SDEPT，SDEPT→MN，（SNO，CNAME）→G }
设F’={SNO→SDEPT，SNO→MN，SDEPT→MN，(SNO，CNAME)→G，(SNO，
SDEPT)→SDEPT}F是最小覆盖，而F ’不是。
因为：F ’-{SNO→MN}与F ’等价 F ’-{(SNO，SDEPT)→SDEPT}也与F ’等价
F ’-{(SNO，SDEPT)→SDEPT}∪{SNO→SDEPT}也与F ’等价
七、极小化过程
定理5.3 每一个函数依赖集F均等价于一个极小函数依赖集Fm。此Fm称为F的最小依赖集
证:构造性证明，依据定义分三步对F进行“极小化处理”，找出F的一个最小依赖集。
(1)逐一检查F中各函数依赖FDi：X→Y，
若Y=A1A2 …Ak，k >2，则用 { X→Aj |j=1，2，…， k} 来取代X→Y。
引理5.1保证了F变换前后的等价性。
(2)逐一检查F中各函数依赖FDi：X→A，
令G=F-{X→A}，若A≤XG+， 则从F中去掉此函数依赖。
由于F与G =F-{X→A}等价的充要条件是A≤XG+ 。因此F变换前后是等价的。
(3)逐一取出F中各函数依赖FDi：X→A，
设X=B1B2…Bm，逐一考查Bi （i=l，2，…，m），若A∈（X-Bi ）F+ ，则以X-Bi 取
代X。由于F与F-{X→A}∪{Z→A}等价的充要条件是A≤ZF+ ，其中Z=X-Bi。因此F变换
前后是等价的。
由定义，最后剩下的F就一定是极小依赖集。因为对F的每一次“改造”都保证了改造
前后的两个函数依赖集等价，因此剩下的F与原来的F等价。 证毕
定理5.3的证明过程 也是求F极小依赖集的过程
[例3] F = {A→B，B→A，B→C，A→C，C→A}
Fm1、Fm2都是F的最小依赖集：
Fm1= {A→B，B→C，C→A}
Fm2= {A→B，B→A，A→C，C→A}
F的最小依赖集Fm不一定是唯一的。
它与对各函数依赖FDi 及X→A中X各属性的处置顺序有关。
极小化过程( 定理5.3的证明 )也是检验F是否为极小依赖集的一个算法。若改造后的
F与原来的F相同，说明F本身就是一个最小依赖集。
在R<U，F>中可以用与F等价的依赖集G来取代F
原因：两个关系模式R1 <U，F>，R2<U，G>，如果F与G等价，那么R1的关系一定是R2的
关系。反过来，R2的关系也一定是R1的关系。
关系模式的分解
1．模式分解的等价标准
规范化过程中将一个关系模式分解为若干个关系模式，应该保证分解后产生的模式和原来的模式等价。常用的等价标准有要求：
● 分解是具有无损连接性的；
● 分解是保持函数依赖的；
● 分解既要具有无损连接又要保持函数依赖两种。
将一个关系模式R(U,F)分解为若干个关系模式R1(U1,F1),R2(U2,F2)…Rn(Un,Fn)（其中U＝U1 U2 … Un，R1为F在U1上的投影），这意味着相应的将存储在一个二维表r中的数据分散到若干个二维表r1,r2,…,rn中（其中r1是r在属性组U1上的投影）。我们当然希望这样的分解不丢失信息，也就是说，希望能够通过对关系r1,r2…rn的自然连接运算重新得到关系r中的所有信息。
事实上，将关系r投影为r1,r2,…,rn时并不会丢失信息，关键是对r1,r2,…,rn作自然连接可能会产生一些原来r中没有的元组，从而无法区别那些元组是r中原来有的，即数据库中应该存在的数据，在这个意义上丢失了信息。
例如：设关系模式S(SNO,CLASSNO,DEPTNO)在某一时刻的关系r如下表5-14
表5-14
SNO CLASSNO DEPTNO
S1 C1 D1
S2 C2 D2
S3 C2 D2
S4 C3 D1
若按分解方案一将关系模式S分解为：
S11(SNO,DEPTNO)和
S12(CLASSNO,DEPTNO)，
则将r投影到S11和S12的属性上，得到关系r11如表5-15，r12如表5-16。
表5-15
SNO DEPTNO
S1 D1
S2 D2
S3 D2
S4 D1
表5-16
CLASSNO DEPTNO
C1 D1
C2 D2
C3 D1
对分解后的两个关系作自然连接r11*r12，得到r'如表5-17如下：
表5-17
SNO CLASSNO DEPTNO
S1 C1 D1
S1 C3 D1
S2 C2 D2
S3 C2 D2
S4 C1 D1
S4 C3 D1
r'中的元组S1C3D1和S4C1D1都不是原来r中的元组。就是说，我们无法知道原来r中到底有哪些元组，这是我们不希望的。
定义1：设关系模式R(U,F)分解为关系模式R1(U1,F1)，R2(U2,F2)，…，Rn(Un,Fn)，若对于R的任何一个可能的关系r，都有r=r1*r2…*rn，即r在R1,R2,…,Rn上的投影的自然连接等于r，则称关系模式R的这个分解是具有无损连接性的。
分解1不具有无损连接性，这是一个不好的分解方案。
在将一个关系模式分解为三个或者更多个关系模式的情况下，要判别分解是否具有无损连接性需要比较复杂的算法。然而若将一个关系模式分解为两个关系模式，则很容易判别分解是否具有无损连接性。
关系模式R(U,F)分解为关系模式R1(U1,F1),R2(U2,F2)是具有无损连接性的分解的充分必要条件是（U1∩U2→U1-U2）∈F+，或者（U2∩U1→U2-U1）∈F+。
让我们再考察第二种分解方案，将关系模式S分解为：
S21(SNO,CLASSNO)，
S22(SNO,DEPTNO)
由于U1∩U2＝SNO，U1-U2=CLASSNO，显然U1 U2→U1-U2，所以分解2具有无损连接性。然而分解2也不是一个很好的分解方案，将前面例子的关系r投影到S21,S22的属性上，得到关系r21如表5-18和r22如表5-19：
表5-18
SNO CLASSNO
S1 C1
S2 C2
S3 C2
S4 C3
表5-19
SNO DEPTNO
S1 D1
S2 D2
S3 D2
S4 D1
在这种分解中，假设学生S3从C2班转到C3班，于是我们需要在r21中将元组S3C2修改为S3C3，同时在r22中将元组S3D2修改为S3D1。如果这两个修改没有同时完成，数据库中就会存在不一致信息。这是因为分解得到的两个关系模式不是互相独立造成的。F中的函数依赖CLASSNO→DEPTNO既没有投影到关系模式R22中，而是跨在两个关系模式上。函数依赖是数据库中的完整性约束条件。在r中，若两个元组的X值相等，则Y值也必须相等。现在r的一个元组中的X值和Y值跨在两个不同的关系中，为维护数据库的一致性，在一个关系中修改X值时就需要相应的在另外一个关系中修改Y值，这当然是很麻烦而且是容易出错的，于是我们要求模式分解保持函数依赖这条等价标准。
定义2：设关系模式R(U,F)分解为关系模式R1(U1,F1)，R2(U2,F2)，…，Rn(Un,Fn)，若F=(F1F2…Fn) ，即F所逻辑蕴含的函数依赖一定也由分解得到的各个关系式中的函数依赖所逻辑蕴含，则称关系模式R的这个分解是保持函数依赖的。
分解方案二不是保持函数依赖的，因为分解得到的关系模式中只有函数依赖SNO→CLASSNO，丢失了函数依赖CLASSNO→DEPTNO。不是一个好的分解。
分解方案三是保持函数依赖的。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）