关系数据库设计

背景

  • RDB设计工程方法的代表：E-R图方法

    • 绘制 E-R
    • E−R→RDBE-R\rightarrow RDB模式
    • 模式优化

  • RDB设计工程方法的问题

    • E-R质量和设计人员能力水平相关
    • E-R质量难以保证，致使E-R方法设计质量难以保证
    • 其它RDB模式工程设计方法存在类似问题

  • 模式规范化方法的研究状况

    • 提出了模式规范化的标准：为决定因素
      • 1NF,2NF,3NF,BCNF,4NF,5NF,6NF
    • 给出了泛关系分解到具体范式的算法
    • 算法多为Np算法，无法实际执行

  • 规范化方法学习价值

    • 理解不同范式的优缺点
    • 理解相应的模式改进方法
    • 作为重要指导思想指导模式设计

  • 本章讲述关系模式规范化理论、方法

  • 好的关系设计特点

    • 不必存储不必要的重复信息，同时又可以方便地获取信息
    • 同数据本质结构相吻合

第一范式

如果某个域的元素被认为是不可再分的单元，那么这个域就是原子的(atomic)。如果一个关系模式R的所有的属性域都是原子的，我们称关系模式R属于第一范式(first normal form, 1NF)

关系数据库中的所有关系模式均应该满足1NF

原子域

域元素被认为是不可分的单元，称域是原子的

域原子性分析示例：

  • 学号：201106102

  • 学号的编码规则决定了学号可以分段解释。(这是数据的客观特点，不能改变)

  • 学号域是原子的吗？

    • 如果需要DBMS分段解释学号含义，则学号域不是原子域
    • 否则，学号域是原子域

函数依赖

UU 是所有属性的集合，α，β\alpha，\beta是属性的集合。

设 R(U)R(U) 是属性集 UU 上的关系模式， α,β⊆U\alpha,\beta \subseteq U， rr 是 R(U)R(U) 上的任意一个关系实例，如果有

对 ∀t,s∈r\forall t, s \in r，若 t[α]=s[α]t[\alpha] = s[\alpha]，则 t[β]=s[β]t[\beta] = s[\beta]

那么称 “α\alpha 函数决定 β\beta ”，或“ β\beta 函数依赖于α\alpha ”，记作 α→β\alpha \rightarrow \beta

称 α\alpha 为决定因素， β\beta 为被决定因素

  • 如 sno→sname，(sno，cno)→scoresno\rightarrow sname，(sno，cno)\rightarrow score

  • 也就是说，如果有 α\alpha 值相同，就必须有 β\beta 上的值相同。

平凡函数依赖

如果 α→β\alpha \rightarrow \beta ，但 β⊄α\beta \not\subset \alpha，则称其为非平凡的函数依赖，否则(即 β⊆α\beta \subseteq \alpha )称为平凡(trivial)的函数依赖

如 (sno，sname)→sname(sno，sname)\rightarrow sname 是平凡的函数依赖

平凡的函数依赖永远成立

部分函数依赖

在关系模式 R(U)R(U) 中，如果 α→β\alpha\rightarrow\beta，且对于任意 α\alpha 的真子集α′\alpha '，都有 α′↛β\alpha'\not\rightarrow\beta，则称 β\beta 对 α\alpha 完全函数依赖，也就是说，α\alpha 缺少任一属性都无法唯一确定 β\beta，记作α→fβ\alpha \overset f \rightarrow \beta 。否则称为 β\beta 对 α\alpha 部分函数依赖，记作α→pβ\alpha \overset p \rightarrow \beta （也就是说α\alpha 的部分属性就可以唯一确定 β\beta）

例如：

(sno,cno)→fscore(sno,cno)\overset f \rightarrow score

(sno,cno)→psname(sno,cno)\overset p \rightarrow sname

传递函数依赖

在关系模式 R(U)R(U) 中，如果 α→β, β→γ, β↛α, β⊄α\alpha\rightarrow\beta,\,\beta\rightarrow\gamma,\,\beta\not\rightarrow\alpha,\,\beta\not\subset\alpha，则称 γ\gamma 对 α\alpha 传递函数依赖。

函数依赖与码

  • 设 KK 为 R<U,F>R< U, F > 的属性组，若 K→UK\rightarrow U，则称 KK 为 RR 的超码
  • 设 KK 为 R<U,F>R< U, F > 的超码，若 K→fUK\overset f \rightarrow U，则称 KK 为 RR 的候选码
  • 包含在任意一个候选码中的属性，称作主属性

函数依赖的推理规则

  • 除了给定的函数依赖，我们需要考虑模式上成立的所有函数依赖

  • 给定一组函数依赖，是否能导出另外一些函数依赖，或另外的函数依赖是否成立。

逻辑蕴涵

定义

  • 关系模式 RR，FF是其函数依赖集，如果从 FF 的函数依赖能够推出 α→β\alpha\rightarrow\beta ，则称 FF 逻辑蕴涵 α→β\alpha\rightarrow\beta，记作 F├  α→βF├ \,\,\alpha\rightarrow\beta

  • 另一种描述：给定关系模式 RR，如果某一个满足 FF 的关系实例 rr 也满足 ff，则 RR 上函数依赖 ff 被 RR 上的函数依赖集 FF 逻辑蕴涵， F├ fF├ \,f

  • 被 FF 所逻辑蕴涵的函数依赖的全体所构成的集合称作 FF 的函数依赖集的闭包（closure），记作:

    • F+={α→β ∣ F├  α→β }F^+=\{\alpha\rightarrow\beta\,|\,F├ \,\,\alpha\rightarrow\beta\,\}

R(U,F)R(U, F)（关系模式）, U=X,YU = {X, Y}（属性集）, F=X→YF = {X\rightarrow Y}（函数依赖集）

Armstrong公理系统与正确性证明

所有希腊字母都是属性集，所有英文字母都是单个属性。

S1={f ∣ 可用Armstrong公理从F中导出的函数依赖f}S1 = \{ f \,|\,可用Armstrong公理从F中导出的函数依赖f \}

S2={f ∣ 被F所逻辑蕴涵的所有函数依赖f}S2 = \{ f \,|\,被F所逻辑蕴涵的所有函数依赖f \}

  • 正确性(Sound)：用Armstrong公理从F中导出的函数依赖必为F所蕴涵 S1⊆S2S1 \subseteq S2

  • 完备性(Complete)：F所蕴涵的函数依赖都能用Armstrong公理从F中导出 S2⊆S1S2 \subseteq S1

α,β,γ,δ\alpha,\beta,\gamma,\delta 是属性集

rr 是 R<U,F>R<U, F> 上的任一关系，t,s∈rt,s \in r，（t,st,s是 rr 的两个元组）

自反律(reflexivity)

若 β⊆α\beta\subseteq\alpha，则 α→β\alpha\rightarrow\beta

不妨假设 t[α]=s[α]t[\alpha]=s[\alpha]，我们只需要证明 t[β]=s[β]t[\beta]=s[\beta]， 下面的证明类似，就不再写该假设，而是直接当成条件使用。

∵t[α]=s[α] , β⊆α\because t[\alpha]=s[\alpha]\,,\,\beta\subseteq\alpha

∴t[β]=s[β]\therefore t[\beta]=s[\beta]

∴α→β\therefore \alpha\rightarrow\beta

增广律(augmentation)

若 α→β\alpha\rightarrow\beta，则 αγ→βγ\alpha\gamma\rightarrow\beta\gamma

∵不妨假设 t[αγ]=s[αγ]\because 不妨假设\, t[\alpha\gamma] = s[\alpha\gamma]

∴t[α]=s[α],t[γ]=s[γ]\therefore t[\alpha]=s[\alpha],t[\gamma]=s[\gamma]

∵α→β\because \alpha\rightarrow\beta

∴t[β]=s[β]\therefore t[\beta] = s[\beta]

∴t[βγ]=s[βγ]\therefore t[\beta\gamma]=s[\beta\gamma]

∴αγ→βγ\therefore \alpha\gamma\rightarrow\beta\gamma

传递律(transitivity)

若 α→β, β→γ\alpha\rightarrow\beta,\,\beta\rightarrow\gamma，则 α→γ\alpha\rightarrow\gamma

∵α→β,假设 t[α]=s[α]\because \alpha\rightarrow\beta,假设\,t[\alpha]=s[\alpha]

∴t[β]=s[β]\therefore t[\beta]=s[\beta]

∵β→γ\because\beta\rightarrow\gamma

∴t[γ]=s[γ]\therefore t[\gamma] = s[\gamma]

∴α→β\therefore \alpha\rightarrow\beta

合并律(union rule)

若 α→β\alpha \rightarrow \beta ， α→γ\alpha\rightarrow\gamma ，则 α→βγ\alpha\rightarrow\beta\gamma

∵假设 t[α]=s[α]\because 假设\,t[\alpha]=s[\alpha]

∴t[β]=s[β], t[γ]=s[γ]\therefore t[\beta]=s[\beta],\,t[\gamma]=s[\gamma]

∴t[βγ]=s[βγ]\therefore t[\beta\gamma]=s[\beta\gamma]

∴α→βγ\therefore \alpha\rightarrow\beta\gamma

或者使用增广律和传递律：

∵α→β,α→γ\because \alpha \rightarrow \beta, \alpha\rightarrow\gamma

∴α→αβ,αβ→βγ\therefore \alpha\rightarrow\alpha\beta,\alpha\beta\rightarrow\beta\gamma

∴α→βγ\therefore\alpha\rightarrow\beta\gamma

分解律(decomposition rule)

若 α→βγ\alpha\rightarrow\beta\gamma ，则 α→β\alpha\rightarrow\beta 且 α→γ\alpha\rightarrow\gamma

