4模式的分解
# 0x1.模式的分解
把低一级的关系模式分解为若干个高一级的关系模式的方法==不是唯一==的 (==最小函数依赖集、分解方式都不唯一==) 只有能够保证分解后的关系模式与原关系模式==等价==,分解方法才有意义
# 0x2.投影
# 0x3.关系模式分解的标准
# 0.三种模式分解等价的定义:
- 分解具有无损连接性
- 分解要保持函数依赖
- 分解既要保持函数依赖,又要具有无损连接性
并无层次关系 不同准则,决定模式的分离程度; 范式就是对分离程度的测度
# 1.无损连接性
关系模式R<U,F>的一个分解 ρ={ R1<U1,F1>,R2<U2,F2>, …,Rn<Un,Fn>} 若R与R1、R2、…、Rn自然连接的结果相等,则称关系模式R的这个分解ρ具有==无损连接性==(Lossless join) 具有无损连接性的分解==保证不丢失信息== 无损连接性==不一定能解决==插入异常、删除异常、修改复杂、数据冗余等问题
# 2.保持函数依赖
设关系模式R<U,F>被分解为若干个关系模式 R1<U1,F1>,R2<U2,F2>,…,Rn<Un,Fn> (其中U=U1∪U2∪…∪Un,且不存在Ui 属于 Uj,Fi为F在Ui上的投影),若F所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖Fi所逻辑蕴含,则称关系模式R的这个分解是==保持函数依赖==的(Preserve dependency)
# 3.例子(帮助理解)
原表:
# 1.第一种分解
分解后的数据库丢失了许多信息 例.如无法查询16001学生所在系或所在宿舍。 如果分解后的关系可以通过自然连接恢复为原来的关系,那么这种分解就没有丢失信息
# 2.第二种分解
多了很多信息,这也叫做信息丢失。
NL DL比原来的SL关系多了3个元组 无法知道16002、16004、16005 究竟是哪个系的学生
元组增加了,信息丢失了
# 3.第三种分解
将SL分解为下面二个关系模式: ND(Sno, Sdept) NL(Sno, Sloc) 分解后的关系为:
第三种分解方法具有无损连接性 问题: 这种分解方法没有保持原关系中的函数依赖 SL中的函数依赖Sdept→Sloc 没有投影到关系模式ND、NL上
# 4.第四种分解
将SL分解为下面二个关系模式: ND(Sno, Sdept) DL(Sdept, Sloc)
这种分解方法就保持了函数依赖和无损连接。
# 5.总结
第一种分解方法既不具有无损连接性,也未保持函 数依赖,它不是原关系模式的一个等价分解 第二种分解方法未保持函数依赖,不具有无损连接性 (丢失信息) 第三种分解方法具有无损连接性,但未持函数依赖 (丢失依赖) 第四种分解方法既具有无损连接性,又保持了函数依赖
# 0x4.模式的分解的作用
若要求分解保持函数依赖,那么模式分离总可以达到3NF,但不一定达到BCNF;
若要求分解既保持函数依赖,又具有无损连接性,可以达到3NF,但不一定能达到BCNF;
若要求分解具有无损连接性,那一定可以达到4NF;(有时可能丢失函数依赖)
# 0x5.模式分解相关算法
# ==0.候选码求解算法==
分析: 对于给定的关系模式R<U, F>,依照函数依赖集F将U中的属性分为以下四类: L类属性: 在F中只出现在函数依赖的左部的属性; R类属性: 在F中只出现在函数依赖的右部的属性; LR类属性: 分别出现在F中的函数依赖左部和右部的属性; N类属性: 不在F中的函数依赖中出现的属性。 结论: ① L类属性和N类属性必包含于任一候选码中; ② R类属性必不包含于任何候选码中; ③ LR类属性不能确定是否在码中。
候选码求解算法涉及到的两个推论:
# 推论1:
关系模式R(U,F),若X是L类属性,且x+包含了R的全部属性,则x是R的惟一候选码。
# 推论2:
关系模式R(U,F),若X是L类、N类组成的属性集,且x+包含了R的全部属性,则x是R的惟一候选码。 例:设R(A,B,C,D,E,P),G={A→D, E→D, D→B, BC→D, DC→A},求R的所有候选码。 解:L类属性:C,E N类属性:p R类属性:无 LR类属性:A,B,D (CEP)+=ABCDEP ∴ CEP是R的惟一候选码
# 算法步骤:
(1) 依照函数依赖集F将R中的所有属性分为L类、R类、LR类和N类 属性,令X为L、N类属性的集合,Y为LR类属性集合; (2) 若X~F~^+^=U,则X为R的唯一候选码,结束;否则转(3);(P191,算法6.1) (3) 逐一取Y中的单一属性A,若(XA)~F~^+^=U,则XA为候选码 , 令Y=Y-{A} ,转(4); (4)若已找出所有候选码,则转(5)否则再依次取Y中的任意两个、三个……属性,与X组成属性组XZ ,若(XZ)~F~^+^ =U, 且XZ不包含已求得的候选码,则XZ为候选码。 (5)算法结束,输出结果。
# 例题:
设关系模式R < U,F >,其中U = { H,I,J,K,L },若 F = {H→IJ,J→K,IJK→L,L→H,L→K },关系模式R的候选关键字有 () 个。
本题在函数依赖集F中无L类和N类属性,所有属性都是LR类属性,因此,X=空集,Y={ H,I,J,K,L }。 分别取Y中的单一属性求闭包。
得出H、L都是候选码,然后继续考虑两个的情况 首先要去掉Y中的H和L,Y={ I,J,K },然后遍历
所以IJ,是候选码 对于本题来说,2个判断完毕后找到候选码,再判断3个的情况就没有意义了。 因此最终的候选码为H、L、IJ,共3个
# 6.2判别一个分解的无损连接性
# 例题:
# 6.3(合成法)转换为3NF的保持函数依赖的分解
# 步骤:
1、求关系模式R<U,F>的最小依赖集Fm。 2、找出所有不在Fm中出现的属性,这些属性构成R0<U0,F0>。把这些属性从U中去掉,剩余的属性仍记为U。 3、若Fm中存在X→A,且XA=U,则R不用分解。 4、对F中的每一个函数依赖X→A,构造一个关系模式R(XA)。如果存在X→A1,X→A2,…,X→An,则构造R(XA1A2…An)。
# 例题:
关系模式R<U,F>,其中U={C,T,H,R,S,G},F={CS→G,C→T,TH→R,HR→C,HS→R},将其分解成3NF并保持函数依赖。 1、计算Fm,求得F即为Fm。
2、由于R中的所有属性均在F中都出现,所以转下一步。 假设: U={C,T,H,R,S,G},F={CS→G} 由于T,H,R没有在F中出现,于是将R0={THP}作为一个分解关系
3、对F按具有相同左部的原则分为: R1=CSG,R2=CT,R3=THR,R4=HRC,R5=HSR。 所以ρ={R1(CSG),R2(CT),R3(THR),R4(HRC),R5(HSR)}。 相同左部分的原则: 举例:C→T ,C→A是相同的左部,则将二者合并为一个关系C→AT
# 6.4转换为3NF既有无损连接性又保持函数依赖的分解
# 步骤:
1、先转换为3NF的保持函数依赖的分解。 2、求得关系模式R<U,F>的码X,令τ= ρ {R(X)}。 3、若存在X⊆Ui,则将R(X)从τ中去掉;若存在Ui⊆X,则将R(Ui)从τ中去掉。
# 例题:同上
1、先转换为3NF的保持函数依赖的分解,就是上面的结果ρ={R1(CSG),R2(CT),R3(THR),R4(HRC),R5(HSR)}。 2、求关系模式R<U,F>的码为HS,令τ= ρ {HS} = {R1(CSG),R2(CT),R3(THR),R4(HRC),R5(HSR),R*(HS)} 3、由于存在HS⊆HSR,所以去掉R*(HS)。 4、综上τ={R1(CSG),R2(CT),R3(THR),R4(HRC),R5(HSR)}为所求分解。
# 6.5(分解法)转换为BCNF的无损连接分解
# 步骤:
INPUT:关系模式R 以及在R上成立的函数依赖集F 1.初始化 P = {R} 2.若P中的所有关系模式S都是BCNF,则转步骤(4) 3.若P中有一个模式S不是BCNF,则S中必能找到一个函数依赖X->A,X不是S的候选码,且A不属于X。设S1 =XA,S2 = S-A,分解后的{S1,S2}替代S,转步骤(2) 4.算法结束,输出P *注:学习的前置条件:会求候选码
*注:步骤3中,A不属于X的含义: 如果有函数依赖 CD->C,则C是属于{CD}的,如果C->D,则D是不属于{C}的。
*注:模式S的解释:如P={R1(ABC),R2(KMG)},这里的S可以指代R1,也可以指代R2。
*注:如何判断BCNF:函数依赖项的左侧都是候选码,即为BCNF。
# 例题:
原文网址【scholat学者网】:
R={A,B,C,D,E,F,G},F={A—>B, A—>C ,C—>D, C—>E, E—>FG},将R分解成BCNF。
解:
步骤1:初始化P={R} = {R(A,B,C,D,E,F,G)}
步骤2:计算一下R的候选键,易知R的候选键为A。
步骤3-1:从函数依赖集F中容易发现,A—>B, A—>C 是满足BCNF的,C—>D不满足,且D不属于{C},因此
令S1 = CD,S2=S-{D} = {A,B,C,E,F,G},替换R
即P={R1(C,D),R2(A,B,C,E,F,G)}。
此时,F分成两部分。F1={C—>D},F2={A—>B, A—>C , C—>E, E—>FG}
步骤3-2:由R1已经满足BCNF了,所以不用管它了。继续计算R2的候选键,易知R2的候选键为A
同样,A—>B, A—>C满足BCNF了,C—>E不满足,且E不属于{C},因此
令R3 = CE,R4 = R2-E={A,B,C,F,G},替换R2。(为了书写美观,写加入后的R3写为R2,R4写为R3,后续同样操作,不再赘述)
即P={R1(C,D),R2(C,E),R3(A,B,C,F,G)}。
此时,F2分成两部分,新的F3={C->E},F4={A—>B, A—>C , C—>FG}
即:F1={C—>D},F2={C->E},F3={A—>B, A—>C , C—>FG}
*注:特别关注函数依赖C—>FG,是由C—>E, E—>FG导出的传递依赖。给与我们的提示是,在书写新的函数依赖集时,千万不要遗漏掉传递依赖等性质推出的新依赖。
步骤3-3:由R1,R2已经满足BCNF了,所以不用管它了。继续计算R3的候选键,易知R3的候选键为A
此时A—>B, A—>C 已经满足BCNF了,而C—>FG不满足,且C不属于{FG}
因此令R4=CFG,R5=R3-{FG} = {A,B,C}。
因此替换掉原来的R3,即: 即P={R1(C,D),R2(C,E),R3(C,F,G),R4(A,B,C)}。
F3分解为两部分,F4={ C—>FG},F5={A—>B, A—>C}。
即:F1={C—>D},F2={C->E},F3={ C—>FG},F4={A—>B, A—>C}。
显然,R4的候选键为A,且F4中的函数依赖左侧都是候选键,因此P中的所有分解都满足BCNF。故算法结束
综上,分解为P={R1(C,D),R2(C,E),R3(C,F,G),R4(A,B,C)}。