范式理论

求属性集闭包

result = α
repeat
for each β → γ in F 
        if β ⊆ result then result = result ∪ γ
until(result不再改变)

求函数依赖集的闭包

对于任意的$\gamma \in R$，找出闭包$\gamma ^+$，并且对于任意的$S\subseteq \gamma ^+$，输出一个函数依赖$\gamma \to S$

求候选键

给定关系模式$R(U,F)$，将$R$的所有属性分为$L,B,N$三类
$L$表示只在函数依赖左边出现
$B$表示在函数依赖两边都有出现
$N$表示未在函数依赖中出现
令$X=L\cup N$，若$X^+$包含$U$，则$X$是唯一候选键
否则，从$B$中任取一个属性$A$，若$XA^+$包含$U$，则$XA$是一个候选键，然后调换$B$中属性反复尝试
如果已经找到全部候选键，结束
否则，从$B$中任取两个属性，三个属性$\cdots$，反复尝试

求正则覆盖$F_c$

小$tips:$正则覆盖至少存在一个但不唯一
$(1)$右部最小化：用分解法则使$F$中的任何一个函数依赖的右边仅含一个属性
$(2)$除本求包：从第一个函数依赖$X\to Y$开始，先将其从$F$中去除，然后在剩下的函数依赖中求$X^+$，若$X^+$包含$Y$，就说明$X\to Y$确实冗余，否则保留$X\to Y$
$(3)$左部最小化：尝试去掉左侧无关属性，如$XY\to A$，若要判断$Y$是冗余属性，则计算$X^+$，若$X^+$包含$A$，说明$Y$是无关属性，去掉它
$(4)$如果第三步有修改，那要退回到第二步重新做
$(5)$把左部相同的函数依赖合并

$3NF$分解

$(1)$求出$F_c$
$(2)$$F_c$中每个$X\to Y$构成一个模式$XY$
$(3)$如果每个模式都不包含$R$的候选键，那么把候选键作为一个模式放入模式集中
$(4)$如果分解完后，存在某个$R_i\subseteq R_j$，舍掉$R_i$

判断分解是否保持函数依赖

对$F$中每个$\alpha \to \beta$做以下过程：

result = α
repeat
for each 分解后的 Ri
    t = (result ∩ Ri)的闭包 ∩ Ri
    result = result ∪ t
until(result不再改变)

若$result$包含$\beta$所有属性，则该依赖被保持
若每个依赖都被保持，则该分解保持依赖

求函数依赖$F$在某个属性子集上的投影

列出属性子集(设属性子集里有$n$个属性)里单属性、任意组合双属性、任意组合三属性、$\cdots $、$直到任意组合(n-1)属性$在原$F$上的所有闭包
把右部的平凡属性、不在属性子集内的属性去掉
例：关系模型$R(A,B,C,D),F=\lbrace AB\to C, D\to B\rbrace$，那么$F$在模式$(ACD)$上的投影$\pi_{ACD}(F)$是什么
$A^+=A$
$C^+=C$
$D^+=DB$
$AC^+=AC$
$AD^+=ABCD$
$CD^+=BCD$
在草稿上先把$B$划掉
再把平凡属性划掉
最后划的只剩$AD^+=C$
那么投影$\pi_{ACD}(F)=\lbrace AD\to C\rbrace$

$BCNF$分解

如果某个$R_i$(原$F$在$R_i$上的投影)中存在一个非平凡函数依赖$\alpha \to \beta$的左部$\alpha$不是超键，则将$R_i$分解成$(\alpha \beta)$和$(R_i-\beta)$
一直这样找不符合的函数依赖，再分解
直到分解符合$BCNF$要求