数据库系统概论笔记

数据库系统概论(王珊 萨师煊 编著)笔记。

第一章 绪论

1.数据库系统概述

1.1数据库的4个基本概念

• 数据：描述事物的符号记录称为数据。数据的含义称为数据的语义，数据与其语义是不可分的。
• 数据库：长期存储在计算机内、有组织的、可共享的大量数据的集合。数据库中的数据按一定的数据模型组织、描述和存储，具有较小的冗余度、较高的数据独立性和易扩展性，并可为各种用户共享。
• 数据库管理系统(DBMS)：科学组织和存储数据，高效获取和维护数据。主要有以下功能：
  • 数据定义功能
  • 数据组织、存储和管理
  • 数据操纵功能
  • 数据库的事务管理和运行管理
  • 数据库的建立和维护功能
  • 其他功能
• 数据库系统(DBS)：由数据库、数据库管理系统、应用程序和数据库管理员组成的存储、管理、处理和维护数据的系统。

1.2数据管理技术的产生和发展

• 人工管理阶段->文件系统阶段->数据库系统阶段。
• 从文件系统到数据库系统标志着数据管理技术的飞跃。

1.3数据库系统的特点

• 数据结构化：数据库系统实现整体数据的结构化。数据库中的数据不仅针对一个应用，而是面向整个组织或企业。
• 数据的共享性高，冗余性低且易扩充。
• 数据独立性高：数据独立性包括物理独立性和逻辑独立性。
  • 物理独立性是指用户的应用程序与数据库中的物理存储是相互独立的。
  • 逻辑独立性是指用户的应用程序与数据库的逻辑结构是相互独立的。
• 数据由数据库管理系统统一管理和控制：数据库的共享是并发的，为了保证数据一致性，数据库管理系统还必须提供以下几方面的数据控制功能：
  • 数据的安全性保护：防止不合法使用造成的数据泄密和破坏。
  • 数据的完整性检查：控制数据的正确性，有效性和相容性。
  • 并发控制
  • 数据库恢复

2.数据模型

数据模型是数据库系统的核心和基础。包含两类，第一类是概念模型，第二类是逻辑模型和物理模型。

• 概念模型：从用户的观点对信息和数据建模，主要用于数据库设计。
• 逻辑模型：从计算机系统的观点对数据建模，主要用于数据库管理系统的实现。
• 物理模型：描述数据在系统内部的表示方式和存取方法。

2.1 概念模型

• 概念模型：对信息建模。概念模型是认识抽象到数据库管理系统支持的数据模型的一个中间层次。以下是概念模型中的一些术语：
  • 实体：客观存在并可相互区别的实物称为实体。
  • 属性：实体所具有的某一特性。
  • 码(key)：唯一标识实体的属性集称为码。
  • 实体型：用实体名和属性名集合来抽象和刻画同类实体。例如：学生(学号，姓名，性别，院系)。
  • 实体集：同一类型实体的集合称为实体集。
  • 联系：实体之间的联系通常是指不同实体集之间的联系。有一对一，一对多和多对多等多种类型。
• 概念模型的一种表示方法：实体-联系方法(E-R方法)，见第7章。

*2.2 数据模型的组成要素

• 数据结构：描述数据库的组成对象以及对象之间的联系。
• 数据操作：对数据库中各种对象的实例允许执行的操作的合集，包括操作及有关的操作规则。
• 完整性约束：一组完整性规则。

2.3 常用的数据模型

层次模型

• 数据库中满足下面两个条件的基本层次联系的集合为层次模型：
  • 有且只有一个结点没有双亲结点，称为根结点。
  • 根以外的其他结点只有一个双亲结点。
• 数据操纵主要为查询，插入，删除，更新。操作要满足层次模型的完整性约束条件。
• 层次模型的优点：
  • 数据结构简单清晰。
  • 查询效率高(因为联系用有向边表示)。
  • 提供了良好的完整性支持。
• 层次模型的缺点：
  • 现实中很多联系是非层次性的。
  • 一个结点有多个双亲结点，就只能引入冗余数据，应用程序编写复杂。
  • 查询子女结点必须通过双亲结点。
  • 结构严密，层次命令趋于程序化。

网状模型

• 数据库中满足下面两个条件的基本层次联系的集合为网状模型：
  • 允许一个以上的结点无双亲。
  • 一个结点可以有多于一个的双亲。
• 具体的网状数据库系统对数据操纵都加了一些限制，提供了一定的完整性约束。
• 网状模型的优点：
  • 能够更为直接的描述现实世界。
  • 具有良好的性能，存储效率较高。
• 网状模型的缺点：
  • 结构比较复杂，不利于最终用户掌握。
  • DDL，DML复杂，并且要嵌入一种高级语言中，不容易掌握和使用。
  • 记录之间的联系通过存取路径实现，访问数据时必须选择适当的存取路径，用户必须了解系统结构的细节。

关系模型

关系模型由一组关系组成，每个关系的数据结构是一张规范化的二维表。

• 关系模型的术语：
  • 关系：对应一张表
  • 元组：表中的一行
  • 属性：列
  • 码：唯一确定一个元组
  • 域：属性的取值范围
  • 分量：元组中的一个属性值
  • 关系模式：对关系的描述一般为：关系名（属性1，属性2…）
• 关系模型要求关系必须是规范化的，每一个分量必须是一个不可分的数据项。
• 关系模型的优点：
  • 建立在严格数学概念上。
  • 概念单一，结构简单清晰。
  • 关系模型存取路径透明，有更高的数据独立性，更好的安全保密性。

其他相关内容见第二章。

*3.数据库系统的结构(三级模式结构)

• 模式也称逻辑模式，是数据库中全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图。数据库管理系统提供模式数据定义语言(DDL)来严格定义模式。
• 外模式：数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述，是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。
• 内模式：数据物理结构和存储方式的描述，是数据在数据库内部的组织方式。
• 为了实现以上三个抽象层次的联系和转换，数据库管理系统在三级模式之间提供了两层映像：外模式/模式映像和模式/内模式映像。
  • 外模式/模式映像：定义了外模式与模式之间的对应关系。
  • 模式/内模式映像：定义了数据全局逻辑结构和存储结构之间的关系。
• 数据库模式即全局逻辑结构是数据库的中心与关键，独立于数据库的其他层次。
• 当模式改变时，修改映像使外模式不变，这保证了数据与程序的逻辑独立性。当存储结构(内模式)改变时，修改映像使模式保持不变，这保证了数据与程序的物理独立性。

第二章 关系数据库

1.关系数据结构及形式化定义

1.1关系

以下是集合论角度下关系数据结构的形式化定义。 - 域：一组具有相同数据类型的值的集合。 - 笛卡尔积：域上的一种集合运算。 - 笛卡尔积中的每一个元素叫做一个n元组，元组中每个值叫做一个分量。 - 一个域允许的不同取值个数称为这个域的基数。 - 域D1，D2，D3......的子集叫做在域D1，D2...上的关系，表示为R(D1，D2，...，D3)，R表示关系的名字，n是关系的目或度。n=1时为单元关系，n=2时为二元关系。 - **若关系中的某一属性组的值能唯一标识一个元组，而其子集不能，则该属性组为候选码。** - 若一个关系有多个候选码，则选定其中一个为主码。 - 候选码的诸属性称为主属性。其他属性为非主属性。 - 最极端的情况下，所有属性为关系模式的候选码，称为全码。 - 关系可以有三种类型：基本关系，查询表和视图表。 - 基本关系具有以下六条性质： - 列是同质的。 - 不同的列可出自同一个域。 - 列可交换。 - 元组候选码不能取相同值。 - 行可交换。 - 分量必须是原子的，每一个分量必须是不可分的数据项。 ### 1.2关系模式

