数据库设计

数据库设计的问题

数据冗余：大量重复数据

1. 浪费磁盘空间
2. 不分表，则会导致大量的数据冗余

修改异常

1. 修改异常浪费时间，并且用户容易造成错误。
2. 在修改一个数据的时候，会导致大量数据列的修改。

删除异常

删除一个信息实体的同时，可能会导致其他实体信息被同时删除。

插入异常

实体不完全是无法进行插入的

实体关系模型(Entity-Relationship, E-R)

E-R 模型是一种描述数据库的抽象方法。

实体关系建模的方法更多依赖于直觉而非机器, 但会导致相同的设计。

模型的组成

实体

• 实体是具有公共属性的可区分的现实世界对象的集合。
• 一个实体对应一个关系表，是一组物体。
• 每一行都是一个实体，或者一个实体的实例，代表一个物体。
• 实体是用长方形表示的。

属性

• 属性是描述实体或关系（定义如下）的属性的数据项。

• 属性是椭圆形表示，单值属性用单实线连接，多值属性用双实线连接

  

• 特殊的属性

  • 候选键/标识符：标识符是唯一标识实体实例的属性或属性集，在名字下面用下划线表示。

  • 主键/主标识符：被数据库设计者选择出来的作为表中特定行唯一标识符的候选键，在名字下面用下划线表示。

  • 描述符：描述符是一个非键属性。

  • 复合属性：一组共同描述属性的简单属性，student_name 是复合属性，符合属性使用单值和多值属性复合而成。

    

  • 多值属性：单个实例这个属性可以具有多个值。

    

关系

给定 m 个实体的有序列表，分别为 E1，E2，…Em，(同一实体在列表中可能出现多次)

关系 R 定义了这些实体的实例之间的对应规则。

具体来说，R 代表一组 m 元组，这是实体实例的笛卡尔积的子集。

关系是用菱形表示的

关系可以有额外的属性

关系可以有环出现

实体参与关系的基数

实体 E 和 F，关系 R，下图中点是实体的实例，线是关系实例

只有如上这四种情况：

• 如果实体 E 中的所有实例最多只有一个关系相关，则 max-card(E, R) = 1
• 如果实体 E 中的所有实例有超过一个关系相关，则 max-card(E, R) = N
• 如果实体 E 中所有实例最少只有一个关系相关，则 min-card(E, R) = 1
• 如果实体 E 中所有实例中有没有关系相关的，则 min-card(E, R)= 0

card(E, R)

每一个关系都有这样的一组 card(E, R) = (0, N)=(min-card(E, R), max-card(E, R))

max-card()

• max-card(X, R) = 1：单值参与
• max-card(X, R) = N：多值参与

min-card()

• min-card(X, R) = 1：强制参与
• min-card(X, R) = 0：可选参与

ER 模型的转换规则

转换规则一

1. 实体映射到单个表。实体的单值属性映射到列(复合属性映射到多个简单列)。
2. 实体出现成为表的行。

转换规则二

1. 多值属性必须映射到其自己的表。
2. 对于ORDBMS 并不适用。

转换规则三(多对多关系规则)

1. 将二元联系转换为关系（N-N关系）：当两个实体E和F参与多对多二进制关系R时，该关系将映射到相关关系数据库设计中的代表表 T。
2. T还包含附加到关系的所有属性的列。

转换规则四(多对一关系规则)

1. 在具有单值参与的实体（多面）中用外键表示。
2. 如果max-card(F, R) = 1，每一个对应关系可以用外键来关联。

转换规则五(一对一关系规则，一侧可选参与)

1. 表示为两个表的外键列在一个具有强制参与的表中：定义为NOT NULL的列。

转换规则六(一对一关系规则，双侧必选参与)

1. 永远不会分裂。 将其视为单个表中的两个实体是适当的。

规范化

函数依赖(FD, Functional Dependency)

A→B：A 在函数上决定 B，或者 B 在功能上取决于 A。

Armstrong 公理

从已知的一些函数依赖，可以推导出另外一些函数依赖，这就需要一系列推理规则。

基本规则

