数据库系统概论概念整理

# 关系

# 域

域是属性的取值范围，是属性的取值集合。

# 笛卡尔积

给定一组域 D1, D2, ..., Dn，它们的笛卡尔积是指所有可能的 n 元组的集合。$D_1 \times D_2 \times ... \times D_n = \{(d_1, d_2, ..., d_n) | d_1 \in D_1, d_2 \in D_2, ..., d_n \in D_n\}$

# 关系的数学定义

$D_1 \times D_2 \times ... \times D_n$ 的一个子集称为关系，关系的元组称为关系的行，用$R(D_1, D_2, ..., D_n)$ 表示，其中$R$ 是关系名，$n$ 是关系的度，$D_1, D_2, ..., D_n$ 是关系的域。

# 码

# 候选码

在一个关系中，能惟一标识元组的属性或最小属性集称为关系的候选码。

# 主码

若一个关系中有多个候选码，则选其中的一个为主码。

# 外码

设 F 是基本关系 R 的一个或一组属性，但不是 R 的码。Ks 是基本关系 S 的主码。如果 F 与 Ks 相对应，则称 F 是 R 的外码。并称基本关系 R 为参照关系（Referencing Relation），基本关系 S 为被参照关系（Referenced Relationship）。

# 主属性

如果一个属性包含在任何一个候选码中，则称该属性为主属性。
不包含在任何一个候选码中的属性称为非主属性。

# 关系的性质

关系是一个二维表，表的每一行对应一个元组，表的每一列有一个属性名且对应一个域。

1. 分量必须取原子值
2. 列是同质的，即每一列的值来自同一域，具有相同的数据类型。每列的属性名是不同的。
3. 表中的列称为属性，给每列起一个名称即属性名。
4. 列的排列顺序是无关紧要的，有时为了使用方便，使用时有列序。
5. 关系中任意两个元组不能完全相同
6. 行的顺序无关。

每个关系都有称之为关键字的属性集唯一标识各元组。

# 关系完整性约束

# 实体完整性约束

规则：若属性 A 是基本关系 R 的主属性，则属性 A 不能取空值。

# 参照完整性约束

规则：在参照关系 R 中，如果属性 F 是 R 的外码，那么 F 的值必须是被参照关系 S 的主码的值，或者是空值。

# 用户定义完整性约束

用户定义的完整性约束是指用户自己定义的完整性约束，如：年龄不能为负数。

# 关系代数

# 传统集合运算

• 并：$\cup$
• 交：$\cap$
• 差：$-$
• 笛卡尔积：$\times$

# 专门的关系运算

# 选择：$\sigma$

选择运算是从关系中选择满足某一条件的元组，即从关系 R 中选取满足条件 C 的元组。

# 投影：$\Pi$

投影运算是从关系中选择出满足某一条件的属性，即从关系 R 中选取满足条件 C 的属性。

# 连接：$\Join$

连接运算是从两个关系中选取满足某一条件的元组，即从关系 R 和 S 中选取满足条件 C 的元组。

# 自然连接

自然连接是指两个关系中的公共属性进行等值比较，相等的元组连接起来。R.A = S.A，$R \Join S$

# 等值连接

等值连接是指两个关系中的属性进行等值比较，相等的元组连接起来。R.A = S.B，$R \underset{A=B}{\Join} S$

# 外连接

外连接是指连接运算中，如果某个元组在一个关系中没有匹配的元组，那么在结果中仍然保留这个元组，只是在另一个关系中的元组的属性值为空。

# 除：$\div$

设 R 和 S 除运算的结果为 T，则 T 包含所有在 R 中但不在 S 中的属性和值，且 T 的元组与 S 的元组经过组合均能出现在 R 中。即 T = R $\div$ S。
例如：
R：

S：

则 R $\div$ S：

# 除运算的代数表达式

$R \div S = \Pi_{A} (R) - \Pi_{A} ((\Pi_{A} (R) \times \Pi_B(S)) - R)$

# 查询优化

# 查询优化的准则

1. 尽可能早地执行选择操作（减少中间运算结果）
2. 对关系进行预处理（索引、排序）
3. 同时进行投影和选择运算
4. 把投影同其前或后的双目运算结合起来。（合并连接的选择与投影操作，以减少扫描的次数）
5. 合并选择与笛卡尔积组成一个连接
6. 寻找公共子表达式

# 关系代数等价变换规则

# 连接、笛卡尔积交换律

• $R \Join S = S \Join R$

# 连接、笛卡尔积结合律

• $R \Join (S \Join T) = (R \Join S) \Join T$

# 投影的串接定律（注意条件）

• $\Pi_{A_1, A_2, ..., A_n}(\Pi_{B_1, B_2, ..., B_m}(R)) = \Pi_{A_1, A_2, ..., A_n}(R)$

# 选择的串接定律

• $\sigma_{C_1 \land C_2}(R) = \sigma_{C_1}(\sigma_{C_2}(R))$

# 选择与投影的交换律（注意条件）

