Skip to content

范化与范式

函数依赖

函数依赖：关系表RR 中取两个子集α\alpha 和β\beta ，如果对于RR 中任意两个元组t1t_1 和t2t_2 在α\alpha 各属性相等的时候也满足β\beta属性都相等，则记α→β\alpha \rightarrow \beta。（t1[α]=t2[α]⇒t1[β]=t2[β]）（t_1[\alpha]=t_2[\alpha]\Rightarrow t_1[\beta]=t_2[\beta]）

超键与候选键

超键：当且仅当K→RK\rightarrow R时，才认为KK是RR的超键。

候选键：K→RK\rightarrow R且不存在任何一个KK的子集KiK_i使得Ki→RK_i\rightarrow R

平凡函数依赖

平凡函数依赖：如果β⊆α\beta \subseteq \alpha，我们认为α→β\alpha\rightarrow\beta是平凡的。

无损分解

无损分解：将一个关系表RR拆分成两个关系表R1R_1和R2R_2，如果ΠR1⋈ΠR2=R\Pi_{R_1}\bowtie \Pi_{R_2}=R，则认为是无损分解；如果R⊂ΠR1⋈ΠR2R\subset \Pi_{R_1}\bowtie \Pi_{R_2}，则是有损分解。

无损分解的充分条件：R1∩R2→R1或R1∩R2→R2R_1 \cap R_2\rightarrow R_1或 R_1\cap R_2 \rightarrow R_2。也就是说证得其一可知其为无损分解。

函数依赖的闭包

函数依赖的闭包：给定一个函数依赖的集合FF，将所有能从FF中推出的函数依赖构成的集合记作该集合的闭包F+F^+。

当且仅当关系RR中的一个函数依赖存在于闭包F+F^+中时，它才成立。

函数依赖的闭包的获取方法：阿姆斯特朗公理

  • 自反律：如果β⊆α\beta\subseteq\alpha，则α→β\alpha\rightarrow\beta。
  • 增补律：如果α→β\alpha\rightarrow\beta，则γα→γβ\gamma\alpha\rightarrow\gamma\beta
  • 传递律：如果α→β\alpha\rightarrow\beta且β→γ\beta\rightarrow\gamma，则α→γ\alpha\rightarrow\gamma。

还有其它几个规则，可以由上面这些推出：

  • 合并律：如果α→β\alpha\rightarrow\beta且α→γ\alpha\rightarrow\gamma，则α→βγ\alpha\rightarrow\beta\gamma。
  • 分解律：如果α→βγ\alpha\rightarrow\beta\gamma，则α→β\alpha\rightarrow\beta且α→γ\alpha\rightarrow\gamma。
  • 伪传递率：如果α→β\alpha\rightarrow\beta且γβ→δ\gamma\beta\rightarrow\delta，则αγ→δ\alpha\gamma\rightarrow\delta。

需要注意的是，这里面αβ\alpha\beta并不是集合意义上的交集，而是并集。

具体算法：每轮循环中，先使用自反律和增补律，然后使用传递率。

属性集合的闭包

属性集合的闭包：将集合α\alpha在函数依赖集合FF下的闭包记作α+\alpha^+。

计算流程：

  • 初始化：结果集合resultresult初始化为α\alpha。
  • 循环以下过程：如果FF中某个函数依赖β→γ\beta\rightarrow\gamma满足β\beta是resultresult的子集，则将γ\gamma添加到resultresult中。

判断属性集合α\alpha是否为超键的方式：判断其闭包α+\alpha^+是否与关系集合RR等价。

判断函数依赖α→β\alpha\rightarrow\beta是否成立（函数依赖是否在函数的闭包中）的方式：判断β⊂α+\beta\subset \alpha^+是否成立。

函数依赖的闭包的获取方法2：对于RR的每一个子集γ\gamma，求它的闭包γ+\gamma^+，且对每一个γ+\gamma^+的子集SS，输出一个函数依赖γ→S\gamma\rightarrow S。所有输出的交集即是函数依赖的闭包。

依赖保持和它的验证方法

依赖保持：在验证分解后的子关系上的函数依赖时，无需进行笛卡尔积即可进行验证。（一个说法是，任意函数依赖中的所有属性都必须在同一个子关系中。）

依赖保持的新定义：将一个表格RR拆分成R1,R2,...,RnR_1, R_2,...,R_n，又将F+F^+中只包含RiR_i中属性的函数依赖的集合称作“FF在RiR_i上的限定”FiF_i，则当(F1∪F2∪...∪Fn)+=F+(F_1\cup F_2\cup ...\cup F_n)^+=F^+时，FF中所有依赖都被F′F'逻辑蕴含，从而实现了依赖保持。