关系的描述称为关系模式。可以形式化表示为R(U，D，DOM，F)。通常简记为R(U)。关系模式是型，关系是值；关系模式是静态的，关系是动态的，变化的；关系是关系模式在某一时刻的状态或内容。关系和关系模式常统称为关系，根据上下文进行区分。

• R：关系名
• U：属性名集合
• DOM：属性来自的域
• F：属性间数据的依赖关系集合

2.关系操作

2.1基本的关系操作

五种基本的关系操作：选择、投影、并、差、笛卡尔积。其他操作如连接，除，交可用基本操作定义和导出。

2.2关系数据语言分类

• 关系代数语言(ISBL)
• 关系演算语言
  • 元组关系演算语言(ALPHA)
  • 域关系演算语言(QBE)
• 具有关系代数和关系演算双重特点的语言(SQL)

3.关系的完整性

• 实体完整性：主属性不能取空值
• 参照完整性：F是基本关系的一个或一组属性，但不是R的码，Ks是基本关系S的主码，如果F与Ks对应，F是R的外码，并称R为参照关系，S为被参照关系。R和S不一定不同。
  • 一个关系的属性为另一个关系的主码，则这个属性是这个关系的外码，这个关系为参照关系。
  • 参照完整性规则：外码的取值或者为空，或者为被参照关系的某个元组的主码值。
• 用户定义的完整性

4.关系代数

练习：

​ https://blog.csdn.net/qq_45978890/article/details/114177921

第三章 关系数据库标准语言SQL

1.数据定义

操作对象	创建	删除	修改
模式	CREATE SCHEMA	DROP SCHEMA
表	CREATE TABLE	DROP TABLE	ALTER TABLE
视图	CREATE VIEW	DROP VIEW
索引	CREATE INDEX	DROP INDEX	ALTER INDEX

1.1模式定义和删除

模式定义语句如下：

CREATE SCHEMA <模式名> AUTHORIZATION <用户名> [<表定义子句>|<视图定义子句>|<授权定义子句>]

删除模式语句如下：

DROP SCHEMA <模式名><CASCADE|RESTRICT>

### 1.2基本表的定义和修改 **表的定义**

定义基本表：

CREATE TABLE <表名>(<列名><数据类型>[列级完整性约束条件])

例：

/*建立一个学生表*/
CREATE TABLE Student(
	Sno CHAR(9)PRIMARY KEY,
    Sname CHAR(20)UNIQUE,
    Ssex CHAR(2),
    Sage SMALLINT,
    Sdept CHAR(20)
);
/*建立一个课程表*/
CREATE TABLE Course(
	Cno CHAR(4) PRIMARY KEY,
    Cname CHAR(40) NOT NULL,
    Cpno CHAR(4),
    Ccredit SMALLINT,
    /*表级完整性约束条件*/
    FOREIGN KEY (Cpno) REFERENCES Course(Cno)
);
/*建立学生选课表SC*/
CREATE TABLE SC(
	Sno CHAR(9),
    Cno CHAR(4),
    Grade SMALLINT,
    PRIMARY KEY(Sno,Cno),
    FOREIGN KEY(Sno) REFERENCES Student(Sno),
    FOREIGN KEY(Cno) REFERENCES Cource(Cno)
)

表中的每一个属性都来自一个域，域的概念用数据类型实现，以下是常用的几种数据类型： | 数据类型 | 含义 | | ----------------------------- | ---------------------------- | | CHAR(N),CHARACTER(N) | 定长字符串 | | VARCHAR(N),CHARACTERVARING(N) | 最大长度为n的字符串 | | CLOB | 字符串大对象 | | BLOB | 二进制大对象 | | INT,INTEGER | 长整数 | | SMALLINT | 短整数 | | BIGINT | 大整数 | | NUMERIC(P,D) | 定点数，p位数，小数点后有d位 | | DECIMAL(P,D),DEC(P,D) | 同上 | | REAL | 单精度浮点 | | DOUBLE PRECISION | 双精度浮点 | | FLOAT(N) | 可选精度浮点 | | BOOLEAN | 逻辑布尔量 | | DATE | 日期，YYYY-MM-DD | | TIME | 时间，HH:MM:SS | | TIMESTAMP | 时间戳类型 | | INTERVAL | 时间间隔类型 |

每一个表都属于一种模式，使用以下方法可以定义基本表所属的模式：

CREATE TABLE TEST.Student(...);

**表的修改**

修改基本表的格式为：

ALTER TABLE<表名>
[ADD[COLUMN]<新列名><数据类型>[完整性约束]]
[ADD<表级完整性约束>]
[DROP [COLUMN]<列名>[CASCADE|RESTRICT]]
[DROP CONSTRAINT<完整性约束名>[RESTRICT|CASCADE]]
[ALTER COLUMN<列名><数据类型>];

例：

ALTER TABLE Student ADD S_entrance DATE;
ALTER TABLE Student ALTER COLUMN Sage INT;
ALTER TABLE Course ADD UNIQUE(Cname);

### 1.3建立索引

建立索引是加快查询速度的有效手段。建立索引的一般格式为：

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

- UNIQUE表示索引的每一个索引值只对应唯一的数据记录。 - CLUSTER表示聚簇索引。 - 次序可选为ASC升序或DESC降序，默认为升序ASC

CREATE UNIQUE INDEX Stusno ON Student(Sno);
CREATE UNIQUE INDEX Cousno ON Cource(Cno);
CREATE UNIQUE INDEX SCno ON SC(Sno ASC,Cno DESC);

## 2.数据查询

基本查询格式如下：

SELECT
FROM
WHERE
GROUP BY
ORDER BY

2.1 单表查询

#基本列查询
SELECT 
FROM
#去除重复元素
SELECT DISTINCT 
FROM
#查询满足条件的元组
WHERE ... BETWEEN ... AND ...;
WHERE ... IN ();
WHERE ... LIKE '_*_A%' ESCAPE '*';			#_表示单字符，%表示任意长度字符，ESCAPE表示换码字符
WHERE ... IS NULL;
#ORDER BY子句
ORDER BY ... DESC/ASC
#限制条数
LIMIT 0,2

#聚集函数
SELECT COUNT(*)
FROM STUDENT;
SELECT COUNT(DISTINCT SNO)
FROM SC;
SELECT AVG(GRADE)
FROM SC
WHERE CNO='1';
SELECT MAX(GRADE)
FROM SC
WHERE CNO='1';
/*
	聚集函数遇到空值时除COUNT(*)外，都直接跳过空值。
	WHERE语句不可以用聚集函数作为条件表达式，聚集函数只能用于SELECT和GROUP BY中的HAVING子句
*/

#GROUP BY子句
SELECT CNO,COUNT(SNO)
FROM SC
GROUP BY CNO;
SELECT SNO
FROM SC
GROUP BY SNO
HAVING COUNT(*)>3;
SELECT SNO,AVG(GRADE)
FROM SC
GROUP BY SNO
HAVING AVG(GRADE>=90);

2.2 连接查询

# 连接
SELECT student.sno,sname
FROM student,sc
WHERE student.sno=sc.sno AND
	sc.cno='2' AND sc.grade>90;
# 自然连接(把目标列中重复的属性去掉)，方式同上
# 自身连接，需要为表起别名
SELECT first.cno,seconde.cpno
FROM course first,course second
WHERE first.cpno=second.cno;
# 外连接，把表中的悬浮元组保存在结果关系中
SELECT student.sno,sname,ssex,sage,sdept,cno,grade
FROM student LEFT OUTER JOIN sc ON (student.sno=sc.sno)
# 多表连接和以上类似

2.3 嵌套查询

# 不相关子查询
SELECT name
FROM student
WHERE dept IN
	(
        SELECT dept 
        FROM student
        WHERE name='刘晨'
    );