• $\sigma_{C}(\Pi_{A_1, A_2, ..., A_n}(R)) = \Pi_{A_1, A_2, ..., A_n}(\sigma_{C}(R))$（条件 C 中只包含 A₁, A₂, ..., A_n）
• $\Pi_{A_1, A_2, ..., A_n}(\sigma_{C}(R)) = \Pi_{A_1, A_2, ..., A_n}\sigma_{C}(\Pi_{A_1, A_2, ..., A_n, B_1, ..., B_m}(R))$

# 选择与笛卡尔积的交换律

• $\sigma_{C}(R \times S) = \sigma_{C}(R) \times S$
• $\sigma_{C}(R \times S) = \sigma_{C_1}(R) \times \sigma_{C_2}(S)$
• $\sigma_{C}(R \times S) = \sigma_{C_2}(\sigma_{C_1}(R) \times S)$

# 选择与并、差的分配律

• $\sigma_{C}(R \cup S) = \sigma_{C}(R) \cup \sigma_{C}(S)$
• $\sigma_{C}(R - S) = \sigma_{C}(R) - \sigma_{C}(S)$

# 投影与并的分配律

• $\Pi_{A_1, A_2, ..., A_n}(R \cup S) = \Pi_{A_1, A_2, ..., A_n}(R) \cup \Pi_{A_1, A_2, ..., A_n}(S)$

# 投影与笛卡尔积的分配律

• $\Pi_{A_1, A_2, ..., A_n, B_1, B_2, ..., B_m}(R \times S) = \Pi_{A_1, A_2, ..., A_n}(R) \times \Pi_{B_1, B_2, ..., B_m}(S)$

# 关系代数表达式的优化算法

1. 把$\sigma_{F_1, F_2, ..., F_n}(R)$ 变换为$\sigma_{F_1}(\sigma_{F_2}(...(\sigma_{F_n}(R))...))$。
2. 对每一个选择尽可能把它移到树的叶端。
3. 对每一个投影尽可能把它移到树的叶端。
4. 合并选择和投影或一个选择后跟一个投影。
5. 将得到的语法树的内节点分组。（每一双目运算和它所有的直接祖先为一组）
6. 生成一个程序，每组节点的计算是程序中的一步。求值顺序为先子孙，后祖先。

# SQL

# 数据定义语言（DDL）

# CREATE

CREATE TABLE <表名> (

  <列名> <数据类型>[ <列级完整性约束条件> ],

  <列名> <数据类型>[ <列级完整性约束条件> ],

  ...

  [,<表级完整性约束条件>]

);

# 数据类型

1. 定长和变长字符串：CHAR (n)、VARCHAR (n)
2. 定长和变长二进制串：BIT (n)、BIT VARING (n)
3. 整型数：INT、SMALLINT、TINYINT
4. 浮点数：FLOAT、DOUBLE PRECISION
5. 日期型：DATE
6. 时间型：TIME
7. 时标：TIMESTAMP

# 列级完整性约束条件

• 主码约束：PRIMARY KEY，只有一个主码时，可以在列定义后面加上 PRIMARY KEY
• 唯一性约束：UNIQUE
• 非空值约束：NOT NULL

# 表级完整性约束条件

• 主码约束：PRIMARY KEY， PRIMARY KEY (列名)
• 参照完整性约束：FOREIGN KEY， FOREIGN KEY (列名) REFERENCES 表名(列名)

# ALTER

ALTER TABLE <表名> ADD <列名> <数据类型> [完整性约束条件];

ALTER TABLE <表名> DROP COLUMN <列名>;

ALTER TABLE <表名> MODIFY COLUMN <列名> <数据类型> [完整性约束条件];

# DROP

DROP TABLE <表名>;

# 添加索引

CREATE [Unique|CLUSTER] INDEX <索引名> ON <表名> (<列名>[<次序>][, <列名>[<次序>]], ...);

• 用 <表名> 指定要建索引的基本表名字
• 索引可以建立在该表的一列或多列上，各列名之间用逗号分隔
• 用 <次序> 指定索引值的排列次序，升序： ASC ，降序： DESC 。缺省值： ASC
• UNIQUE 表明此索引的每一个索引值只对应唯一的数据记录
• CLUSTER 表示要建立的索引是聚集索引

# 唯一索引

• 对于已含重复值的属性列不能建 UNIQUE 索引
• 对某个列建立 UNIQUE 索引后，插入新记录时 DBMS 会自动检查新记录在该列上是否取了重复值。这相当于增加了一个 UNIQUE 约束

# 聚集索引

• 聚集索引是一种特殊的索引，它对表中的数据记录进行了物理排序，使得数据记录的物理存储顺序与索引的逻辑顺序一致
• 在一个基本表上最多只能建立一个聚簇索引
• 聚集索引的用途：对于某些类型的查询，可以提高查询效率
• 聚集索引的适用范围
  • 很少对基表进行增删操作
  • 很少对其中的变长列进行修改操作

# 删除索引

DROP INDEX <索引名> ON <表名>;

# 修改索引

ALTER INDEX <索引名> ON <表名> RENAME TO <新索引名>;

# 数据操纵语言（DML）

# SELECT

# 单表查询