一种避免计算F+F^+的验证依赖保持的方法：

  • 初始时刻result=αresult=\alpha
  • 不断重复以下过程：对于每个RiR_i，t=(result∩Ri)+∩Rit=(result\cap R_i)^+\cap R_i，result=result∪tresult=result\cup t。（这里计算闭包使用的是整个FF）
  • 当resultresult没有变化时，如果resultresult包含β\beta中的所有属性，则α→β\alpha\rightarrow\beta得到保持。

这个不断重复的过程其实相当于计算FiF_i下的resultresult闭包，对每个RiR_i进行重复后得到F′F'下的resultresult闭包。

无关属性

无关属性：在函数依赖集合FF中的某个函数依赖中，删去之后不会影响F+F^+的属性。

无关属性的判定：对于一个函数依赖α→β\alpha\rightarrow\beta，

如果A∈αA\in \alpha且根据FF可以推出(F−{α→β})∪{(α−A)→β}(F-\{\alpha\rightarrow\beta\})\cup\{(\alpha-A)\rightarrow\beta\}，则认为A是无关属性；如果A∈βA\in \beta且根据(F−{α→β})∪{α→(β−A)}(F-\{\alpha\rightarrow\beta\})\cup\{\alpha\rightarrow(\beta-A)\}可以推出FF，则认为A是无关属性。

上面这个“可以推出”判断起来比较复杂，可以通过判断“属性的闭包是否包含新属性”来代替。

检验A∈αA\in \alpha是否是无关属性：只需检查(α−A)→β(\alpha-A)\rightarrow\beta是否可以从FF中推断出（成立）即可。使用FF计算(α−A)+(\alpha-A)^+，如果β⊂(α−A)+\beta\subset (\alpha-A)^+则得证。

检验A∈βA\in \beta是否是无关属性：只需检查从β\beta中去除A之后还能否推出α→A\alpha\rightarrow A。使用F′=(F−{α→β})∪{α→(β−A)}F'=(F-\{\alpha\rightarrow\beta\})\cup\{\alpha\rightarrow(\beta-A)\}计算α\alpha的新闭包α+\alpha^+，如果A∈α+A\in \alpha^+则得证。

正则覆盖

正则覆盖：一个函数集合FF的正则覆盖FcF_c满足如下条件：

  • FF可以推出FcF_c
  • FcF_c可以推出FF
  • FcF_c中的任何函数依赖都不包含无关变量
  • FcF_c中任意两个函数依赖的左侧都两两不同。

正则覆盖的计算方法：

  • 初始时设Fc=FF_c=F
  • 将所有形如α→β1\alpha\rightarrow\beta_1和α→β2\alpha\rightarrow\beta_2合并为α→β1β2\alpha\rightarrow\beta_1\beta_2
  • 在FcF_c中遍历各函数依赖，如果发现一个无关属性，则将其删除。但是每个循环只删除一个。
  • 重复以上过程，直到FcF_c不再发生变化。

BCNF

BC范式（BCNF）：如果F+F^+中的所有函数关系α→β\alpha \rightarrow \beta都满足：

  • α→β\alpha\rightarrow\beta是平凡的（即β⊂α\beta\subset\alpha）
  • 或者α\alpha是关系R的超键

则认为这个关系表RR满足BCNF。当F+F^+是空集的时候，也认为该关系表满足BCNF。

F+F^+可以通过将属性随机组合来判断是否存在函数依赖。

拆分关系RR以满足BC范式：如果关系RR中α→β\alpha\rightarrow\beta不满足BCNF，则将RR分成α∪β\alpha\cup\beta和R−(β−α)R-(\beta-\alpha)。

BCNF的检测方法

检查α→β\alpha\rightarrow\beta是否违反BCNF：如果不是平凡函数依赖，则计算α+\alpha^+，当其为关系RR的超键时认为不违反。

简化的检查方法：只检查一个给定的函数集合FF是否满足BCNF，而不是F+F^+。不过在检测RR的分解是否满足BCNF时不能用这个方法，容易漏检。

分解后的BCNF检测方法：

  1. 遍历FF在RiR_i上的限定（F+F^+中只包含RiR_i中属性的函数依赖的集合）中的所有函数依赖，测试是否满足BCNF。
  2. 或使用原有的函数依赖FF。对于任意一个属性子集α⊆Ri\alpha \subseteq R_i，验证α+\alpha^+不包括Ri−αR_i-\alpha中的任何属性或包括RiR_i中的所有属性。（前者对应BCNF中的“平凡”条件，后者对应“超键”条件。）如果BCNF被某个函数依赖α→β\alpha\rightarrow\beta打破，则一定存在一个α→(α+−α)∩Ri\alpha\rightarrow(\alpha^+-\alpha)\cap R_i在RiR_i上存在。

BCNF的分解算法