# 相关子查询
SELECT sno,cno
FROM SC x
WHERE Grade >= (
    			SELECT AVG(Grade)
               	FROM SC y
    			WHERE y.sno=x.sno
               );
# ANY(SOME)/ALL
SELECT name,age
FROM student
WHERE age<ALL
	(
        SELECT age
        FROM student
        WHERE dept='CS'
    )
    AND dept!='CS';
# EXIST
SELECT name 
FROM student
WHERE EXISTS
	(
    	SELECT *
        FROM SC
        WHERE sno=student.sno AND cno='1'
    );

2.4 集合查询

# UNION
SELECT * 
FROM student
WHERE dept='CS'
UNION (UNION ALL)
SELECT *
FROM student
WHERE age<=19;
# INTERSECT
SELECT * 
FROM student
WHERE dept='CS'
INTERSECT
SELECT *
FROM student
WHERE age<=19;
# EXCEPT
SELECT * 
FROM student
WHERE dept='CS'
EXCEPT
SELECT *
FROM student
WHERE age<=19;

3.数据更新

3.1 插入

# 插入元组
INSERT
INTO student(sno,sname,ssex,sdept,sage)				#可以不指出属性名，但VALUE要保持顺序
VALUES('201215128','陈东','男','IS',18);			  #未给出的列将自动赋空值
# 插入子查询结果
CREAT TABLE DEPT_AGE
	(SDEPT CHAR(15)
     AVG_AGE SMALLINT);
INSERT DEPT_AGE(SDEPT,AVG_AGE)
SELECT SDEPT,AVG(SAGE)
FROM STUDENT
GROUP BY SDEPT;

3.2 修改数据

# 修改一个元组的值
UPDATE student
SET sage=22
WHERE sno='201215121';
# 修改多个元组的值
UPDATE student
SET sage=sage+1;
# 带子查询的修改语句
UPDATE SC
SET grade=0
WHERE sno IN
	(SELECT sno
     FROM student
     WHERE sdept='CS');

3.3 删除数据

使用DELETE语句进行删除，方式与修改数据的方式相同。

4.空值的处理

空值是‘不知道’，‘不确定’，‘不存在’的值。在插入元组时，未指定的属性将为空。空值通过IS NULL和IS NOT NULL来判断。属性定义中有NOT NULL约束条件的不能取空值，加了UNIQUE限制的属性不能取空值，码属性不能取空值。空值与另一个值的算数运算结果为空值，与另一个值的比较运算结果为UNKNOWN。在查询语句中，只有使WHERE和HAVING子句中的选择条件为TRUE的元组才被选出作为结果。

5.视图

5.1 定义与删除视图

CREAT VIEW命令用于建立视图。该语句将视图的定义存入数据字典，并不执行其中的SELECT语句，只在对视图查询时，才按视图的定义从基本表中将数据查出。

# 建立视图，省略属性列名
CREATE VIEW IS_Student
AS
SELECT sno,sname,sage
FROM student
WHERE sdept='IS';
# 建立视图，并要求进行修改和插入操作时仍保证该视图满足SELECT的条件
CREATE VIEW IS_Student
AS
SELECT sno,sname,sage
FROM student
WHERE sdept='IS'
WITH CHECK OPTION

若视图从单个基本表导出，只去掉了某些行列，保留了主码，则称这类视图为行列子集视图。

视图不仅可以建立在一个或多个表上，也可以建立在一个或多个定义好的视图上。还可以用带有聚集函数和GROUP BY的子句查询来定义视图，这种视图称为分组视图。

删除视图使用DROP VIEW语句。删除后视图的定义将从数据字典中删除。如果基本表删除了，视图将无法使用，但定义还在数据字典中，需要使用DROP VIEW删除。

5.2 查询视图

视图定义后就可以像基本表一样查询了。如果查询的视图存在，则从数据字典中取出视图的定义，把定义中的子查询和用户的查询结合起来，转换成等价的对基本表的查询，再执行修正的查询，这一转换过程称为视图消解。

5.3 更新视图

视图的更新与查询类似，最终要转换为对基本表的更新，也需要进行视图消解。需要注意的是，有些事图是不可更新的，还有一些视图则是不允许更新的。

第四章 数据库安全性

数据库安全性是指防止用户对数据库的不合法使用导致的数据泄露，更改或破坏。

1.概述

不安全因素：

• 非授权用户对数据库的恶意存取和破坏
• 重要或敏感的数据被泄露
• 安全环境的脆弱性

安全标准：

• TCSEC
• CC

2.数据库安全性控制

2.1 用户身份鉴别

常用的用户身份鉴别方法：

• 静态口令鉴别
• 动态口令鉴别
• 生物特征鉴别
• 智能卡鉴别

2.2 存取控制

存取控制机制主要包括定义用户权限和合法权限检查两部分。两类根据数据库安全等级所支持的存取控制为：

• 自主存取控制DAC(C1级安全)
• 强制存取控制MAC(B1级安全)

2.3 自主存取控制方法

自主存取控制方法中，用户对于不同的数据库对象有不同的存取权限，不同用户对同一对象也有不同的权限，用户还可以将自己的存取权限转授给他人。

自主存取控制主要通过GRANT语句和REVOKE语句实现。

# GRANT
GRANT SELECT
ON TABLE STUDENT
TO U1
WITH GRANT OPTION;	# 该用户可以以同样方式授权其他用户
# REVOKE
REVOKE SELECT
ON TABLE STUDENT
FROM U1;

对数据库模式的授权在创建用户时实现，数据库用户有三种权限：CONNECT,RESOURCE,DB。

数据库还支持对一组与数据库操作相关的权限命名，称为角色。使用CREATE ROLE语句创建，授权和收回权限的方式与对用户的操作相同。

自主存取控制的缺点是可能存在数据无意识的泄露。因为数据本身并无安全性标记。

2.4 强制存取控制方法

强制存取控制方法中，数据库管理系统所管理的全部实体被分为主体和客体。主体包括用户及用户进程，客体包括文件，基本表等。数据库系统为每个主体或客体的实例创建一个敏感度标记。每个数据库对象被标以一定的密级，每一个用户被授予某一个级别的许可证。对于任意一个对象，只有具有合法许可证的用户才可以存取。主体对客体的存取必须遵循以下规则：

• 主体许可证级别大于或等于客体密级时，才能读取客体
• 主体许可证级别小于或等于客体密级时，才能写客体

第二条是为了防止恶意降低密级进行数据泄露。

3.视图机制

视图由一个或多个基本表导出，是虚表，在数据库中只保存定义。视图可以像基本表一样进行查询和删除，但更改受限制。视图机制可以限制数据对象，把保密数据对无权存取的用户隐藏起来，提供一定程度的安全保护。使用视图可以简化用户的操作；能够使用户以多种角度看待同一数据；对重构数据库提供了一定的逻辑独立性；可以更清晰地表达查询。

4.审计机制

审计功能把用户对数据库的所有操作记录下来放入审计日志，审计员可以通过审计日志监控数据库行为，找到非法存取数据的人，时间和内容等。审计机制提供了一种事后安全检查的机制。

AUDIT ALTER,UPDATE
ON SC;
NOAUDIT ALTER,UPDATE
ON SC;

5.数据加密

数据加密能有效防止数据库数据在存储和传输中失密。数据加密主要包括存储加密和传输加密。

6.其他安全性保护

其他安全性保护包括推理控制，数据库应用中的隐蔽信道和数据隐私保护等技术。

第五章 数据库完整性

数据库完整性是指数据的正确性和相容性。为维护数据库的完整性，数据库管理系统必须能够实现以下功能：

• 提供定义完整性约束的机制
• 提供完整性检查
• 进行违约处理

1.实体完整性

实体完整性定义：

# 列级定义
CREATE TABLE Student
	(Sno CHAR(9) PRIMARY KEY
    );