∵γ⊆βγ\because\gamma\subseteq\beta\gamma

∴βγ→γ\therefore \beta\gamma\rightarrow\gamma（自反律）

∵α→βγ\because \alpha\rightarrow\beta\gamma

∴α→γ\therefore \alpha\rightarrow\gamma（传递律）

同理 α→β同理\,\alpha\rightarrow\beta

伪传递律(pseudotransitivity rule)

若 α→β\alpha \rightarrow \beta ，γβ→δ\gamma\beta \rightarrow \delta ，则 γα→δ\gamma\alpha \rightarrow \delta

∵α→β\because \alpha\rightarrow\beta

∴αγ→γβ\therefore \alpha\gamma\rightarrow\gamma\beta（增广律）

∵γβ→δ\because \gamma\beta\rightarrow\delta

∴γα→δ\therefore \gamma\alpha\rightarrow\delta（传递律）

Armstrong公理与闭包问题

一般来说，F⊂F+F\subset F^+，我们希望通过Armstrong公理和 FF 找出 F+F^+

但这其实是一个NP问题，也就是说，对于 α→β∈F+\alpha\rightarrow\beta\in F^+，对于所有n个属性，该属性可能在属性集 α\alpha 中，也可能在属性集 β\beta 中，或者都不在。也就是说，α,β\alpha,\beta 各有 2n2^n 种可能性，然后在搜索过程中我们要将所有可能的属性集进行排列组合，一共就有 2n×2n=22n2^n\times2^n=2^{2n} 种可能性。显然，指数级的时间复杂度。

属性集的闭包（Attribute Closure）

令 α\alpha 为属性集，将函数依赖集 FF 下被 α\alpha 函数确定的所有属性的集合称作 FF 下 α\alpha 的闭包，记作 αF+\alpha^+_F

aF+={A ∣ a→A能由F出发根据Armstrong公理导出}a^+_F= \{ A \,|\, a \rightarrow A能由F出发根据Armstrong公理导出 \}

示例：

R<U,F>R< U, F >， 属性集 U={A,B,C}U=\{A,B,C\}，

函数依赖集 F={A→B，B→C}F=\{A \rightarrow B，B \rightarrow C\}

则

AF+={A,B,C}A^+_F = \{A,B,C\}

BF+={B,C}B^+_F = \{B,C\}

CF+={C}C^+_F = \{C\}

函数依赖集的闭包转化为属性集的闭包

判定 α→β\alpha\rightarrow \beta 是否能由 FF 根据Armstrong公理导出，可转化为求 αF+\alpha^+_F ，判定 β⊆αF+\beta \subseteq \alpha^+_F是否成立

算法(计算基于函数依赖集 FF 的属性集 α\alpha 的闭包)

属性集闭包算法的完备性(算法能够找出 aF+a^+_F 中的全部属性)

  • 在算法执行过程中，如果存在某个属性应该属于 aF+a^+_F ，但是不属于result，则必定存在函数依赖 β→γ(b⊆result)\beta \rightarrow \gamma(b \subseteq result) 并且 γ\gamma 中至少有一个属性不在result中。

  • 当算法结束时，所有函数依赖均已被处理过，γ\gamma 中的属性都已经加到result中。因此我们可以确定 aF+a^+_F中的所有属性都在result中。

示例

R<U，F>,U=(A,B,C,G,H,I),F={A→B,A→C,CG→H,CG→I,B→H}R< U， F >, U = (A, B, C, G, H, I), F = \{A\rightarrow B, A\rightarrow C, CG\rightarrow H, CG\rightarrow I, B\rightarrow H\}，计算 (AG)F+(AG)^+_F

R<U,F>,U=(C,T,H,R,S),F={C→T,HR→C,HT→R,HS→R}R< U, F >, U = (C, T, H, R, S),F = \{C\rightarrow T, HR\rightarrow C, HT\rightarrow R, HS\rightarrow R\}

问题：HR是候选码吗？HS呢？

(HR)F+={HRCT}(HR)^+_F=\{HRCT\}，所以HR不是候选码。

(HS)F+={HSRCT}(HS)^+_F=\{HSRCT\} 且 HF+={H},SF+={S}H^+_F=\{H\},S^+_F=\{S\}，所以HS是候选码

Armstrong公理完备性证明

  • Armstrong公理完备性的含义：F+F^+ 中的每一个函数依赖，必定可以从 FF 出发，根据Armstrong公理推导出来。

  • 要证明完备性，首先计算 F+F^+，但是计算 F+F^+，是一个NP问题。因此需要用到属性集的闭包。

  • Armstrong公理完备性证明：证明完备性的的逆否命题：即如果函数依赖性 α→β\alpha\rightarrow\beta 不能从 FF 出发根据Armstrong公理推出，则 α→β\alpha\rightarrow\beta 一定不能为 FF 所逻辑蕴含。证明分三步。

    • 一个命题等价于其逆否命题

证明如下：

  1. 若 V→WV\rightarrow W 成立，且 V⊆αF+V\subseteq \alpha_F^+，则 W⊆αF+W\subseteq \alpha_F^+

    • 证明：因为：α→α+,V⊆αF+\alpha \rightarrow \alpha^+,V\subseteq \alpha_F^+，所以 α→V\alpha \rightarrow V 成立；V→WV\rightarrow W，所以 α→W\alpha \rightarrow W成立，所以 W⊆αF+W\subseteq \alpha_F^+。

  2. 构造一张二维表 rr，它由两个元组构成，可以证明 rr 必定是关系模式 R<U,F>R<U,F> 的一个关系实例，即 FF 中的所有函数依赖在 rr 上成立。(U是属性集)

​ aF+a_F^+ U−aF+U - a_F^+

​ 11……….1 00……….0

​ 11……….1 11……….1

假设 rr 不是 R<U,F>R<U,F> 的关系实例。必定由于 V→W∈FV\rightarrow W\in F且 V→WV\rightarrow W在 rr 上不成立导致的。由于 rr 的特殊构造，如果 V→WV\rightarrow W 在 rr 上不成立，只能 V⊆F+V\subseteq F^+，而 WW 不是 aF+a_F^+ 的子集，可是由上一步得知，W⊈F+W\not\subseteq F^+ 。所以r必定是关系模式 R<U,F>R<U,F> 的一个关系实例。

  1. 若 α→β\alpha\rightarrow\beta 不能从 FF 出发由Armstrong公理推出，则 β\beta 不是 aF+a_F^+ 的子集，因此，必有 β\beta 的真子集 β’\beta’ 满足 β⊆U−aF+\beta \subseteq U - a_F^+，则 α→β\alpha\rightarrow\beta 在 rr 中不成立，即 α→β\alpha\rightarrow\beta 必不为 FF 所逻辑蕴含。

补充：候选码的求解理论和算法

属性集的闭包包含了所有属性，则说明这是超码，只有当其所有可能的真子集都不是超码，这才是候选码。这是一个NP问题。

如何判断一个属性集是否候选码。

下面我们给出简易的方法：

对于给定的关系模式 R(U,F)R(U,F)，可将其属性分为4类：

  • L类：仅出现在F的函数依赖左部的属性

  • R类：仅出现在F的函数依赖右部的属性

  • N类：在F的函数依赖两边均未出现的属性

  • LR类：在F的函数依赖两边均出现的属性

定理1：对于给定的关系模式 R(U,F)R(U,F) ，若 α(α⊆U)\alpha (\alpha \subseteq U) 是L类属性，则 α\alpha 必为 RR 的任意一个候选码的成员。

  • 例：设关系模式 R(U,F)，U={A，B，C，D}，F={D→B，B→D，AD→B，AC→D}R(U,F)，U = \{A，B，C，D\}，F = \{D \rightarrow B，B \rightarrow D，AD \rightarrow B，AC \rightarrow D\}，求R的候选码

  • 解：AA、CC 是 L类属性， ACAC 必是 RR 的一个候选码的成员，(AC)F+={ACDB}(AC)_F^+ = \{ACDB\}，(A)F+={A}(A)_F^+ = \{A\}，(C)F+={C}(C)_F^+ = \{C\}，所以 ACAC 是 RR 的唯一候选码。（唯一性的确定可以参考下面的推论）

推论：对于给定的关系模式 R(U,F)R(U,F) ，若 α(α⊆U)\alpha (\alpha \subseteq U) 是L类属性，且 αF+\alpha_F^+ 包含了U中的全部属性，则 α\alpha 一定是R(U,F)R(U,F) 的唯一候选码

定理2：对于给定的关系模式 R(U,F)R(U,F) ，若 α(α⊆U)\alpha (\alpha \subseteq U) 是R类属性，则 α\alpha 不包含在 R(U,F)R(U,F) 任何候选码中