SELECT [DISTINCT] <列名> [<目标列表达式>] 

FROM <表名> 

[WHERE <条件>]

[GROUP BY <列名>]

[HAVING <条件>]

[ORDER BY <列名> [ASC|DESC]];

• <目标列表达式> ：可以是常量、列名、表达式、函数等
• 常用的查询条件： = 、 <> 、 < 、 > 、 <= 、 >= 、 BETWEEN 、 LIKE 、 IN 、 IS NULL 、 AND 、 OR 、 NOT
• 字符串匹配： % 表示任意长度的字符串， _ 表示一个字符： [NOT] LIKE '<匹配串>' [ESCAPE '<转义字符>'] ， ESCAPE 用于指定转义字符。
• 使用集函数： COUNT 、 SUM 、 AVG 、 MAX 、 MIN ， COUNT(*) 表示计算行数， <集函数>([DISTINCT|ALL] <列名>)
• 使用 GROUP BY 后， SELECT 中的列名只能是 GROUP BY 中的列名或集函数
• HAVING 和 WHERE 的区别： WHERE 用于对行进行筛选， HAVING 用于对组进行筛选

# 多表查询

# 等值连接 INNER JOIN

SELECT <列名>

FROM <表名1>, <表名2>

WHERE <表名1>.<列名> = <表名2>.<列名>;

# 外连接 OUTER JOIN

SELECT <列名>

FROM <表名1> 

[LEFT|RIGHT] OUTER JOIN <表名2>

ON <表名1>.<列名> = <表名2>.<列名>;

# TOP-N 查询

SELECT <列名>

FROM <表名>

ORDER BY <列名> [ASC|DESC]

LIMIT N;

# 嵌套查询

# 子查询

• 限制：不能使用 ORDER BY
• 不相关子查询：是由里向外逐层处理。即每个子查询在上一级查询处理之前求解，子查询的结果用于建立其父查询的查找条件。
• 相关子查询
  • 首先取外层查询中表的第一个元组，根据它与内层查询相关的属性值处理内层查询，若 WHERE 子句返回值为真，则取此元组放入结果表；
  • 然后再取外层表的下一个元组；
  • 重复这一过程，直至外层表全部检查完为止。

# IN

SELECT <列名>

FROM <表名>

WHERE <列名> IN (SELECT <列名> FROM <表名>);

# 带有比较运算符的子查询

SELECT <列名>

FROM <表名>

WHERE <列名> <比较运算符> (SELECT <列名> FROM <表名>);

• 当能确切知道内层查询返回单值时，可用比较运算符（>，<，=，>=，<=，!= 或 < >）。
• 与 ANY 或 ALL 谓词配合使用

# 带有 EXISTS 的子查询

• EXISTS 谓词：判断子查询是否返回结果，返回结果为真，否则为假。

  	SELECT <列名>
  	FROM <表名>
  	WHERE EXISTS (SELECT <列名> FROM <表名>);

• NOT EXISTS：判断子查询是否返回结果，返回结果为假，否则为真。

  	SELECT <列名>
  	FROM <表名>
  	WHERE NOT EXISTS (SELECT * FROM <表名>);

• 用 EXISTS/NOT EXISTS 实现全称量词

  	SELECT >
  	FROM <表名> AS T1
  	WHERE NOT EXISTS (
  	SELECT <列名>
  	FROM <表名> AS T2
  	WHERE NOT EXISTS (
  	SELECT <列名>
  	FROM <表名> AS T3
  	WHERE T1.<列名> = T2.<列名> AND T2.<列名> = T3.<列名>
  	)
  	);

# INSERT

# 插入单行

INSERT INTO <表名> (<列名>[, <列名>, ...])

VALUES (<值>[, <值>, ...]);

# 插入子查询

INSERT INTO <表名> (<列名>[, <列名>, ...])

<子查询>;

• SELECT 子句目标列必须与 INTO 子句匹配
  • 值的个数
  • 值的类型

# UPDATE

UPDATE <表名>

SET <列名> = <值>[, <列名> = <值>, ...]

[WHERE <条件>];

# DELETE

DELETE 

FROM <表名>

[WHERE <条件>];

# 视图

# 创建视图

CREATE VIEW <视图名> [(<列名>[, <列名>, ...])]

AS <子查询>

[WITH CHECK OPTION];

• WITH CHECK OPTION ：保证视图中的数据满足视图的定义

# 查询视图

SELECT <列名>

FROM <视图名>;

# 更新视图

UPDATE <视图名>

SET <列名> = <值>[, <列名> = <值>, ...]

[WHERE <条件>];

# 删除视图

DROP VIEW <视图名>;

# 数据控制语言（DCL）

# 授权 GRANT

GRANT <权限>[, <权限>, ...]

[ON <对象类型> <对象名>]

TO <用户或角色>[, <用户或角色>, ...]

[WITH GRANT OPTION];

• <权限> ： SELECT 、 INSERT 、 UPDATE 、 DELETE 、 ALL
• <对象类型> ： TABLE 、 VIEW 、 DATABASE
• WITH GRANT OPTION ：允许被授权的用户或角色将权限授予其他用户或角色