# 表级定义
CREATE TABLE Student
	(Sno CHAR(9),
     Sname CHAR(20) NOT NULL
     PRIMARY KEY(Sno,Sname)
    );

完整性检查中，检查主码值是否唯一，主码的属性是否为空，不唯一或有属性为空就拒绝插入或修改。

2.参照完整性

用FOREIGN KEY定义哪些为外码，REFERENCES指明外码参照哪些表的主码。

CREATE TABLE SC
	(Sno CHAR(9) NOT NULL,
     Cno CHAR(4) NOT NULL,
     GRADE SMALLINT,
     PRIMARYKEY(Sno,Cno),
     FOREIGN KEY(Sno) REFERENCES Student(Sno),
     FOREIGN KEY(Cno) REFERENCES Cources(Cno)
	);

破坏参照完整性发生时，系统可以拒绝执行；级联操作(删除或更改所有导致不一致的元组);设置为空值（将导致不一致的元组的属性设为空值）。默认为拒绝执行，可显式进行说明：

CREATE TABLE SC
	(Sno CHAR(9) NOT NULL,
     Cno CHAR(4) NOT NULL,
     GRADE SMALLINT,
     PRIMARYKEY(Sno,Cno),
     FOREIGN KEY(Sno) REFERENCES Student(Sno)
     	ON DELETE CASCADE
     	ON UPDATE CASCADE,
     FOREIGN KEY(Cno) REFERENCES Cources(Cno)
     	ON DELETE NO ACTION
     	ON UPDATE CASCADE
	);

3.用户定义的完整性

用户定义属性上的约束条件包括：

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

# 属性上的约束条件
CREATE TABLE SC
	(Sno CHAR(9) NOT NULL,
     Cno CHAR(4) NOT NULL,
     GRADE SMALLINT CHECK (GRADE>=0 AND GRADE<=100),
     PRIMARYKEY(Sno,Cno),
     FOREIGN KEY(Sno) REFERENCES Student(Sno),
     FOREIGN KEY(Cno) REFERENCES Cources(Cno)
	);
# 元组上的约束条件
CREATE TABLE Student
	(Sno CHAR(9),
     Sname CHAR(20) NOT NULL,
     Ssex CHAR(2),
     Sage SMALLINT,
     PRIMARY KEY(Sno),
     CHECK(Ssex=‘女’ OR Sname NOT LIKE 'Ms.%')
    );

4.完整性约束命名

为了方便灵活地增加，删除完整性约束条件，可以对完整性约束进行命名。

CREATE TABLE STUDENT
	(Sno CHAR(9),
     Sname CHAR(20)
     CONSTRAINT C1 NOT NULL,
     Sage SMALLINT
     CONSTRAINT C2 CHECK(Sage>0 AND Sage<100),
     Ssex CHAR(2)
     CONSTRAINT C4 CHECK (Ssex IN ('male','female')),
     CONSTRAINT StudentKey PRIMARY KEY(Sno)
    );
# ALTER CONSTRAINTS
ALTER TABLE Student
	DROP CONSTRAINT C1;
ALTER TABLE Student
	ADD CONSTRAINT C2 CHECK(Sno>'000000000');

5.断言

断言是更具一般性的约束，可以定义涉及多个表或聚集操作的比较复杂的完整性约束。使用CREATE ASSERTION语句来创建断言，且每个断言都有一个名字。

# 限制数据库课程最多60名学生选修
CREATE ASSERTION ASSE_SC_DB_NUM
	CHECK (60>=(
        		SELECT count(*)
                FROM Course,SC
                WHERE SC.CNO=COURSE.CNO AND COURSE.CNAME=‘数据库’
    			)
          );
# 限制每个学期每门课程最多60名学生选修
ALTER TABLE SC ADD TERM DATE;
CREATE ASSERTION ASSE_SC_CNUM2
	CHECK(
        60>=ALL(SELECT COUNT(*) FROM SC GROUP BY Cno,TERM)
    	);
# 删除断言
DROP ASSERTION 断言名

需要注意的是，如果断言很复杂，则系统在检测和维护断言上的开销较高，使用断言时需要注意。

6.触发器

触发器是用户定义在关系表上的一类由时间驱动的特殊过程。定义后，触发器将被保存在数据库服务器中，任何用户对表的增、删、查、改操作均由服务器自动激活相应的触发器。触发器类似约束，但更加灵活，可以实施更为复杂的检查和操作。关于触发器有以下几点：

• 表的拥有者才可以创建触发器，而且可创建的触发器数量有限。
• 触发器只能定义在基本表上，不能定义在视图上。
• 触发事件可以是UPDATE/INSERT等的组合，AFTER/BEFORE是触发的时机。
• 触发器按照触发间隔可分为行级触发器FOR EACH ROW和语句级触发器FOR EACH STATEMENT。
• 触发器被激活时，只有当触发条件为真时才执行。

触发器的一般格式为：

CREATE TRIGGER 触发器名
BEFORE|AFTER 触发事件 ON 表名
REFERENCING NEW|OLD ROW AS 变量
FOR EACH ROW|STATEMENT
WHEN 触发条件 触发动作体

以下是触发器的几个例子：

# 将INSERT语句增加的元组数记录到insertlog中
CREATE TRIGGER Student_Count
AFTER INSERT ON Student
REFERENCING
	NEW TABLE AS DELTA
FOR EACH STATEMENT
	INSERT INTO StudentInsertLog(Numbers)
	SELECT COUNT(*) FROM DELTA;
# 将分数增加10%的操作添加到一个另一个表SC_U
CREATE TRIGGER SC_T
AFTER UPDATE OF Grade ON SC
REFERENCING
	OLDROW AS OldTuple
	NEWROW AS NewTuple
FOR EACH ROW
WHEN (NewTuple.Grade>=1.1*OldTuple.Grade)
	INSERT INTO SC_U (Sno,Cno,OldGrade,NewGrade)
	VALUES(OldTuple.Sno,OldTuple.Cno,ldTuple.Grade,NewTuple.Grade);
# 教授的工资不低于4000，低于4000则改为4000
CREATE TRIGGER Insert_Or_Update_Sal
BEFORE INSERT OR UPDATE ON Teacher
REFERENCING NEW row AS newtuple
FOR EACH ROW
BEGIN
	IF(newtuple.Job=‘教授’) AND newtuple.Sal<4000)
		THEN newtuple.Sal:=4000;
	END IF;
END;

一个表上可能有多个触发器，触发器激活时执行顺序是BEFORE触发器、激活触发器的SQL语句，该表上的AFTER触发器。对于同一个表上的多个触发器，遵循涉嫌创建谁先执行的原则，有的数据库管理系统按照触发器名字排序执行。

删除触发器的语句如下：

FROP TRIGGER 触发器名 ON 表名

第六章 关系数据理论

1.概述

本章主要的内容为如何构造一个好的数据库模式，即应该构造几个关系模式，每个关系由哪些属性组成等。

作为一个二维表，关系要满足的最基本的要求是每个分量必须是不可分的数据项。满足该条件的关系模式就属于第一范式1NF。

数据依赖是关系内部属性与属性之间的约束关系，体现数据间的相关联系。数据依赖中最重要的是函数依赖和多值依赖。函数依赖是最为普遍的，但是如果函数依赖存在不好的性质，就会导致插入异常，删除异常，冗余等许多问题。

函数依赖的一个例子：F={Sno->Sdept，Sdept->Mname，(Sno，Cno)->Grade}。

2.规范化

2.1 函数依赖

函数依赖包括非平凡的函数依赖，平凡的函数依赖(X->X)。若X->Y，X称为函数的决定属性组，也称为决定因素。通常我们只讨论非平凡的函数依赖。