定理3：对于给定的关系模式 R(U,F)R(U,F) ，若 α(α⊆U)\alpha (\alpha \subseteq U) 是N类属性，则 α\alpha 必包含在 R(U,F)R(U,F) 的任意一个候选码中

  • 示例1：设有关系模式 R(U,F)，U={A，B，C，D，E，P}，F={A→D，E→D，D→B，BC→D，DC→A}R(U,F)，U = \{A，B，C，D，E，P\}，F = \{A \rightarrow D，E \rightarrow D，D \rightarrow B，BC \rightarrow D，DC \rightarrow A\}，求 RR 的候选码

  • 解：CECE 是 L 类属性，CECE 必在候选码中，PP 是 N 类属性，PP 也必须在候选码中，因为 (CEP)F+={ABCDEP}(CEP)_F^+ = \{ABCDEP\}，且CEPCEP 的真子集都不是超码， 所以 CEPCEP 是唯一的候选码

  • 示例2：假设有关系模式 R(U,F)，U={A，B，C，D，E}，F={A→D，E→D，D→B，BC→D，DC→A}R(U,F)，U = \{A，B，C，D，E\}，F = \{A \rightarrow D，E \rightarrow D，D \rightarrow B，BC \rightarrow D，DC \rightarrow A\}，求关系模式 RR 的候选码

  • 解：CECE 未在函数依赖的右侧出现，CECE 一定是候选码属性，(CE)F+={ABCDE}(CE)_F^+ = \{ABCDE\}，且 CECE 的真子集都不是超码，CECE 是关系模式 RR 的唯一候选码

  • 示例3：假设有关系模式R(U,F)，U={A，B，C，D，E}，F={A→BC，CD→E，B→D，E→A}R(U,F)，U = \{A，B，C，D，E\}，F = \{A \rightarrow BC，CD \rightarrow E，B \rightarrow D，E \rightarrow A\}，求 RR 的所有候选码

  • 解：ABCDEABCDE 在 FF 的各个函数依赖的左侧和右侧均出现过（都是LR），因此，候选码可能包含 ABCDEABCDE

    • 可以除去 ABCDABCD 属性，组成候选码的属性可能是 EE，(E)F+={ABCDE}(E)_F^+ = \{ABCDE\}，EE 是候选码
    • 因为 CD→ECD\rightarrow E，所以可除去ABE，候选码的属性可能是CD，(CD)F+={ABCDE}(CD)_F^+ = \{ABCDE\}，CF+={C}，DF+={D}C_F^+ = \{C\}，D_F^+ = \{D\}，CDCD 是候选码
    • 可除去 ADEADE，候选码的可能属性是 BCBC，(BC)F+={ABCDE}(BC)_F^+ = \{ABCDE\}，BF+={BD}B_F^+ = \{BD\}， CF+={C}C_F^+ = \{C\}，BCBC是候选码
    • 还可除去 BCDEBCDE，候选码为 AA
    • 这道题的主要收获就是我们往往可以通过一个确定的候选码以及与这个候选码相关的函数依赖来推断其他的候选码。如做这道题时我先确定了 CDCD，这个是最显然的，然后依据 B→DB\rightarrow D 推知 BCBC 也是候选码，然后由A→BCA\rightarrow BC 知 AA 是候选码，又由 E→AE\rightarrow A 知 EE 是候选码。

正则覆盖

假设在一个关系模式上有一个函数依赖集 FF。当用户对于关系进行更新时，数据库系统将保证此操作不会破坏任何一个函数依赖

可以通过测试与给定函数依赖集有相同闭包的简化集的方式，来降低检测的开销

函数依赖集的等价和覆盖

函数依赖集 F,GF,G，若 F+=G+F^+= G^+，则称 FF 与 GG 等价。

若 FF 与 GG 等价，则称 FF 是 GG 的一个覆盖， GG 是 FF 的一个覆盖。

F+=G+  ⟺  F⊆G+,G⊆F+F^+ = G^+ \iff F \subseteq G^+,G \subseteq F^+

无关属性(extraneous attributes)

如果去除一个函数依赖中的属性，不会改变该函数依赖集的闭包，则称该属性是无关的(extraneous)

对于函数依赖集 FF 及 FF 中函数依赖 α→βα\rightarrowβ。属性 AA 在 α\alpha 中是无关的，如果 A∈αA∈α，并且 F├(F–{α→β})∪{(α−A)→β}F├ (F – \{\alpha\rightarrow\beta\})∪\{(\alpha- A) \rightarrow \beta\}。也就是说能由 FF 推出 (F–{α→β})∪{(α−A)→β}(F – \{α\rightarrowβ\})∪\{(α- A) \rightarrowβ\}

  • 为什么不考虑(F–{α→β})∪{(α−A)→β}├F(F – \{α\rightarrowβ\})∪\{(α- A) \rightarrowβ\}├ F ?
  • 我们假设右面的函数依赖集为 GG，那么对于 FF，F{−,−,α→β,−,−}F\{-,-,\alpha \rightarrow\beta,-,-\}，对于G，G{−,−,(α−A)→β,−,−}G\{-,-,(\alpha-A)\rightarrow\beta,-,-\}，显然如果 (α−A)→β(\alpha-A)\rightarrow\beta，那么一定有 α→β\alpha\rightarrow\beta

对于函数依赖集 FF 及 FF 中函数依赖 α→βα\rightarrowβ。属性 AA 在 β\beta 中是无关的，如果 A∈βA∈\beta，并且 (F–{α→β})∪{α→(β−A)}├ F(F – \{α\rightarrowβ\})∪\{α \rightarrow (β-A)\}├\,F。也就是说能由 (F–{α→β})∪{α→(β−A)}(F – \{α\rightarrowβ\})∪\{α \rightarrow (β-A)\} 推出 FF

  • 为什么不考虑 F├(F–{α→β})∪{α→(β−A)}F├ (F – \{α\rightarrowβ\})∪\{α \rightarrow (β-A)\}
  • 同上，α→β\alpha\rightarrow\beta，A∈βA\in \beta，则必有 α→(β−A)\alpha\rightarrow (\beta-A)

无关属性的核心：能够被函数依赖集 FF 逻辑蕴涵的函数依赖，不必出现在F中

示例

F1={AB→C,A→C}F_1 = \{AB \rightarrow C,A \rightarrow C\}中

F2={AB→CD，A→C}F_2 = \{AB \rightarrow CD， A \rightarrow C\}中

请找出上述两个函数依赖集中的无关属性

在 F1F_1 中，BB 在 AB→CAB \rightarrow C 中是无关属性。

在 F2F_2 中，CC 在 AB→CDAB \rightarrow CD 中是无关属性。

检验无关属性的方法

考虑 α→βα\rightarrow β 中的属性 AA

  • 如果 A∈αA\in α，令 γ=α−{A}\gamma = α- \{A\}，并计算 γ→β\gamma\rightarrow β是否可以由 FF 推出，即计算在函数依赖集 FF 下的 γF+\gamma_F^+，如果 γF+\gamma_F^+ 包含 ββ 的所有属性，则 AA 在 αα 中是无关的
  • 如果 A∈βA\in β，F’=(F−{α→β})∪{α→(β−A)}F’= ( F - \{α\rightarrow β\})∪\{α\rightarrow (β - A) \} 检验 α→Aα\rightarrow A 是否能由 F’F’ 推导出，即计算函数依赖集F’F’ 下的 αF’+α_{F’}^+，如果 αF’+α_{F’}^+ 包含 A，则A在 ββ 中是无关的
  • 注意处理无关属性的时候一次只处理一个函数依赖。

小技巧：若 α→βγ,β→γ\alpha\rightarrow\beta\gamma,\beta\rightarrow\gamma，那么显然对于第一个式子， γ\gamma是无关属性，因为 α→γ\alpha\rightarrow\gamma 是可以推导出来的。

若 α→βγ,αβ→...\alpha\rightarrow\beta\gamma,\alpha\beta\rightarrow...可以考虑 β\beta 是无关属性

样例

F={AB→CD,A→E,E→C}F=\{AB \rightarrow CD, A \rightarrow E, E \rightarrow C\}，CC 在 AB→CDAB \rightarrow CD上是否是无关属性？

F’={AB→D,A→E,E→C}F’=\{AB \rightarrow D, A \rightarrow E, E \rightarrow C\} 下ABAB 的属性闭包为 {ABCDE}\{ABCDE\}，包含 CC，因此C在 AB→CDAB \rightarrow CD上是无关属性

或者，显然 A→CA\rightarrow C，那么 AB→CAB\rightarrow C，因此 CC 在 AB→CDAB \rightarrow CD上是无关属性

正则覆盖（Canonical Cover）

满足下列条件的函数依赖集 FF 称为正则覆盖，记作 FcF_c：

  • FcF_c 与 FF 等价

  • FcF_c 中任何函数依赖都不含无关属性

  • FcF_c 中函数依赖的左半部都是唯一的（比如A→B,A→CA\rightarrow B,A\rightarrow C，这种情况就不满足）

注意：正则覆盖未必唯一

计算算法

算法—计算函数依赖集 FF 的正则覆盖 FcF_c

Fc=FF_c = F

REPEAT

使用合并律将 FcF_c 中 α→βα\rightarrow β 和 α→γα\rightarrow \gamma合并为 α→βγα \rightarrow β\gamma （保证左半边是唯一的）

找出在含无关属性的函数依赖 α→βα\rightarrow β，删除 α→βα\rightarrow β 中的无关属性

UNTIL FcF_c 不再改变

注意：

  1. 检查无关属性是基于当前函数依赖集合中的函数依赖，而不是原始的 FF

    • 也就是说，检查无关属性的属性集是基于上一次的属性集的处理结果

  2. 不能同时讨论一个函数依赖中的两个属性的无关性，一次只能讨论一个属性

  3. 如果一个函数依赖的右半部只包含一个属性，例如， A→CA \rightarrow C，并且右边的属性是无关的，那么将得到一个右部为空的函数依赖，这样的函数依赖应该删除

从某种意义上说，FcF_c 是最小的，它不含无关属性，并且具有相同左半部的函数依赖都已经被合并，所以验证 FcF_c 比验证 FF 本身更容易

最小覆盖

最小覆盖定义(补充):

关系模式 R(U,F)R(U,F)，FF 的最小覆盖记为 FmF_m，FmF_m 满足： Fm  ⟺  FFm\iff F，并且：

  1. FmF_m 不含无关属性

  2. FmF_m中函数依赖右端属性是唯一的

