《数据库系统概论》笔记

1 绪论

数据库是长期存储在计算机内有组织、大量、共享的数据集合。它可以供各种用户共享，具有最小冗余度和较高的数据独立性。数据库管理系统在数据库建立、运用和维护时对数据库进行统一控制，以保证数据的完整性和安全性，并在多用户同时使用数据库时进行并发控制，在发生故障后对数据库进行恢复。

数据与数据的结构

视图（view），或数据（data）是某种表现形式下表现出来的数据库中的数据。

模式（schema）是对数据库中数据所进行的一种结构性的描述，是所观察到数据的结构信息。

三级模式

外模式，或用户模式，是某一用户能够看到与处理的数据的结构描述，是局部的。

模式，或概念模式，是从全局角度理解/管理的数据的结构描述，含相应的关联约束。

内模式，或物理模式，是存储在介质上的数据的结构描述。

两层映像

E-C Mapping：将外模式映射为概念模式，从而支持数据概念视图向外部视图的转换，便于用户观察和使用。保证了逻辑独立性。

C-I Mapping：将概念模式映射为内模式，从而支持数据概念视图向内部视图的转换，便于机器存储和处理。保证了物理独立性。

模式与模式的结构

数据模型，是规定模式统一描述方式的模型，是对模式本身结构的抽象。

三大经典数据模型：关系模型（表）、层次模型（树）、网状模型（图）。

关系模型

关系模型是处理关系（Table）的，由三部分组成：基本结构、关系运算和完整性约束。

2 关系数据库

2.1 关系数据库结构及形式化定义

域

域是一组具有相同数据类型的值的集合

笛卡尔积

$D_1 \times D_2 \times … \times D_n = {(d_1, d_2, …, d_n)|d_i \in D_i, i = 1, 2, …, n} $

每个元素 $(d_1, d_2, ..., d_n)$(d1​,d2​,...,dn​) 称为元组，元素中每一个值 $d_i$di​ 称为分量。

一个域允许的不同取值个数称为这个域的基数，笛卡尔积得到的集合的基数为 $M=\prod_{i=1}^n m_i$M=∏i=1n​mi​ 。

关系

$D_1 \times D_2 \times ... \times D_n$D1​×D2​×...×Dn​ 的子集（一般是具有某一方面意义的真子集）叫做在域 $D_1, D_2, ..., D_n$D1​,D2​,...,Dn​ 上的关系，表示为 $R(D_1, D_2, ..., D_n)$R(D1​,D2​,...,Dn​)，R 是关系的名字，n 是关系的目或度数。

关系的中某一属性组的值能唯一地标识一个元组，而其子集不能，则称该属性组为候选码。若一个关系中有多个候选码，则选定其中一个为主码。候选码中的属性称为主属性，其他的则为非主属性。若所有属性都是候选码，则为全码。

关系的三种类型

1. 基本表/基本关系（实际存储数据的逻辑表示）
2. 查询表（查询结果对应的表）
3. 视图表（虚表，不对应实际存储的数据）

基本关系的性质

1. 列是同质的，即同属一个域
2. 不同的列可出自不同的域
3. 列是无序的
4. 候选码的值不能相同
5. 行是无序的
6. 每一个分量必须是一个不可分的数据项（最基本的性质）

关系模式

$R(U, D, DOM, F)$R(U,D,DOM,F)，R 为关系名，U 为属性名集合，D 为 U 中属性的域，DOM 为属性到域的映射集合，F 为属性间的数据依赖关系集合。

关系是关系模式在某一时刻的状态或内容。关系模式是静态的，而关系是动态的。

2.3 关系的完整性

实体完整性

关系数据库中每个元组应该是可区分的，是唯一的，这样的约束条件用实体完整性来保证。

实体完整性的规则即基本关系的主属性不可取空值。

参照完整性

属性 F 不是基本关系 R 的码，属性 K 是基本关系 S 的主码，若 F 与 K 相对应，则 F 是 R 的外码，且 R 称为参照关系，S 称为被参照关系。外码不一定要与相对应的主码同名，但实践中往往同名。

参照完整性规则就是定义外码与主码之间的引用规则：若属性 F 是基本关系 R 的外码，那么对于 R 中的每个元组，F 必须取空值或等于被参照关系中某个元素的主码值。

用户定义的完整性

用户定义的完整性就是针对某一具体关系数据库的约束条件，它反应某一具体应用所涉及的数据必须满足的语义要求。

2.4 关系代数

基本关系操作

选择、投影、并、差、笛卡尔积

传统的集合运算

并（$\cap$∩）、差（$-$−）、交（$\cup$∪）、笛卡尔积（$\times$×）

选择

选择，即从关系中选择出满足给定条件的诸元组，是从行的角度上进行的运算。

$σ_F(R)=\{t|t \in R \land F(t)=true\}$σF​(R)={t∣t∈R∧F(t)=true} ，F 表示选择条件 ，基本形式为 $X \theta Y$XθY。

投影

投影，即从关系中选择出若干属性列组成新的关系，是从列的角度上进行的运算。

$Π_A(R)= \{t[A]|t \in R\}$ΠA​(R)={t[A]∣t∈R}，A 为 R 中的属性列，需要去除重复的行。

连接

连接，即从两个关系的笛卡尔积中选取属性间满足一定条件的元组。