1. 自反规则：If Y 包含于 X，then X -> Y
2. 传递规则：If X -> Y，Y -> Z，then X -> Z
3. 增广规则：If X -> Y，XZ -> YZ

扩展规则

1. 合并规则：If X -> Y and X -> Z，then X -> YZ
2. 分解规则：If X -> YZ，then X -> Y，and X -> Z
3. 伪传递规则：If X -> Y，and WY -> Z，then XW -> Z
4. 聚集规则：If X -> Y，and WY -> Z，then XW -> Z

在表格上寻找最小依赖

1. 寻找单个的最小依赖

   

2. 将可以合并的依赖进行合并

   

3. 考虑需要考虑的多种依赖

   

   1. 不需要考虑含有属性 D 的情况是因为 D 决定了剩余所有属性，再增加属性同样能决定剩余所有属性，因为寻找最小依赖所以不需要再增加属性。
   2. 不需要考虑含有属性 B 的情况是因为其它所有属性都决定 B，因此在函数决定关系的左边添不添加 B 并不影响该关系。

4. 考虑最后一个依赖

   

5. 最终的结果

   

函数依赖集F的闭包(Closure of a Set of FDs)

闭包，记作 $F^{+}$，就是当前集合能扩展出来的所有的函数依赖集

函数依赖集的覆盖

表 T 上的函数依赖集 F 覆盖了表 T 上的函数依赖集 G 当且仅当 F 可以通过推导关系推导出 G，也就是 G 包含于 $F^{+}$

函数依赖集的等价：F 覆盖 G 并且 G 覆盖 F

属性集的闭包(Closure of a Set of Attributes)

给定表 T 上的一个属性集合 X，表 T 上的一个属性集合 F ，我们定义 X 在 F 下的闭包(我们记为 $X^{+}$ 或者是 $X_F^{+}$ )是在函数依赖集 F 的闭包上的 X->Y 的属性 Y 的最大集合。

$$X_F^{+}=\{A|X\to A\in F^{+}\}$$

方法

先把 $X^{+}$ 赋值为 X，然后对于函数依赖集 F 中的每一项, 若左侧包含于当前的 $X^{+}$，将右侧的并入 $X^{+}$，直到 $X^{+}$ 中不再增加。

例题

$$\text{ Example 6.6.7: }\mathrm{F}=\{\left({\mathrm{f}}_1\right)\mathrm{B}\to \mathrm{CD},\left({\mathrm{f}}_2\right)\mathrm{AD}\to \mathrm{E}\text{ , }\left(f_3\right)B\to A\},\text{ compute }\{B{\}}^{+}?$$

答案：

$X^{+}=\{A,B,C,D,E\}$

最小覆盖(Minimal Cover)

• 最小依赖也就是最小覆盖，上面是通过表格得到最小依赖，这里是通过函数依赖集获得最小依赖。
• 没有冗余的函数依赖。
• 每一个函数依赖的左边都没有多余属性。

方法

1. 创建函数依赖集 F 的等价函数依赖集 H，它的右边只有单个属性。
2. 顺次去掉 H 中非关键的单个依赖。 将 H 中的一项 X->Y 去掉，得到新的函数依赖集 J，若 $J^{+}=H^{+}$ 则称这个函数依赖是非关键的，也就是说去除这个函数依赖对 $H^{+}$ 没有任何影响。也可以通过判断 $X^{+}$ 是否还包含 Y 来判断。
3. 在不改变 $H^{+}$ 的前提下, 将 H 中的每个函数依赖用左边属性更少的函数依赖替换。 [font color=“red”]注意: 第三部中函数依赖集如果发生了变化, 需要返回第二步。[/font]
4. 用合并规则创建一个等价的函数依赖集 M。

例题

$F=\{a\to b,bc\to d,ac\to d\}$，求 F 的最小覆盖 M