# 撤销 REVOKE

REVOKE <权限>[, <权限>, ...]

[ON <对象类型> <对象名>]

FROM <用户或角色>[, <用户或角色>, ...];

# 关系规范化理论

# 函数依赖

# 函数依赖的定义

设 R (U) 是属性集 U 上的关系模式。X，Y 是 U 的子集。若对于 R (U) 的任意一个可能的关系 r，r 中不可能存在两个元组在 X 上的属性值相等，而在 Y 上的属性值不等，则称 X 函数确定 Y 或 Y 函数依赖于 X，记作 X→Y。

• 决定因素：X
• 平凡函数依赖：X→Y，Y 是 X 的子集，称为平凡函数依赖
• 非平凡函数依赖：X→Y，Y 不是 X 的子集，称为非平凡函数依赖
• 互相依赖：X→Y，Y→X，称为互相依赖，记作 X↔Y

# 完全函数依赖

在关系模式 R (U) 中，若$X→Y$，并且对于 X 的任何一个真子集 X'，都有$X' \nrightarrow Y$，则称 Y 对 X 完全函数依赖，记作$X \overset{F}{\rightarrow} Y$。

# 部分函数依赖

在关系模式 R (U) 中，若$X→Y$，并且存在 X 的真子集 X'，使得$X'→Y$，则称 Y 对 X 部分函数依赖，记作$X \overset{P}{\rightarrow} Y$。

# 传递函数依赖

在关系模式 R (U) 中，若$X→Y$，（$Y \subsetneq X$），$Y \nrightarrow X$，存在 Z，使得$Y→Z$，则称 Y 对 X 传递函数依赖，记作$X \overset{T}{\rightarrow} Y$。

# 码的函数依赖

设 K 为 R (U,F) 中的属性或属性组，若$K \overset{F}{\rightarrow} U$，则称 K 为 R (U,F) 的候选码。

• 主码：若一个关系中有多个候选码，则选其中的一个为主码。
• 主属性：如果一个属性包含在任何一个候选码中，则称该属性为主属性。
• 非主属性：不包含在任何一个候选码中的属性称为非主属性。
• 全码：整个属性组是码
• 外码：关系模式 R 中属性或属性组 X 并非 R 的码，但是 X 是另一个关系模式 S 的码，则称 X 为 R 的外码。
• 超码：一个包含关键字的属性集合也能用函数决定（不是完全函数依赖，而是部分函数确定）属性全集，这种包含主码的属性集合称为超码。

# 范式

# 第一范式

关系模式 R (U) 中的每一个属性都是不可再分的基本数据项。

• 缺点：数据冗余，数据更新异常

# 第二范式

关系模式 R (U) 是第一范式的基础上，非主属性完全函数依赖于任何一个候选码。

# 第三范式

关系模式 R (U) 是第二范式的基础上，非主属性不传递函数依赖于任何一个候选码。

# BCNF 范式

关系模式$R(U，F) ∈1NF$。若$X→Y$ 且$Y⊈ X$ 时$X$ 必含有码，则$R(U，F) ∈BCNF$。即：关系模式$R(U，F)$ 中，若每一个决定因素都包含码，则$R(U，F) ∈BCNF$。

• 一个满足 BCNF 的关系模式有:
  • 所有非主属性对每一个码都是完全函数依赖。
  • 所有主属性对每一个不包含它的码也是完全函数依赖。
  • 没有任何属性完全函数依赖于非码的任何一组属性。

如果$R∈3NF$，且 R 只有一个候选码，则 R 必属于 BCNF

# 数据依赖的公理系统

# 函数依赖集的闭包

# 函数依赖集 F 的逻辑蕴涵

对于 R (U,F)，如果 X→Y 不在 F 中，但是对于其任何一个关系 r，X→Y 都成立，则称 F 逻辑蕴含 X→Y。或者说： X→Y 可以由 F 导出

# 函数依赖集 F 的闭包

定义：在关系模式 R (U，F) 中为 F 及 F 所逻辑蕴含的函数依赖的全体叫做 F 的闭包。记为 F⁺。$F^+=\{X→Y|F及能由F根据Armstrong公理导出\}$

# Armstrong 公理

对于关系模式 R (U,F)，有

1. 自反律：若$Y \subset X \subset U$，则$X→Y$ 为$F$ 所蕴含
2. 增广律：若$X→Y$ 为$F$ 所蕴含，且$Z \subset U$，则$XZ→YZ$ 为$F$ 所蕴含
3. 传递律：若$X→Y$，$Y→Z$ 为$F$ 所蕴含，则$X→Z$ 为$F$ 所蕴含
4. 合并律：若$X→Y$，$X→Z$，则$X→YZ$ 为$F$ 所蕴含
5. 伪传递律：若$X→Y$，$WY→Z$，则$WX→Z$ 为$F$ 所蕴含
6. 分解律：若$X→Y$ 及$Z \subseteq Y$，$X→Z$ 为$F$ 所蕴含

# 属性集闭包与 F 逻辑蕴涵的充要条件

# X 关于函数依赖集 F 的闭包