$R \bowtie_{A \theta B} S=\{t_rt_s|t_r \in R \land t_s \in S \land t_r[A] \ \theta \ t_s[B]\}$R⋈AθB​S={tr​ts​∣tr​∈R∧ts​∈S∧tr​[A] θ ts​[B]}，其中 A 和 B 分别为 R 和 S 上列数相等且可比的属性组，θ 是比较运算符。

θ 为 = 的连接运算称为等值连接。自然连接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是同名的属性组，并且在结果中把重复的属性列去掉。即若 R 和 S 中具有相同的属性组 B，U 为 R 和 S 的全体属性集合，则自然连接可记作 $R \bowtie S = \{t_rt_s[U-B]|t_r \in R \land t_s \in S \land t_r[B] = t_s[B]\}$R⋈S={tr​ts​[U−B]∣tr​∈R∧ts​∈S∧tr​[B]=ts​[B]}。

做自然连接时，公共属性在一个关系中的值，在另一个关系中不存在，就会导致这些元组被舍弃，被称为悬浮元组。如果把悬浮元组页保存在结果中，而在其他属性上填空值，那么这种连接就叫做外连接。只保留左边的悬浮元组叫左外连接，只保留右边的悬浮元组叫右外连接。

除

给定一个关系 R(X, Z)，当 t[X] = x 时，x 在 R 中的象集定义为 $Z_x = \{t[Z]|t \in R,t[X]=x\}$Zx​={t[Z]∣t∈R,t[X]=x}

设关系 R 除以关系 S 的结果为关系 T，则 T 包含所有在 R 但不在 S 中的属性及其值，且 T 的元组与 S 的元组的所有组合都在 R 中。

给定 R(X, Y) 和 S(Y, Z)，其中 X、Y、Z 为属性组。R 中的 Y 与 S 中的 Y 可以不同名，但必须来自相同的域。R 除以 S 得到关系 P(X)，其中元组在 X 上分量值 x 的象集 $Y_x$Yx​ 包含 S 在 Y 上投影的集合，即

$R \div S = \{t_r[X] \ | \ t_r \in R \land \Pi_Y(S) \in Y_x\}$R÷S={tr​[X] ∣ tr​∈R∧ΠY​(S)∈Yx​}

求解步骤过程

1. 找出关系 R 和关系 S 中相同的属性，即 Y 属性。在关系 S 中对 Y 做投影，结果如下
   

2. 被除关系 R 中与 S 中不相同的属性列是 X ，关系 R 在属性 X 上做取消重复值的投影为 {X1，X2}；

3. 求关系 R 中 X 属性对应的像集 Y
   根据关系R的记录，可以得到与 X1 值有关的记录，如图 3 所示；与 X2 有关的记录，如图 4 所示
   

4. 判断包含关系
   R÷S 其实就是判断关系 R 中 X 各个值的像集 Y 是否包含关系 S 中属性 Y 的所有值。对比即可发现：
   X1 的像集只有 Y1，不能包含关系 S 中属性 Y 的所有值，所以排除掉 X1；
   而 X2 的像集包含了关系 S 中属性 Y 的所有值，所以 R÷S 的最终结果就是 X2
   

利用除运算，可以计算至少包含了某个属性集合的元组对应的主码（比如选课表中，查询至少选修课程 1 与课程 3 的学生姓名）。

（这上面的图和除法计算过程是参考某篇博客的，找不到原文了。。侵删）

3 关系数据库标准语言 SQL

学生表：Student(Sno, Sname, Ssex, Sage, Sdept)

课程表：Course(Cno, Cname, Cpno, Ccredit)

选课表：SC(Sno, Cno, Grade)

3.3 数据定义

一个关系数据库管理系统的实例中可以建立多个数据库，一个数据库中可以建立多个模式，一个模式下通常包括多个表、视图和索引等数据库对象。

模式的定义与删除

• 定义模式

要创建模式，调用该命令的用户必须拥有数据库管理员权限，或者获得了数据库管理员授予的 CREATE SCHEMA 的权限。创建模式的同时，还可以在这个模式定义中进一步创建基本表、视图，定义授权。

如果没有指定 <模式名>，那么模式名默认为 <用户名>。定义模式实际上定义了一个命名空间。

• 删除模式

CASCADE（级联）表示在删除模式的同时把该模式中所有的数据库对象全部删除；RESTRICT（限制）表示如果该模式中已经定义了下属的数据库对象（表、视图等），则拒绝该删除语句的执行。

基本表的定义、删除与修改

• 定义基本表

涉及多个属性列的完整性约束条件必须定义在表级。

关系模型中的域，在 SQL 中对应的是数据类型。常用的数据类型如下

• 修改基本表

• 删除基本表

RESTRICT 表明删除表时有限制，删除的表不能被其他表的约束所引用（如 CHECK, FORREIGN KEY），不能有视图，不能有触发器，不能有存储过程或函数等。如果有，则此表不能被删除。

CASCADE 表明删除表时没有限制，依赖于删除的表的对象（如视图）将被一同删除。

默认情况是 RESTRICT。

索引的建立与删除

• 建立索引

UNIQUE 表明此索引的每一个索引值只对应唯一的数据记录；CLUSTER 表明要建立的索引是聚簇索引。

次序可选 ASC（升序，默认）或 DESC（降序）。

• 修改索引

• 删除索引

3.4 数据查询

