Lec6 数据库规范化

阅读信息

1858 字  7 分钟  本页总访问量 加载中...

引入

Q：为什么要规范化？

如果将所有信息存在一张大表中，可能有以下问题：

1. 冗余：相同的项被存储多次
2. 更新异常：修改某个值时，需要同时修改所有相关元组，如果漏改则会发生异常
3. 插入异常：新插入元组时，可能信息不全导致无法插入
4. 删除异常：删除部分属性时，可能错误将整个元组删除

Q：应该怎么规范化？

将原表分解，使每个表尽量只表达一种主要事实。分解至少需要满足无损链接和依赖保持。

第一范式（1NF）

第一范式（1NF）： 要求所有属性的域都是原子的（atomic），即所有属性都是不可再分的单元。不能放列表或嵌套结构。

属性的原子性与“使用方式”有关。e.g.学号“CS0012”可以看成一整个字符串，也可以看成院系+编号。

1NF是属性的基本要求，并没有解决冗余和异常问题。

函数依赖

函数依赖（FD） 用于表示属性间的唯一确定关系，作为后续判断冗余、分解的工具。

\(\alpha\) 决定 \(\beta\)（其中 \(\alpha\) 和 \(\beta\) 为schema的子集）：若两行的 \(\alpha\) 相同，则两者的 \(\beta\) 相同。esp.，如果某个属性集能决定整个关系的所有属性，则其为super key。

Q：怎么判断函数依赖关系？

对于给定的行，容易判断是否满足F；但不能仅由有限个行推出F，通常由schema的语义决定。

平凡函数依赖（trivial FD）： 如果 \(\beta\in\alpha\)，则称 \(\alpha \to \beta\) 是平凡的。

函数依赖闭包

函数依赖闭包： 对于函数依赖的集合 \(F\)，其闭包 \(F^+\) 为可以由 \(F\) 推导的来的所有函数依赖的集合。

Q：函数依赖闭包有什么用？

用于找出所有“隐含的约束”，用于后续求属性集闭包等。

Q：已知函数依赖集F，怎么求其闭包？

1. 三条Armstrong公理：

2. 自反律：if \(\beta\in\alpha\), then \(\alpha \rightarrow \beta\)

3. 增补律：if \(\alpha \rightarrow \beta\), then \(\lambda\alpha \rightarrow \lambda\beta\)

4. 传递律：if \(\alpha \rightarrow \beta\) and \(\beta \rightarrow \gamma\), then \(\alpha \rightarrow \gamma\)

5. 额外常用性质：

6. 伪传递律：if \(\alpha \rightarrow \beta\) and \(\gamma \rightarrow \theta\), then \(\alpha\gamma \rightarrow \theta\)

7. 合并律：if \(\alpha \rightarrow \beta\) and \(\alpha \rightarrow \gamma\), then \(\alpha \rightarrow \beta\gamma\)
8. 分解律：if \(\alpha \rightarrow \beta\gamma\), then \(\alpha \rightarrow \beta\) and \(\alpha \rightarrow \gamma\)

实际中，\(F^+\) 规模非常大（指数级），几乎不显式求函数依赖闭包，而是通过下面的属性闭包来间接判断。

属性集闭包

属性集闭包： 在函数依赖集F下，对于属性集 \(\alpha\)，其闭包 \(\alpha^+\) 为 \(\alpha\) 能直接或间接决定的所有属性的集合。

Q：属性集闭包有什么用？

1. 判断函数依赖是否成立。如果a能决定b，则等价于b在a的闭包中。
2. 判断某个属性集是否为super key。属性集a是super key等价于所有属性都在其闭包中。
3. 判断某个属性集是否为candidate key。根据上一点，如果属性集a本身为super key，所有真子集都不是super key，则其为candidate key。

Q：已知属性集a，怎么求其闭包？

首先将闭包初始化为原属性集a。检查函数依赖中的每一条，如果决定的属性在当前闭包中，则将被决定的属性加入闭包。直至闭包中属性不再新增。

result = a
while (changes to result) {
    for each b->g in F {
        if (b in result)
            result += g
    }
}
a* = result

正则覆盖

正则覆盖（canonical cover）： 对于函数依赖集 \(F\)，其正则覆盖 \(F_C\) 为与 \(F\) 等价的（能推出的依赖关系一样）、最小的函数依赖集，没有冗余依赖、也没有多余属性。

Q：已知函数依赖集F，怎么求其正则覆盖？