设 F 为属性集 U 上的一组函数依赖，$X \subseteq U$，$X_F^+=\{A|X→A能由F根据Armstrong公理导出\}$，X_F⁺ 称为属性集 X 关于函数依赖集 F 的闭包

# F 逻辑蕴涵的充要条件

设 F 为属性集 U 上的一组函数依赖，$X,Y\subseteq U$， $X→Y$ 能由 F 根据 Armstrong 公理导出的充分必要条件是$Y\subseteq X_F^+$

# 求属性集闭包 X_F⁺ 的算法

算法：输入：X，F，输出：X_F⁺

1. 令$X^{(0)}=X$，$i=0$
2. 求 B, $B=\{A|(\exist V)(\exist W)(V→W∈F \wedge V \subseteq X^{(i)} \wedge A∈W)\}$
3. $X^{(i+1)}=B∪X^{(i)}$
4. 判断$X^{(i+1)}= X^{(i)}$ 吗？
5. 若相等或$X^{(i)}=U$ 则$X^{(i)}$ 就是$X_F^+$，算法终止。
6. 若否，则$i=i+1$，返回第 2 步。

对于属性闭包算法的终止条件，下列四种方法是等价的：

1. X⁽ⁱ⁺¹⁾ = X⁽ⁱ⁾
2. 当发现 X⁽ⁱ⁾ 包含了全部属性时；
3. 在 F 中的函数依赖的右部属性中，再也找不到 X⁽ⁱ⁾ 中未出现过的属性。
4. 在 F 中未用过的函数依赖的左部属性中已没有 X⁽ⁱ⁾ 的子集。

# 码值理论

对于给定的关系 R，和函数依赖集 F，可将其属性分为 4 类：

• L 类：仅出现在左部的属性
• R 类：仅出现在右部的属性
• LR 类：既出现在左部又出现在右部的属性
• N 类：既不出现在左部也不出现在右部的属性

# 求候选码的相关定理

• 对于给定的关系模式 R 及其函数依赖集 F，若 X（X∈R）是 L 类属性，则 X 一定是 R 的候选码的成员。
• 对于给定的关系模式 R 及其函数依赖集 F，若 X（X∈R）是 N 类属性，则 X 一定是 R 的候选码的成员。
• 对于给定的关系模式 R 及其函数依赖集 F，若 X（X∈R）是 R 类属性，则 X 必不在任何候选码中。
• 对于给定的关系模式 R 及其函数依赖集 F，若 X（X∈R）是 LR 类属性，则 X 可能是 R 的候选码的成员。

# 多属性依赖集候选关键字求解算法

1. 将 R 的所有属性分为 L、R、N 和 LR 两类，令 X 代表 L 和 N 类，Y 代表 LR 类
2. 求 X⁺。若 X⁺ 包含了 R 的全部属性，则 X 为 R 的惟一候选关键字，转 5；否则转 3
3. 在 Y 中取一属性 A，求 (XA)⁺ 。若它包含 R 的全部属性，则转 4；否则，调换一属性反复进行这一过程，直到试完所有 Y 中的属性。
4. 如果已找出所有候选关键字，则转 5；否则在 Y 中依次取两个、三个、……，求它们的属性闭包，直到其闭包包含 R 的全部属性
5. 停止，输出结果

# 函数依赖的推理规则

Armstrong 公理系统是有效的（正确性）、完备的。

• 正确性：指公理 1、2、3 是正确的。
• 有效性：指由 F 出发根据 Armstrong 公理推导出来的每一个函数依赖一定在 F⁺。
• 完备性：指 F⁺ 中的每一个函数依赖，必定可以由 F 出发根据 Armstrong 公理推导出来。

# 函数依赖集的等价和最小函数依赖集

• 等价定义：如果 G⁺=F⁺，则称 G 和 F 是等价的，记为 G=F。
• F⁺=G⁺ 的充要条件是$F \subseteq G^+$ 且$G \subseteq F^+$。
• 最小依赖集：如果函数依赖集 F 满足下列条件，则称 F 为一个极小函数依赖集，也称最小依赖集或最小覆盖。
  • F 中任一函数依赖的右部仅含有一个属性。
  • F 中不存在这样的函数依赖 X→A，使得 F 与 F-{X →A} 等价。[不存在冗余 FD]
  • F 中不存在这样的函数依赖 X→A，X 有真子集 Z 使得 F-{X →A}∪{Z→A} 与 F 等价。[决定因素不存在冗余]

# 最小函数依赖集的求解算法

1. 将$X→A_1A_2…A_k(k>2)$ 转换为$X→A_i(i=1,2,…,k)$。[将右部属性分解为单个属性]
2. 逐个检查函数依赖$X→A$，令$G=F-\{X→A\}$，若$A∈(X)_G^+$，则从 F 中去掉$X→A$。[逐个检查 F 中的每一项，看是否$F-\{X→A\}$ 与 F 等价]
3. 逐个检查函数依赖$X→A$，若$X=B_1B_2…B_m$，逐个考查$B_i(i=1,2,…,m)$，若$A∈(X-B_i)_F^+$，则以$X-B_i$ 取代 X。[判每个函数依赖左部是否有冗余属性]

