数据库-常见概念及⼀⼆三、BC范式
属性闭包
闭包就是由⼀个属性直接或间接推导出的所有属性的集合。
闭包算法：
result = a  //求属性a的属性闭包
while(result 发⽣改变){
for 每⼀个result中的关系a->b
if(a 在result中){
result加⼊属性b
}
}
测试超键：如果a是R的超键那么我们可以计算a的闭包A，如果A包含了R的所有属性那么a的确是R的超键。
常⽤推导式：
(1)Reflexivity：b是a的组成，那么a决定b
(2)Augmentation：a决定b那么ra决定rb
(3)Transitivity：传输性
(4)Union：a决定b，a决定c那么a决定bc
(5)Decomposition：a决定br，那么a决定b，a决定r
(6)Pseudotransitivity（伪递移法则）：如果a决定b以及cd决定e，那么ac决定e
简单例⼦：
f={a->b，b->c，a->d，e->f}；由a可直接得到b和d，间接得到c，则a的闭包就是{a，b，c，d}
正则覆盖
F的正则覆盖Fc是⼀个依赖集，使得F与Fc相互逻辑蕴涵。Fc中任何函数依赖都不含⽆关属性。Fc中函数依赖左半部分都是唯⼀的。
正则覆盖算法
//由定义可以得到，正则覆盖其实就是在做去除所有冗余属性这个事
Fc = F
while(Fc 发⽣变化 ){
使⽤合并规则构造an----&bn的格式
去除冗余  //请参考附加属性Extraneous Attributes的算法
}
附加属性
Extraneous Attributes，额外属性，附加属性。意思是如果⼀个关系中拿掉⼀个属性后的属性闭包与原属性闭包相同，那么很明显有没有那个被拿掉的属性都⼀样，这是⼀个冗余的属性。
附加属性算法
//A中关系alpha->beta
//测试属于alpha的属性a是否多余
计算{alpha - a}的属性闭包 B
if B包含a {
a属性多余
}else{
a属性不多余
}
//测试属于beta的属性b是否多余
A1 = （A-{alpha->beta}）∪{alpha->（beta-b）}
在 A1 下计算alpha的闭包，如果A1包含b那么b多余
简单例⼦
AB->CD ,A->E,E->C，判断AB->CD中C是否多余
易得 AB->D下
(AB)的闭包 = (ABCDE)
C in AB->C
D is extraneous;
⽆损连接分解
⽆损连接分解是将⼀个关系模式分解成若⼲个关系模式后，通过⾃然联接和投影等运算仍能还原到原来的关系模式，则称这种分解为⽆损连接分解。
关系模式R(U，F)的⼀个分解ρ={R1<U1,F1>,R2<U2,F2>}具有⽆损连接的充分必要条件是：U1∩U2→U1-U2 属于F+ 或 U1∩U2→U2 -U1属于F+
⼀个优秀的关系模式的分解应当满⾜三个条件：消除异常（冗余、更新异常、删除异常），信息的可恢复以及依赖的保持。
⽆损连接分解算法
//有属性集R，依赖集F，⼀个分解r{r1,r2,}
while(有变化){
for 每⼀个R中的关系 a->b{
对于所有的r中左侧含相同a的分解
统⼀b
}
if 某⼀个分解ri变成R{
是⽆损连接
}
}
依赖保持
如果分解可以推出原依赖，就说它们是保持依赖的。
依赖保持算法
//对F上的每⼀个α→β
result = α;
while(result发⽣改变){
for each 分解后的Ri
t=(result ∩ Ri)+  ∩  Ri
result=result  ∪  t
}
if β属于result{
α→β被保持
}else{
α→β不被保持
}
BCNF范式
BC范式（BCNF）：在第三范式的基础上，数据库表中如果不存在任何字段对任⼀候选关键字段的传递函数依赖则符合第三范式。即不存在⾮关键字段决定关键字段的情况。
BC范式分解算法：
result = R
R_1 = 空集
for i in 1,2,
//如果R_i不违反BCNF，则不分解R_i
if R_i 关系模式中有α --> β违反了 BC范式
relust =  (result-R_i) + (R_i-(α-β)) + (α+β)
简单例⼦：R = {A ，B， C， D}
I. C → D, C → A, B → C
很容易由 C → D, C → A, B → C
判断出 B 是主码 由于存在 B->C->D 和 B->C->A 故不是3NF，更不是BCNF
分解如下：（B,C)(C,A,D) 这两个关系都是BCNF
II. ABC → D, D → A如果R不是⼀个BCNF， 将它分解为BCNF范式。
由于ABC →D,D →A 可知 ABC 是主码，但存在⾮主属性决定主属性（D->A)不满⾜BCNF，分解如下：（A,B,C)(D,A) 这两个关系都是BCNF
⼀、⼆、三范式
第⼀范式（1NF）：数据表中的每⼀列（每个字段）必须是不可拆分的最⼩单元。
第⼆范式（2NF）：满⾜1NF后，要求表中的所有列，都必须依赖于主键。
第三范式（3NF）：满⾜第⼆范式（2NF）且表中的每⼀列只与主键直接相关⽽不是间接相关，即表中的每⼀列只能依赖于主键。（即⼀张表中只能有另⼀张表中的主键，⽽不能有其他的任何信息，其他的信息⼀律⽤主键在另⼀表查询）
三范式是BC范式的放宽
三范式分解算法
多值依赖
多值依赖MVD：指在关系R中，当给定某个属性集合的值 时，存在另外⼀组属性集合，该组属性集合的值与关系中所有其他属性的值独⽴。为便于理解，将⼀个关系的属性分为三个属性组A、B、C，当给定属性A的值 时，B和C的属性组上的取值独⽴，意思是说B和C的取值可以随意搭配出现在关系中，B的取值不会影响C的取值。
候选码的选取
算法：按以下步骤求候选键：
1.只在FD右部出现的属性，不属于候选码;
2.只在FD左部出现的属性，⼀定存在于某候选码当中;
3.外部属性⼀定存在于任何候选码当中;
4.其他属性逐个与2,3的属性组合，求属性闭包，直⾄X的闭包等于U，若等于U，则X为候选码。
例：R<U,F>,U=(A,B,C,D,E,G),F={AB–>C,CD–>E,E–>A.A–>G}，求候选码。
因G只在右边出现，所以G⼀定不属于候选码;⽽B,D只在左边出现，所以B,D⼀定属于候选码;BD的闭包还是BD，则对BD进⾏组合，除了G以外,BD 可以跟A,C,E进⾏组合
先看ABD
数据库属性的概念
ABD本⾝⾃包ABD,⽽AB–>C,CD–>E,A–>G，所以ABD的闭包为ABDCEG=U
再看BDC
CD–>E,E–>A,A–>G,BDC本⾝⾃包，所以BDC的闭包为BDCEAG=U
最后看BDE
E–>A,A–>G,AB–>C,BDE本⾝⾃包，所以BDE的闭包为BDEAGC=U
因为(ABD)、(BCD)、(BDE)的闭包都是ABCDEG所以本问题的候选码有3个分别是ABC、BCD和BDE