建议在看之前熟悉候选键的求法,不清楚的可以转到这里来:
步骤:
INPUT:关系模式R以及在R上成立的函数依赖集F
1.初始化P={R}
2.若P中的所有关系模式S都是BCNF,则转步骤(4)
3.若P中有一个模式S不是BCNF,则S中必能找到一个函数依赖X->A,X不是S的候选码,且
A不属于x(如果CD->C,右侧元素属于左侧,则不需要分解)。设S1=XA,S2=S-A分解后的(S1S2}替代S转步骤(2)
4.算法结束,输出P
例:
R={A,B,C,D,E,F,G} F={A->B,A->C,C->D,C->E,E->FG},将R分解为BCNF范式
步骤一:初始化
p={A,B,C,D,E,F,G} = {A->B,A->C,C->D,C->E,E->FG}
L:{A}
R:{B,D,F,G}
LR:{C,E}
N为空集
x=LUN=A,A的闭包={A,B,C,D,E,F,G},所以A是唯一候选键
步骤二:
= {A->B,A->C,C->D,C->E,E->FG}
判断bcnf范式:看函数依赖的左侧是否全为候选键,如果是,就是BCNF范式
(1)很明显{C->D}不满足bcnf范式的要求:
则设R1=CD,R2=R-D={A,B,C,D,E,F,G}-{D}={A,B,C,E,F,G}
P={R1,R2}={R1{C,D},R2{A,B,C,E,F,G}}
F1={C->D} F2={A->B,A->C,C->E,E->FG}
注:如果存在C->D,D->E类似的传递依赖虽然D没有在F2中,但是C->E要写在F2中
(2)求F2={A->B,A->C,C->E,E,->FG},与上面的算法同理,A是唯一候选键
注:每一次的候选码都是在变化的,只是这里恰巧是A,如果这里的候选码是B,那么就要看左侧是否全为B,来判断是否为BCNF范式
C->E不满足BCNF范式
R2=CE, R3=R2-E={A,B,C,F,G}
P={R1{CD},R2{CE},R3{A,B,C,F,G}}
F2={C->E} F3={A->B,A->C,C->FG} //虽然R3中没有E,但是可以通过传递依赖推出C->FG
F4={A->B,A->C,C->FG}
(3)求F3的候选码:与上面的算法同理,A是唯一候选键
C->FG不满足BCNF范式,所以:
R4=CFG,R5=R3-FG={A,B,C}
P={R1{C,D},R2{C,E},R3{C,F,G},R4{A,B,C}}
在F4中函数依赖只有{A->B,A->C}
至此每一项都是BCNF范式
P={R1{C,D},R2{C,E},R3{C,F,G},R4{A,B,C}}
💖💖💖这里还有💖💖💖
保持无损连接和函数依赖的3NF合成算法,一起看看吧!!!