# 关系模式的分解算法

# 模式分解的定义

关系模式$R(U,F)$ 的一个分解$ρ=\{R_1(U_1,F_1),…,R_k(U_k, F_k)\}$ 是若干个关系模式的一个集合，其中，

1. $U=\bigcup\limits_{i=1}^n U_i$，$F_i$ 是 F 在$U_i$ 上的投影。则称 ρ 是 R (U) 的一个分解。
2. 对每个$i,j(𝑖≤𝑗≤𝑛,1≤𝑗≤𝑛且𝑖≠𝑗)$ 有$U_i≠U_j$
3. $F_i(i=1,2,…,n)$ 是 F 在$U_i$ 上的投影，函数依赖集合$\{X\rightarrow Y | X\rightarrow Y\in F^+ \wedge XY \subseteq U_i\}$ 的一个覆盖 F_i 叫做在属性 U_i 上的投影。

# 求 F_i 的算法

定义：设$ρ=\{ R_1<U_1,F_1>,R_2<U_2,F_2>,…,R_k<U_k,F_k>\}$ 是关系模式$R<U, F>$ 的一个分解，$U= \{A_1, …, A_n\}$，$F= \{ FD_1, FD_2, …, FD_m\}$ (假设 F 为最小函数依赖集) 。

1. 逐一考查 F 中的每一函数依赖$X→Y$，若 X,Y 中的每一属性都在$R_i$ 中，则$X→Y∈F_i$，转 (2)；
2. 依次取$R_i$ 中的单一属性 B，求$B_F^＋$，若$A_j ⊆ U_i$ 且$A_j ⊆ B_F^＋$且$B→A_j$ 不能由当前求得的$F_i$ 逻辑地推出，则$B→A_j ∈F_i$，令$U_i＝ U_i－B$，转 (3)；
3. 依次任取$U_i$ 中的多个属性构成属性组 X，若 X 不是当前求得的$F_i$ 中的函数依赖左部的子集，求$X_F^＋$ ，若$A_j⊆U_i$ 且$A_j⊆X_F^＋$且$X→A_j$ 不能由当前求得的$F_i$ 逻辑地推出，则$X→A_j ∈F_i$，转 (4)；
4. 重复 (3)，直到取尽$U_i$ 中的所有属性或所有相同属性个数的 X 均是当前求得的$F_i$ 的某一函数依赖的左部的子集，算法结束。

注：若 F 为最小函数依赖集，此算法求得的$F_i$ 亦为最小函数依赖集。

# 分解的无损连接性判定

# 无损连接性的定义

如果一个关系模式分解后，可以通过自然连接恢复原模式的信息，这一特性称为分解的无损连接性。

# 无损连接性的判定

$ρ=\{R_1(U_1,F_1),…,R_k(U_k,F_k)\}$ 是$R(U,F)$ 的一个分解，$U=\{A_1,…,A_n\}$，$F=\{FD_1,FD_2,…,FD_p\}$。

1. 构造一个 n 列 k 行的二维表 T，$T_{ij}=\begin{cases} a_j & A_j\in R_i \\ b_{ij} & A_j\notin R_i \end{cases}$
2. 根据 F 中函数依赖修改表 T 的内容，修改规则：逐个考察 F 中的每个函数依赖$X→Y$，在属性 X 所在的那些列上找出具有相同符号的行，在这些行上使对应于 Y 的各属性列位置上的符号改为相同，如果其中有一个符号为$a_j$，则把其它符号也改为$a_j$，否则改为$b_{mj}$，其中 m 是这些行的最小行号。直至在表中发现一行已变成$a_1a_2…a_k$，或表不能再进行修改为止。
3. 如果发现表中有一行已变成$a_1a_2…a_k$，则表示该分解具有无损连接性，否则分解不是无损连接的。

换的原则：

1. 有 a，有 b，向 a 看齐。
2. 只有 b，但下标不同，则大的向小的看齐

# 独立投影法则

如果 R 只被分解为两个关系模式，则可用更简单的方法进行检验：

定理：设$ρ=\{R_1(U_1),R_2(U_2)\}$ 是 R (U) 的一个分解，则 ρ 为无损分解的充分必要条件为$(U_1∩U_2)\rightarrow (U_1-U_2)∈F^+$ 或$(U_1∩U_2)\rightarrow (U_2-U_1) ∈F^+$

结论：如果两个关系模式间的公共属性集至少包含其中一个关系模式的关键字，则此分解必定具有无损连接性（或连接不失真性）

# 分解的保持函数依赖性判定

若关系$R(U,F)$ 的一个分解$ρ=\{R_1(U_1,F_1),…,R_k(U_k,F_k)\}$ 的所有函数依赖的并集（$\bigcup\limits_{i=1}^kF_i$）逻辑蕴涵了 F 中所有函数依赖，即 $(\bigcup\limits_{i=1}^kF_i)^+=F^+$，则称分解 ρ 具有函数依赖保持性。

# 关系模式的分解

# 分解算法 1：转换为 3NF 的保持函数依赖的分解