SELECT 语句根据 WHERE 子句的条件表达式从 FROM 子句指定的基本表、视图或派生表中找出满足条件的元组，再按 SELECT 子句中的目标列表达式选出元组中的属性值形成结果表。如果有 GROUP BY 子句，则将结果按 <列名 1> 的值进行分组，该属性列值相等的元组为一个组，通常会在每组中作用聚集函数。如果 GROUP BY 子句带 HAVING 短语，则只有满足指定条件的组才予以输出。如果有 ORDER BY 子句，则结果表还要按 <列名 2> 的值的升序或降序排序。

单表查询

• <目标列表达式> 可以是表中的属性列（全选为 *）、算术表达式、字符串常量、函数等，相当于投影。

• DISTINCT 表明去除重复行，ALL 表明保留所有结果行。

• <条件表达式> 筛选出满足条件的元组。

BETWEEN … AND … 表明上下界（均包含）。

IN 后接 (elem1, elem2, elem3, … , elemn），相当于 <列名> = elem1 OR <列名> = elem2 OR …。

字符模糊匹配：[NOT] LIKE ‘<匹配串>’ [ESCAPE ‘<转义字符>‘]。匹配串中还可以含有通配符 %（代表任意长度的字符串）和 _（代表任意单个字符）。数据库字符集为 ASCII 时一个汉字需要两个 _，为 GBK 时只需要一个 _。

• ORDER BY 后接 ASC 表示结果按照升序排列，DESC 降序。默认 ASC。空值的次序由系统决定。
• 聚集函数可以作用在列上。

当聚集函数遇到空值时，除 COUNT(*) 外，都跳过空值而只处理非空值。

WHERE 子句中不能用聚集函数作为条件表达式。聚集函数只能用于 SELECT 子句和 GROUP BY 中的 HAVING 子句。

• GROUP BY 子句将查询结果按某一列或多列的值分组，值相等的为一组。分组是为了细化聚集函数的作用对象，也就是说，分组后聚集函数将作用于每一个组，每一个组都会有一个函数值。

WHERE 子句作用于基本表或视图，从中选择满足条件的元组；HAVING 短语作用于组，从中选择满足条件的组。

连接查询

• WHERE 子句中的条件表达式可以在不同的表的属性列间作比较，隐式地执行了表的连接运算。
• 可以进行自身连接。为此，需要为表取别名以区分。

• 可以进行外连接：LEFT OUTER JOIN（左外连接）、RIGHT OUTER JOIN（右外连接）。使用外连接时，确定连接比较的属性列，采用 ON <条件表达式> 或 USING(<列名>) 而非 WHERE。

嵌套查询

子查询的 SELECT 语句不能使用 ORDER BY 子句，ORDER BY 只能用在最终结果上。

子查询的查询条件依赖于父查询（相当于父查询的变量传参给子查询），就叫相关子查询，否则叫不相关子查询。

• IN

• 比较运算符（明确子查询只有一个值时可以采用比较运算符）

• ANY（SOME）或 ALL

• EXISTS

EXISTS 代表存在量词 $\exist$∃ 。带有 EXISTS 为此的子查询不返回任何数据，只产生布尔值：子查询结果非空时为真，为空时为假。EXISTS 的子查询，其目标表达式通常都用 *。

SQL 没有全称量词 $\forall$∀ ，当需要用到全称量词的逻辑时，原查询需要进行一定的逻辑等价替换：

所有带 IN、比较运算符、ANY/ALL 谓词的子查询都能被 EXISTS 替换，但并非所有 EXISTS 都能被上述谓词替换。

集合查询

SELECT 语句的查询结果是元组的集合，所以多个 SELECT 语句的结果可进行集合操作：并 UNION、交 INTERSECT、差 EXCEPT。

派生表查询

子查询不仅可以出现在 WHERE 子句中，还可以出现在 FROM 子句中，这时子查询生成的临时派生表成为主查询的查询对象。

若子查询中没有聚集函数，派生表可以不指定属性列，子查询 SELECT 子句后面的列名为其默认属性；但必须为派生表指定一个别名。

3.5 数据更新

插入数据

INTO 子句中的列名顺序可以与表不一样，但一定要与常量数据一一对应；也可以不列全，未列出的属性列为默认值 NULL；若 INTO 子句中没有指明任何属性列名，则新插入的元组必须在每个属性列上均有值。

字符串要用单引号括起来。

INSERT 语句还可以插入子查询的结果

修改数据

删除数据

注意 DELETE 与 DROP 的区别，DELETE 是删除数据，DROP 是删除表。

3.6 空值的处理

空值由 IS NULL 判断，而不能用 == NULL。

在条件表达式中，只有选择条件为 TRUE 的元组才被选出作为输出结果，UNKNOWN 的值不选。

3.7 视图

视图是从一个或几个基本表（或视图）导出的表，是一个虚表，即数据库中只存放视图的定义，而不存放视图的数据。

定义视图

子查询即任意的 SELECT 语句。WITH CHECK OPTION 表示对视图进行 UPDATE、INSERT、DELETE 操作时要保证更新、插入或删除的行满足视图定义中的谓词条件（即子查询中的条件表达式）。

执行 CREATE VIEW 只是把视图的定义存入数据字典，并不执行其中的 SELECT 语句。只是在对视图查询时，才按视图的定义从基本表中将数据查出。因此，定义视图时可以根据应用的需要设置一些派生属性列（比如算术表达式），这些派生属性列在实际中并不存在，只有需要使用时才会临时计算，省空间。

查询视图

查询存在的视图时，系统从数据字典中取出视图的定义，把定义中的子查询和用户的查询结合起来，转换成等价的对基本表的查询，然后再执行修正了的查询，称为视图消解。

更新视图

更新视图时，也通过视图消解。加上 WITH CHECK OPTION 子句的视图，在更新时会检查定义中的条件，并拒绝掉不满足条件的更新操作。

并不是所有表都是可更新的，反正至少行列子集视图是可更新的。

视图的作用

1. 简化用户的操作
2. 使用户能以多种角度看待同一数据
3. 对重构数据库提供了一定程度的逻辑独立性
4. 能够对机密数据提供安全保护
5. 更清晰地表达数据

4 数据库安全性

4.2 数据库安全性控制

存取控制

存取控制机制主要包括定义用户权限和合法权限检查两部分。

在自主存取控制方法中，用户对于不同的数据库对象有不同的存取权限，不同的用户对同一对象也有不同的权限，而且用户还可将其拥有的存取权限转授给其他用户，因此自主存取控制非常灵活。

在强制存取控制方法中，每一个数据库对象被标以一定的密级，每一个用户也被授予某一个级别的许可证。对于任意一个对象，只有具有合法许可证的用户才可以存取。强制存取控制因此相对比较严格。

自主存取控制

用户权限是由两个要素组成的：数据库对象和操作类型。定义一个用户的存取权限就是要定义这个用户可以在哪些数据库对象上进行哪些类型的操作。

• GRANT

SQL 使用 GRANT 向用户授予数据的操作权限。

若指定了 WITH GRANT OPTION 子句，则意味着被授予权限的用户可以再将该权限授予其他用户。

• REVOKE

REVOKE 向用户收回已授予的权限。

指定 CASCADE 将用户转授的权限也一并收回。

• 数据库角色

数据库角色是一组权限的集合。

创建角色：CREATE ROLE <角色名>

给角色授权：GRANT 语句

将一个角色授予其他的角色或用户：

若指定 WITH ADMIN OPTION 子句，则意味着被授予角色的角色或用户还可以再将该角色授予其他用户或角色。

收回角色权限：REVOKE

强制存取控制方法

在强制存取控制中，数据库管理系统所管理的全部实体被分为主体和客体。主体即实际用户或用户进程，客体即各类数据。对于主体和客体的每个实例，都会被指派一个敏感度标记。敏感度标记有：绝密（Top Secret, TS）、机密（Secret, S）、可信（Confidential, C）、公开（Public, P）等，密级依序降低。

强制存取控制机制就是通过对比主题的敏感度标记和客体的敏感度标记，最终确定主体是否能够存取客体。规则如下：

1. 仅当主体的许可证级别大于或等于客体的密级时，该主体才能读取相应的客体。
2. 仅当主体的许可证级别小于或等于客体的密级时，该主体才能写相应的客体。

规则 2 的原因是为了防止高密级用户将高密级客体写入低密级客体中，导致数据泄露。

5 数据库完整性

数据库的完整性是指数据的正确性和相容性的。数据的正确性是指数据是符合现实世界语义、反应当前实际状况的；数据的相容性是指数据库同一对象在不同关系表中的数据是符合逻辑的。

数据库的完整性是为了防止数据库中存在不符合语义的数据；数据库的安全性为了防止数据库被恶意破坏和非法存取。

5.1 实体完整性

实体完整性在 CREATE TABLE 中用 PRIMARY KEY 定义。

定义实体完整性后，每当插入数据或对更新主码时，将会进行实体完整性检查，检查主码是否唯一、是否不为空。

5.2 参照完整性

参照完整性在 CREATE TABLE 中用 FOREIGN KEY 定义哪些列为外码，用 REFERENCES 定义这些外码参照哪些表的主码。

5.3 用户定义的完整性

用户定义的完整性在 CREATE TABLE 时根据应用需求定义约束条件。

• 列值非空（NOT NULL）
• 列值唯一（UNIQUE）
• 检查列值是否满足一个条件表达式（CHECK）

5.4 完整性约束命名子句

定义完整性约束

CONSTRAINT <完整性约束条件名> <完整性约束条件>

修改完整性约束

用 ALTER TABLE 语句修改

5.6 断言

任何对定义的断言所涉及关系的操作都会触发关系数据库管理系统对断言的检查，任何使断言不为真的操作都会被拒绝执行。

创建断言

CREATE ASSERTION <断言名> <CHECK子句>

删除断言

DROP ASSERTION <断言名>

5.7 触发器

6 关系数据理论

$R(U, D, DOM, F)$R(U,D,DOM,F)，在讨论模式设计时，可以简化为 $R(U, F)$R(U,F)，F 为属性组 U 上的一组数据依赖。数据依赖是一个关系内部属性与属性之间的一种约束关系，通过属性间值的相等与否来体现，类似于数学中的函数，自变量确定后函数值也就唯一确定了。

6.2 规范化

函数依赖

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

很显然，与数学中的函数非常相像。

码

1NF

关系数据库中的关系是要满足一定要求的，满足不同程度要求的为不同范式。

第一范式（1NF）是最基本的范式，它要求每一个分量必须是不可分的数据项。

一个低一级范式的关系模式通过模式分解可以转换为若干个高一级范式的关系模式的集合，这种过程就叫规范化。

2NF

若 $R \in 1NF$R∈1NF ，且每一个非主属性完全函数依赖于任何一个候选码，则 $R \in 2NF$R∈2NF 。

有关系模式：S-L-C(Sno, Sdept, Sloc, Cno, Grade)

不满足 2NF，意味着将会存在两种非主属性：一种完全函数依赖于码（就叫它 FNA 吧），一种部分函数依赖于码（PNA）。当试图插入 PNA 时，由于只需码中的部分属性就能确定，也就意味着码中有部分属性是不需要的或暂时未知的，那么，插入这个 PNA 时就会因为码值一部分为空，违反了实体完整性而被拒绝插入。除插入异常外，不满足 2NF 还会导致删除异常、修改复杂等问题。

要使得上述例子满足 2NF，可以用投影分解，将 S-L-C 分解为两个关系模式：SC(Sno, Cno, Grade) 和 S-L(Sno, Sdept, Sloc)，即将 FNA 和 PNA 分开，让 FNA 与当前码分为一个关系，让 PNA 与码中能完全函数确定 PNA 的部分属性作为新的码分为一个关系。

3NF

分解的方法就是打断传递依赖，将 X、Y 作为一个关系，Y、Z 作为一个关系。

BCNF

多值依赖

设 R(U) 是属性集 U 上的一个关系模式。X，Y，Z 是 U 的子集，并且 Z = U - X - Y。关系模式 R(U) 中多值依赖 X →→ Y 成立，当且仅当对 R(U) 的任一关系 r，给定的一对（x，z）值，有一组 Y 的值，这组值仅仅决定于 x 值而与 z 值无关。

很好理解，就是一个关系模式 R(X, Y, Z)，若 Y、Z 函数依赖于 X，那没关系，因为函数依赖 X 到 Y，X 到 Z 分别只有一个映射，对于一个特定的 x 值，只会有确定的一组（y，z）值。若 Y、Z 多值依赖于 X，问题很大，这意味着 X 到 Y，X 到 Z 分别有多个映射，即 X 与 Y，或 X 与 Z，是一对多的关系，Y 与 Z 会产生多种组合。

假设 X 确定 Y 的有 n 个不同的值，X 确定 Z 的有 m 个不同的值，若是函数确定，那么 n、m 都为 1，只会产生一种组合，只需要一条记录，相对于分别存储 Y、Z 需要两条记录，是更优的；若是多值确定，那么就有了 n * m 个组合，而实际上 Y、Z 分别存储只需要 n + m 条记录，显然是分别存储是更优的，集中存储会出现大量的浪费。

4NF

规范化小结

任意一个二元模式至少可以达到 BCNF 范式；任意一个全码模式至少可以达到 BCNF 范式。

6.3 数据依赖的公理系统

Armstrong 公理系统

闭包，或判定 X → Y 是否能由 F 导出

函数依赖集等价

简单来说，就是先把右边含有多个属性的拆开，然后消除冗余的依赖（即若一个属性分别依赖于多个其他属性，保留其中一个），最后消除部分依赖（依赖左部均为最小属性集） 。

7 数据库设计

概述

数据库设计分为 6 个阶段：

1. 需求分析
2. 概念结构设计
3. 逻辑结构设计
4. 物理结构设计
5. 数据库实施
6. 数据库运行和维护

需求分析

需求分析就是分析用户的需求，包括

• 信息要求。需要的信息的内容和性质，以得知需要存储哪些数据。
• 处理要求。需要的数据处理功能，和对性能的要求。
• 安全性与完整性要求。

数据字典是需求分析的成果。它是关于数据库中数据的描述，即元数据，而不是数据本身。数据字典包括数据项、数据结构、数据流、数据存储、处理过程。

概念结构设计

概念结构设计就是将需求分析得到的用户需求抽象为信息结构（即概念模型）。常用的概念模型是 E-R 图，它包括实体、属性、实体之间的联系。

实体之间的联系有一对一联系（1:1）、一对多联系（1:n）、多对多联系（m:n）。

E-R 图提供了表示实体型、属性和联系的方法：实体型用矩形、属性用椭圆形、联系用菱形。

实体型与联系均可拥有属性。属性不能再有需要描述的性质，也不能与其他实体有联系。

在设计大型系统时，往往需要分别设计子系统的 E-R 图，然后将它们集成其他，得到全局 E-R 图。在这个过程中，首先需要合并 E-R 图，即解决各分 E-R 图之间的冲突，生成初步 E-R 图。各分 E-R 图之间的冲突主要有三类：

1. 属性冲突。同一属性在不同 E-R 图上的域不同、或取值单位不同。
2. 命名冲突。同名异义、异名同义。
3. 结构冲突。同一对象的抽象不一致、同一实体的属性不一致、同一联系的类型不一致。

然后，需要消除不必要的冗余（比如冗余的数据或联系），设计基本 E-R 图。可以用分析或规范化理论来解决。

逻辑结构设计

逻辑结构设计就是把概念结构设计阶段设计好的概念模型转换为与选用数据库管理系统产品所支持的数据模型相符合的逻辑结构。对于 E-R 图而言，就是将实体型和实体型间的联系转换为关系模式，并确定这些关系模式的属性和码。

一个实体型转换为一个关系模式，关系的属性就是实体的属性，关系的码就是实体的码。对于实体型间的联系，有不同的情况：

• 一个 1:1 联系可以转换为一个独立的关系模式，也可以与任意一端对应的关系模式合并。如果转换为一个独立的关系模式，则与该联系相连的各实体的码以及联系本身的属性均转换为关系的属性，每个实体的码均是该关系的候选码。如果与某一端实体对应的关系模式合并，则需要在该关系模式的属性中加入另一个关系模式的码和联系本身的属性。
• 一个 1:n 联系可以转换为一个独立的关系模式，也可以与 n 端对应的关系模式合并。如果转换为一个独立的关系模式，则与该模式相连的各实体的码以及联系本身的属性均转换为关系的属性，而关系的码为 n 端实体的码。
• 一个 m:n 联系转换为一个关系模式。与该联系相连的各实体的码以及联系本身的属性均转换为关系的属性，各实体的码组成关系的码或关系码的一部分。
• 三个或三个以上实体间的一个多元联系可以转换为一个关系模式。
• 具有相同码的关系模式可以合并。

物理结构设计

物理结构设计就是为给定的逻辑模型选取一个最适合应用要求的物理结构。通常分为两步：首先确定数据库的物理结构，在关系数据库中主要指存取方法和存储结构；然后对物理结构进行评价，评价的重点是时间和空间效率。如果评价结果满足设计要求，则可进入到物理实施阶段，否则，就需要重新设计或修改物理结构，甚至是逻辑结构。

常用的存取方法有索引方法和聚簇方法。

索引方法使用最普遍的是 B+ 树索引和 hash 索引。

聚簇方法是把属性（组）中具有相同值的元组集中存放在连续的物理块中，该属性（组）就成为聚簇码。一个数据库可以建立多个聚簇，一个关系只能加入一个聚簇。聚簇通常建立于经常需要进行连接、比较的关系间的连接属性、比较属性上。

8 数据库编程

8.1 嵌入式 SQL

嵌入式 SQL 能够提高 SQL 的逻辑控制能力，以补齐非过程化的短板。对嵌入式 SQL，数据库管理系统一般采用预编译方法处理，即由数据库管理系统的预处理程序对用宿主语言编写的源程序进行扫描，识别出嵌入式 SQL 语句，把它们转换成主语言调用语句，以使主语言编译程序能识别它们，然后由主语言的编译程序将纯的主语言程序编译成目标码。

当主语言为 C 时，语法格式为 EXEC SQL <SQL语句>;，Java 时为 #SQL {<SQL语句>}; 。

嵌入式 SQL 语句与主语言之间的通信

• SQL 通信区

SQL 语句执行后，系统会反馈当前工作状态和运行环境的若干信息（如 SQLCODE，指示语句是否执行成功），存储于 SQL 通信区中。用 EXEC SQL INCLUDE SQLCA 定义。

• 主变量

嵌入式 SQL 语句中可以使用主语言的程序变量（简称为主变量）来输入或输出数据，并可选择附带一个指示变量来指示相应主变量的值或条件。主变量和指示变量须在 BEGIN DECLARE SECTION 与 END DECLARE SECTION 之间进行说明，并加前缀 : 与数据库对象名以区别。

• 游标

SQL 是面向集合的，而主语言是面向记录的，因此需要一个数据缓冲区，即游标，来存放 SQL 语句的执行结果。用于可以通过游标逐一获取记录并赋给主变量，交给主语言进一步处理。

• 建立和关闭数据库连接

嵌入式 SQL 语句要访问数据库必须先连接数据库，所有数据据操作执行完毕后，还要关闭数据库连接。

不用游标的 SQL 语句

• 查询结果为单记录的 SELECT 语句

此时，可以用 INTO 子句指定存放查询结果的主变量，不需使用游标。

查询结果的某些列可能为空值，主变量会被赋值为 NULL，若指定了指示变量，则为空的相应主变量的指示变量会被赋负值，而不再向主变量赋值。

• 非 CURRENT 形式的增删改语句

使用游标的 SQL 语句

• 查询结果为多条记录的 SELECT 语句

使用游标的步骤为：

1. 说明游标。EXEC SQL DECLARE <游标名> CURSOR FOR <SELECT语句>; ，定义游标仅仅是一条说明性语句，并不执行。

2. 打开游标。EXEC SQL OPEN <游标名>; ，打开游标实际上执行了相应的 SELECT 语句，把查询结果取到缓冲区中。这时游标处于活动状态，指针指向查询结果集中的第一条记录。

3. 推进游标指针并取当前记录。EXEC SQL FETCH <游标名> INTO <主变量>[<指示变量>]...; ，其中主变量必须与 SELECT 语句中的目标列表达式具有一一对应关系。

4. 关闭游标。EXEC SQL CLOSE <游标名>;，关闭游标以释放资源，并取消了与原来的查询结果的联系。被关闭的游标可以再度打开，并与新的查询语句相联系。

• CURRENT 形式的 UPDATE 和 DELETE 语句

8.4 ODBC

9 关系查询处理和查询优化

9.1 关系数据库系统的查询处理

查询处理过程

查询处理是将查询语句转换为高效的查询执行计划的过程，分为 4 个阶段：查询分析、查询检查、查询优化和查询执行。查询分析主要做 SQL 语句的语法分析；查询检查主要做 SQL 语句的语义分析、安全性完整性检查等，并将 SQL 语句转换为等价的关系代数表达式，通常以查询树的形式；查询优化主要做代数优化和物理优化。

查询算法实现

• 选择操作
  
  
• 连接操作

9.3 代数优化

关系代数表达式等价变换规则

查询树的启发式优化

1. 选择运算应尽可能先做。
2. 把投影运算和选择运算同时进行。
3. 把投影同其前或后的双目运算结合起来。
4. 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算。
5. 找出公共子表达式。
   

9.4 物理优化

物理优化就是要选择高效合理的操作算法或存取路径，求得优化的查询计划，包括：基于规则的启发式优化、基于代价估算的优化、两者结合的优化方法。

10 数据库恢复技术

10.1 事务的基本概念

事务是用户定义的一个数据库操作序列，这些操作要么全做，要么全不做，是一个不可分割的工作单位。一个程序通常包含多个事务。

事务通常以 BEGIN TRANSACTION 开始，以 COMMIT 或 ROLLBACK 结束。COMMIT 表示提交，将事务中所有对数据库的更新写回到磁盘上的物理数据库中去，事务正常结束；ROLLBACK 表示回滚，即在事务运行的过程中发生了故障，事务不能继续执行，系统将事务中对数据库所有已完成的操作全部撤销，回滚到事务开始时的状态。

事务具有 4 个特性（ACID）：原子性（atomicity）、一致性（consistency）、隔离性（isolation）和持续性（durability）。

• 原子性：事务是数据库的逻辑工作单位，事务中的操作要么全做，要么全不做。
• 一致性：事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。一致性状态是指数据库只包含成功事务提交的结果的状态。
• 隔离性：并发执行的各事务之间不能相互干扰。
• 持续性：一个事务一旦提交，它对数据库中的数据的改变就应该是永久性的。

保证事务 ACID 特性，就需要在事务意外终止时提供恢复机制，在多个事务交叉执行时提供并发控制机制。

10.3 故障的种类

1. 事务内部的故障：有些事务内部的故障可以被程序发现（如数值不满足要求），但更多的故障是非预期的，不能由运用程序处理。事务故障意味着事务没有达到预期终点，因此数据库可能处于不正确状态。此时，需要执行事务撤销以撤销该事务所作出的修改。

2. 系统故障：系统停止运转，所有运行事务都异常终止。一些尚未完成的事务的结果可能已送入物理数据库，需要在重启后撤销异常终止的事务；一些已经完成的事务可能尚未写回到磁盘上的物理数据库中，需要在重启后将重做已提交的事务。

3. 介质故障：硬件损坏，破坏性大。

4. 计算机病毒

10.4 恢复的实现技术

恢复机制的关键就是：如何建立冗余数据，以及如何利用这些冗余数据实施数据库恢复。

建立冗余数据最常用的技术是数据转储和登记日志文件。

数据转储

转储即数据库管理员定期将整个数据库复制到其他存储介质上保存起来的过程。但利用数据转储恢复数据库时，只能将数据库恢复到转储时的状态，还必须重新运行之后的所有更新事务。

转储分为静态转储和动态转储。静态转储很简单，但必须中止数据库，降低数据库的可用性。动态转储不必等待事务结束，但不能保证数据正确有效，必须将动态转储期间事务的更新活动记录成日志文件才行，然后用恢复系统故障的方法（见后）来达到一致性状态。

转储还可以分为海量转储和增量转储。海量转储每次转储全部数据，增量转储每次只转储上一次转储后更新过的数据。

登记日志文件

日志文件是用来记录事务对数据库的更新操作的文件。登记日志时，必须严格按并发事务执行的时间次序记录；必须先写日志文件，后写数据库。

10.5 恢复策略

事务故障的恢复

反扫一遍。

系统故障的恢复

系统故障需要撤销故障发生时未完成的事务，重做已完成的事务。

正扫找出待操作事务 -> 反扫撤销未完成事务 -> 正扫重做已完成事务。

介质故障的恢复

重装数据库，然后重做已完成的事务。

10.6 具有检查点的恢复技术

检查点记录的内容包括：建立检查点时刻所有正在执行的事务清单，以及这些事务最近一个日志记录的地址。周期性地建立检查点，保存数据库状态，可以改善恢复效率。

系统出现故障时，恢复子系统将根据事务的不同状态采取不同的恢复策略：

简单来说，就是检查点之前提交的事务可以忽略，检查点之后系统故障之前提交的事务需要重做，系统故障时还未完成的事务需要撤销。

恢复的步骤，简单来说就是先找到检查点，正扫一遍日志，正在执行的或开始执行的事务加入 UNDO-LIST，提交的事务从 UNDO-LIST 移到 REDO-LIST，扫描结束后分别对队列做 UNDO 和 REDO 操作。

11 并发控制

11.1 并发控制概述

并发操作破坏了隔离性，带来的不一致性有：

1. 丢失修改：两个事务读入同一数据并修改，常见的竞态。
2. 不可重复读：一个事务 T1 读取一个数据后，另一个事务 T2 修改了同一数据，当 T1 再次读取该数据，发现此次读取与前次读取不一致。
3. 读脏数据：一个事务 T1 读取并修改一个数据后，另一个事务 T2 读取了同一数据，过后 T1 又由于某种原因撤销了对该数据的修改，此时 T2 读取到的数据就是脏数据。

11.2 *

*是实现并发控制的重要技术。所谓*就是事务 T 在对某个数据对象操作之前，先向系统发出请求，对其加锁。加锁后事务 T 就对该数据对象有了一定的控制，在事务 T 释放它的锁之前，其他事务不能更新此数据对象。

基本的*类型有两种：

1. 排他锁，或写锁。若事务 T 对数据对象 A 加上 X 锁，则只允许 T 读取和修改 A，其他任何事务都不能再对 A 加任何类型的锁，直到 T 释放 A 上的锁为止。这就保证了其他事务再 T 释放 A 上的锁之前不能再读取和修改 A。
2. 共享锁，或读锁。若事务 T 对数据对象 A 加上 S 锁，则事务 T 可以读 A 但不能修改 A，其他事务只能再对 A 加 S 锁，而不能加 X 锁，直到 T 释放 A 上的 S 锁为止。这就保证了其他事务可以读 A，但在 T 释放 A 上的 S 锁之前不能对 A 做任何修改。
   

11.3 *协议

一级*协议

一级*协议指，事务 T 在修改数据 R 之前必须先对其加 X 锁，直到事务结束才释放。

一级*协议可防止丢失修改，并保证事务 T 是可恢复的，但不能防止不可重复读和读脏数据。

二级*协议

二级*协议指，在一级*协议的基础上，增加事务 T 在读取数据 R 之前必须先对其加 S 锁，读完后即可释放 S 锁。

二级*协议可防止丢失修改和读脏数据，但不能防止不可重复读。

三级*协议

三级*协议指，在一级*协议的基础上，增加事务 T 在读取数据 R 之前必须先对其加 S 锁，直到事务结束才释放。

三级*协议可防止丢失修改、读脏数据、不可重复读三个问题。

11.4 活锁和死锁

活锁

活锁是指事务反复尝试访问数据均失败的情况。这里采用 FCFS 就能解决。

死锁

死锁是两个或多个事务相互等待各自持有的资源从而导致僵持的状态。

预防死锁就是要破坏产生死锁的条件：

1. 一次*法：要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行。但这会降低系统的并发度，并且难以预料所有需要使用到的数据。

2. 顺序*法：预先对数据对象规定一个*顺序，所有事务都按这个顺序实施*。但维护*顺序非常困难。

诊断死锁的方法有：

1. 超时法：如果一个事务的等待时间超过了规定的时限，就认为发生了死锁。
2. 等待图法：生成事务等待图，如果图中存在回路，则出现了死锁。

解除死锁的方法通常是选择一个处理死锁代价最小的事务，将其撤销，释放此事务持有的所有的锁。

11.5 并发调度的可串行性

可串行化调度

多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行这些事务时的结果相同，称这种调度策略为可串行化调度。可串行性是并发事务正确调度的准则。

虽然同一调度的不同的可串行化调度顺序不同，可能会导致不同的结果，但只要是可串行性的，就是正确的。

冲突可串行化调度

冲突操作是指不同事务对同一数据的读写操作和写写操作：

不同事务的冲突操作和同一事务的两个操作是不能交换次序的。

给定一个调度，在保证冲突操作的次序不变的情况下，若该调度通过交换两个事务不冲突操作的次序可得到一个串行的调度，则称该调度为冲突可串行化的调度。若一个调度是冲突可串行化的，则一定是可串行化的调度。因此，可用这种方法来判断一个调度是否是可串行化的。但要注意，冲突可串行化只是可串行化的充分条件，而不是必要条件。

11.6 两段锁协议

为了保证并发调度的正确性，并发控制机制必须提供一定的手段来保证调度是可串行化的，通常采用两段锁协议（2PL）：

1. 第一阶段是获得*，也称为扩展阶段，在这个阶段，事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁；
2. 第二阶段是释放*，也成为收缩阶段，在这个阶段，事务可以释放任何数据项上的任何类型的锁，但是不能再申请任何锁。

若并发执行的所有事务均遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的。

11.7 *的粒度

多粒度*

*对象的大小称为*粒度。*对象可以是逻辑单元，如属性、元组、关系；也可以是物理单元，如页。*的粒度越大，并发度就越小。

同时支持多种*粒度是比较理想的，因此定义多粒度树，根结点是整个数据库，代表最大的粒度，叶子结点代表最小的粒度。

多粒度*协议允许对多粒度树中的各个结点独立加锁。对一个结点加锁意味着对这个结点的所有子结点加同样类型的锁。于是，显示*是直接加到数据对象的锁，隐式*是其父结点被加了锁，但它们的效果是一致的。因此，系统检查*冲突时，不仅要检查结点的显示*，还要上溯父结点检查隐式*，还要检查子结点的显示*。

意向锁

为了解决多粒度*协议的低效率，引入了意向锁，数据库管理系统就无须逐个检查下一级结点的显示*。如果对一个结点加意向锁，则说明该结点的下层结点正在被加锁；对任一结点加锁时，必须先对它的上层结点加意向锁。

三种常用的意向锁：

1. 意向共享锁（IS 锁）：它的子结点将要加 S 锁
2. 意向排他锁（IX 锁）：它的子结点将要加 X 锁
3. 共享意向排他锁（SIX 锁）：将要对它先加 S 锁，再加 IX 锁。

申请*时应该按自上而下的次序进行；释放*时应该按自下而上的次序进行。