示例： R(U,F),U={A,B,C}，F={A→BC,B→AC,C→AB}R(U,F) , U = \{A,B,C\}，F=\{A→BC,B→AC,C→AB\}

  • Fc/Fm：A→B，B→C，C→AF_c/F_m：A\rightarrow B，B\rightarrow C，C\rightarrow A

  • Fc/Fm：A→C，C→B，B→AF_c/F_m ： A→C，C→B，B→A

  • Fc：A→BC，B→A,C→AF_c ： A\rightarrow BC，B\rightarrow A,C\rightarrow A

  • Fm：A→B,A→C，B→A,C→AF_m ： A\rightarrow B, A\rightarrow C，B\rightarrow A,C\rightarrow A

正则覆盖样例

F={A→BC，B→C，A→B，AB→C}F = \{A \rightarrow BC，B\rightarrow C，A\rightarrow B，AB\rightarrow C\}，计算 FcF_c

  • 合并 A→BCA\rightarrow BC 和 A→BA\rightarrow B 为 A→BCA\rightarrow BC

    • F1={A→BC，B→C，AB→C}F_1 = \{A\rightarrow BC，B\rightarrow C，AB\rightarrow C\}

  • BB 在 AB→CAB\rightarrow C 中是无关的

    • F2={A→BC，B→C，A→C}F_2 = \{A\rightarrow BC，B\rightarrow C，A\rightarrow C\}

  • 合并 A→BCA\rightarrow BC 和 A→CA\rightarrow C 为 A→BCA\rightarrow BC

    • F3={A→BC，B→C}F_3 = \{A\rightarrow BC，B\rightarrow C\}

  • CC 在 A→BCA\rightarrow BC 中是无关的

    • Fc={A→B，B→C}F_c = \{A\rightarrow B，B\rightarrow C\}

示例2

F={AB→CE，A→C，GP→B，EP→A，CDE→P，HB→P，D→HG，ABC→PG}F=\{AB \rightarrow CE，A \rightarrow C，GP \rightarrow B，EP \rightarrow A，CDE \rightarrow P，HB \rightarrow P，D \rightarrow HG，ABC \rightarrow PG\}，求FcF_c

  • 没有可以合并的函数依赖

  • 在 AB→CEAB \rightarrow CE 中，因为 A→CA \rightarrow C，所以C是无关属性

    • F1={AB→E，A→C，GP→B，EP→A，CDE→P，HB→P，D→HG，ABC→PG}F_1 = \{AB \rightarrow E，A \rightarrow C，GP \rightarrow B，EP \rightarrow A，CDE \rightarrow P，HB \rightarrow P，D \rightarrow HG，ABC \rightarrow PG\}

  • 因为 A→C，ABC→PGA \rightarrow C， ABC \rightarrow PG中C是无关的

  • Fc={AB→E，A→C，GP→B，EP→A，CDE→P，HB→P，D→HG，AB→PG}F_c = \{AB \rightarrow E，A \rightarrow C，GP \rightarrow B，EP \rightarrow A，CDE \rightarrow P，HB \rightarrow P，D \rightarrow HG，AB \rightarrow PG\}

示例3

模式 R(U,F)，U={A，B，C}，F={A→BC,B→AC,C→AB}R(U,F)，U = \{A，B，C\}，F=\{A→BC, B→AC, C→AB\}

正则覆盖有多个：

Fc1={A→B,B→C,C→A}F_{c1}=\{A→B, B→C, C→A\}

  • F={A→BC,B→AC,C→AB}F=\{A→BC, B→AC, C→AB\}

    F1={A→B,B→AC,C→AB}F_1=\{A→B, B→AC, C→AB\}

    F2={A→B,B→C,C→AB}F_2=\{A→B, B→C, C→AB\}

    Fc={A→B,B→C,C→A}F_c=\{A→B, B→C, C→A\}

Fc2={A→B,B→AC,C→B}F_{c2}=\{A→B, B→AC, C→B\}

Fc3={A→C,C→B,B→A}F_{c3}=\{A→C, C→B , B→A\}

Fc4={A→C,B→C,C→AB}F_{c4}=\{A→C, B→C, C→AB\}

Fc5={A→BC,B→A,C→A}F_{c5} = \{A→BC, B→A, C→A\}

示例4

F={E→G，G→E，F→EG，H→EG，FH→E}F=\{E → G，G → E，F → EG，H → EG，FH → E\}，计算 FcF_c

1、无需合并

2、在 FH→EFH → E 中，FF 是无关属性，因此，F1={E→G，G→E，F→EG，H→EG}F_1=\{E → G，G → E，F → EG，H → EG\}

3、在 F1F_1 中， F→EGF → EG 和 H→EGH → EG 中，EGEG 均为无关属性

最终： Fc1={E→G，G→E，F→G，H→G}F_{c1}= \{E → G，G → E，F → G，H → G\}

​ Fc2={E→G，G→E，F→G，H→E}F_{c2}= \{E → G，G → E，F → G，H → E\}

​ Fc3={E→G，G→E，F→E，H→E}F_{c3}= \{E → G，G → E，F → E，H → E\}

​ Fc4={E→G，G→E，F→E，H→G}F_{c4}= \{E → G，G → E，F → E，H → G\}

示例5

关系模式 R，U={A,B,C,D,E}R，U = \{A,B,C,D,E\}，有两个函数依赖集 FF 和 GG，F={A→B，AB→C，D→AC，D→E}F = \{A → B，AB → C，D → AC，D → E\} 和 G={A→BC,D→AE}G = \{A → BC,D → AE\} ，FF 和 GG 是否等价？

关系模式的设计问题

示例

考虑为管理职工的级别和工资信息而设计一个关系模式(主码：职工姓名，假设职工不重名)

  • 信息的不可表示问题

    • 插入异常：如果没有职工具有8级工资，则8级工资的工资数额就难以插入
    • 删除异常：如果仅有职工赵明具有4级工资，如果将赵明删除，则有关4级工资的工资数额信息也随之删除了

  • 信息的冗余问题

    • 数据冗余：职工很多，工资级别有限，每一级别的工资数额反复存储多次
    • 更新异常：如果将5级工资的工资数额调为650，则需要找到每个具有5级工资的职工，逐一修改

解决之道：分解

模式分解

模式分解的定义

  • 函数依赖集合 F_i = \{\alpha \rightarrow \beta \,|\, \alpha \rightarrow \beta \in F^+ \and (\alpha\, \beta) \subseteq U_i\}称为 FF 在 UiU_i 上的投影

  • 关系模式 R<U,F>R<U , F> 的一个分解是指 ρ={R1<U1,F1>,R2<U2,F2>,…,Rn<Un,Fn>}\rho = \{R_1<U_1 , F_1> , R_2<U_2 , F_2>, … , R_n<U_n , F_n>\}

其中 U=U1∪U2∪…∪UnU= U_1 \cup U_2 \cup … \cup U_n，并且没有 Ui⊆Uj，1≤i，j≤nU_i \subseteq U_j，1≤i，j ≤n， FiF_i 是 FF 在 UiU_i 上的投影，称为限定(restriction)

  • 分解的基本代数运算

    • 投影
    • 自然连接

  • 分解的要求

    • 无损连接分解（分解的底线，必须保证）
    • 保持函数依赖（尽量保持）

模式分解中的问题

有损与无损

原来的关系得不到正确的还原。

函数依赖的保持

某些关系丢失（如 B→CB\rightarrow C丢失）

无损连接分解

关系模式 R<U,F>，U=U1∪U2∪…∪UnR<U , F> ， U = U_1 \cup U_2 \cup … \cup U_n

ρ={R1<U1,F1>,R2<U2,F2>,…,Rn<Un,Fn>}\rho = \{R_1<U_1 , F_1> , R_2<U_2 , F_2>, … , R_n<U_n , F_n>\} 是 R<U,F>R<U , F> 的一个分解，ρ\rho 是 R<U,F>R<U , F> 的一个关系实例，定义 mρ(r)=⋈i=1n∏Ui(r)m_{\rho}(r) = \overset {n} {\mathop{\bowtie } \limits_{i=1} }∏U_i(r)，若对于 R<U,F>R<U , F> 的任一个关系实例 rr ，都有 r=mρ(r)r = m_{\rho}(r)，则称 rr 是 R<U,F>R<U , F> 的一个无损连接分解。

无损连接分解判断-表格法

设关系模式 R(U,F)，U=A1,…,AnR(U,F)，U = {A_1,…,A_n}，RR 的一个分解 ρ={R1,…,Rk}\rho = \{R_1,…,R_k\}。无损连接分解表格法的判断步骤如下：

  • 构造一张 kk 行 nn 列的表格，每列对应一个属性 Aj(1≤j≤n)A_j(1≤j≤n)，每行对应一个模式 Ri(1≤i≤k)R_i(1≤i≤k)。如果 AjA_j 在 RiR_i 中，那么在表格的第 ii 行第 jj 列处填上符号 aja_j，否则填上符号 bijb_{ij}。

  • 把表格看成模式 RR 的一个关系实例，反复检查 FF 中每个 ff 在表格中是否成立，若不成立，则修改表格中的元素。修改方法如下：

    • 对于 FF 中一个 f：α→βf： \alpha \rightarrow \beta ，如果表格中有多行在 α\alpha 分量上相等，在 β\beta 分量上不相等，那么把这些行在 β\beta 分量上改成相等：如果 β\beta 的分量中有一个是 aja_j，那么另一个也改成 aja_j；如果没有 aja_j，那么用其中的一个 bijb_{ij} 替换另一个(尽量把 ijij改成较小的数，亦即取 ii 值较小的那个)。

  • 若在修改的过程中，发现表格中有一行全是 α\alpha，即 α1,α2,…,αn\alpha_1,\alpha_2,…,\alpha_n，那么可立即断定分解 rr 相对于 FF 是无损连接分解，此时不必再继续修改。若经过多次修改直到表格不能修改时，发现表格中不存在有一行全是 α\alpha 的情况，那么分解就是有损的。