输入：关系模式 R 和函数依赖集 F
输出：结果为 3NF 的一个依赖保持分解

步骤：

1. 对 R 中的函数依赖集 F 进行极小化处理（处理后的函数依赖集仍记为 F）
2. 找出不在 F 中出现的属性，把这样的属性构成一个关系模式，把这些属性从 U 中去掉，剩余的属性仍记为 U
3. 若有$X\rightarrow A∈F$，且$XA=U$，则$ρ=\{R\}$，算法中止
4. 否则，对于 F 中的每一个$X\rightarrow A$，构成一个关系模式$XA$。（如果有$X\rightarrow A_1,X\rightarrow A_2,…,X\rightarrow A_n$（左部相同），则可以用模式$XA_1A_2…A_n$ 代替 n 个模式$XA_1,XA_2,…,XA_n$;
5. 算法结束

# 分解算法 2：结果为 3NF，且具有依赖保持和连接不失真的分解

1. 设$X$ 是$R(U,F)$ 的码。$R(U,F)$ 已由前面的算法 1 分解为$ρ=\{R_1(U_1,F_1),R_2(U_2,F_2),…,R_k(U_k,F_k)\}$, 令$τ= ρ∪X$。
2. 若有某个$U_i$，$X\subseteq U_i$，将$X$ 从$τ$ 中去掉
3. 若有某个$U_i$，使得$X \subseteq U_i$，$τ$ 就是所求的分解

# 数据库事务

# 关系数据库的事务定义

• 一个事务可以是一条 SQL 语句，或者是一组 SQL 语句，甚至整个程序。
• 在一个 SQL 程序中可以包含一个或者多个事务。

# 两种事务定义方式

# 隐性控制

当程序员没有定义显性事务的时候，就由数据库管理系统按缺省的规则自动划分事务。例如，把每条单独的 SQL 语句都视为一个事务

# 显性控制

• BEGIN TRANSACTION ：是事务开始的标记，表示开始一个事务。
• COMMIT ：是事务成功结束的标记，表示提交当前事务。
• ROLLBACK ：是事务失败结束的标记，表示撤销当前事务

# 事务执行的五种状态

# 活动状态（Active）

事务正在执行，还没有执行最后一条操作语句，此时事务处于活动状态

# 部分提交状态（Partially Committed）

当事务中最后一条操作语句被执行之后，事务处于部分提交状态。
操作的输出可能还驻留在主存中没有及时写入物理磁盘，如果发生故障，则事务对数据库的更新影响依然可能会丢失，不能说事务已经成功完成

# 提交状态（Committed）

当事务执行 COMMIT 之后就处于提交状态。
此时，事务不但部分提交了，并且已经将一些必要的信息写入磁盘，确保即使此时发生故障，事务对数据库的更新也能够重建并永久保持。处于提交状态的事务，就成功结束

# 失败状态（Failed）

当事务运行的过程中发生了故障，不能继续执行下去，则事务执行处于失败状态。
处于失败状态的事务，必须撤销事务对数据库所造成的任何改变，恢复到事务开始执行之前的数据库状态。

# 中止状态（Aborted）

当事务显式或隐式执行 ROLLBACK 之后就处于中止状态。
此时，处于失败状态的事务，已经将数据库恢复到事务开始执行之前的状态，处于中止状态的事务，就已经失败结束了。

# 事务的 ACID 特性

• 原子性（Atomicity）：事务是不可分割的工作单位
• 一致性（Consistency）：事务提交后，数据库从一个一致性状态变到另一个一致性状态。
• 隔离性（Isolation）：在事务完成之前，它对数据库产生的结果不能被其它事务引用。
• 持续性（Durability）： 一旦事务执行成功 (提交)，其对数据产生的效果永久有效

# 事务恢复策略

# 事务故障的恢复

恢复策略：反向扫描日志文件，将日志中更新前的数据写回到数据库中，直至事务的开始标志。

# 系统故障的恢复

恢复策略：撤销故障发生时未完成的事务，重做已完成的事务。

方法：

1. 正向扫描日志文件；找出故障发生前已经提交的事务，将该事务放入 REDO 队列；找出故障发生前未提交的事务，将其放入 UNDO 队列。
2. 对 UNDO 队列做撤销操作
3. 对 REDO 队列做重做操作

# 介质故障的恢复

恢复策略：利用数据库副本和日志文件副本进行恢复。（需要 DBA 介入）

# 系统使用检查点进行恢复的步骤

从重新开始文件中找到最后一个检查点记录在日志文件中的地址，找到最后一个检查点

• 由该检查点找到检查点建立时刻所有的动态事务清单
• 从检查点正向扫描日志文件
  • 如有新开始的事务，放入 UNDO 队列
  • 如有提交的事务，将该事务从 UNDO 放入 REDO 队列
• 执行 UNDO 和 REDO 处

# 并发

# 并发操作引发的问题

• 丢失修改：两个事务同时读取同一数据项，一个事务修改后，另一个事务再修改，前一个事务的修改被覆盖
• 脏读：一个事务读取到另一个事务未提交的数据
• 不可重复读：一个事务读取到另一个事务已提交的数据
  • 读不一致
  • 删除幻影
  • 插入幻影