BCNF分解算法：

  • 给结果集合赋初值：result={R}result=\{R\}（注意这是一个关系表的集合）
  • 计算F+F^+
  • 如果resultresult中存在一个RiR_i不满足BCNF，则找到其中一个违背BCNF且α∩β=∅\alpha\cap\beta=\varnothing的函数依赖α→β\alpha\rightarrow\beta，将resultresult更新为(result−Ri)∪(Ri−β)∪(α, β)(result-R_i)\cup (R_i-\beta)\cup(\alpha,\ \beta)（即，从resultresult中去掉RiR_i，然后向其中添加Ri−βR_i-\beta和(α,β)(\alpha,\beta)）。循环执行这一步。

3NF

三范式（3NF）：如果F+F^+中的所有函数关系α→β\alpha \rightarrow \beta都满足：

  • α→β\alpha\rightarrow\beta是平凡的（即β⊂α\beta\subset\alpha）
  • 或者α\alpha是关系R的超键
  • 或者β−α\beta-\alpha中的每个属性都包含在RR的某个候选键中

则认为这个关系表RR满足3NF。

3NF的检测方法

3NF检测方法：

  • 只需检测FF中的函数依赖而非F+F^+
  • 使用属性集合的闭包检测对于每个函数依赖α→β\alpha\rightarrow\beta，α\alpha是否为超键。
  • 如果α\alpha不是超键，检测β\beta中的每个属性是否包含在RR的某个候选键中。

3NF的分解算法

3NF分解算法：

  • 获得FF的正则覆盖FcF_c
  • 初始化i=0i=0
  • 对于FcF_c中的每个函数依赖α→β\alpha\rightarrow\beta，如果在1≤j≤i1\leq j\leq i中没有任何一个关系RjR_j包含αβ\alpha\beta，则ii自增1，添加Ri=αβR_i=\alpha\beta；
  • 如果在1≤j≤i1\leq j\leq i中没有任何一个关系RjR_j包含RR的候选键，则ii自增1，添加Ri=R的任意一个候选键R_i=R的任意一个候选键；
  • 如果某个关系包含了另一个关系，则删除被包含的冗余关系；
  • 得到分解后的RiR_i的集合

或者用一种更接近自然语言的方法描述：

初始情况下，分解后的关系表构成的集合为空集。对于FF的正则覆盖中的每个关系α→β\alpha\rightarrow\beta，如果没有任何一个分解后的关系表包含αβ\alpha\beta，则将其作为一个分解后的关系表添加到集合中。遍历结束后，如果没有任何一个分解后的关系表包含RR中的任意一个候选键，则选择一个候选键作为一个分解后的关系表添加到集合中。最后，删除重复的关系表。

多值依赖

多值依赖：将RR的属性分为α\alpha，β\beta和R−α−βR-\alpha-\beta三部分，如果对于任意一对元组t1和t2t_1和t_2，存在t3和t4t_3和t_4满足：

norm-1

则认为α→→β\alpha\rightarrow\rightarrow\beta，同时有α→→R−α−β\alpha\rightarrow\rightarrow R-\alpha-\beta。

注意：如果有α→β\alpha\rightarrow\beta则一定有α→→β\alpha\rightarrow\rightarrow\beta。

多值依赖的闭包：如果记函数依赖和多值依赖的集合为DD，则将所有DD逻辑蕴含的函数依赖和多值依赖的集合称为多值依赖的闭包D+D^+。可以根据其二者的定义计算出多值依赖的闭包。具体规则不做展开。

平凡多值依赖：α∪β=R\alpha\cup\beta=R或者β⊂α\beta\subset \alpha。

第四范式

第四范式（4NF）：所有D+D^+中的形如α→→β\alpha\rightarrow\rightarrow\beta的多值依赖满足以下两个条件之一：α→→β\alpha\rightarrow\rightarrow\beta是平凡的，或者α\alpha是RR的一个超键。

如果一个关系符合第四范式，它一定符合BCNF。

DD在集合RiR_i上的限定DiD_i：包含D+D^+中所有只含RiR_i中属性的函数依赖或者所有形如α→→β∩Ri\alpha\rightarrow\rightarrow\beta\cap R_i的多值依赖，其中α⊆Ri\alpha \subseteq R_i且α→→β∈D+\alpha\rightarrow\rightarrow\beta\in D^+。

4NF分解算法：与BCNF的很像

  • 给结果集合赋初值：result={R}result=\{R\}（注意这是一个关系表的集合）
  • 计算D+D^+，并用DiD_i表示DD在集合RiR_i上的限定
  • 如果resultresult中存在一个RiR_i不满足4NF，则找到其中一个违背4NF且α∩β=∅\alpha\cap\beta=\varnothing的多值依赖α→→β\alpha\rightarrow\rightarrow\beta，将resultresult更新为(result−Ri)∪(Ri−β)∪(α, β)(result-R_i)\cup (R_i-\beta)\cup(\alpha,\ \beta)（即，从resultresult中去掉RiR_i，然后向其中添加Ri−βR_i-\beta和(α,β)(\alpha,\beta)）。循环执行这一步。