函数依赖还可以分为完全函数依赖和部分函数依赖。对于完全函数依赖X->Y，Y不依赖于X的真子集，只有选取完整的X，才能选定唯一的Y，例如(Sno，Cno)->Grade。而不完全依赖是指X->Y，X的真子集和Y也能形成依赖关系，即X的真子集就可以确定唯一的Y，例如(Sno，Cno)->Sdept。

2.2 码

设K为关系R中的属性或属性组，若U完全依赖于K，则K为R的候选码。若候选码多于一个，则其中一个被选定为主码。任何一个候选码中的属性为主属性，否则为非主属性或非码属性。

关系R中的属性或属性组X非R的码，为另一个关系模式的码，则X是R的外码。

2.3 范式

关系数据库中的关系是要满足一定要求的，满足不同程度要求的为不同范式。一个低一级范式的关系模式通过模式分解可以转换为若干个高一级范式的关系模式的集合，这种过程就叫做规范化。

2.4 2NF

若R为第一范式，且每一个非主属性完全函数依赖于任何一个候选码，则R为第二范式。第二范式保证了关系中的每一个属性，都是可以通过另一个候选码属性确定的，即关系中不存在和候选码无关的属性，这确保了表中只含有与候选码相关的一类信息。

2.5 3NF

若R中不存在码X，属性组Y及非主属性Z，使得X->Y,Y->Z成立，Y不完全依赖于X，则关系R满足第三范式。这条范式是指关系中不存在传递依赖，每一个属性都是和主码直接相关的。

第三范式可以简单表述为：每一个非主属性既不传递依赖于码，也不部分依赖于码。

2.6 BCNF(修正的第三范式)

BCNF在第三范式的基础上，增加了要求：每一个决定因素都包含码。即所有属性都只完全函数依赖于码，不依赖于非码的一组属性。

2.7 4NF

4NF消除了属性之间的非平凡且非函数依赖的多值依赖。

3.Armstrong公理系统

Armstrong公理系统是讨论函数依赖的一个完备的公理系统，对于关系模式R，有以下推理规则：

• 自反律：若Y⊆X⊆U，则X→Y为F所蕴含。

• 传递律：若X→Y，Y→Z，则X→Z为F所蕴含。

• 增广律：若X→Y，Z⊆U，则XZ→YZ为F所蕴含。

在讨论函数依赖时，需要求出Armstrong公理能推导出的所有函数依赖的集合。因此引入以下定义：

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

如果函数依赖集F满足一些条件，则F为一个最小依赖集。下面直接给出求解最小依赖集的方法：

• 使F中函数依赖的右部仅有一个属性(分解)
• 去掉冗余的函数依赖(先去掉X→Y，求X的闭包，若含Y，则X→Y可以去掉，否则保留)
• 去掉函数依赖左部冗余的属性(XY→A，求X的闭包，若含A，则X→A，Y可以去掉)

第七章 数据库设计

1.概述

数据库设计是指对于一个给定的应用环境，构造优化的数据库逻辑模式和物理结构，并据此建立数据库及其应用系统，使之能够有效存储和管理数据，满足用户应用需求。特点是重视技术、管理、基础数据的收集和整理；结构(数据)设计和行为(处理)设计相结合。数据库设计的基本步骤如下：

• 需求分析：通过调查分析，获得用户对数据库的信息要求，处理要求，安全性与完整性要求。
• 概念结构设计：产生独立于数据库管理系统的概念模式(E-R图)。
• 逻辑结构设计：将E-R图转换为数据模型，如关系模型。并按照用户处理和安全的要求建立必要的视图。
• 物理结构设计：根据数据库管理系统特点和处理的需要，进行物理存储安排，建立索引，形成数据库内模式。
• 数据库实施
• 数据库运行和维护

2.需求分析

• 数据字典：数据字典是通过详细的数据收集和分析后的主要成果。是关于数据库中数据的描述，是元数据。在需求分析阶段建立，在设计过程中不断修改和完善。数据字典通常包含数据流，数据项，数据结构，数据存储和处理过程等。

3.概念结构设计

将需求分析得到的用户需求抽象为概念模型的过程就是概念结构设计。概念模型通常用E-R模型来表示和描述。

3.1 E-R模型

E-R模型由实体，属性，实体之间的联系等构成。实体型之间的联系包括一对一联系，一对多联系，多对多联系等，多个实体型之间也可以存在联系，单个实体型内也可以存在联系。这些实体与实体之间的联系用E-R图来表示。在E-R图中，对于实体，属性，联系的表示方法如下：

• 实体型用矩形表示
• 属性用椭圆表示
• 联系用菱形表示

由于一个实体可能存在多个属性，为了表述清晰，可以不把属性在E-R图中画出，而是直接写出，例如：

实体：

实体名1(属性1，属性2，属性3...)

然后再给出E-R图。

3.2 概念结构设计

概念结构设计的第一步是对数据进行分类，确定实体，属性，联系。实体与属性划分时，能看作属性的尽量看作属性，并按照两条准则：

• 属性不能和其他实体具有联系：例如人事管理系统中，如果职称与工资，补贴无关，就可以视作职工的属性。否则看作一个实体对待更合适。
• 作为属性，不能有再需要描述的性质。

概念结构设计时，通常自顶向下确定需求，自底向上设计概念结构。首先设计各子系统的分E-R图，然后再集成起来，得到全局E-R图。集成过程一般有两步：

• 合并：解决各分E-R图之间的冲突，合并分E-R图产生初步E-R图，冲突有以下几种：
  • 属性冲突：域或取值单位冲突
  • 命名冲突
  • 结构冲突：同一对象有不同的抽象(在不同子系统分别看作实体，属性)，实体间的联系在不同系统中不同，同一实体有不同的属性等。
• 消除不必要的冗余，设计基本E-R图

4.逻辑结构设计

逻辑结构设计的任务是把概念结构设计的基本E-R图转变为与选定数据库管理系统对应的数据模型的逻辑结构。下面以关系模型为例介绍转换过程。

将E-R图转换为关系模型的逻辑结构。关系模型是一组关系模式的集合，转换实际上就是将E-R图转换为一些关系模式。其中，实体可以直接转换为关系模式，而联系则有以下情况：

• 1;1联系可以转换为一个关系模式，也可以与任意一端的关系模式合并。
• 1:n联系可以转换为一个关系模式，或与n端关系模式合并。
• m:n或多个实体间的联系可以转换为一个关系模式。
• 具有相同码的关系模式可以合并。

完成转换后，可以对得到的数据模型进行优化，具体的方法是合并与分解，以规范化理论为依据，但不一定要规范化到程度很高，要考虑使用情况。

得到了全局的逻辑模型后，还应该根据局部应用的需求，为用户设计外模式，外模式使用应符合用户习惯的别名，且应该为不同用户设计不同的外模式，并简化用户对系统的使用。

5.物理结构设计

物理结构设计的任务是为给定的逻辑数据模型选取一个最适合应用要求的物理结构。物理设计分为两步：

• 确定数据库的物理结构，在关系数据库中主要指存取方法和存储结构
• 对物理结构进行评价，重点评价时间和空间效率

下面简要介绍关系型数据库的物理设计。

5.1 存取方法选择

存取方法是快速存取数据库中数据的技术。数据库管理系统一般提供多种存取方法。常用的存取方法为索引方法和聚簇方法。

• B+树索引存取方法：对属性列或属性组建立索引。如果一个属性或属性组经常被查询，连接或作为聚集函数的参数，可以考虑建立索引。维护索引要付出代价，因此索引不是越多越好。
• HASH索引存取方法：如果一个关系的属性主要出现在等值连接条件或等值比较选择条件中，并且关系大小不变，或数据库提供了动态HASH存取方法，则可以选择HASH存取方法。
• 聚簇存取方法：将某个属性上有连续或相同值的元组放在连续物理块中称为聚簇。该属性称为聚簇码。聚簇可以大大提高按聚簇码查询的效率，但开销也很大，一个关系只能使用一个聚簇码。应该尽量使用稳定的聚簇码，应用应该主要通过聚簇码进行连接或访问，否则聚簇码值总是改变，维护的开销会很大。