示例

已知 R<U,F>，U={A,B,C,D,E}，F={A→C,B→C,C→D,DE→C,CE→A}R<U,F>，U = \{A,B,C,D,E\}，F = \{A→C,B→C,C→D,DE→C,CE→A\}，RR 的一个分解为 R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)R_1(AD)，R_2(AB)，R_3(BE)，R_4(CDE)，R_5(AE)，判断这个分解是否具有无损连接性。

表格初始化如上图，对于 A→CA \rightarrow C，在 R1,R2,R5R_1,R_2,R_5 上属性 AA 列的值都是 a1a_1，则将对应属性CC 那一列的值改成一样的，列中没有 aa，所以将这三行在该列上的值都改为 b13b_{13}。

改完后如下。

对于 B→CB \rightarrow C， 在 R2,R3R_2,R_3 上属性 BB 列的值都是 a2a_2，则将对应属性CC 那一列的值改成一样的，列中没有 aa，所以将这两行在该列上的值都改为 b13b_{13}。

改完后如下。

以此类推。

改完后：

说明分解是无损的。

无损连接分解判断-快速法

前提：分解后的关系模式只有两个

在函数依赖约束下，是必要条件，可能有多值依赖

关系模式 R(U,F)R(U,F) 的分解 ρ={R1，R2}\rho=\{R_1，R_2\}，则 ρ\rho 是一个无损连接分解的充分条件是R1∩R2→R1R_1∩R_2\rightarrow R_1 或 R1∩R2→R2R_1∩R_2\rightarrow R_2 成立，或：R1∩R2→R1−R2R_1∩R_2\rightarrow R_1 - R_2 或 R1∩R2→R2−R1R_1∩R_2\rightarrow R_2 - R_1

（R1,R2R_1,R_2表示两个关系模式中的属性）

示例

R(U,F)，U={A,B,C},F={A→B},r={R1(AB),R2(AC)}R(U,F)，U = \{A, B, C\}, F=\{A \rightarrow B\}, r=\{R_1(AB), R_2(AC)\}

R1∩R2=A,R1－R2=BR_1∩R_2 = A, R_1－R_2 = B

由 A→BA \rightarrow B ，得到 ρ\rho 是无损连接分解

保持函数依赖的分解

给定关系模式 R(U,F)R(U,F)，γ\gamma 是 UU 的子集，函数依赖集合 FF 在 γ\gamma 上的投影定义为

\Pi_{\gamma}(F) =\{\alpha \rightarrow \beta \,|\, \alpha\rightarrow \beta \in F^+ \and \alpha\beta \subseteq \gamma\}

设 ρ={R1,R2,…,Rn}\rho = \{R_1, R_2, …, R_n\} 是关系模式 R<U,F>R<U , F> 的一个分解，如果 F+=(∏R1(F)∪…∪∏Rn(F))+F^+ = (∏R_1 (F)\cup … \cup ∏R_n (F))^+（两个闭包相等），则称 ρ\rho 是保持函数依赖的分解

判定保持依赖

通过检查 FF 中的每一个函数依赖都在分解后的某一个关系上成立，可以判断这个分解是否是保持依赖的。

但是，有时分解是保持依赖的，但是 FF 上的一个依赖不在分解后的任何一个关系上成立，也有可能是保持依赖的分解。只要 F+=(∏R1(F)∪…∏Rn(F))+F^+ = (∏R_1 (F)\cup … ∏R_n (F))^+ 即可。因此这个验证只能是充分条件，必须寻找其他的判断方法。

为了避免计算 F+F^+，给出一种更有效的算法。思想如下：通过使用修改后的属性闭包的形式，判断 FF 上的每一个函数依赖 α→βα\rightarrow β 在分解中是否被保持。

例如对于 R(U,F)，U={A,B,C}，F={A→B,B→C}R(U,F)，U = \{A, B, C\}，F= \{A\rightarrow B , B\rightarrow C\} 的分解 ρ{<{AB},{A→B}>,<{AC},{A→C}>}\rho\{<\{AB\},\{A\rightarrow B\}>,<\{AC\},\{A\rightarrow C\}>\}

我们只需要判断：B→C∈{A→B，A→C}+B\rightarrow C\in \{A\rightarrow B， A\rightarrow C\}^+ 是否成立

也就是判断 C∈B{A→B，A→C}+C\in B^+_{\{A\rightarrow B， A\rightarrow C\}}，也就是属性 BB 在该属性集下的闭包是否包含 CC

算法

模式分解示例

示例1：设关系模式 R<U,F>R<U, F>，其中 U={A,B,C,D,E}，F＝{A→BC，C→D，BC→E，E→A}U=\{A, B, C, D, E\}，F＝\{A→BC，C→D，BC→E，E→A\}，则分解 ρ={R1(ABCE)，R2(CD)}ρ=\{R_1(ABCE)，R_2(CD)\} 满足以下哪一条?

–A．具有无损连接性、保持函数依赖

–B．不具有无损连接性、保持函数依赖

–C．具有无损连接性、不保持函数依赖

–D．不具有无损连接性、不保持函数依赖

A

示例2：给定关系模式 R<U,F>，U={A,B,C,D,E}，F＝{B→A，D→A，A→E，AC→B}R<U, F>，U=\{A, B, C, D, E\}，F＝\{B→A，D→A，A→E，AC→B\}，其候选码为？则分解 ρ={R1(ABCE)，R2(CD)}ρ=\{R_1(ABCE)，R_2(CD)\} 满足？

候选码为 CDCD ，不具有无损连接性、不保持函数依赖

B→A，A→E，AC→BB→A，A→E，AC→B 在 R1R_1上成立，D→AD→A 在 R1R_1 和 R2R_2 上都不成立，因此需做进一步判断。

对于 D→AD→A 应用保持依赖算法：

Result = D

对R1R_1，result∩R1=∅result∩R_1 = \emptyset，tt为 ∅\emptyset，result = D

再对 R2R_2，result∩R2=Dresult∩R_2 = D，(D)+={ADE}，t=(D)+∩R2=D(D)^+ = \{ADE\} ，t = (D)^+ ∩R_2 = D，result = D

一个循环后result未发生变化，因此最后result = D，并未包含 AA，所以 D→AD→A 未被保持，该分解不是保持依赖的。

示例3：给定关系模式 R(U,F)，U={A,B,C,D,E,F}，F={A→BC,CD→E,B→D,BE→F,EF→A}R(U, F)，U =\{A,B,C,D,E,F\}，F = \{A → BC, CD → E, B → D, BE → F, EF → A\}，请说明下列分解是否是无损连接分解？是否是保持依赖的分解？ρ={R1(ABCD)，R2(EFA)}ρ= \{R_1(ABCD)，R_2(EFA)\}

判断无损连接分解：R1∩R2={A},AF+={A,B,C,D,E,F}R_1 ∩ R_2 = \{A\},A^+_F = \{A, B, C, D, E, F\}，而 A→R1A → R_1 ，所以是无损连接分解

判断保持依赖的分解：观察 CD→ECD → E 和 BE→FBE → F 是否被保持？CD→ECD → E 和 BE→FBE → F 没有被保持

示例4：给定关系模式 R(U,F)，U={A,B,C,D,E,F}，F={A→BC,CD→E,B→D,BE→F,EF→A}R(U, F)，U =\{A,B,C,D,E,F\}，F = \{A → BC, CD → E, B → D, BE → F, EF → A\}，请说明下列分解是否是无损连接分解？是否是保持依赖的分解？ρ={(ABC)，(BD)，(BEF)}ρ = \{(ABC)，(BD)，(BEF)\}

非无损

判断保持依赖的分解：观察 CD→ECD → E 和 EF→AEF →A 是否被保持？CD→ECD → E 和 EF→AEF → A 没有被保持

范式

  • 范式是对关系模式的不同数据依赖程度的要求

  • 通过模式分解将一个低级范式转换为若干个高级范式的过程称作规范化

  • 范式是衡量关系模式的标准

范式（1NF等）指该范式的定义，同时也代表满足该范式的关系模式的集合，比如 2NF⊂1NF,R∈1NF2NF \subset 1NF,R\in 1NF

1NF

关系中每一分量不可再分。即不能以集合、序列等作为属性值。

2NF

样例

关系模式 S(sno,sname,dno,dean,cno,score)S(sno, sname, dno, dean, cno, score)

主码：sno, cno

  • 不良特性
    • 插入异常：如果学生没有选课，关于他的个人信息及所在学院的信息就无法插入
    • 删除异常：如果删除学生的选课信息，则有关他的个人信息及所在学院的信息也随之删除
    • 更新异常：如果学生转专业，若他选修了k门课，则需要修改k次
    • 数据冗余：如果一个学生选修了k门课，则有关他的所在学院的信息重复
改造

属性有两种，一种完全依赖于候选码，一种部分依赖于候选码。

将S分解为：

SC(sno,cno,score)SC(sno , cno , score)，主码：sno,cnosno,cno

S_SD(sno,sname,dno,dean)S\_SD(sno, sname, dno, dean)，主码：snosno

定义

若 R∈1NFR\in 1NF，且每个属性满足下列准则之一：

  • 它出现在一个候选码中
  • 它没有部分依赖于一个候选码 (也就是说不存在候选码的一部分决定该属性的情况)

则 R∈2NFR\in 2NF

核心就是消除非主属性对候选码的部分依赖

上面的例子中，sname,dnosname,dno 不出现在候选码中，且部分依赖候选码

3NF

样例