1. 本来就做好了
2. 依次尝试去掉非关键依赖
   1. 尝试去掉 $a\to b$，$G=\{bc\to d,ac\to d\}$，$\{a{\}}_G^{+}=\{a\}$，不包含 b ，所以不能去掉。
   2. 尝试去掉 $bc\to d$，$G=\{a\to b,ac\to d\}$，$\{b,c{\}}_G^{+}=\{b,c\}$，不包含 d ，所以不能去掉。
   3. 尝试去掉 $ac\to d$，$G=\{a\to b,bc\to d\}$，$\{a,c{\}}_G^{+}=\{a,b,c,d\}$，包含 d ，所以能去掉。
3. 上一步的结果 $F=\{a\to b,bc\to d\}$，尝试减少左侧的属性
   1. 尝试将 $bc\to d$ 精简为 $c\to d$，得到 $G=\{a\to b,c\to d\}$，$\{c{\}}_F^{+}=\{c\}$，不包含 d，G 的依赖集相比 F 发生变化，所以不能精简。
   2. 尝试将 $bc\to d$ 精简为 $b\to d$，得到 $G=\{a\to b,b\to d\}$，$\{b{\}}_F^{+}=\{b\}$，不包含 d，G 的依赖集相比 F 发生变化，所以不能精简。
4. 没有需要合并的地方，最终结果为 $F=\{a\to b,bc\to d\}$

表格分解

规约化

把一张表分解为一张或者多张更小的表，但是在分解表的时候并不能经常保证蕴含了原来表的全部信息，造成了有损分解。

无损分解

判断分解成的两个表是不是无损分解, 就得根据表 T 的函数依赖集 F，检查两张表的标题交集的属性能否决定其中一张表的所有标题属性。

如何无损分解?

每个函数依赖左边的属性在老的核心的表中都出现，并决定了所有新表中的其他属性。

范式(NF, Normal Form)

超键

超键在关系中能够唯一标识元组的属性集，允许有多余属性。

给定表 T 和 它的一组函数依赖集 F，属性集 $X\subseteq Head(T)$，下面的描述等价

1. X 是 T 的超键
2. $X\to Head(T)$ 或者 $X_F^{+}\to Head(T)$

候选键

候选键同样可以唯一标识元组, 不允许有多余属性。

寻找候选键的方法

依次尝试去掉在 Head(T) 中的属性，若去掉后的属性集在 F 的闭包中包含了 T 的所有属性(可以决定 T 所有的属性)，就可以真的去掉了。

主属性(Primary Attribute)

候选键里的属性就是主属性。

1NF

关系型数据库的一张表中，每一列都不可再分割，即某一属性不能有多个值。

2NF

在 1NF 的基础上，消除了非主属性对于键（指候选键）的部分函数依赖。

判断方法

1. 找出表中所有非主属性
2. 查看是否存在有非主属性对键的部分函数依赖，若无则符合 2NF
3. 将数据表拆分成含有较少字段的表，修改为符合 2NF

3NF

在 2NF 的基础之上，消除了非主属性对于键的传递函数依赖。如果存在非主属性对于键的传递函数依赖，则不符合 3NF 的要求。

进行3NF的算法

给定通用表 T 和 FD 集 F 的情况下，该算法会生成 3NF 中的 T 的无损连接分解，并保留 F 的所有 FD。

1. 首先，将 F 替换成 F 的最小覆盖。
2. S = 空集
3. 对 F 中的所有 X->Y
   1. 如果对全部 Z 属于 S， $X\bigcup Y$ 不包含于 Z，则 $S=S\bigcup Head(X\bigcup Y)$
4. 如果对T的全部候选键K
   1. 对 Z 全部的 Z 属于 S，K 不包含于 Z
   2. 选择候选键 K，$S=S\bigcup Head(K)$

示例：

[scode type=“red” size=""]第三步这里我觉得图中有错误，R 的候选键应该是 {CE}，但是 {CE} 包含于 {CEB} 中，所以最后结果应该为 {BG} {CEB} {CA} {BD} {CD}[/scode]

BCNF

在 3NF 基础上消除主属性对候选键的部分依赖和传递依赖。

BCNF 一定是 3NF

3NF 不一定是 BCNF

BCNF分解算法

1. 首先求出最小依赖集合
2. 找到候选键，合并成子集
3. 然后检查函数依赖左侧是不是都是候选键

将3NF分解为BCNF