5.2 确定数据库的存储结构

数据库的存储结构主要指数据的存放位置，包括确定关系，索引，聚簇，日志，备份等的存储安排或存储结构。确定数据的存放位置，应该将数据的易变部分和稳定部分，经常存取和存取频率低的部分分开存放，提高I/O效率，也可以将日志文件和数据库对象放在不同的磁盘上，或是将较大的表放在两个磁盘上，有许多方法可以让存储结构和存放位置有利于数据库的性能。

关系型数据库管理系统一般都提供了一些系统配置变量和存储分配参数，管理人员可以通过参数对数据库进行物理优化。系统配置变量有很多，例如并发用户数，同时打开的数据库对象数，缓冲区参数，物理块的大小，锁的数目等。

6.数据库的实施和维护

数据库设计完成后，就要进行数据库的实施，并且组织数据入库，然后就可以使用数据库应用了。数据库应用程序设计应该和数据库设计同时进行，当数据库设计完成后，就可以载入数据，进行应用程序的调试。数据库试运行时，先从小批量数据调试开始，再逐步增加数据；且开始时数据库系统可能还不稳定，操作人员还不熟悉，要做好数据库的转储和恢复，以免破坏数据库。

数据库试运行合格后，就可以投入正式运行了，在运行阶段，维护工作主要包括数据库的转储和恢复，数据库的安全性和完整性控制，数据库性能的监督、分析和改造，数据库的重组织与重构造。这里就不一一介绍了。

第八章 数据库编程

本章主要介绍的内容是关于数据库编程的，包括嵌入式SQL，过程化SQL，存储过程以及函数。由于不同的数据库实际提供了不同的应用接口，不一定兼容嵌入式SQL，而存储过程以及函数主要在实验中学习，故本章内容不再介绍。

第九章 关系查询处理和查询优化

本章介绍关系数据库的查询处理和查询优化技术。首先介绍关系数据库管理系统的查询处理步骤，然后介绍查询优化技术。查询优化一般可分为代数优化和物理优化。代数优化是对关系代数表达式的优化，物理优化则是通过存取路径和底层操作算法的选择进行优化。

1.关系数据库系统的查询处理

关系数据库管理系统的查询处理可以分为四个阶段：

• 查询分析：对语句进行词法分析和语法分析，并进行检查。
• 查询检查：对语句进行语义检查，检查数据字典中是否有语句中的数据对象，用户是否有存取权限，是否是对视图的查询(需要进行消解)，是否违反完整性约束。检查通过后将语句转化为内部表示，即等价的关系代数表达式，并用查询树表示。
• 查询优化：对查询进行优化。一般包括代数优化和物理优化，代数优化是对关系代数表达式的优化，物理优化则是通过存取路径和底层操作算法的选择进行优化。
• 查询执行：由代码生成器生成执行查询的代码，执行后返回结果。

2.实现查询操作的算法示例

2.1 选择操作的实现

简单的选择操作的实现方法如下：

• 简单全表扫描算法：按照次序读出物理块到内存并逐个元组扫描。
• 索引扫描算法：如果选择条件的属性存在索引，首先通过索引找到满足条件的元组指针，再通过元组指针找到元组。如果有多个选择条件并且都有索引，例如Sdept=CS AND Sage>20，则可以求索引元组指针交集，也可以取出满足一个条件的所有元组，再选出符合第二个条件的。

当选择率较低时，索引扫描算法优于全表扫描算法，但选择率较高，或者要查找的元组均匀分布在表中的情况下，全表扫描可能性能更好，因为扫描索引也有开销，对每一个索引码，从B+树根节点到叶子节点的每个节点都要执行一次I/O。

2.2 连接操作的实现

连接操作是查询处理最常用也最耗时的操作之一，连接操作的一些算法实现如下：

• 嵌套循环算法：对外层循环的元组，检查内层循环的每一个元组，在连接属性上是否相等。
• 排序-合并算法：先对两表按连接属性排序，取一个表A中的第一个元组，扫描另一个表B中具有相同连接属性的元组并连接，直到遇到了不相同的第一个元组，再返回表A取下一个元组，重复这个过程。对于大表，尽管没有排序时要先进行排序，执行时间仍然会比嵌套循环更少。
• 索引连接算法：若在表A已经建立了连接属性的索引，对表B的每一个元组，由连接属性值通过表A的索引查找相应的元组，找到后进行连接。
• hash join算法：hash join也是处理等值连接的算法。它把连接属性作为hash码，用同一个hash函数把两表中的元组散列到hash表中。第一步划分阶段，创建hash表，对包含较少元组的表处理，把元组分散到hash表的桶中；第二步试探阶段，对另一个表进行一遍处理，把元组也按同一个hash函数散列，找到适当的hash桶，并将匹配的元组连接起来。

3.关系数据库系统的查询优化

3.1 代数优化

代数优化是基于关系代数等价变换规则的优化方法。关系代数的等价变换规则是一组基本的结合律，串接定律，交换律等。此处直接介绍查询树的启发式优化算法。在查询处理的第二步，查询检查后，会产生查询树，通常使用启发式算法对查询树进行优化，典型的启发式规则有：

• 选择运算尽可能先做：减少计算中间结果。(最重要的规则，可以大大减少中间结果的大小)
• 投影运算和选择运算同时进行：扫描关系时同时完成。
• 投影和前或后的双目运算结合：没有必要为了去掉字段扫描关系。
• 把一些选择和笛卡尔积结合为连接运算：连接运算要比笛卡尔积节省很多时间。
• 找出公共子表达式：如果子表达式的结果重复出现且不太大，可以将该结果存入中间文件。当查询视图时，视图的定义就是公共子表达式。

以下是一个代数优化的例子：

对学生-课程数据库，查询信息系学生选修了的所有课程名称。

SELECT Cname
FROM Student,Course,SC
WHERE Student.Sno=SC.Sno 
AND SC.Cno=Course.Cno 
AND Student.Sdept=’IS’;

试画出用关系代数表示的语法树，并用关系代数表达式优化算法对原始的语法树进行优化处理，画出优化后的标准语法树。

3.2 物理优化

代数优化改变查询语句中操作的次序和组合，但不涉及底层操作路径。对每一种操作，可以有多种算法，多条存取路径，物理优化就是从多种算法和多条路径中选择高效合理的操作和算法进行查询。选择的方法可以是：

• 基于规则的启发式优化
• 基于代价估算的优化
• 两者结合的优化

基于启发式规则的存取路径选择优化

对于选择操作，小关系直接使用全表顺序扫描，即使存在索引；大关系则使用以下启发式规则：

• 选择条件为主码=值，选择主码索引
• 选择条件为非主属性=值，并且存在索引，估算查询结果的元组数目，如果比例较小，例如<10%，可以使用索引扫描，否则还是采用全表顺序扫描
• 对于选择条件是属性的非等值查询或范围查询，同上，需要估算结果元组数目
• 对于AND连接的合取选择条件，如果有涉及这些属性的组合索引，优先采用组合索引扫描，某些列上有一般索引，也可以用索引扫描方法
• 对于OR连接的析取选择条件，一般使用全表顺序扫描

第十章 数据库恢复技术

1.事务的基本概念

事务是用户定义的一个操作序列，这些操作只能全做或全不做，是不可分割的工作单位。事务开始与结束可以由用户显式控制，如果没有控制，数据库系统会自动划分事务。事务通常以BEGIN TRANSACTION开始，以COMMIT或ROLLBACK结束。COMMIT表示提交，将所有对数据库的更新写到磁盘上的物理数据库中。ROLLBACK表示回滚，当出现某些故障，事务不能继续执行，就撤销所有已完成的操作，回到事务开始时的状态。