# 并发调度及可串行化

# 事务的表示方法

$R_i(X)$ 表示事务$T_i$ 的读 X 操作
$W_i(X)$ 表示事务$T_i$ 的写 X 操作

# 冲突操作

定义：如果两个操作来自不同的事务，它们对同一数据单位进行操作，并且其中至少有一个是写操作，则称这两个操作是相互冲突的或冲突操作。

# 串行调度

调度$S$ 中的任意两个事务$T_i$ 和$T_j$，如果$T_i$ 的所有操作都先于$T_j$ 的所有操作，或者相反，则称$S$ 为串行调度。

串行调度事务执行的结果总是正确的，串行调度不能够充分利用系统资源

# 并发调度

如果在一个调度中，各个事务交叉地执行，这个调度称为并发调度。

# 可串行化的调度

如果一个事务集的并发调度与某一串行调度是等价的，则称该并发调度是可串行化的

调整次序注意：

• 不能改变冲突操作的先后次序
• 同一事务的读写先后顺序不能改变

可串行化是作为并发调度正确与否的判定准则！

# 冲突可串行化

一个调度 Sc 在保证冲突操作的次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一个调度 Sc’，如果 Sc’是串行的称调度 Sc 为冲突可串行化调度

一个调度是冲突可串行化的，一定是可串行化调度，反之则不成立！

# 冲突可串行化的判定方法：构造前驱图

设 S 是若干事务$\{T_1,T_2,…,T_n\}$ 的一个调度，S 的前驱图$G(V，E)$ 是一个有向图，其构成规则如下：

• V 是由所有参加调度的事务构成的节点
• E 是图中的一条有向边，如果 O_i 和 O_j 是冲突操作，且 O_i 先于 O_j 执行，则在图中有一条边 T_i→T_j
  • 事务 T_i 读 x 在事务 T_j 写 x 之前
  • 事务 T_i 写 x 在事务 T_j 读 x 之前
  • 事务 T_i 写 x 在事务 T_j 写 x 之前

若一个调度的前趋图无环，则该调度是调度可串行化的

由于图中无回路，必有一个节点无入弧，将这个节点及其相连的弧删去，并把该节点存入先进先出的队列中。对剩下的图做同样的处理，直至所有节点移入队列中。按照队列中次序串行安排各事务的执行，就可以得到一个等价的串行调度（拓扑排序）

冲突可串行化调度是可串行化调度的充分条件，不是必要条件！

# 事物的隔离性级别

# SQL92 定义了四种隔离性级别

• 读未提交（Read uncommitted）：最低的隔离级别，一个事务可以读到另外一个事务未提交的数据，不允许丢失修改，接受读脏数据和不可重复读现象。
• 读已提交（Read committed）：若事务还没提交，其他事务不能读取该事务正在修改的数据；不允许丢失修改和读脏数据，接受不可重复读现象。
• 可重复读（Repeatable read）：事务多次读取同一数据对象的结果一致。不允许丢失修改、读脏数据和读不一致，接受幻影读现象。
• 可串行化（Serializable）最高级别的隔离性，保证可串行化，不允许丢失修改、读脏数据、读不一致以及幻影读现象的发生

# 封锁技术

# 排它锁（X 锁，写锁）

若事务 T 对数据对象 A 加上排它锁，则只允许 T 读取和修改 A，不允许其他任何事务再对 A 加锁，直到 T 释放 A 上的 X 锁。

# 共享锁（S 锁，读锁）

若事务 T 对数据对象 A 加上共享锁，则事务 T 可以读 A 但不能修改 A，其他事务只能对 A 加 S 锁，而不能加 X 锁，直到 T 释放 A 上的 S 锁。

# 封锁协议

# 两阶段协议（Two- Phase Locking Protocol ，2PL 协议）

某一事务在对数据进行读、写之前，先要申请并获得对该数据的封锁。
在释放一个封锁之后，事务不再申请和获得任何其它封锁

任何一个遵从 2PL 协议的调度都是可串行化的

• 说明 1：事务遵守 2PL 协议是可串行化调度的充分条件，而不是必要条件
• 说明 2：事务遵守 2PL 协议可达到第 3 级封锁协议的要求

# 封锁导致的问题

# 死锁

事务 T1 已经封锁 A，而又想申请封锁 B，而此时事务 T2 已经封锁 B，而又想申请封锁 A，这样，T1 等待 T2 释放 B，而 T2 等待 T1 释放 A，使得 T1、T2 均无法继续执行下去，这种情况称为死锁。

死锁检测

• 超时法： 事务的等待超过了规定的时限
• 等待图法：检测等待图中是否有回路存在。

# 活锁

事务 T1，T2 申请数据对象 A，T1 先给 A 加锁，T1 释放 A 上的锁后，事务 T3 又给 A 加锁，T2 等待，这样，A 始终被其他事务封锁，事务 T2 可能长时间得不到 A，这种情况称为活锁

避免活锁的方法：采用先来先服务的服务