S_SD(sno,sname,dno,dean)S\_SD(sno, sname, dno, dean)

  • 不良特性
    • 插入异常：如果学院没有学生，则有关学院的信息就无法插入
    • 删除异常：如果学生全部毕业了，则在删除学生信息的同时有关学院的信息也随之删除了
    • 更新异常：如果学生转专业，不但要修改dno，还要修改dean，如果换院长，则该学院每个学生元组都要做相应修改
    • 数据冗余：每个学生存储了所在院长的信息

SSD∉3NFS_SD \not \in3NF，因为有 sno→dno，dno→deansno\rightarrow dno，dno\rightarrow dean

改造

将S_SD分解为 S(sno,sname,dno)S (sno, sname, dno)，D(dno,dean)D (dno, dean)

定义

关系模式 R<U,F>R<U , F>中，F+F^+ 中所有函数依赖 α→βα\rightarrow β ，至少有以下之一成立 ：

  1. α→βα\rightarrow β 是平凡的函数依赖；
  2. αα 是超码；
  3. β−αβ - α （集合做差）的每一个属性 AA 都包含在 RR 的候选码中，则称 R∈3NFR\in 3NF。
    • 注意：并不要求集合之差在同一个候选码当中
    • 注意候选码是要保证完全依赖的，否则是超码

关系模式 R<U,F>R< U , F > 中，若不存在这样的某一个码 XX，属性组 YY 及非主属性 Z(Z⊄Y)Z(Z \not \sub Y)，使得下式成立： X→Y,Y→Z,Y↛XX\rightarrow Y , Y\rightarrow Z , Y\not\rightarrow X，（构成了一个传递依赖） 则称 R∈3NFR\in 3NF

  • 主属性：包含在候选码中的属性
  • 即 RR 中没有非主属性 ZZ 传递依赖于 RR 的某一个码

PS.作为判断3NF时的一种优化，可以只考虑 FF 上的函数依赖，而不是 F+F^+，也可以分解 FF 上的函数依赖，让它们的右半部只包含一个属性，并用这个结果代替 FF

关系模式分解算法

简单算法

分解后的关系要达到3NF且保持函数依赖的分解

输入：关系模式 R(U,F)R(U,F)

  1. 计算 FF 的正则覆盖 FcF_c

  2. 若有 α→β∈Fcα\rightarrow β\in F_c ，且 α∪β=Uα\cup β = U，则算法终止

  3. 对 FcF_c 按具有相同左部的原则进行分组(设为k组)，每一组函数依赖所涉及的属性全体为 UiU_i，令 FiF_i 为 FcF_c 在 UiU_i 上的投影，则 ρ={R1<U1,F1>,…,Rk<Uk,Fk>}\rho = \{R_1<U_1 , F_1> , … , R_k<U_k , F_k>\} 是 R<U,F>R<U , F> 的一个保持函数依赖的分解，并且每个Ri<Ui,Fi>∈3NFR_i<U_i , F_i> \in 3NF

返回 ρ\rho

示例1

R(U,F)，U={sno，dno，dean，cno，score}R(U,F)，U=\{sno，dno，dean，cno，score\}

F={sno→dno，sno→dean，dno→dean，(sno,cno)→score}F=\{sno\rightarrow dno，sno\rightarrow dean，dno\rightarrow dean，(sno,cno)\rightarrow score\}

  • FC={sno→dno，dno→dean，(sno,cno)→score}F_C=\{sno\rightarrow dno，dno\rightarrow dean ，(sno,cno)\rightarrow score\}

  • 分组

R1{(sno，dno)，sno→dno}R_1 \{(sno，dno)，sno\rightarrow dno\}

R2{(dno，dean)，dno→dean}R_2 \{(dno，dean)，dno\rightarrow dean\}

R3{(sno，cno，score)，(sno,cno)→score}R_3 \{(sno，cno，score)， (sno,cno)\rightarrow score\}

可以验证，这是无损分解。

显然候选码是AB，因为这两个是L类属性而C是R类属性。

由于A或B都不是超码，而且C不在候选码中，所以不属于3NF。

R1∩R2={A}，A→C,A→R1R_1\cap R_2=\{A\}，A\rightarrow C,A\rightarrow R_1，所以是无损连接。按函数依赖，显然有损

解决上面的问题：3NF合成算法

输入关系模式 R(U,F)R(U,F)，在前面算法的基础上

1、ρ={R1<U1,F1>,…,Rk<Uk,Fk>}\rho = \{R_1<U_1 , F_1> , … , R_k<U_k , F_k>\} 是 R<U,F>R<U , F> 的一个保持函数依赖的3NF分解

2、设 α\alpha 为 R<U,F>R<U , F>的任意候选码，若有某个 UiU_i， α⊆Ui\alpha \subseteq U_i，则 ρ\rho 即为达到3NF且同时保持无损连接与函数依赖的分解，否则令 τ=ρ∪{R∗<α，Fα>}τ = \rho∪\{R* < \alpha ，F_{\alpha}>\}

返回 ττ

  • Step1必须是对 FcF_c 中的函数依赖构造关系(不能是F中函数依赖)

  • 必须进行Step2的检查并在必要时构造候选码关系模式，检查候选码是否包含在某个关系模式当中，否则，分解不是无损分解

教材算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
令Fc为F的一个正则覆盖
i = 0
for  each Fc中的函数依赖α-β（用-代替右箭头）  
   i := i + 1;
   Ri := αβ;
 if 模式Rj, j = 1,2,…,i 都不包含R的候选码 then 
    i := i + 1;
    Ri := R的任意候选码;
repeat/*删除冗余关系模式*/  //下面是相对上面算法多出的部分
 if 模式 Rj 包含于另一个模式Rk中 then
   Rj := Ri;
   i := i – 1;
Until 没有可以删除的Rj
return (R1,R2,…Ri)

算法比较

  • 本质相同，都能无损、保持依赖地分解为3NF

  • 区别在于教材算法检查要构造的模式，是否是某个已经构造的模式的子集，如果是，不再构造该模式

  • 教材算法构造的模式集合结果相对本算法更加简洁

  • 不过更简练的分解不一定是更好的分解

合成算法的算法正确性分析

三个条件：保持依赖、无损、分解结果的关系是3NF

保持依赖

  • 通过为一个给定的正则覆盖中的每一个函数依赖显式构造一个模式，该算法确保了函数依赖。

  • 该算法分解结果不唯一

    • FcF_c 不唯一
    • 候选码不唯一使得集合在并上候选码后的结果不唯一
无损连接

通过保证至少有一个模式包含了被分解模式的候选码，该算法保证了分解是一个无损连接分解。证明如下：

注意：有损分解一定是多了一些元组。

那么就不存在这样的 tt，那就一定是无损的（没有多出来的元组）

  • 注意第三点：元组tt是由 rr 中投影得来的，所以一定有 t[α]∈rit[\alpha]\in r_i，而且注意其候选码上的值相等，则就是同一个元组。
每个关系模式都是3NF

如果关系模式 RiR_i 在由3NF综合算法产生的分解中，则 Ri∈3NFR_i∈3NF，考虑 RiR_i 上的任意函数依赖 γ→B\gamma \rightarrow B(此处 BB 满足右侧单一属性)满足3NF的定义 。证明如下：

假定综合算法中产生 RiR_i 的函数依赖是 α→β(α→β∈Fc)α\rightarrow β (α\rightarrow β ∈ F_c)（那么Ui=αβU_i=\alpha\beta），B∈RiB∈ R_i，则 B∈αB∈α 或者 B∈βB∈β，考虑下列三种情况：

  • B∈α∧B∈βB∈α∧B∈β：因为B在 ββ 中是无关属性（比如 AB→BCAB \rightarrow BC），所以 α→βα\rightarrow β 不会出现在 FcF_c 中（正则覆盖保证无无关属性），这种情况不成立

  • B∉α∧B∈βB\not\in α∧B∈β：

    • γ\gamma 是一个超码，则 Ri∈3NFR_i∈3NF
    • 注意到 α\alpha 是 RiR_i 唯一的候选码，那么 RiR_i的任意超码都要包含 α\alpha。如果γ\gamma 不是一个超码，则 αα 中一定包含一些不在 γ\gamma 中的属性。因为 γ→B\gamma \rightarrow B 在 F+F^+ 中，通过 B∈γFc+B∈ \gamma^+_{F_c} 得到的。 γ→B\gamma \rightarrow B 的推导不会用到 α→βα\rightarrow β，否则 α∈γFc+α∈ \gamma^ +_{F_c}，因为假定 γ\gamma 不是超码（如果用到 α→βα\rightarrow β ，就会得到 γ→α\gamma\rightarrow \alpha，说明 γ\gamma 是超码），所以上述结论是不成立的。现在，使用 α→(β−{B})α\rightarrow (β- \{B\}) 和 γ→B\gamma \rightarrow B，得到 α→Bα\rightarrow B，这表明 BB 在 α→βα\rightarrow β 中是右无关属性，这也是不可能的(因为 α→βα\rightarrow β 是 FcF_c 中的函数依赖，不存在无关属性)。所以，如果 B∈βB∈β，则 γ\gamma 一定是超码。

  • B∈α∧B∉βB∈ α∧B \not\in β：因为 αα 是候选码，3NF的第三个条件满足。

示例

设有关系模式 R(U,F)，U={ABCDEFGHI}，F={AB→C，A→DE，B→GH，D→I}R(U,F)，U= \{ABCDEFGHI\}，F=\{AB→C，A→DE，B→GH，D→I\}，试求：

  1. RR 的候选码；

  2. 将 RR 分解成属于3NF，并且具有保持依赖性和无损连接。

1.候选码：ABF

2.首先求出F的正则覆盖Fc={AB→C,A→DE,B→GH,D→I}，F_c=\{AB→C,A→DE,B→GH,D→I\}，