1. 合并：将A-B和A-C合并为A-BC
2. 删除左边的多余属性：判断AB-C能否简化为A-C（即检查A的闭包是否包含C）
3. 删除左边的多余属性：尝试将A-BC拆分为A-B和A-C，检查A-C能否由其他函数依赖推导得到，如果能，则删除该依赖
4. 重复执行上述几步，直至函数依赖集不变

分解

分解（decomposition）： 将一张大表拆成几张更小、更合理的表。其个根本目的是将“一个事实被重复存很多次”变成“一个事实存一次，通过关联恢复”。

分解必须满足以下两个条件：

1. 无损连接分解
2. 依赖保持

无损连接分解

无损连接分解（lossless-join decomposition）： 将原表投影为两个子表，两个子表连接后必须与原表完全相等。

Q：为什么会出现损失？

在有损连接分解中，两张表只保留了各自属性的集合，子表之间没有足够的信息说明属性间的对应关系，因此连接后产生伪元组（spurious tuple）问题。

Q：怎么判定是否为无损连接？

将表 \(R\) 分解为 \(R_1\) 和 \(R_2\)，若为无损分解，则以下两条件至少一个成立：

• \(R_1 \cap R_2 \to R_1\)
• \(R_1 \cap R_2 \to R_2\)

直观理解：当两个子表的公共属性能决定其中一个子表的全部属性，重新join时，不会随便匹配，因此不会产生伪元组。

依赖保持

依赖保持（dependency preservation）: 拆分后能直接在各个子表中检查原有的函数依赖关系，而不用将子表join起来检查。

Q：怎么判定是否满足依赖保持？

对每个子表，取出只涉及其内部属性的函数依赖，记为 \(F_i\)。若满足函数依赖，则需满足：

\[ (F_1\cup F_2\cup \cdots \cup F_n)^+ = F^+ \]

BC范式

BCNF（Boyce-Codd Normal Form）：对于表R中的函数依赖关系 \(\alpha \rightarrow \beta\)，要么为平凡的（\(beta\) 包含于 \(\alpha\)）或 \(\alpha\) 为key。

Q：为什么BCNF能消除冗余？

当某个属性能决定其他某些属性，但其不是super key时，会导致冗余。假设A决定B，但A不是super key，即存在属性C，使得A决定C不成立。对于同样的A，C有多个不同的取值，于是相同的B被重复存储多次。BCNF即用于避免所有的冗余情况。

Q：如果不满足BCNF，怎么拆分成子表？

如果发现A能决定属性集B，但A不是super key，则将原关系拆分为 (A,B) 和 (R-B)；即一个子表存储决定关系，另一个子表存剩下的内容。如果子表仍不满足BCNF，则继续拆分，直至满足。

BCNF分解一定是无损连接分解。因为公共部分保留了A，而A是第一个子表的super key。

第三范式

第三范式（3NF）： 对于所有函数依赖 \(A\to B\)，要么是平凡的，要么A是super key，要么B是主属性。

其中，主属性（prime attributes） 指属于某个candidate key的属性。

Q：怎么判断被决定的属性是不是主属性？

检查函数依赖时，一般从正则覆盖中检查，而不是用原始的函数依赖集。

1. 找出所有的candidate key：凡是不出现在任何函数依赖的右边的属性，一定在candidate key中；再计算闭包，检查是否满足super key，不满足则继续添加。
2. 检查被决定的属性是否出现在某个candidate key中。

Q：如果不满足3NF，怎么拆分成子表？

1. 求函数依赖集的正则覆盖 \(F_C\)
2. 对 \(F_C\) 中的每条函数依赖A-B，将A和B新建为子表
3. 如果上述建立的子表中，没有任何一张包含某个candidate key，则新建一张表，专门放某个candidate key
4. 必要时去掉被包含的子表

其中，candidate key的表保证了无损连接。

物化视图

第四范式

多值依赖

Q：为什么需要多值依赖？

BCNF解决“一个属性决定另一属性”的问题，但如果存在两个彼此独立的“多值集合”，在表中存储其笛卡尔积，导致冗余。

多值依赖（multivalued dependency，MVD）： 如果对属性集A、B，对任意元组，如果A相同，B的取值和剩余属性的取值额能自由交叉组合，则称多值依赖 \(A \to \to B\) 成立。

直观理解：同一个A，可以对应多个B，但这组B的取值由A决定。

第四范式定义