事务具有4个特性，原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation)、持久性(Durability)，这四个特性被称为事务的ACID特性。

• 原子性：事务是数据库工作的逻辑单位，只能全做或全不做。
• 一致性：事务必须使数据库从一个一致性状态到另一个一致性状态。
• 隔离性：一个事务的执行不能被其他事务干扰。
• 持久性：一个事务一旦提交，对数据库中数据的改变就应该是永久性的。接下来的其他操作或故障不对其结果有影响。

2.数据库恢复概述

数据库管理系统必须具有把数据库从错误状态恢复到某一已知的正确状态的功能，这就是数据库的恢复。

3.故障的种类

数据库系统中可能发生的故障，大致可分为以下几类：

• 事务内部的故障：事务内部的故障有些是事务程序本身可以发现的，有些是非预期的，不能由事务程序处理。事务故障表示事务没有达到预期终点，因此恢复程序要强行回滚该事务，撤销该事务已作出的对数据库的修改，这类恢复操作称为事务撤销。
• 系统故障：系统故障是造成系统停止运转的任何事件，使得系统要重新启动。恢复子系统必须在系统重新启动时进行事务撤销。系统故障时还可能有已完成的事务没有写到物理数据库中，还需要重做所有已提交的事务。
• 介质故障：外存故障，磁盘损坏，磁头碰撞等。这类故障发生概率小，但破坏最大。
• 计算机病毒：人为的故障或破坏。

各类故障对数据库的影响有两种可能，一是数据库本身被破坏，二是数据库没有被破坏，但数据可能不正确。恢复的基本原理是采用冗余。

4.恢复的实现技术

4.1 数据转储

数据转储是数据库恢复的基本技术。转储即定期将整个数据库复制到存储介质上保存，作为后备副本。数据库遭到破坏后，可以装入后背副本，将数据库恢复到转储时的状态。为了将数据库恢复到故障发生时的状态，还需要重新运行转储以后的所有更新事务。

转储可分为静态转储和动态转储。

• 静态转储：在系统无运行事务时进行转储。
• 动态转储：转储期间允许对数据库进行存取和修改。此方式转储和事务可以并发执行，但不能保证转储结束的后备副本正确有效，还需要使用日志文件记录转储期间各事务对数据库的修改。

转储还可分为海量转储和增量转储。

• 海量转储：每次转储全部数据库。
• 增量转储：每次只转储上一次转储后更新过的数据。

根据转储时期，转储内容，转储可分为静态海量转储，静态增量转储，动态海量转储，动态增量转储。

4.2 登记日志文件

日志文件是用来记录事务对数据库的更新操作的文件。日志文件主要有两种格式，以记录为单位的日志文件和以数据块为单位的日志文件。对以记录为单位的日志文件，记录需要登记事务的开始和结束标记，以及所有更新操作，每一个开始和结束标记，更新操作都有一个日志记录，日志记录包含事务标识，操作对象，类型，修改前后的值等。

日志文件的主要作用是：

• 事务故障恢复和系统故障恢复必须用日志文件。
• 动态转储必须建立日志文件，和后备副本结合恢复数据库。
• 静态转储也可以建立日志文件，和后备副本结合恢复数据库到故障前某一刻的状态。

为保证数据库是可恢复的，登记日志文件时必须遵守两条原则：

• 登记的次序严格按照并发事务执行的时间次序。
• 必须先写日志文件，后写数据库。

5.恢复策略

不同故障使用不同的故障恢复方法和策略。

事务故障的恢复由系统利用日志文件自动完成，撤销该事务对数据库进行的修改。方式是反向扫描日志文件，找到该事务的更新操作，就进行逆操作，直到读到事务的开始标记。

系统故障的恢复由系统在重新启动时自动完成，不需要用户干预。方式是正向扫描日志文件，找出故障发生前已经提交的事务(存在BEGIN TRANSACTION 和 COMMIT记录)，将其事务标识加入REDO重做队列，将未完成的事务的事务标识记入UNDO撤销队列，然后撤销撤销队列中的事务，重做重做队列中的事务。

介质故障的恢复首先要装入最新的数据库后备副本，使数据库恢复到最近一次转储的一致性状态。对于动态转储的数据库副本，还需要装入转储开始时刻的日志文件副本，进行REDO和UNDO，才能将数据库恢复到一致状态。然后装入转储结束时刻的日志文件副本，重做已经完成的事务，就可以恢复数据库了。

6.具有检查点的恢复技术

利用日志对数据库恢复时，需要检查所有日志记录，耗费大量时间，还可能将很多已经将更新写入数据库的事务进行了重做，浪费了大量时间。为了解决这些问题，产生了具有检查点的恢复技术。这类技术在日志文件中添加检查点记录，增加了一个重新开始文件，让恢复子系统动态维护日志。

检查点记录的内容包括：

• 建立检查点时刻正在执行的事务清单。
• 这些事务最近一个日志记录的地址。

重新开始文件则记录了各个检查点记录在日志文件中的地址。通过不断记录检查点，就可以只对检查点到故障发生时的事务进行处理，解决上述浪费时间的问题。系统使用检查点恢复的步骤是：

• 从重新开始文件找到最后一个检查点记录在日志文件中的地址，在日志文件中找到最后一个检查点记录。
• 由检查点记录得到检查点建立时刻所有正在执行的事务清单ACTIVE-LIST，并建立REDO-LIST和UNDO-LIST事务队列，将所有ACTIVE-LIST中的事务先添加到UNDO-LIST。
• 从检查点开始正向扫描日志文件，将完成的事务从UNDO-LIST转移到REDO-LIST。
• 重做REDO-LIST中的事务，撤销UNDO-LIST中的事务。

7.数据库镜像

随着存储介质的价格下降，为了应对介质故障，并避免周期性转储的负担，许多数据库管理系统提供了数据库镜像功能，自动将数据库或其中的关键数据复制到另一个磁盘，并自动保证一致性。数据库镜像也可以用于并发操作，让数据被修改时，其他用户可以读镜像数据库的数据，而不用等待。数据库镜像一般只对关键数据和日志文件进行镜像。

第十一章 并发控制

1.概述

数据库是一个共享资源，供多个用户使用，同一个时刻并发运行的事务数很多。事务不是严格按照一个一个完成的串行顺序执行的，而是并行执行的，并行事务轮流交叉运行。在单处理器上，并行事务并不是真正并行运行的，但减少了处理器空闲时间，提高了系统效率。

事务是并发控制的基本单位，保证事务的ACID特性是事务处理的重要任务。为了保证事务的隔离性和一致性，数据库系统需要对并发操作进行正确调度。并发操作带来的数据不一致性有以下三种：

• 丢失修改：两个事务读入同一数据并修改，其中一个事务的修改丢失。
• 不可重复读：一个事务读取数据，另一个事务执行了更新操作(修改，删除，插入)，当读取数据的事务重新读取数据时，无法重现前一次读的结果。
• 读脏数据：一个事务修改某一数据，紧接着另一事务读取该数据，修改数据的事务接下来因为某些原因被撤销，读取数据的事务读到的数据为脏数据，与数据库的数据不一致。

并发控制机制就是使用正确的调度使一个用户的事务不受另一个用户的干扰，避免数据的不一致性。

并发控制的主要技术有封锁，时间戳，乐观控制法和多版本并发控制等。

2.封锁

数据库对数据对象使用两种类型的基本封锁保证数据一致性。