得了 τ＝({ABC},{ADE},{BGH},{DI},{ABF})τ ＝(\{ABC\}, \{ADE\}, \{BGH\}, \{DI\}, \{ABF\})

BCNF

样例

关系模式 STC(U,F)STC(U,F)，每位老师只教授一门课。其中

U={sno,tno,cno}U=\{sno , tno , cno\}

F={tno→cno，(sno，tno)→cno，(sno，cno)→tno}F=\{tno \rightarrow cno， (sno，tno)\rightarrow cno， (sno，cno)\rightarrow tno\}

(sno，tno)，(sno，cno)(sno，tno)，(sno，cno)为候选码。

不良特性

  • 插入异常：如果没有学生选修某位老师的任课，则该老师担任课程的信息就无法插入

  • 删除异常：删除学生选课信息，会删除掉老师的任课信息

  • 更新异常：如果老师所教授的课程有所改动，则所有选修该老师课程的学生元组都要做改动

  • 数据冗余：每位学生都存储了有关老师所教授的课程的信息

  • 原因

    • 主属性对码的不良依赖

改造

将STC分解为：(sno，tno)，(tno，cno)(sno，tno)，(tno，cno)

定义

关系模式 R<U,F>R< U , F >中，所有的形如 α→βα\rightarrow β 的函数依赖 (α⊆U，β⊆U)( α\subseteq U，β\subseteq U )，下面至少有一个成立

  • α→βα\rightarrow β是平凡的函数依赖

  • αα 是模式 RR 的一个超码

如 STC∉BCNFSTC \not\in BCNF，因为 tno→cnotno \rightarrow cno，而 tnotno 不是超码

BCNF的本质

  • (在只考虑函数依赖的前提下)一个关系模式只描述一件事

  • 非码决定因素的相关决定关系讲述了另外一件事

    • R1：U = {sno,sname,dno,dname}
    • F = {sno→(sname,dno)，dno→dname}
    • R1讲述了“学生”和“学院”两件事，R1∉BCNFR1\not\in BCNF

  • 有多个码是一件事的不同方面，本质仍是一件事

    • R2：U = {sno,pid,sname,age,dno}
    • F = {sno→pid,sname,age,dno，pid →sno}
    • R2有两个码，讲述了”学生”一件事， R2∈BCNFR2\in BCNF

判断关系模式是否属于BCNF

检查非平凡的函数依赖 α→βα\rightarrow β 是否违反BCNF，即检查 α+α^+，并验证它是否包含了 RR 上的所有属性，判断 αα 是否是 RR 的超码

  • 检查关系模式 RR 是否属于BCNF，仅需要检查给定集合 FF 上的函数依赖，不需要检查 F+F^+ 。因为如果 FF 上没有函数依赖违反BCNF，则 F+F^+上也不会有函数依赖违反BCNF

当关系模式被分解后，需要根据 F+F^+ 判断一个 RiR_i 是否属于BCNF，不属于的话需要再次分解

例如：R(U,F)，U={ABCDE},F={A→B,BC→D}。将R分解为R1和R2，U1={AB}，U2={ACDE}R(U,F)，U = \{ABCDE\}, F = \{A \rightarrow B, BC \rightarrow D\}。将R分解为R1和R2，U1 =\{AB\}，U2 = \{ACDE\}

R2R_2 中没有来自于 FF 中的函数依赖，但是 AC→D∈F+AC \rightarrow D∈F^+，所以 R2R_2 不属于BCNF。需要再分解 R2

因此，计算分解后的关系模式是否属于BCNF是NP的

分解算法

注意

此算法只能产生无损连接分解，若要求分解保持函数依赖，那么分解后的模式总可以达到3NF，但不一定能达到BCNF

当我们用 (Ri−β)(R_i - β)和 (αβ)(αβ) 代替模式 RiR_i 时，保持依赖 α→βα\rightarrow β，而且 (Ri−β)∩(αβ)=α(R_i - β) ∩ (αβ)=α

如果我们没有要求 α∩β=∅α\cap β=\emptyset ，那么 α∩βα∩β 中的那些属性就不会出现在模式 (Ri−β)(R_i - β) 中，而依赖 α→βα\rightarrow β 也不成立，因此不保证无损连接分解

如果 α∩β<>∅α∩β<>\emptyset，αα 中的属性 {A,B,C}\{A,B,C\}，ββ 中的属性 {C,D,E}\{C,D,E\}，RiR_i 中的属性{A,B,C,D,E,F,G}\{A,B,C,D,E,F,G\}， Ri–β={A,B,F,G}R_i – β=\{A,B,F,G\}， αβ={A,B,C,D,E}αβ=\{A,B,C,D,E\}，(Ri–β)∩(αβ)={A,B}( R_i – β)∩ (αβ)=\{A,B\}，则 (Ri–β)∩(αβ)→β( R_i – β)∩ (αβ) \rightarrow β 不成立，这就说明我们得到的不是无损分解

多值依赖

样例

关系模式 TEACH(cno，tno，bno)TEACH(cno，tno，bno)，一门课程由多名老师担任，同一门课程的不同老师可以使用相同的一套参考书；一位老师可以承担多门课。 它的候选码是 (cno，tno，bno)(cno，tno，bno)，所以属于BCNF

不良特性

  • 插入异常：当某门课程增加一名教师时，该门课程有多少本参考书就必须插入多少个元组；同样当某门课程需要增加一本参考书时，它有多少个教师就必须插入多少个元组

  • 删除异常：当删除一门课程的某个教师或者某本参考书时，需要删除多个元组

  • 更新异常：当一门课程的教师或参考书作出改变时，需要修改多个元组

  • 数据冗余：同一门课的教师与参考书的信息被反复存储多次

定义

  • 描述型：关系模式 R(U)R(U)，α、β、γ⊂U\alpha、\beta、\gamma \subset U，并且 γ=U–α–β\gamma = U – \alpha – \beta，多值依赖 α→→β\alpha \rightarrow\rightarrow \beta 成立当且仅当对 R(U)R(U) 的任一关系实例 rr ，给定的一对 (α1，γ1)(\alpha_1，\gamma_1) 值，有一组 β\beta 的值，这组值仅仅决定于 α\alpha 值而与 γ\gamma 值无关
    • 注意，是”有一组 β\beta 的值“，而不是一个

如在关系模式TEACH中，对(c1 , b1)有一组tno值(t1 , t2)，对(c1 , b2)也有一组tno值(t1 , t2)，这组值仅取决于cno的取值，而与bno的取值无关。因此，tno多值依赖于cno，记作 cno→→tnocno\rightarrow \rightarrow tno，同样有 cno→→bnocno\rightarrow \rightarrow bno

  • 形式化：关系模式 R(U)R(U)，α、β、γ⊂U\alpha、\beta、\gamma \subset U，并且 γ=U–α–β\gamma = U – \alpha – \beta，对于 R(U)R(U) 的任一关系实例 rr，若存在元组 t1，t2t1，t2，使得 t1[α]=t2[α]t1[\alpha] = t2[\alpha]，那么就必然存在元组 t3，t4t3，t4，使得：

t3[α]=t4[α]=t1[α]=t2[α]t3[\alpha] = t4[\alpha] = t1[\alpha] = t2[\alpha]

t3[β]=t1[β]，t3[γ]=t2[γ]t3[\beta] = t1[\beta]， t3[\gamma] = t2[\gamma]

t4[β]=t2[β]，t4[γ]=t1[γ]t4[\beta] = t2[\beta] ， t4[\gamma] = t1[\gamma]

则称 β\beta 多值依赖于 α\alpha 。

性质

  • 多值依赖具有对称性，即：若α→→β\alpha \rightarrow \rightarrow \beta ，则 α→→γ\alpha\rightarrow \rightarrow \gamma ，其中 γ=U–α–β\gamma =U–\alpha–\beta

  • 函数依赖是多值依赖的特例，即：若 α→β\alpha \rightarrow \beta ，则 α→→β\alpha\rightarrow \rightarrow \beta

  • 若 α→→β\alpha \rightarrow \rightarrow \beta ，U – α – β=∅U\,–\,\alpha\,–\,\beta=\emptyset 或者 β⊆α\beta \subseteq \alpha ，则称 α→→β\alpha\rightarrow \rightarrow \beta 为平凡的多值依赖

  • 多值依赖具有传递性，若 α→→β，β→→γ\alpha →→ \beta ， \beta →→ \gamma ， 则 α→→γ – β\alpha →→ \gamma\, –\, \beta

  • 若 α→→β，α→→γ\alpha →→ \beta ，\alpha →→ \gamma ，则 α→→β∪γ\alpha →→ \beta \cup \gamma

  • 若 α→→β，α→→γ\alpha →→ \beta ，\alpha →→ \gamma ，则 α→→β∩γ\alpha →→ \beta ∩ \gamma

  • 若 α→→β，α→→γ\alpha →→ \beta ，\alpha →→ \gamma ，则 α→→β−γ，α→→γ−β\alpha →→ \beta - \gamma ，\alpha →→ \gamma - \beta

举例

多值依赖与函数依赖

区别

  • 函数依赖规定某些元组不能出现在关系中，也称为相等产生依赖

  • 多值依赖要求某种形式的其它元组必须在关系中（就比如形式化的定义中写的 “必然存在元组t3、t4”），也称为元组产生依赖

