关系

域

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

笛卡尔积

给定一组域D1, D2, …, Dn，它们的笛卡尔积是指所有可能的n元组的集合。D1×D2×...×Dn={(d1,d2,...,dn)∣d1∈D1,d2∈D2,...,dn∈Dn}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\}

关系的数学定义

D1×D2×...×DnD_1 \times D_2 \times ... \times D_n的一个子集称为关系，关系的元组称为关系的行，用R(D1,D2,...,Dn)R(D_1, D_2, ..., D_n)表示，其中RR是关系名，nn是关系的度，D1,D2,...,DnD_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⋈SR \Join S

等值连接

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

外连接

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

除：÷\div

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

A B
1 1
1 2
1 3
2 2
2 3

S：

B
1
2
3

则R ÷\div S：

A
1
除运算的代数表达式

R÷S=ΠA(R)−ΠA((ΠA(R)×ΠB(S))−R)R \div S = \Pi_{A} (R) - \Pi_{A} ((\Pi_{A} (R) \times \Pi_B(S)) - R)

查询优化

查询优化的准则

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

关系代数等价变换规则

连接、笛卡尔积交换律

  • R⋈S=S⋈RR \Join S = S \Join R

连接、笛卡尔积结合律

  • R⋈(S⋈T)=(R⋈S)⋈TR \Join (S \Join T) = (R \Join S) \Join T

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

  • ΠA1,A2,...,An(ΠB1,B2,...,Bm(R))=ΠA1,A2,...,An(R)\Pi_{A_1, A_2, ..., A_n}(\Pi_{B_1, B_2, ..., B_m}(R)) = \Pi_{A_1, A_2, ..., A_n}(R)

选择的串接定律

  • σC1∧C2(R)=σC1(σC2(R))\sigma_{C_1 \land C_2}(R) = \sigma_{C_1}(\sigma_{C_2}(R))

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

  • σC(ΠA1,A2,...,An(R))=ΠA1,A2,...,An(σC(R))\sigma_{C}(\Pi_{A_1, A_2, ..., A_n}(R)) = \Pi_{A_1, A_2, ..., A_n}(\sigma_{C}(R))（条件C中只包含A1, A2, …, An）
  • ΠA1,A2,...,An(σC(R))=ΠA1,A2,...,AnσC(ΠA1,A2,...,An,B1,...,Bm(R))\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))

选择与笛卡尔积的交换律

  • σC(R×S)=σC(R)×S\sigma_{C}(R \times S) = \sigma_{C}(R) \times S
  • σC(R×S)=σC1(R)×σC2(S)\sigma_{C}(R \times S) = \sigma_{C_1}(R) \times \sigma_{C_2}(S)
  • σC(R×S)=σC2(σC1(R)×S)\sigma_{C}(R \times S) = \sigma_{C_2}(\sigma_{C_1}(R) \times S)

选择与并、差的分配律

  • σC(R∪S)=σC(R)∪σC(S)\sigma_{C}(R \cup S) = \sigma_{C}(R) \cup \sigma_{C}(S)
  • σC(R−S)=σC(R)−σC(S)\sigma_{C}(R - S) = \sigma_{C}(R) - \sigma_{C}(S)

投影与并的分配律

  • ΠA1,A2,...,An(R∪S)=ΠA1,A2,...,An(R)∪ΠA1,A2,...,An(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)