• 排他锁(X锁/写锁)：事务T对数据对象A加上排他锁，则只允许T读取修改A，其他事务不能对A加任何锁，直到T释放该锁。
• 共享锁(S锁/读锁)：事务T对数据对象A加上共享锁，T只能读取A，其他事务可以对A加共享锁，不可以加排他锁，直到T释放该锁。

3.封锁协议

对数据加锁时，要约定一些规则，这些规则称为封锁协议。

封锁协议	一致性保证	协议
一级封锁协议	不丢失修改	事务T在修改数据之前必须加X锁，事务结束释放该锁。
二级封锁协议	不丢失修改，不读脏数据	在一级封锁协议基础上，事务T在读取数据之前必须 加S锁， 读完后释放S锁
三级封锁协议	不丢失修改，不读脏数据，可重复读	在一级封锁协议基础上，事务T在读取数据之前必须 加S锁， 事务结束后释放S锁

4.活锁和死锁

和操作系统并发控制一样，封锁会引起活锁和死锁等问题。

活锁是指一个事务等待锁，但是由于许多事务都在等待锁，而每次一个事务释放锁时，总是将锁交给其他等待锁的事务，导致这个事务永远等待锁的情况。避免活锁的方法是使用先来先服务的策略，按照次序让事务获取锁。

死锁的情况是两个事务封锁了两个数据对象，而这两个事务又都需要使用对方当前上锁的数据对象，导致互相等待。在数据库中，解决死锁的问题有两类方法，一类是预防死锁，另一类是允许死锁发生，定期诊断并解除死锁。死锁的预防存在很大的困难，因此数据库普遍采用诊断并解除死锁的方法。

• 死锁的预防：

  • 一次封锁法：每个事务必须一次将所有要使用的数据全部加锁，否则不能执行。这个方法能有效防止死锁，但一开始就封锁了所有数据，降低了并发度，而且如果要在一开始就封锁所有可能使用的数据对象，只能扩大封锁范围，进一步降低了并发度。
  • 顺序封锁法：预先对数据对象规定一个封锁顺序，按顺序封锁。这种方法的问题为：事务中的数据对象很多且会变化，很难维护一个封锁顺序；封锁请求可以随事务执行动态决定，难以确定所有的封锁对象及顺序。

• 死锁的诊断

  • 超时法：如果事务等待时间超过规定时限，就认为发生超时。这种方法时限的确定困难，时限短可能误判死锁，时限长则死锁不能及时发现。
  • 等待图法：用事务等待图表示所有事务的等待情况。并发控制系统周期生成事务等待图，通过检测是否存在回路判断是否出现了死锁。
• 死锁的解除：数据库通常采用的方法是选择一个处理死锁代价最小的事务，将其撤销，释放此事务持有的所有的锁，使其他事务可以正常运行。

5.并发调度的可串行性

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

可串行性是并发事务正确调度的准则。一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度。

接下来介绍判断可串行化调度的充分条件，首先介绍冲突操作。

• 冲突操作：不同的事务对同一个数据的读写操作和写写操作。例如：Ri(x)与Wj(x)，i≠j。

两事务的冲突操作或同一事务的两个操作一旦交换顺序，结果就会不同，因此考虑可串行化的调度时，不能交换冲突操作或同一事务的两个操作的顺序。一个调度在保证冲突操作次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一个调度，如果新的调度是串行的，则原调度为冲突可串行化的调度。若一个调度是冲突可串行化的调度，则一定是可串行化的调度。需要注意冲突可串行化是可串行化调度的充分条件，不是必要条件。

例：

有三个事务的一个调度r3(B)r1(A)w3(B)r2(B)r2(A)w2(B)r1(B)w1(A)，该调度是否为冲突可串行化的调度?

该调度是冲突可串行化的调度。

交换r1(A)和w3(B)，得到r3(B)w3(B)r1(A)r2(B)r2(A)w2(B)r1(B)w1(A)

交换r1(A)和w2(B)，得到r3(B)w3(B)w2(B)r2(B)r2(A)r1(A)r1(B)w1(A)

r3(B)w3(B)w2(B)r2(B)r2(A)r1(A)r1(B)w1(A)等价于一个串行调度T3T2T1，因此原调度为冲突可串行化的调度。

6.两段锁协议

为了保证并发调度的正确性，数据库管理系统需要保证调度是可串行化的。目前数据库管理系统普遍采用两段锁协议实现并发调度的可串行性，从而保证调度的可串行性。

两段锁指两个阶段对数据项加锁和解锁：

• 对任何数据进行读，写操作之前，首先要申请并获得对数据的封锁
• 在释放一个封锁之后，事务不再申请和获得任何其他封锁

两段锁的两段的含义是，事务分为两个阶段，第一阶段获得锁，称为扩展阶段，该阶段只能获得锁，不能释放锁；第二阶段是释放锁，称为收缩阶段，该阶段只能释放锁，不能获得锁。

若并发执行的所有事务都遵守两段锁协议，则这些事务的任何并发调度策略都是可串行化的。不过事务遵守两段锁协议也只是可串行化调度的充分条件，不是必要条件。需要注意，两段锁协议中，第一阶段没有要求一次对所有使用的数据对象加锁，因此不是一次封锁法，是可能产生死锁的。

最后比较一下两段锁协议与三级封锁协议，这两种协议的目的不同，两段锁协议的目的是保证并发调度的正确性，而三级封锁协议的目的是保证数据的一致性。遵守三级封锁协议一定遵守两段锁协议。

7.封锁的粒度

7.1 多粒度封锁

封锁对象的大小称为封锁粒度。封锁对象可以是逻辑单元(关系，索引，属性)，也可以是物理单元(页)。封锁粒度越大，并发度越小，系统开销越小。为了平衡开销与并发度，一个系统中应该同时支持多种封锁粒度供不同的事务选择，这种封锁称为多粒度封锁。需要封锁时，考虑封锁开销和并发度两个因素，适当选择合适的封锁粒度。例如处理一个关系的大量元组可以以关系为封锁粒度，处理少量元组的事务可以以元组为封锁粒度，处理多个关系的大量元组的事务可以以数据库为封锁粒度。

多粒度封锁情况可以用多粒度树表示，多粒度树根节点是数据库，表示最大的数据粒度，叶子节点表示最小的数据粒度。多粒度封锁的协议允许多粒度树找那个的每个节点独立加锁，并且一个节点加锁，其后代子节点也被加同样的锁。因此多粒度封锁中的数据可能以两种方式封锁：

• 显式封锁：直接加到数据对象的锁
• 隐式封锁：由于上级节点加锁导致当前节点加锁

显式封锁和隐式封锁的效果是一样的。在对数据对象加锁时，要检查有无显式封锁冲突，还要检查上级节点，检查是否与隐式封锁冲突，也要检查下级节点，判断下级节点的显式封锁是否与当前加锁带来的隐式封锁冲突，这样的检查效率很低，因此引入了一种新型锁提高效率，称为意向锁。

7.2 意向锁

意向锁的含义是：如果对一个节点加意向锁，说明其下层后代节点正在被加锁；对任一节点加锁时，必须先对其上层节点加意向锁。以下是三种常见用的意向锁：

• IS锁：对一个数据对象加IS锁，表示其下层节点要加S锁。
• IX锁：对一个数据对象加IX锁，表示其下层节点要加X锁。
• SIX锁：对一个数据对象加IX锁，表示对其加S锁，再加IX锁。例如事务对某个表加SIX锁，表示事务要读整个表，同时更新个别元组。

数据锁的相容矩阵如下：

T1/T2	S	X	IS	IX	SIX
S	Y	N	Y	N	N
X	N	N	N	N	N
IS	Y	N	Y	Y	Y
IX	N	N	Y	Y	N
SIX	N	N	Y	N	N

有了意向锁之后，就可以只检查当前数据是否有不相容的锁，上层节点是否有不相容的锁，不需要检查下层后代节点是否有不相容的锁。