有效性范围

  • α→β\alpha \rightarrow \beta 的有效性仅决定于 α、β\alpha 、 \beta 属性集上的值，它在任何属性集 W(αβ⊆W⊆U)W( \alpha\beta \subseteq W \subseteq U) 上都成立。若α→β\alpha \rightarrow \beta 在 R(U)R(U) 上成立，则对于任何 β′⊆β\beta' \subseteq \beta ，均有 α→β′\alpha \rightarrow \beta' 成立

  • α→→β\alpha \rightarrow\rightarrow \beta 的有效性与属性集范围有关

    α→→β\alpha \rightarrow\rightarrow \beta 在属性集 W(αβ⊆W⊆U)W( \alpha\beta \subseteq W \subseteq U) 上成立，但在 UU 上不一定成立

    α→→β\alpha \rightarrow\rightarrow \beta 在 UU 上成立，那么α→→β\alpha \rightarrow\rightarrow \beta 在属性集 W(αβ⊆W⊆U)W( \alpha\beta \subseteq W \subseteq U) 上成立

    若α→→β\alpha \rightarrow\rightarrow \beta 在 R(U)R(U) 上成立，则不能断言对于 β′⊆β\beta'\subseteq \beta ，是否有α→→β′\alpha \rightarrow\rightarrow \beta' 成立

都不成立。

闭包

令 DD 表示函数依赖和多值依赖的集合，DD 的闭包 D+D^+ 是由 DD 逻辑蕴涵的所有函数依赖和多值依赖的集合

我们可以用函数依赖和多值依赖的形式化定义由 DD 计算 D+D^+

4NF

定义

函数依赖和多值依赖集为 DD 的关系模式 RR 属于4NF的条件是：对于所有 D+D^+ 中形如： α→→β\alpha \rightarrow\rightarrow \beta 的多值依赖（其中 α⊆R∧β⊆Rα\subseteq R∧ β\subseteq R），至少有以下条件之一成立：

  • α→→β\alpha \rightarrow\rightarrow \beta 是一个平凡的多值依赖；
  • αα 是模式 RR 的超码。
    • 注意超码与多值依赖无关
示例

R1R_1 ，R2R_2 都不是， R3R_3 是BCNF但不是4NF， R4,R5R_4,R_5 都是

4NF的本质

(在只考虑函数和多值依赖的前提下) 4NF只讲一件事，非码的多值决定关系讲述了另外一件事

证明 4NF⊂BCNF4NF \subset BCNF

假设 R∈4NF,R∉BCNFR \in 4NF,R \not\in BCNF。因为 R∉BCNFR \not\in BCNF，一定存在 α→βα→β， αα 不是超码，因为 α→βα→β，得到 α→→βα→→ β，所以 R∉4NFR \not\in 4NF。假设不成立。

又：存在 R(D)∈BCNF，R(D)∈4NFR(D)\in BCNF，R(D)\in 4NF

关系模式的分解算法-4NF

DD 在 RiR_i 上的投影(限定)是集合 DiD_i，它包含以下内容：

  • D+D^+ 中所有只含 RiR_i 中属性的函数依赖；

  • 所有形如 α→→β∩Riα→→ β∩R_i 的多值依赖，其中 α⊆Riα \subseteq R_i 并且 α→→βα→→ β 属于 D+D^+

示例

小结

  • 1NF：数据库表的每一列都是不可分割的原子数据项，而不能是集合，数组，记录等非原子数据项。

  • 2NF：1NF的基础上，非码属性必须完全依赖于码。在1NF基础上消除非主属性对主码的部分函数依赖

  • 3NF：在1NF基础上，任何非主属性不依赖于其它非主属性。在2NF基础上消除传递依赖。

  • BCNF：在1NF基础上，任何非主属性不能对主键子集依赖，在3NF基础上消除对主码子集的依赖

  • 4NF：在多值依赖的视角评价关系模式

时态数据建模

时态数据是与时间段有关的数据，该时间段表明数据有效的时间。数据快照表示一个特定时间点上该数据的值。在特定时间点上成立的函数依赖称为时态函数依赖。

时态函数依赖在常规的函数依赖中很难推理。

习题课

分解为BCNF

一

R(U,F):U={ABCD},F={AB→C,C→D,D→A}R(U,F):U=\{ABCD\},F=\{AB \rightarrow C,C\rightarrow D,D\rightarrow A\}

显然 C→D,D→AC \rightarrow D,D \rightarrow A 不满足BCNF，可以分解为 R1(CD),R2(ABC)R_1(CD),R_2(ABC)。

对应到算法之中，此时 Ri=R=resultR_i=R=result，所以 result−Ri=∅result-R_i=\emptyset 。

注意到 R2R_2 中存在 C→A∈F+C \rightarrow A\in F^+，而且显然不满足BCNF，需要继续分解，将 R2(ABC)R_2(ABC) 分解为 R21(CA),R22(CB)R_{21}(CA),R_{22}(CB)，再检验三个关系模式，都满足BCNF，分解完成

（当然也可以先将 D→AD\rightarrow A 分解出来）

二

R(U,F):U={ABCD},F={B→C,B→D}R(U,F):U=\{ABCD\},F=\{B \rightarrow C,B\rightarrow D\}

B→C,B→DB \rightarrow C,B\rightarrow D 都不满足BCNF，将 B→CB\rightarrow C 分解出来，可以分解为 R1(BC),R2(ABD)R_1(BC),R_2(ABD)，由于 B→DB \rightarrow D 不满足BCNF，继续分解 R2R_2 为 R21(BD),R22(AD)R_{21}(BD),R_{22}(AD)，分解完成

三

R(U,F):U={ABCD},F={AB→C,BC→D,CD→A,AD→B}R(U,F):U=\{ABCD\},F=\{AB \rightarrow C,BC\rightarrow D,CD\rightarrow A,AD \rightarrow B\}

本身就满足BCNF

四

R(U,F):U={ABCDE},F={AB→C,DE→C,B→D}R(U,F):U=\{ABCDE\},F=\{AB \rightarrow C,DE\rightarrow C,B\rightarrow D\}

三个函数依赖都不满足BCNF，首先分解为 R1(ABC),R2(ABDE)R_1(ABC),R_2(ABDE)，发现 R2R_2 仍然不满足BCNF，分解为 R21(BD),R22(ABE)R_{21}(BD),R_{22}(ABE)，完成

五

R(U,F):U={ABCDEF},F={A→B,C→DF,AC→E,D→F}R(U,F):U=\{ABCDEF\},F=\{A \rightarrow B,C\rightarrow DF,AC\rightarrow E,D\rightarrow F\}

除了 AC→EAC \rightarrow E，都不满足BCNF，首先分解出 A→BA \rightarrow B 为 R1(AB),R2(ACDEF)R_1(AB),R_2(ACDEF)，然后再分解出 C→DFC\rightarrow DF 为R21(CDF),R22(ACE)R_{21}(CDF),R_{22}(ACE)，由于 D→FD\rightarrow F，R21R_{21} 不满足BCNF，分解为 R211(DF),R212(CD)R_{211}(DF),R_{212}(CD)，完成

分解为3NF

一

R(U,F):U={ABCD},F={AB→C,C→D,D→A}R(U,F):U=\{ABCD\},F=\{AB \rightarrow C,C\rightarrow D,D\rightarrow A\}

候选码不唯一，有 AB,BC,BDAB,BC,BD，那么显然属于3NF，因为 A,C,DA,C,D 都在候选码中。

二

R(U,F):U={ABCD},F={B→C,B→D}R(U,F):U=\{ABCD\},F=\{B \rightarrow C,B\rightarrow D\}

候选码是 ABAB，BB 不是超码，C、DC、D不在候选码中，不是3NF，Fc={B→CD}F_c=\{B\rightarrow CD\}，分解结果({BCD},{AB})(\{BCD\},\{AB\})

三

R(U,F):U={ABCD},F={AB→C,BC→D,CD→A,AD→B}R(U,F):U=\{ABCD\},F=\{AB \rightarrow C,BC\rightarrow D,CD\rightarrow A,AD \rightarrow B\}

属于3NF。

四

R(U,F):U={ABCDE},F={AB→C,DE→C,B→D}R(U,F):U=\{ABCDE\},F=\{AB \rightarrow C,DE\rightarrow C,B\rightarrow D\}

候选码为 ABEABE，Fc=FF_c=F，分解为 ({ABC},{DEC},{BD},{ABE})(\{ABC\},\{DEC\},\{BD\},\{ABE\})

五

R(U,F):U={ABCDEF},F={A→B,C→DF,AC→E,D→F}R(U,F):U=\{ABCDEF\},F=\{A \rightarrow B,C\rightarrow DF,AC\rightarrow E,D\rightarrow F\}

候选码为 ACAC，Fc={A→B,C→D,AC→E,D→F}F_c=\{A \rightarrow B,C\rightarrow D,AC\rightarrow E,D\rightarrow F\}，分解为 ({AB},{CD},{ACE},{DF})(\{AB\},\{CD\},\{ACE\},\{DF\})。

作业题拾遗

R({A,B,C,D,E,G},{A→BCD,BC→DE,B→D,D→A})R(\{A,B,C,D,E,G\},\{A \rightarrow BCD,BC\rightarrow DE,B\rightarrow D,D\rightarrow A\})

计算 FcF_c：

由 B→DB\rightarrow D，F1={A→BC,BC→E,B→D,D→A}F_1=\{A\rightarrow BC,BC\rightarrow E,B\rightarrow D,D\rightarrow A\}

由 B→D,D→A,A→BCB\rightarrow D,D\rightarrow A,A\rightarrow BC，则B→CB\rightarrow C，F2={A→BC,B→E,B→D,D→A}F_2=\{A\rightarrow BC,B\rightarrow E,B\rightarrow D,D\rightarrow A\}。

  • 注意这种多级传递的情况，可能遗漏
  • 注意一次只处理一个函数依赖

合并相同左项得 Fc={A→BC,B→DE,D→A}F_c=\{A\rightarrow BC,B\rightarrow DE,D\rightarrow A\}