投影与笛卡尔积的分配律

  • ΠA1,A2,...,An,B1,B2,...,Bm(R×S)=ΠA1,A2,...,An(R)×ΠB1,B2,...,Bm(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. 把σF1,F2,...,Fn(R)\sigma_{F_1, F_2, ..., F_n}(R)变换为σF1(σF2(...(σFn(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→YX→Y，并且对于X的任何一个真子集X’，都有X′↛YX' \nrightarrow Y，则称Y对X完全函数依赖，记作X→FYX \overset{F}{\rightarrow} Y。

部分函数依赖

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

传递函数依赖

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

码的函数依赖

设K为R(U,F)中的属性或属性组，若K→FUK \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)∈1NFR(U，F) ∈1NF。若X→YX→Y且Y⊈XY⊈ X时XX必含有码，则R(U，F)∈BCNFR(U，F) ∈BCNF。即：关系模式R(U，F)R(U，F)中，若每一个决定因素都包含码，则R(U，F)∈BCNFR(U，F) ∈BCNF。

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

如果R∈3NFR∈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公理导出}F^+=\{X→Y|F及能由F根据Armstrong公理导出\}

Armstrong公理

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

  1. 自反律：若Y⊂X⊂UY \subset X \subset U，则X→YX→Y为FF所蕴含
  2. 增广律：若X→YX→Y为FF所蕴含，且Z⊂UZ \subset U，则XZ→YZXZ→YZ为FF所蕴含
  3. 传递律：若X→YX→Y，Y→ZY→Z为FF所蕴含，则X→ZX→Z为FF所蕴含
  4. 合并律：若X→YX→Y，X→ZX→Z，则X→YZX→YZ为FF所蕴含
  5. 伪传递律：若X→YX→Y，WY→ZWY→Z，则WX→ZWX→Z为FF所蕴含
  6. 分解律：若X→YX→Y及Z⊆YZ \subseteq Y，X→ZX→Z为FF所蕴含

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

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

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

F逻辑蕴涵的充要条件

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

求属性集闭包XF^+^的算法

算法：输入：X，F，输出：XF^+^

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

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

  1. X^(i+1)^ = X^(i)^
  2. 当发现X^(i)^包含了全部属性时；
  3. 在F中的函数依赖的右部属性中，再也找不到X^(i)^中未出现过的属性。
  4. 在F中未用过的函数依赖的左部属性中已没有X^(i)^的子集。
码值理论

对于给定的关系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⊆G+F \subseteq G^+且G⊆F+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→A1A2…Ak(k>2)X→A_1A_2…A_k(k>2)转换为X→Ai(i=1,2,…,k)X→A_i(i=1,2,…,k)。[将右部属性分解为单个属性]
  2. 逐个检查函数依赖X→AX→A，令G=F−{X→A}G=F-\{X→A\}，若A∈(X)G+A∈(X)_G^+，则从F中去掉X→AX→A。[逐个检查F中的每一项，看是否F−{X→A}F-\{X→A\}与F等价]
  3. 逐个检查函数依赖X→AX→A，若X=B1B2…BmX=B_1B_2…B_m，逐个考查Bi(i=1,2,…,m)B_i(i=1,2,…,m)，若A∈(X−Bi)F+A∈(X-B_i)_F^+，则以X−BiX-B_i取代X。[判每个函数依赖左部是否有冗余属性]

关系模式的分解算法

模式分解的定义

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

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

定义：设ρ={R1<U1,F1>,R2<U2,F2>,…,Rk<Uk,Fk>}ρ=\{ R_1<U_1,F_1>,R_2<U_2,F_2>,…,R_k<U_k,F_k>\}是关系模式R<U,F>R<U, F>的一个分解，U={A1,…,An}U= \{A_1, …, A_n\}，F={FD1,FD2,…,FDm}F= \{ FD_1, FD_2, …, FD_m\} (假设F为最小函数依赖集) 。

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

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

分解的无损连接性判定

无损连接性的定义

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

无损连接性的判定

ρ={R1(U1,F1),…,Rk(Uk,Fk)}ρ=\{R_1(U_1,F_1),…,R_k(U_k,F_k)\}是R(U,F)R(U,F)的一个分解，U={A1,…,An}U=\{A_1,…,A_n\}，F={FD1,FD2,…,FDp}F=\{FD_1,FD_2,…,FD_p\}。

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

换的原则：

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

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

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

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

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

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

关系模式的分解

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

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

步骤：

  1. 对R中的函数依赖集F进行极小化处理（处理后的函数依赖集仍记为F）
  2. 找出不在F中出现的属性，把这样的属性构成一个关系模式，把这些属性从U中去掉，剩余的属性仍记为U
  3. 若有X→A∈FX\rightarrow A∈F，且XA=UXA=U，则ρ={R}ρ=\{R\}，算法中止
  4. 否则，对于F中的每一个X→AX\rightarrow A，构成一个关系模式XAXA。（如果有X→A1,X→A2,…,X→AnX\rightarrow A_1,X\rightarrow A_2,…,X\rightarrow A_n（左部相同），则可以用模式XA1A2…AnXA_1A_2…A_n代替n个模式XA1,XA2,…,XAnXA_1,XA_2,…,XA_n;
  5. 算法结束
分解算法2：结果为3NF，且具有依赖保持和连接不失真的分解
  1. 设XX是R(U,F)R(U,F)的码。R(U,F)R(U,F)已由前面的算法1分解为ρ={R1(U1,F1),R2(U2,F2),…,Rk(Uk,Fk)}ρ=\{R_1(U_1,F_1),R_2(U_2,F_2),…,R_k(U_k,F_k)\},令τ=ρ∪Xτ= ρ∪X。
  2. 若有某个UiU_i，X⊆UiX\subseteq U_i，将XX从ττ中去掉
  3. 若有某个UiU_i，使得X⊆UiX \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处

并发

并发操作引发的问题

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

并发调度及可串行化

事务的表示方法

Ri(X)R_i(X)表示事务TiT_i的读X操作
Wi(X)W_i(X)表示事务TiT_i的写X操作

冲突操作

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

串行调度

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

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

并发调度

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

可串行化的调度

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

调整次序注意：

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

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

冲突可串行化

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

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

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

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

  • V是由所有参加调度的事务构成的节点
  • E是图中的一条有向边，如果Oi和Oj是冲突操作，且Oi先于Oj执行，则在图中有一条边Ti→Tj
    • 事务Ti读x在事务Tj写x之前
    • 事务Ti写x在事务Tj读x之前
    • 事务Ti写x在事务Tj写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锁。

封锁协议

封锁级别 加锁 放锁 解决问题
一级 事务T在修改数据A之前必须先对其加X锁 事务结束才释放X锁 解决丢失修改问题
二级 一级封锁协议加上事务T在读取数据A之前必须对其加S锁 读完后即可释放S锁 解决丢失修改和读脏数据问题
三级 一级封锁协议加上事务T在读取数据A之前必须对其加S锁 事务结束才释放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，这种情况称为活锁

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