数据库笔记 | Rainnn の Blog

type

status

date

slug

summary

DB复习

往年题

年份	往年题链接
2023	山东大学软件学院数据库2022-2023期末考试回忆版_山东大学数据库期末考试-CSDN博客
ㅤ	山东大学软件学院2023数据库系统期末回忆版_山东大学数据库期末-CSDN博客
2022	山东大学软件学院数据库系统2022年春期末考试_山东大学数据库期末考试-CSDN博客
ㅤ	山东大学2022年6月27日软件学院数据库系统期末考试回忆版_山东大学数据库期末-CSDN博客
2021	https://blog.csdn.net/weixin_46841376/article/details/118307456
2019	https://blog.csdn.net/weixin_42925536/article/details/94399575
2018	https://blog.csdn.net/LockeSher/article/details/86750766
2017	https://blog.csdn.net/Jemary_/article/details/80895170

其他往年题（文件版）：

一、引言

1.1 概述

考察简答、概念理解

四个基本概念：

数据（Data）

数据（data）：数据库中存储的基本对象。数据即描述事物的符号记录。数据的种类包括文字、图形、图像等。数据的特点在于与其语义是不可分的（数据的形式不能完全表达其内容）。

数据结构分为逻辑结构和物理结构：

逻辑结构：数据之间存在的逻辑关系。表、树、图、数组…
物理结构：数据在计算机内的存储方式。顺序方式、链接方式…

数据库（Database）

数据库（database）是长期储存在计算机内、有组织的、可共享的大量数据集合。数据库的特征包括：

数据按一定的数据模型组织、描述和储存
可为各种用户共享
冗余度较小
数据独立性较高
易扩展

数据库管理系统（DBMS） Database Management System

数据库管理系统 DBMS：由一个相互关联的数据集合（数据库）和一组用以访问这些数据的程序组成，这个数据集合通常称作数据库（Database），其中包含了关于某个机构的信息。或简述为系统软件，对数据库进行统一管理和控制。

DBMS的主要功能包括数据定义功能、数据操作功能、数据库的运行管理和数据库的建立和维护功能。

数据库系统（DBS）Database System

数据库系统（DBS）是指在计算机系统中引入数据库后的系统，由数据库、数据库管理系统、应用系统和数据库管理员构成。

1.2 数据管理的发展

数据管理经历了三个发展阶段：

人工管理阶段（50年代中期以前）

文件系统阶段（50年代后期-60年代中期）

数据库系统阶段（60年代后期开始）

大数据阶段（2005年）

1.3 数据视图

数据库系统的一个主要目的是给用户提供数据的抽象视图，即隐藏关于数据存储和维护的某种细节。

型与值的关系：

型（模式，Schemas）是对数据的结构和属性的说明。

值（实例，Instance）是型的一个具体赋值。

型是相对稳定的，值是随时间不断变化的。

数据库将数据设计成三层结构：

视图层：最高层次的抽象，只描述整个数据库的部分数据

提供了防止用户访问数据库的某些部分的安全机制

逻辑层：描述数据库中的数据以及数据之间的关系，即数据的定义

物理层：描述数据存储

数据库模式就是数据库的总体设计，按照三层的划分，包括：

子模式/外模式：视图层描述的数据库设计，逻辑模式的子集

逻辑模式：逻辑层描述的数据库设计

物理模式：物理层描述的数据库设计

数据库的实例是指特定时刻存储在数据库中的信息的集合。

为了提高数据的物理独立性和逻辑独立性，使数据库的用户观点，即用户看到的数据库，与数据库的物理方面，即实际存储的数据库区分开来，数据库系统的模式是分级的，美国数据系统语言协商会提出模式、外模式、存储模式三级模式的概念。

与独立性的联系：三级模式之间有两级映象。

数据库的三级视图实现了数据独立性：

物理数据独立性：物理模式的改变而不会影响逻辑模式。当物理模式改变时，修改模式/内模式映像，使外模式保持不变，从而应用程序可以保持不变。

逻辑数据独立性：当模式改变时，修改外模式/模式映像，使外模式保持不变，从而应用程序可以保持不变，称为数据的逻辑独立性。

三级模式结构示意如下：

1.4 数据模型

数据模型用来对数据的形式进行描述，包括：

ER模型实体-联系模型

层次模型

网状模型

关系模型

面向对象模型

1.5 数据库语言

DML（Data Manipulation Language）：操纵那些按照某种适当的数据模型组织起来的数据的语言。SQL是使用最广泛的DML。

DDL（Data Definition Langauge）：用于定义数据库模式以及其他特征的语言。

1.6 数据库引擎

存储管理器是一个程序模块，提供了数据库中存储的低层数据与应用程序以及向系统提交的查询之间的接口。

查询处理器包括：

DDL解释器：解释DDL语句，将这些定义记录在数据字典中

DML编译器：将查询语句中的DML语句翻译成为一个执行方案。

查询执行引擎：执行由DML编译器产生的低级指令。

事务是由一系列操作序列构成的程序执行单元，是一个不可分割的工作单位。

事务特性（ACID）：

原子性(Atomicity)

事务中包含的所有操作要么全做，要么全不做
原子性由恢复机制实现

持久性(Durability)

一个事务一旦提交之后，它对数据库的影响必须是永久的
系统发生故障不能改变事务的持久性
持久性通过恢复机制实现

一致性(Consistency)

事务的隔离执行必须保证数据库的一致性
事务开始前，数据库处于一致性的状态；事务结束后，数据库必须仍处于一致性状态
数据库的一致性状态由用户来负责，由并发控制机制实现
如银行转帐，转帐前后两个帐户金额之和应保持不变
事务运行过程中允许暂时的不一致

隔离性(Isolation)

系统必须保证事务不受其它并发执行事务的影响
对任何一对事务T1，T2，在T1看来，T2要么在T1开始之前已经结束，要么在T1完成之后再开始执行
隔离性通过并发控制机制实现

详见第十七章

1.7 数据库和应用系统结构

DBMS的运行过程（了解）：

用户向DBMS发出命令

DBMS对命令进行语法检查、语义检查、存取权限检查，决定是否执行该命令

DBMS执行查询优化，把命令转换为一串单记录的存取操作序列

执行存取操作序列（反复执行以下各步，直至结束）

DBMS首先在缓冲区内查找记录，若找到转10，否则转6

DBMS查看存储模式，决定从哪个文件存取哪个物理记录

DBMS根据6的结果，向操作系统发出读取记录的命令

操作系统执行读取数据的命令

操作系统将数据从数据库存储区送到系统缓冲区

DBMS根据用户命令和数据字典的内容导出用户所要读取的数据格式

DBMS将数据记录从系统缓冲区传送到用户工作区

DBMS将执行状态信息返回给用户

数据库体系结构（了解）

数据库系统的体系结构很大程度上取决于数据库系统所运行的计算机系统

集中式

客户/服务器式远程数据库用户工作用的客户机（client）运行数据库系统的服务器(server)

客户/服务器式 b三段式 application-server在server维护简单安全

并行 (多处理器) 并行系统通过并行地使用多个处理器和磁盘来提高处理速度和I/O速度

分布式在分布式数据库系统中，数据库存储在几台计算机中，分布式系统中的计算机之间通过网络相互通信，它们不共享主存储器或者磁盘

二、关系模型

2.1 关系数据结构

关系：某一时刻对应某个关系模式的内容（元组的集合称作关系）。现实世界的实体以及实体之间的各种联系均采用关系来表示

每个属性可能的取值范围（集合）叫做属性的域。属性的值（通常）要求为原子的（不可再分）。

域（Domain）是一组值的集合，这组值具有相同的数据类型。

null（空值）：是一个特殊的值，表示值未知或者不存在。空值给数据库访问和更新带来很多困难。他有两种含义：

无意义（数据项没有值）

值未知（值存在，但没有获取该信息）

空值参与算术运算、比较运算的结果都是Null，参与逻辑运算时除Null or true = true和Null and false = false以外均为Null。

关系：表

元组：行

属性：列

笛卡尔积

一组域D1,D2,D3,…Dn的笛卡尔积为：

笛卡尔积的每个元素（d1,d2,d3,…dn）称作一个n-元组

笛卡尔积的子集叫做在域上的关系，用表示。其中是关系的名字，是关系的度或目。关系是笛卡尔积中有意义的子集。关系也可以表示为二维表。

关系的性质：

元组的顺序是无关紧要的。

列是同质的。每一列中的分量来自同一个域，是同一类型的数据。

不同的列可以来自同一个域，每列必须有不同的属性名。

列的次序可以任意交换。

任意两个元组不能完全相同。

这个性质由笛卡尔积的性质决定，但是许多关系数据库都没有遵循这一性质。

每一分量必须是不可再分的数据。满足这一条件的关系称作满足第一范式（1NF）的

2.2 关系模式和实例

关系模式和关系实例的区别和联系

数据库由多个关系组成。

关系模式：关系的描述称作关系模式，包括关系名、关系中的属性名、属性向域的映象、属性间的数据依赖关系等。关系模式可以表示为：

R：关系名

U：组成该关系的属性名集合

D：属性组U中属性所来自的域

dom：属性向域的映像集合

F：属性间的数据依赖关系集合

关系模型的组成包括：

关系数据结构

关系完整性约束

关系操作集合

2.3 码

码是能唯一标识实体的属性集，他是整个实体集的性质，而不是单个实体的性质。

码的作用：必须有一种能够区分给定关系中的不同元组的方法。一般用元组中的属性来表明，即一个元组的属性值必须是能够唯一区分元组的，一个关系中没有两个元组在所有属性上的取值都相同

码	作用
超码 superkey	超码是一个或者多个属性的集合，这些属性的组合可以使我们在一个关系中唯一地标识一个元组
候选码 candidate key	最小的超码称为候选码，即超码的任意真子集都不能成为超码
主码 primary key	从一个关系的多个候选码中选定一个作为主码
外码 foreign key （可以为空值）	一个关系模式可能在它的属性中包含另一个关系模式的主码，这个属性在上称作在上参照的外码（和r可以是同一个关系）。关系称作外码依赖的参照关系，关系称作外码的被参照关系。

习惯上把主码属性放在其他属性前面，并且加下划线

🌰：{name,id} {name} {id} 都是超码 {name} {id} 是候选码（最小的超码）可以选{id}作为主码（主码属性也可能有很多个）

完整性约束

数据库完整性 (Database Integrity)）：是指数据库中数据的正确性和相容性。由各种各样的完整性约束来保证，数据库完整性约束可以通过DBMS或应用程序来实现

完整性包括三种：

实体完整性约束

参照完整性约束

用户定义的完整性

实体完整性（对主码的要求） 要求关系的主码中的值不能为空值。实体完整性规则规定基本关系的所有主属性都不能取空值。

关系模型必须遵守实体完整性规则的原因：

实体完整性规则是针对基本关系而言的。一个基本表通常对应现实世界的一个实体集或多对多联系

现实世界中的实体和实体间的联系都是可区分的，即它们具有某种唯一性标识

相应地，关系模型中以主码作为唯一性标识

主码中的属性即主属性不能取空值

参照完整性（对外码的要求） 要求如果关系R1的外部码Fk与关系R2的主码Pk相对应，则R1中的每一个元组的Fk值或者等于R2中某个元组的Pk值，或者为空值。

意义：如果R1的某个元组t1参照了关系R2的某个元组t2，则t2必须存在。

用户定义的完整性 要求用户针对具体的应用环境定义的完整性约束条件。

例如：SEX要求取值为“男”或“女”；学分属性只能取值{1，2，3，4}

抽象的查询语言：

关系代数：用对关系的运算来表达查询，需要指明所用

操作关系演算：用谓词来表达查询，只需描述所需信息的特性

元组关系演算：谓词变元的基本对象是元组变量

域关系演算：谓词变元的基本对象是域变量

2.4 数据库模式图

2.6 关系代数

出关系代数的大题与sql结合

基本运算符

关系代数包括六种基本运算符：

选择，selection

从行的角度运算挑选符合条件的元组

投影，project

从列的角度运算关系是一个集合，会删除重复的行

并，union

r，s必须是同元的（属性数目相同）属性的列必须相容

集合差，set difference

笛卡尔积，Cartesian product

连串 r和s的属性如果有相交的，必须使用更名运算

更名，rename

将表E更名为x，并将属性更名为

一些运算律：

投影和并可以分配

投影和差不可以分配

例：找出Physics 系的所有教师的姓名和他们所讲授的课的课程号（ course_id ）

找出开设在2009年秋季学期或者2010年春季学期或者这二者皆开的所有的课程

附加的关系代数运算

集合交

连接

从两个关系的笛卡儿积中选取给定属性间满足一定条件的元组

A,B为R和S上度数相等且可比的属性集合为比较运算符，为等号时称为等值连接

自然连接

从两个关系的笛卡儿积中选取在相同属性列B上取值相等的元组，并去掉重复的属性。

自然连接与等值连接的不同：自然连接中相等的分量必须是相同的属性集合，并且要在结果中去掉重复的属性(两个关系中相同的属性在自然连接的结果关系模式中只出现一次)，而等值连接则不必。

当R和S无相同属性时

可以交换，可以结合

赋值

赋值运算

为使查询表达简单、清晰，可以将一个复杂的关系代数表达式分成几个部分，每一部分都赋予一个临时关系变量，该变量可被看作关系而在后面的表达式中使用。

赋值给临时关系变量只是一种结果的传递，而赋值给永久关系则意味着对数据库的修改。

外连接

外连接运算是连接运算的扩展，可以处理缺失的信息。

为避免自然连接时因失配而发生的信息丢失，可以假定在参与连接的一方关系中附加一个取值全为空值的元组，它和参与连接的另一方关系中的任何一个未匹配上的元组都能匹配，称之为外连接。

外连接 = 自然连接 + 失配的元组

Left Outer Join	左外连接	⟕	自然连接 + 左侧关系中失配的元组
Right Outer Join	右外连接	⟖	自然连接 + 右侧关系中失配的元组
Full Outer Join	全外连接	⟗	自然连接 + 两侧关系中失配的元组

空值处理

聚集函数直接忽略空值（比如在SQL里）

在去重和分组运算中，null 和其他值一样，两个null 被看作是相同的值（比如在SQL里）

使用 unknown 的三值逻辑：

(unknown or true) = true
(unknown or false) = unknown
(unknown or unknown) = unknown

(true and unknown) = unknown
(false and unknown) = false
(unknown and unknown) = unknown

(not unknown) = unknown

在SQL里，如果谓词P 的值是 unknown，则 “P is unknown” 为真

选择（select）谓词的结果如果是unknown ，则相当于 false

除运算

除运算解决的问题：关系之间的包含

象集（Image Set）:

关系R(X , Y), X, Y是属性组，x是X上的取值，定义x在R中的象集为

从R中选出在X上取值为x的元组，去掉X上的分量，只留Y上的分量

给定两个关系R和S，并且S R ，则r s是满足t x s r的最大的关系t(R-S)

广义投影

广义投影运算通过允许在投影列表中使用算数函数来对投影进行扩展。

E 是任意关系代数表达式

是涉及常量以及 E 的模式中属性的算术表达式

例：给定关系 instructor(ID, name, dept_name, salary) 其中salary 是年薪，可以得到每个教师的ID、 name、dept_name及每月的工资

聚集函数

输入值的一个汇集，将单一值作为结果返回

avg: 平均值

min: 最小值

max: 最大值

sum: 求和

count: 计数

聚集运算

在关系代数中

E 是任一关系代数表达式

是用于分组的一系列属性（可以为空）

每个是一个聚集函数

每个是一个属性名

三、SQL介绍

出大题（4~6小题）写查询语句

3.1 SQL查询语言概览

SQL：Structured Query Language，SQL包含：

数据定义语言（DDL）

数据操纵语言（DML）

数据控制语言（DCL）

事务控制

嵌入式SQL和动态SQL

3.2 数据定义语言

SQL的数据定义语言（DDL）能够定义每个关系的信息，包括：

每个关系的模式

每个属性的值域

完整性约束

以及以后我们将要看到的一些信息，比如每个关系的索引集合，每个关系的安全性和权限信息，磁盘上每个关系的物理存储结构。

SQL中的基本类型

一些SQL的基本数据类型：

类型	介绍
`char(n)`	固定长度的字符串
`varchar(n)`	可变长度的字符串
`int`	整数类型（和机器相关的整数的有限子集）
`smallint`	小整数类型（和机器相关的整数类型的子集）
`numeric(p,d)`	定点数，精度由用户指定这个数有 p 位数字，其中 d 位数字在小数点右边
`real`, `double precision`	浮点数与双精度浮点数，精度与机器相关
`float(n)`	浮点数与双精度浮点数，精度与机器相关
`date/time`	日期（年、月、日）/时间（小时、分、秒）

创建表结构

SQL建表示例：

完整性约束

常用完整性约束有：

主码约束PRIMARY KEY

参照完整性约束FOREIGN KEY (something) REFERENCES r

唯一性约束UNIQUE

非空值约束NOT NULL

索引的目的：大部分的查询只涉及数据库中的少量数据，建立索引是加快查询速度的有效手段建立索引。有关说明：

可以动态地定义索引，即可以随时建立和删除索引

不允许用户在数据操作中指定素引，素引如何使用完全由DBMS决定

应该在使用频率高的、经常用于连接的列上建索引

一个表上可建多个索引。索引可以提高查询效率，但素引过多耗费空间，且降低了插入、删除、更新的效率

索引实现（DBMS)：Bt树，散列 (hash）

删除和更改表结构

3.3 索引

索引的定义

unique（distinct）：唯一性索引，不允许表中不同的行在索引列上取相同值。若已有相同值存在，则系统给出相关信息，不建此索引。系统并拒绝违背唯一性的插入、更新

cluster：聚集索引，表中元组按索引项的值排序并物理地聚集在一起。一个基本表上只能建一个聚集索引

asc/desc：索引表中索引值的排序次序，缺省为asc（升序）

例：

索引的删除

可以动态地定义索引，即可以随时建立和删除索引

不允许用户在数据操作中引用索引。索引如何使用完全由系统决定，这支持了数据的物理独立性

应该在使用频率高的、经常用于连接的列上建索引

一个表上可建多个索引。索引可以提高查询效率，但索引过多耗费空间，且降低了插入、删除、更新的效率

3.4 SQL数据查询

SQL数据查询基本结构

SQL的数据操纵语言（DML）提供从数据库中查询信息，以及在数据库中插入元组、删除元组、修改元组的能力。

一个典型的 SQL 查询形式：

Ai 表示一个属性 Ri 表示一个关系 P 是一个谓词

SQL 查询的结果是一个关系。

select子句

select 子句用于列出查询结果中所需要的属性

与关系代数中的投影运算相对应

SQL 中的标识符大小写不敏感（即既可以使用大写字母，也可以使用小写字母）

SQL 允许在关系和查询结果中保留重复的元组

强制去重，需要在 select 之后使用关键字 distinct

关键词all显式指明不去除重复

select子句中的星号代表“所有属性”

select 子句可含有包含+、 –、 *、/运算符的算术表达式，运算对象可以是常量或元组的属性

where子句

where 子句指定查询结果必须满足的条件

与关系代数中的选择谓词相对应

比较结果可以使用逻辑连词 and，or 和 not 连接

比较符号可以用在算术表达式中

查询条件	谓词
比较运算	>，<，=，<>，>=，<=
逻辑运算	and ，or ，not
确定范围	between … and …，not between …and …
确定集合	in，not in
判定空集合	exists，not exists
字符匹配	like，not like
空值	is null，is not null

from子句

from 子句列出了查询中包含的关系

与关系代数中的笛卡儿积运算相对应

笛卡儿积不经常直接使用，它经常与where子句一起使用

3.4 附加的基本运算

连接查询及执行过程

同时涉及多个表的查询称为连接查询

用来连接两个表的条件称为连接条件或连接谓词

一般格式：

连接字段 连接谓词中的列名称为连接字段连接条件中的各连接字段类型必须是可比的，但不必是相同的

执行过程

嵌套循环法(NESTED-LOOP) 首先在表1中找到第一个元组，然后从头开始扫描表2，逐一查找满足连接件的元组，找到后就将表1中的第一个元组与该元组拼接起来，形成结果表中一个元组。表2全部查找完后，再找表1中第二个元组，然后再从头开始扫描表2，逐一查找满足连接条件的元组，找到后就将表1中的第二个元组与该元组拼接起来，形成结果表中一个元组。重复上述操作，直到表1中的全部元组都处理完毕

排序合并法(SORT-MERGE) 首先按连接属性对表1和表2排序对表1的第一个元组，从头开始扫描表2，顺序查找满足连接条件的元组，找到后就将表1中的第一个元组与该元组拼接起来，形成结果表中一个元组。当遇到表2中第一条大于表1连接字段值的元组时，对表2的查询不再继续找到表1的第二条元组，然后从刚才的中断点处继续顺序扫描表2，查找满足连接条件的元组，找到后就将表1中的第一个元组与该元组拼接起来，形成结果表中一个元组。直接遇到表2中大于表1连接字段值的元组时，对表2的查询不再继续重复上述操作，直到表1或表2中的全部元组都处理完毕为止

索引连接法(INDEX-JOIN) 对表2按连接字段建立索引对表1中的每个元组，依次根据其连接字段值查询表2的索引，从中找到满足条件的元组，找到后就将表1中的第一个元组与该元组拼接起来，形成结果表中一个元组

自然连接

只考虑两个关系模式中都出现的属性上取值相同的元组对，并且相同属性的列只保留一个副本

自然连接中的危险：注意有些属性具有相同名称，但它们实际的意义是不同的，在这种情况下，它们可能错误的被认为是相同的属性

更名运算

SQL 允许使用 as子句对关系和属性进行更名：

字符串运算

SQL中通过字符串匹配运算符来支持在字符串上的比较，使用“like”操作符来实现模式匹配，使用两个特殊字符（通配符）描述模式：

百分号 (%) %字符匹配任何子串

下划线(_) _字符匹配任何字符

Like的单向性

‘济南市山大路’ like ‘济南市%’：TRUE
‘济南市%’ like ‘济南市山大路’ ：FALSE

Escape

定义转义字符，以去掉特殊字符的特定含义，使其被作为普通字符看待

如escape '\'，定义 \ 作为转义字符，则可用\%匹配%，用\＿匹配＿

VALUE是大小写敏感的

模式匹配的例子：

SQL 支持一系列的串运算，包括：串联（使用“||”）、大小写转换、计算串长度、抽取子串等等

字符串操作

SQL正则表达式

REGEXP_LIKE(匹配)

REGEXP_INSTR (包含)

REGEXP_REPLACE(替换)

REGEXP_SUBSTR(提取)

^ 表示开始

$ 表示结束

[]内部为匹配范围

{}里的内容表时个数，有几位

查询手机号码是以 1开头接着是3或5再加9位的数字所以这么理解

1开头表达式为 ^[1]{1} 意为开始1位里包含1

3或5 表达式为 [35]{1}

9位数字结束为: [[:digit:]]{9}$ 这里[:digit:]为特殊写法，代表为数字再加个结束符$

^[[:digit:]]+$ 全是数字

排列元组的显示次序

只是显示次序排序，只能是sql的最后一个子句，只能出现目标列内的字段

当排序列含空值时

ASC：排序列为空值的元组最后显示

DESC：排序列为空值的元组最先显示

where子句谓词

表示方法：(v1,v2,…vn)

元组比较：按字典顺序进行比较

例如(a1 , a2)<=(b1 , b2)等价于(a1<b1) or ((a1=b1) and(a2<=b2))

重复

对于存在重复元组的关系，SQL 可以决定在结果中显示该元组的几个副本

一些关系代数运算的多重集版本–给定多重集关系r1和r2 ：

3.5 集合运算

集合运算 union，intersect 和except

上述每个运算都自动去重如果要保留重复，则要使用相应的多重集版本 union all， intersect all 和 except all

如果一个元组在 r 中出现 m 次，在 s 中出现 n次, 那么：

r union all s：m + n 次

r intersect all s ：min(m,n)次

r except all s ：max(0, m – n)次

3.6 空值

元组的一些属性可以为空值，用 null 表示

null 代表一个不知道或者不存在的值

包含 null 的任何算术表达式的计算结果是null

示例：5 + null 的值为 null

谓词 is null 可以用来检测空值

带有 null 的任何比较运算返回 unknown

使用 unknown 的三值逻辑：

(unknown or true) = true
(unknown or false) = unknown
(unknown or unknown) = unknown

(true and unknown) = unknown
(false and unknown) = false
(unknown and unknown) = unknown

(not unknown) = unknown

如果谓词P的值是 unknown，则 “P is unknown” 为真

where 子句中谓词对一个元组计算出的值如果为 unknown，则结果被当做 false 处理

3.7 聚集函数

聚集函数以一个值的集合（集或多重集）为输入，返回单个值

avg: 平均值

min: 最小值

max: 最大值

sum: 总和

count: 计数

Group By

使用GROUP BY子句后，SELECT子句的列名列表中只能出现分组属性和聚集函数,不能出现非聚集的非分组属性

Having

having 子句的谓词在形成分组后起作用，where 子句中的谓词在分组之前起作用

where的作用对象是元组，having的作用对象是分组

除了 count(*)，所有其他的聚集运算都忽略聚集属性上为空值的元组

3.8 嵌套子查询

一个子查询是一个嵌套在其他的查询中的select-from-where 表达式

集合成员资格 in

集合之间的比较 θ

测试集合是否为空 exists

测试集合是否存在重复元组 unique

some子句

all子句

空关系测试

exists 结构测试子查询结果是否有元组，子查询非空的时候，返回 true

EXISTS谓词：

带有EXISTS谓词的子查询不返回任何数据，只产生逻辑真值“true”或逻辑假值“false”

若内层查询结果非空，则返回真值

若内层查询结果为空，则返回假值

由EXISTS引出的子查询，其目标列表达式通常都用*，因为带EXISTS的子查询只返回真值或假值，给出列名无实际意义

相关子查询

执行过程：

首先取外层查询中表的第一个元组，根据它与内层查询相关的属性值处理内层查询，若WHERE子句返回值为真，则取此元组放入结果表然后再取外层表的下一个元组重复这一过程，直至外层表全部检查完为止。

sql中“全部”概念的处理

超集superset

not exists (X except Y)

not exists(not exists)

not in(not in)

用EXISTS表示超集

若A为B的超集，则NOT EXISTS (B EXCEPT A) 为TRUE

对于B EXCEPT A，可以表达为：在B中存在，但在A中不存在的记录也可以用NOT EXISTS 来表达

因此超集可以用两个NOT EXISTS 的嵌套来表达

也可以用两个NOT IN 的嵌套来表达

用EXISTS/NOT EXISTS实现全称量词

SQL语言中没有全称量词可以把带有全称量词的谓词转换为等价的带有存在量词的谓词

除法

测试是否有重复的元组

unique 结构测试一个子查询的结果中是否有重复的元组

在空集中其值为“true”

from子句中的子查询

Lateral 子句允许 from 子句中后面的部分（在关键词 lateral 后面的）访问前面部分的相关变量

注：lateral 是 SQL 标准的一部分，但是许多数据库系统并不支持它，一些数据库（例如 SQL Server）提供了替代它的语法

with子句

with 子句提供了定义临时关系的方法，这个定义只对包含 with 子句的查询有效

with 子句在写复杂查询时非常有用被大多数的数据库系统支持，有较小的语法变化

标量子查询

标量子查询只返回包含单个属性的单个元组

如果子查询的结果返回多个元组，则会产生运行错误

3.9 数据库的修改

删除

从表中删除符合条件的元组，如果没有where语句，则删除所有元组

插入

INTO子句

指定要插入数据的表名及属性列

属性列的顺序可与表定义中的顺序不一致

没有指定属性列：表示要插入的是一条完整的元组，且属性列属性与表定义中的顺序一致

指定部分属性列：插入的元组在其余属性列上取空值

VALUES子句

提供的值必须与INTO子句匹配

值的个数

值的类型

子查询

SELECT子句目标列必须与INTO子句匹配

值的个数

值的类型

更新

指定对哪些列进行更新，以及更新后的值是什么

使用标量子查询的更新

四、中级SQL

4.1 连接表达式

连接操作作用于两个关系并返回一个关系作为结果

一个连接操作是一个笛卡尔积，并且要求两个关系的元组满足某些匹配条件，指定在连接结果中出现的属性

Join操作通常用作from子句中的子查询表达式

例：

外连接是连接操作的扩展，避免了信息的损失

计算join，然后将一个关系中与另一个不匹配的元组添加到结果中

使用null 值

左外连接

右外连接

全外连接

连接关系

连接操作将两个关系作为输入，并返回一个关系作为结果

这些额外的操作通常用作from子句中的子查询表达式

连接条件 – 规定了这两个关系中的哪些元组匹配，以及在连接结果中出现什么属性

连接类型 – 规定了对每个关系中（基于连接条件）不与其他关系中的元组相匹配的元组怎样处理

外连接

在表名后面加外连接操作符(*)或(+)指定非主体表

非主体表有一“万能”的虚行，该行全部由空值组成

虚行可以和主体表中所有不满足连接条件的元组进行连接

由于虚行各列全部是空值，因此与虚行连接的结果中，来自非主体表的属性值全部是空值

4.2 视图

在某些情况下，让所有的用户看到整个逻辑模式（即所有实际存储在数据库中的关系）是不可取的

考虑一个职员需要知道教师的标识、姓名和所在系名，但是没有权限看到教师的工资值此人应该看到的关系由如下SQL语句所描述

视图提供一个对某些用户从视图中隐藏某些数据的机制

任何不是逻辑模式的一部分，但作为虚关系对用户可见的关系称为视图

视图定义

定义视图时并不是由查询表达式的执行结果创造一个新关系

相反，一个视图的定义导致存储一个查询表达式，当该视图被使用时，它就被这个已存储的查询表达式替换

视图特点：

虚表，是从一个或几个基本表（或视图）导出的关系

只存放视图的定义，不会出现数据冗余

基表中的数据发生变化，从视图中查询出的数据也随之改变

查询时,视图名可以出现在任何关系名可以出现的地方

视图(view) vs 表(table)

视图和表都是关系，都可在SQL中直接应用

DB中存储表的模式定义和数据

DB中只存储视图的定义，不存视图的数据

视图数据在使用视图时临时计算

物化视图是提高计算的一种手段，结果等价于临时计算

视图的属性名缺省为子查询结果中的属性名，也可以显式指明，在下列情况下，必须指明视图的所有列名

某个目标列是聚集函数或者列表达式

多表连接时，选出了几个同名列作为视图的字段

需要在视图中为某个列启用新的更合适的名字

目标列是*

一个视图可以用于定义另一个视图的表达式中

如果一个视图关系 v2 用于定义另一个视图关系v1 的表达式中，则称v1 直接依赖于v2

如果一个视图关系v1 直接依赖于另一个视图关系v2，或通过其他视图间接依赖于v2，则称v1 依赖于v2

视图的操作

从单个基本表导出

只是去掉了基本表的某些行和某些列

保留了码，行列子集视图

有些更新不能被单独执行

大部分的SQL实现只允许在简单视图上的更新

from子句中只有一个数据库关系

select子句中只包含关系的属性名，不包含任何表达式、聚集或distinct声明

任何没有出现在select子句中的属性可以取空值

查询中不含有group by或having子句

对于行列子集视图可以更新

视图with check option

视图定义时，指定with check option

要求：通过视图进行的修改，结果必须在视图中

无with check option

可以更新，更新后元组不再出现在视图中

有with check option

不可以更新，update语句将被DBMS拒绝

物化视图

物化视图: 创建一个物理表，此表包含定义视图的查询结果的所有元组

如果查询中使用的关系发生了更新，则物化视图中的结果就会过期

每当视图的底层关系进行更新时要更新视图，以此来维护视图

使用物化视图的目的是为了提高查询性能，是以空间换时间的一种有效手段，更少的物理读/写，更少的cpu时间，更快的响应速度

物化视图对应用透明

物化视图需要占用存储空间

当基表发生变化时，物化视图也应当刷新

规模较大的报表适合使用物化视图来提高查询性能

4.3 事务

工作单元

事务的原子性：要么全部执行，要么回滚

从并发事务中隔离

隐式地开始一个事务：以 commit work 或 rollback work 结束

多数数据库的默认情况：每个SQL语句自动提交

可以关闭自动提交（示例：使用API）

4.4 完整性约束

完整性约束通过保证对数据库的修改不会造成数据的不一致，来防止对数据库数据的意外破坏

not null

指定的属性上，不允许出现空值

限制:任何试图导致某个/某些元组非空属性为空的操作都将被拒绝

primary key（主码）默认为not null

Unique

定义：unique(A1,A2,…)

约束：不允许关系中，有两个元组，在指定的属性组上取值相同

unique本身不限定属性非空

例：若unique（sno, sname, score)

(s1, Lily, 98) (s2, Sam, 98) 是可以的，因为这两个元组在这个属性组上是不同的

Default

默认值：为属性指定默认值

check子句

P是一个谓词

定义：check P

约束：关系上的每一个元组，都必须满足P

check可以针对一个属性

check可以涉及多个属性

check可以涉及其它表，但需考虑约束检查代价

如果S中删除元组，不会触发CHECK子句，只有对SC表的更新才会触发

primary key 主码约束

主码值不允许空，也不允许出现重复

意义：关系对应到现实世界中的实体集，元组对应到实体，实体是相互可区分的，通过主码来唯一标识，若主码为空，则出现不可标识的实体，这是不容许的

主码定义形式

主码子句：PRIMARY KEY(S#)

主码短语：S# CHAR(4) PRIMARY KEY

foreign key 参照完整性

保证在一个关系中给定属性集上的取值也在另一关系的特定属性集的取值中出现

➢ 示例：如果“Biology”是在instructor 关系的元组中出现的一个系的名字，则在department 关系中存在一个包含“Biology”属性的元组

A是一个属性的集合，R和S是两个包含属性A关系，并且A是S的主码如果对于每个在R中出现的A在S中也出现，则A被称为R的外码

外码可以为空（null）

参照完整性中的级联行为

删除基本关系元组

RESTRICT方式只有当依赖关系中没有一个外码值与要删除的基本关系的主码值相对应时，才可以删除该元组，否则系统拒绝此删除操作

CASCADE方式将依赖关系中所有外码值与基本关系中要删除的主码值所对应的元组一起删除（元组A删除，若元组B的外码是A，则B也被删除）

SET NULL方式删除基本关系中元组时，将依赖关系中与基本关系中被删主码值相对应的外码值置为空值

如FOREIGN KEY (S#) REFERENCES S(S#) [ON DELETE [CASCADE | SET NULL] ]

修改基本关系主码

RESTRICT方式只有当依赖关系中没有一个外码值与要修改的基本关系的主码值相对应时，才可以修改该元组主码，否则系统拒绝此次修改

CASCADE方式将依赖关系中所有与基本关系中要修改的主码值所对应的外码值一起修改为新值

SET NULL方式：修改基本关系中元组主码时，将依赖关系中与基本关系中被修改主码值相对应的外码值置为空值

如FOREIGN KEY (S#) REFERENCES S(S#) [ON UPDATE [CASCADE | SET NULL] ]

复杂check子句

为什么这里不用外码？

time_slot_id不是time_slot的主码

每个section都需要有至少一位教师来讲授，这个怎么写？

但是几乎任何方式都不支持check子句中的子查询（使用触发器）

断言

create assertion <assertion-name> check <predicate>;

4.5 SQL的数据类型与模式

SQL固有的数据类型

date:日期，包括年（四位）、月和日

示例：date ‘2005-7-27’

time: 时间，包括小时, 分和秒

示例：time ‘09:00:30’ time ‘09:00:30.75’

timestamp : date 和 time 的组合

示例：timestamp ‘2005-7-27 09:00:30.75’

interval:时

示例：interval ‘1’ day

两个 date/time/timestamp 类型值相减产生一个interval 类型值

可以在 date/time/timestamp 类型的值上加减interval 类型的值

用户定义的类型

SQL中的create type 结构创建用户定义的类型

域

SQL-92 中的create domain 结构创建用户定义的域类型

类型和域相似，但是域本身可以指定约束，如not null

自定义域不支持结构

Type vs Domain

Type：进行强类型检查；

Domain不进行进行强类型检查，支持强制类型转换

Type有严格的OO（面向对象）理论基础，Domain是纯RDB（关系数据库）的概念

大对象类型

大对象（照片，视频，CAD文件等）以large object 类型存储：

blob：二进制数据的大对象数据类型--对象是没有被解释的二进制数据的大集合（对二进制数据的解释由数据库系统以外的应用程序完成）

clob：字符数据的大对象数据类型--对象是字符数据的大集合

当查询结果是一个大对象时，返回的是指向这个大对象的指针，而不是大对象本身

生成唯一码值

DBMS提供了生成唯一码值的管理

该功能仅适用于number型的数据类型

Create table的扩展

模式、目录、环境

一个DBMS可以管理多个catalog目录(instance)

一个instance可以含多个schema模式(userschema)

一个schema可以含多个关系(table/view)

4.6 授权

权限的转授和回收

允许用户把已获得的权限转授给其他用户，也可以把已授给其他用户的权限再回收上来

权限图

结点是用户，根结点是DBA，有向边→，表示用户Ui把某权限授给用户Uj

一个用户拥有权限的充分必要条件是在权限图中有一条从根结点到该用户结点的路径

在数据库的某些部分的几种授权的形式：

Select - 允许读取，但是不能修改数据

Insert - 允许插入新数据，但是不能修改已有数据

Update - 允许修改，但是不能删除数据

Delete - 允许删除数据

修改数据库模式的几种授权的形式：

Index - 允许创建和删除索引

Resources - 允许创建新关系

Alteration - 允许增加或删除关系的属性

Drop - 允许删除关系

SQL中的授权规范

grant 语句用于授予权限

对于某个视图授权后，并没有对该视图所基于的关系授权

一个创建视图的用户不能得到视图上的更新权限，如果该用户在用来定义视图的关系上没有更新权限的话。

权限的授予者必须已经持有相应的权限（或者是数据库管理员）

用户和角色

用户和角色的关系

连接使用数据库，必须以一个特定的用户身份

不能使用role身份直接连接使用数据库

一个用户可同时具备多个角色

一个角色可以为多个用户拥有

角色可以拥有角色

角色拥有关系可以传递

权限可以授予用户或者角色

用户拥有授给本用户的所有权利，以及本用户具有的角色的所有权利

每个用户对自己模式下的对象(表,视图…)拥有属主权(owner)

用户及角色的管理

用户管理

创建用户：create user username identified by password;

删除用户：drop user username;

角色管理

创建角色：create role rolename;

删除角色：drop role rolename;

用户和角色关系的管理

赋予用户角色：grant role1 to u1;

此时u1将继承role1的所有权限

撤销用户角色：revoke role1 to u1;

SQL中的权限

select（可指定列名）

insert

update（可指定列名）

delete

all privileges 所有允许权限的简写形式

SQL中的收回授权

如果同一权限由不同的授权人两次授予同一用户，用户在一次权限被回收后，仍保持有权限

收回权限时，若该用户已将权限授予其它用户，则也一并收回

模式的授权

引用(references)权限允许用户在创建关系时声明外码。

权限的转移

缺省方式下，被授予权限的用户/角色无权把得到的权限在授予另外的用户/角色，如果希望授权时允许接收者把权限再传递给其他用户，需要使用with great option

行级授权

//考前按需补充

五、高级SQL

5.1 使用程序设计语言访问数据库

动态SQL

动态SQL允许运行时以字符串的形式构建SQL，提交查询

嵌入式SQL

嵌入式SQL必须在编译时全部确定，并交给预处理器

JDBC (Java Database Connectivity)

考过写代码

JDBC 是一个支持SQL 的Java API，用于与数据库系统通信

JDBC 也支持元数据检索，例如查询当前数据库中的关系、关系属性的名字和类型

立即执行与预备语句执行

立即执行：

使用Statement类，将sql语句直接交给DBMS执行

一次语句执行DBMS进行一次语句编译

使用预备语句执行：

使用PreparedStatement类，sql语句执行，首先进行编译，编译结果赋予PreparedStatement的对象

预编译的结果可被反复多次执行

同嵌入sql预编译不同(在编译程序时进行)，JDBC的预编译是在程序运行中进行的；

一个sql多次执行：

使用预备语句，仅编译一次

立即执行模式下，需多次编译

在一sql多次执行时，使用预备语句比立即执行的速度快

预备语句

将一个来自用户的输入添加到查询时，使用预备语句比较好

对于查询，使用pStmt.executeQuery()，返回一个结果集(ResultSet)

SQL注入

当有用户的输入做参数时，最好使用预备语句

元数据特性

要考滴

ResultSet元数据（描述数据的数据）

查询结果集元数据

描述查询结果集的属性类型(结果集的模式)

对编程时不能确定结果集模式时非常有用

Sno	Sname	Sage
S1	甲	20
S3	丙	21

Result: rset

Column number	Column Name	Column Type
1	sno	char
2	sname	varchar
3	sage	int

ResultSetMetaData: rsmd

数据库元数据

DataBaseMetaData

对DB数据字典进行封装

类方法可以读取数据字典元数据

屏蔽了数据字典的具体实现模式

对应用提供访问DB数据字典元数据的标准方法

Sno	Sname	Dept	Sage
S1	甲	计	20
S2	乙	软	21
S3	丙	软	20

COLUMN _NAME	COLUMN _TYPE
sno	char
sname	varchar
dept	varchar
sage	int

rset

JDBC中的事务管理

在默认情况下，每个SQL语句都被作为一个被自动提交的独立的事务（对于有多个更新的事务，这种做法并不好）

可以将自动提交关闭 conn.setAutoCommit(false);

事务必须被显式的提交conn.commit(); 或回滚 conn.rollback();

conn.setAutoCommit(true) 打开自动提交

其它特性

JDBC调用函数和过程

JDBC处理大型对象类型

ODBC (Open Database Connectivity)

应用程序与数据库服务器通信的标准

应用程序接口 API (application-program interface) 用于程序和数据库服务器之间的交互

与数据库建立一个连接，

发送查询和更新数据库的语句

//此处省略很多东西…ODBC的使用…代码、预备语句

嵌入式SQL

SQL 查询所嵌入的语言被称为宿主语言（host language），宿主语言中使用的SQL结构被称为嵌入式SQL

确切语法因循宿主语言的惯例

预编译工作模式介绍：预编译将嵌入宿主语言的sql，编译成宿主语言的一段代码，执行这段代码，将完成相应sql调用执行

在嵌入式SQL语句中可以使用宿主语言的变量（在前面加上 : 以与sql变量区分）

如果要遍历一个嵌入式SQL查询的结果，必须声明一个游标变量。

游标 cursor

在查询结果的记录集合中移动的指针 若一个SQL语句返回单个元组，则不用游标 若一个SQL语句返回多个元组，则使用游标

// 此处省略很多内容

5.2 函数和过程化结构

函数

表函数

过程

in表示待复制的参数，out表示为了返回结果而在过程中设置值的参数

允许使用多个同名过程/函数（称为名字重载），只要参数的个数不同，或对于那些有相同参数个数的函数，至少有一个参数的类型不同

过程化结构

5.3 触发器

触发器是一条语句，当对数据库做修改时，它自动被系统执行

要设置触发器机制，必须要：

指明什么条件下执行触发器

指明触发器执行时的动作

触发事件可以是insert，delete 或update

触发器可以指定那个属性的更新使其执行，而其他属性的更新不会让它产生动作

示例：after update of takes on grade

一个更新之前和之后的属性值可以被引用

referencing old row as: 用于删除和更新

referencing new row as: 用于插入和更新

触发器可以在一个事件（额外的约束）之前被激活，示例如下：

5.4 递归查询

parent	child
a	b
a	c
b	d
b	e
d	g
c	f

parent	child
a	b
b	d
d	g
b	e
a	c
c	f

结果集

5.5 高级聚集特性

排名

排名是用order by语句来实现的

假设关系student_grades(ID, GPA) 给出了每个学生的平均绩点

求出每个学生的名次

需要使用一个附加的order by 子句得到排序的元组

在排名中可能会产生隔断：

示例：如果两个学生具有相同的最高GPA，则两人都得到第1名，下一个给出的名次将是3而不是2

dense_rank() 函数则不会产生隔断，所以在上面的例子中，具有次高成绩的元组都得到第2名

如果正在排序的值中存在空值，则将它们视为最高值。可以使用nulls first （空值最先）或nulls last（空值最后）

例如：

对于一个给定的常数n，排名函数ntile(n)按照给定的顺序取得每个分区中的元组，并把它们分成n个具有相同元组数目的桶

示例：

分窗

窗口查询用来对于一定范围内的元组计算聚集函数。比如计算一个固定时间区间的聚集值，这个时间区间被称作一个窗口（window）

用于消除随机变化的影响

六、数据库设计和ER模型

6.1 概述

E-R图的作用：

帮助澄清用户数据需求，分析员和用户对数据需求达到高度一致

数据逻辑模型设计的标准

6.2 ER模型

一个数据库可以建模为：一组实体集，多个实体间的相互关联。

实体集：是具有相同类型及共享相同性质（属性）的实体集合，如全体学生。一个实体集是相同类型，即具有相同性质（或属性）的实体集合。组成实体集的各实体称为实体集的外延（Extension）

实体：客观存在并可相互区分的事物叫实体（唯一标识）。实体是现实世界中可区别于所有其他对象的一个“事物”或“对象”。相关的概念有：

属性：实体集中每个成员具有的描述性性质。一个实体通过一组属性来表示。

属性还可以分为简单属性（不可再分的属性）和复合属性（可以进一步划分的属性，例如外国人姓名First Name和Second Name）。属性的类型包括单值属性（每一个特定的实体在该属性上的取值唯一）、多值属性（每一个特定的实体在该属性上的有多于一个的取值，例如某个实体的联系方式可以有多个）、派生属性（可以从其他相关的属性或实体派生出来的属性值，例：通过生日→age）与基属性。数据库中，一般只存基属性值，而派生属性只存其定义或依赖关系，用到时再从基属性中计算出来。但是不排除基属性和派生属性均保存在数据库中的现象

域：属性的取值范围。

实体集的属性是将实体集映射到域的函数。

联系集

联系集：是相同类型联系的集合，n≥2个实体集上的数学联系。

联系也可以具有描述性属性。

advisor是instructor和student之间的联系集，属性date与该联系关联

联系集的度是指联系集涉及的实体集数量，数据库系统中大部分联系集都是二元联系集（度为2）。

联系集的码：参与联系的实体集的主码的集合形成了联系集的超码。例如(sno, cno) 构成了联系sc的超码。关系集的主码依赖于关系集映射的基数。

6.3 约束

映射基数

表示一个实体通过一个联系集能关联到的实体的个数，在描述二元联系集时非常有用。

对于二元联系集来说，映射基数必然是一下情况之一：

一对一

一对多

多对一

多对多

参与 Participation

参与：实体集之间的关联称为参与，即实体参与联系。

如王军选修“数据库基础”，表示实体“王军”与 “数据库基础”参与了联系“选修”

码

码有许多种：

实体集的超码是一个或多个属性的集合，这些属性的值可以使我们唯一地标识一个实体.

实体集的候选码是一个最小超码

主码：所有候选码中选定一个用来区别同一实体集中的不同实体。

一个实体集中任两个实体在主码上的取值不能相同，实体集属性中作为主码的属性用下划线来标明。

联系集的码

参与实体集合的主键组合形成联系集的超码。例：advisor的超码是(s_id, i_id)

决定候选码的时候必须考虑联系集的映射基数

在选择主键的时候要考虑联系集的语义信息以防有多个候选码

6.4 实体——联系图

考大题画图（给一个实际场景）关系模式 ↔ E-R图

分成两部分的矩形代表实体集

菱形代表联系集

属性在实体集矩形中列出

构成主码的属性以下划线标明

角色

角色(Role)：实体在联系中的作用称为实体的角色，由于参与一个联系的实体集通常是互异的，角色是隐含的一般不需要指定。当同一个实体集不止一次参与一个联系集时，为区别各实体的参与联系的方式，需要显式

全部参与

如果实体集E中的每个实体都参与到联系集R中的至少一个联系，则称E全部参与R；如果实体集E中只有部分实体参与到联系集R的联系中，则称E部分参与R

一对实体在特定联系集中至多有一个关系。因此决定候选码时必须考虑联系集的映射基数，在选择主键的时候必须考虑联系集的寓语义信息以防有多个候选码。

基数约束

在联系集和实体集之间画一个箭头 (→) 或一条线段(—)来表示基数约束。

箭头表示一，线段表示多

基数限制的可选标记

每位学生必须有且只有一名导师，一位教师可以有零或多名学生
（1..1可以换成双线，0..*可以换成线段）
注意！！我们采用与此相反的写法！！！
若按照我们的方法，这个的意思是一个教师必须有且只有一名学生，一个学生可以有多个老师！ — ~~每位学生必须有且只有一名导师，一位教师可以有零或多名学生~~ （1..1可以换成双线，0..*可以换成线段）注意！！我们采用与此相反的写法！！！若按照我们的方法，这个的意思是一个教师必须有且只有一名学生，一个学生可以有多个老师！

0..*等价于“多” （下界是0，上界是无穷）

示例：一个学生要学3到5门课，一门课至少要有20名学生学习

弱实体集

没有足够的属性以形成主码的实体集称作弱实体集

弱实体集存在依赖于 标识实体集

标识性联系是从弱实体集到标识实体集多对一的，并且弱实体集在联系中的参与是全部的

标识性联系 以双菱形表示（弱实体集也有双线—>双矩形）

弱实体集的分辨符可以区分依赖于特定强实体集的弱实体集中的实体的属性的集合

使用标识性实体集的主码以及称为分辨符属性的额外属性来唯一的标识弱实体，而不是将主码与弱实体相关联。

弱实体集的主码是由标识实体集的主码加上该弱实体集的分辨符构成

section是弱实体集，在sec_course联系中的参与是全部的（每个课程段sec必须通过sec_course与某门课程相关联）

弱实体集的分辨符以虚下划线标明，而不是实线

关联弱实体集和标识性强实体集的联系集以双菱形表示

Section的主键 – (course_id, sec_id, semester, year)

ER绘制

参考资料：

https://wenku.baidu.com/view/9b4cc3aadd3383c4bb4cd237.html?_wkts_=1687417935762

6.6 转换为关系模式

根据E-R模型建立数据库模式：E-R图转换为表并进行必要的合并+优化

6.6 转换为关系模式

6.7 扩展E-R特性

特化

自顶而下设计过程; 实体集可能包含一些子集，子集中的实体在某些方面区别于实体集中的其他实体；

这些子集变为低层次的实体集，拥有不适用于高层次实体集的属性或一些部分参与的关系。

在E-R图中，特化用从特化实体指向另一个实体的空心箭头来表示，我们称这种关系为ISA关系 (E.g., instructor “is a” person)。

属性继承：高层实体集的属性可以被低层实体集继承。低层实体集（或子类）同时还继承地参与其高层实体（或超类）所参与的实体集

概括/泛化

自底而上的设计过程– 多个实体集根据共同的特征综合成一个较高层的实体集。

概化只不过是特化的逆过程; 在E-R图中，我们对概化和特化的表示不作区分。

实体可以是给定低层次实体集成员的约束。

另一类约束涉及在一个概化中一个实体集是否可以属于多个低层实体集：

不相交(Disjoint)概化：不相交约束要求一个实体至多属于一个低层实体集

重叠(Overlapping)概化：同一个实体可以同时属于同一个概化中的多个低层实体集（例，一个人可以是学生也可以是老师）

完全性约束：定义高层实体集中的一个实体是否必须至少属于该概化/特化的一个低层实体集：

全部概化: 每个高层实体必须属于一个低层实体集。

部分概化: 允许一些高层实体不属于任何低层实体集。

聚集

通过聚集来减少冗余：

将关系作为抽象实体

允许关系间存在关系

将关系抽象用于新实体

为了表示聚集，需要包含以下信息：

聚集关系的主键

相关实体集的外键

任何描述属性

七、关系数据库设计

大题

7.1 好的关系设计的特点

更大的模式会导致信息重复：信息冗余大、数据不一致等，因此我们会选择更小的模式。

7.2 原子域和第一范式

原子域：域元素被认为是不可分的单元，称域是原子的。

称一个关系模式R属于第一范式，如果R的所有属性的域都是原子的

非原子值使得存储变复杂并且导致数据存贮的冗余

7.3 使用函数依赖进行分解

函数依赖

函数依赖：在合法关系集合上的约束，要求一个特定的属性集合的值唯一决定另一个属性集合的值。一个函数依赖是一个码标识的概化。

函数依赖可以帮助我们确定哪些属性是冗余的，哪些属性是必要的，从而设计出更加高效和优化的数据库结构。

函数依赖使我们能够表示不能用超码表示的约束

函数依赖的使用

利用函数依赖

判定关系的实例是否满足给定函数依赖集F：如果一个关系实例r在函数依赖集F下是合法的，那么r满足 F

说明合法关系集上的约束：如果R上的所有合法关系都满足函数依赖集F，那么F在R上成立

即使一个函数依赖在所有实例上不成立，它可能在某个特定的关系实例上成立

部分函数依赖完全函数依赖

传递函数依赖

平凡的函数依赖

有些函数依赖称为平凡的，因为他们在所有关系中都满足

当是平凡的函数依赖

否则称为非平凡的函数依赖

Boyce-Codd 范式 BCNF

分解一个模式成为BCNF

第三范式 3NF

任何满足BCNF的模式也满足3NF (因为它的每个函数依赖都将满足前两个条件中的一条)

BCNF是3NF的真子集，证明如下：

在某种意义上，3NF的第三个条件代表BCNF条件的最小放宽，以确保每一个模式都有保持依赖的3NF分解

R1 R2 R5 不是BCNF 但R1, R2不是3NF，R5是3NF（cno-tno=cno包含在候选码(sno,cno)中，(sno,cno)是一个超码）

R3 R4 是BCNF，一定是3NF

7.4 函数依赖理论

函数依赖集的闭包

能够从给定F集合推导出的所有函数依赖的集合称为F的闭包

使用符号来表示F集合的闭包，是F的一个超集

计算的算法一定是NP

Armstrong公理系统

Armstrong公理系统是一种用于推导函数依赖的集合的公理系统。它由计算机科学家William W. Armstrong于1974年提出，是现代数据库理论中最重要的基础之一。

Armstrong公理系统包括三个基本公理：

自反律（Reflexivity）：如果，那么X → Y是一个成立的函数依赖。

增广律（Augmentation）：如果X → Y成立，那么对于任何属性集合Z，都有XZ → YZ成立。

传递律（Transitivity）：如果X → Y成立，Y → Z成立，那么X → Z也成立。

推理规则

计算

属性集的闭包

对于属性集α，我们将函数依赖集F下被α函数确定的所有属性的集合称为F下α的闭包，记作

属性集的闭包计算（函数依赖的超码和候选码）

属性集闭包的使用

正则覆盖

函数依赖集可能拥有可从其他推导出来的冗余的依赖

例如: 在{A → B, B → C, A → C}中，A → C 是冗余的

……

F的正则覆盖是一个与F相等的最小的函数依赖集，没有冗余的依赖，也没有无关属性。

无关属性：如果去除一个函数依赖中的属性，不会改变该函数依赖集的闭包，则称该属性是无关的(extraneous)

无关属性的核心：能够被函数依赖集F逻辑蕴涵的函数依赖，不必出现在F中。

满足下列条件的函数依赖集F称为正则覆盖，记作Fc：

Fc 与 F 等价（F逻辑蕴涵Fc中的所有依赖； Fc 逻辑蕴涵 F 中的所有依赖）

Fc 中任何函数依赖都不含无关属性

Fc 中函数依赖的左半部都是唯一的

F的正则覆盖作用：

假设在一个关系模式上有一个函数依赖集F。当用户对于关系进行更新时，数据库系统将保证此操作不会破坏任何一个函数依赖

可以通过测试与给定函数依赖集有相同闭包的简化集的方式，来降低检测的开销

正则覆盖未必唯一。

计算正则覆盖

🔔不能同时讨论F中的两个属性的无关性，一次只能讨论一个属性

正则覆盖未必唯一，例子如下：

考试会考计算简单的正则覆盖（一种结果即可）

无损分解

以上的函数依赖是无损分解的充分条件；这些依赖是必要条件当且仅当所有约束都是函数依赖

保持依赖

保持依赖性的验证：

数据库系统概论—判断分解是否保持函数依赖

来源：学者网-程俊伟

https://www.scholat.com/vpost.html?pid=143851

7.5 分解算法

BCNF验证

简单验证：检查关系模式R是否属于BCNF，仅需检查给定集合F中的函数依赖是否违反BCNF就足够了，不用检查中的所有函数依赖

如果F中没有函数依赖违反BCNF，那么中也不会有函数依赖违反BCNF

当判定R上的一个分解是否违反BCNF时，只用F就不够了

子模式BCNF的判定

BCNF分解算法

BCNF分解并不是总能保持依赖

算法分析：

算法一定可以结束，复杂性为NP，分解算法无损

3NF 第三范式

会考3NF的验证（给实例）

允许一些冗余

单个关系的函数依赖可以在不做连接操作的情况下被验证

一定有无损，保持依赖的分解到3NF

3NF验证

优化: 只需要验证F中的FDs , 不需要验证 F+中的FDs

如果α是一个超码，利用属性闭包来验证每个依赖α→β

如果α不是一个超码，必须验证β中每一个属性是否包含在R的候选码里面

这个验证的代价太大，因为它包含寻找候选码 3NF验证是NP-hard问题 3NF分解可以在多项式时间内完成

3NF分解算法

学会计算，考试会考

7.6 多值依赖 MVDs

多值依赖的使用

检验关系以确定他们在给定的函数依赖集和多值依赖集下是否合法

在合法关系集上指定约束因此我们只考虑满足给定函数依赖集和多值依赖集的关系

如果关系r不满足多值依赖，可以通过向r中增加元组构造一个确实满足多值依赖的关系r‘

MVDs理论

由多值依赖的定义，可以得出以下规则，对于

若α → β, 则 α →→ β

即每一个函数依赖也是一个多值依赖

D的闭包是由D逻辑蕴涵的所有函数依赖和多值依赖的集合

Armstrong公理

多值依赖 Vs 函数依赖

区别

函数依赖规定某些元组不能出现在关系中，也称为相等产生依赖

多值依赖要求某种形式的其它元组必须在关系中，称为元组产生依赖

有效性范围

X→Y的有效性仅取决于X、Y属性集上的值

X→→Y的有效性与属性集范围有关

第四范式 4NF

满足BCNF且不存在多值依赖

函数依赖和多值依赖集为D的关系模式R属于4NF的条件是，对D + 中所有形如 α →→ β 的多值依赖(其中且),至少有以下之一成立

α →→ β是一个平凡的多值依赖（ or ）

α 是R的一个超码

若是4NF则一定是BCNF

4NF分解

无损分解

范式 sduonline

十二、物理存储系统

不考

物理存储系统

十三、数据存储结构

不考

数据存储结构

十四、索引

关系、视图、索引的区别？

14.1 索引基本概念

索引机制用于加快访问所需数据的速度。搜索码是用于在文件中查找记录的属性或属性集。索引文件由搜索码和指针组成。两种基本的索引类型：

顺序索引：基于搜索码值的顺序排序

散列索引：将值平均分布在若干散列桶中，一个值所属的散列桶是由一个函数决定，该函数称为散列函数

索引的评价指标包括：

能有效支持的访问类型

具有特定属性值的记录
或者属性值落在某个特定范围内的记录

访问时间

插入时间

删除时间

空间开销

14.2 顺序索引

在一个顺序索引中，索引项按照搜索码值的排序顺序存储。例如，图书馆作者目录。

索引顺序文件：在搜索码上有聚集索引的⽂件。

主索引：包含记录的文件按照某个搜索码指定的顺序排序，那么该搜索码对应的索引称为主索引。（也被称为聚集索引）

索引根据密度又可以分为：稠密索引、稀疏索引

稠密索引

文件中的每个搜索码值都有一个索引项

稀疏索引

只为搜索码的某些值建立索引项，只有索引是聚集索引时才能使用稀疏索引。

此时要找到搜索码值为K的索引，需要找到搜索码值小于K的最大索引项，并从该记录开始逐个向后查找。因此，其所占空间较小，插入和删除时所需的维护开销也比较小，但定位时的速度更慢。
为文件中的每个块建立一个索引项的稀疏索引是一个很好的折中。

多级索引

如果主索引太大而不能放在内存中，访问效率将变低。解决方案就是把主索引当做一个连续的文件保留在磁盘上，创建一个它之上的稀疏索引。

外层索引：主索引上的稀疏索引内层索引：主索引文件

如果外层索引还是太大而无法放在内存中，可以再次创建一个次级索引，以此类推

对文件进行插入或删除操作时，各级索引必须全部更新

辅助索引

又称非聚集索引，搜索码指定的顺序与文件中记录的物理顺序不同的索引。

索引记录指向一个包含所有具有特定搜索码值的实际记录的指针的桶

辅助索引必须是稠密索引

想要找到属性值在某个满足一定条件的域(不是主索引的搜索码域）内的所有记录

例 1：在按 ID 顺序存储的 instructor 关系上 , 找到所有在一个具体部门工作的教师例 2：找到薪水是某个具体值或具体范围的所有老师

可以使用一个对每个搜索码值都具有索引项的辅助索引

主索引

又称聚集索引，包含记录的文件按照某个搜索码指定的顺序排序，那么该搜索码对应的索引称为主索引。通常使用主码作为主索引。

主索引和辅助索引

索引为记录检索提供了巨大的便利。

但是索引更新的开销被强加于数据库更新之上-当一个文件被修改时，此文件上的每一个索引都必须被更新

按主索引顺序对文件进行顺序扫描是非常有效地，但是使用辅助索引进行顺序扫描是很费时的（每读⼀条记录都可能从磁盘读取⼀个新的块）。

读取块比内存访问相比，花费时间多的多

索引更新

删除

如果被删除的记录是具有某个搜索码值的唯一记录, 那么这个搜索码值同时也被删除

单级索引项删除

稠密索引搜索码的删除与文件记录的删除类似

稀疏索引

对于对应某个搜索码值的索引项,它被删除是通过用下一个搜索码值替换该索引项来完成的
如果下一个搜索码值已经有一个索引项，此索引项被直接删除

插入

单级索引插入:

用被插入记录的搜索码值进行一次检索

稠密索引 – 如果搜索码值没有出现在索引中，将其插

稀疏索引 – 如果索引对文件中的每个块只存储一个索引项，除非创建了一个新的块，否则不对索引做任何改变如果创建了一个新的块，出现在新块中的第一个搜索码值被插入到索引项中

多级索引的插入和删除: 算法是单级算法的简单扩展

14.3 B+树索引文件

B+树索引

顺序索引的特例

对索引顺序文件来讲，随着文件的增大索引查找性能和数据顺序扫描性能都会下降，这是由于许多溢出块会被创建，频繁重组整个文件是必须的。

使用B+树索引文件，可以在数据插入和删除时通过小的自动调整来保持平衡，无需重组文件。（优点）

缺点：增加文件插入和删除的时间开销，同时会增加空间开销

// 此处省略很多很多 B+树的插入、删除…… 多半不考数据结构里的东西，但可能会让计算代价

B+树的一层非叶结点形成一级稀疏索引

B+树文件组织

通过使用B+树索引可以解决索引文件退化问题。

通过使用B+树文件组织可以解决数据文件退化问题。

用B+树文件组织的叶结点存储记录，而不是使用指针

给例子让判断啥啥啥合并？？

14.4 散列索引

散列

桶表示能能存储一条或多条记录的一个存储单位，通常一个桶就是一个磁盘块

在散列文件组织中可以直接从搜索码使用散列函数得到包含记录的桶

散列函数 h 是一个从所有搜索码值的集合 K 映射到桶地址的集合 B 的函数

散列函数用来定位要访问，插入或删除的记录

带有不同搜索码值的记录可以映射到同一个桶中，因此，为了找到一个记录，桶要被依次检索

// 此处省略散列函数（学过）

桶溢出处理

静态散列的不足

静态散列技术要求固定桶地址集合 B ，但是大多数数据库都会随时间而变大，这会带来很严重的问题

如果初始桶的数目太小，随着文件的增长，由于产生太多溢出，导致性能下降

如果预期增长的空间提前被分配，大量空间将被浪费

如果数据库收缩，空间将会被再次浪费

一种解决方案：周期性的对散列结构进行重组（规模大，耗时，扰乱正常操作）

更好的解决方案: 允许桶的数量被动态的修改

// 省略动态散列（只要知道动态散列这个东西就好）

// 顺序索引和散列的比较

14.5 多码访问

多码检索应使用多个索引或使用建立在多属性索引码上的索引

// 覆盖索引

14.6 索引的创建

创建索引

使用 create unique index 来间接并且强制性地指定搜索码是一个候选码

如果数据库系统支持 SQL 标准的 unique 声明，那么这里的 unique 特性就是多余的

删除索引

14.7 写优化索引结构

日志结构合并树Log-structured merge (LSM) tree

缓冲树Buffer tree

B+树的每个内部节点都有一个缓冲区来存储插入信息

14.8 位图索引

位图索引是一种特殊类型的索引，设计用于高效查询多个keys

位图索引主要针对列中大量相同值的列（如“性别”）

位图索引的作用

检索符合条件的元组

统计符合条件的元组个数

位图是一个位(bit)数组，或者一个向量，数组/向量的长度与记录的条数相对应

收入为L1的男性员工：10010 AND 10100 = 10000 所以0号

14.9 时空数据索引

k-d tree 多维索引

每一层把空间分成两个部分，树根层沿一个维度一分为二，注意两边点的个数尽量相同

下次分割沿另一个维度分，以此推至结束

在每个节点中，存储在子树中的大约一半的点位于一侧，一半位于另一侧

四叉树

每个节点有四个对应于四个象限的子节点，以此类推

十五、查询处理

15.1 概述

查询处理的基本步骤：

语法分析与翻译：把查询语句翻译成系统的内部表示形式，也就是翻译成关系代数；语法分析器检查语法，验证关系

优化：一个关系代数表达式可以有许多等价的表达式，也可以用多种不同的算法来执行一个关系代数运算，用于执行一个查询的原语操作序列称为查询执行计划；查询优化就是在所有等效执行计划中选择具有最小查询执行代价的计划。

执行：查询执行引擎接收一个查询执行计划，执行该计划并把结果返回给查询

15.2 查询代价的度量

查询处理的代价可以通过该查询对各种资源的使用情况进行度量，这些资源包括磁盘存取，执行一个查询所用 CPU 时间，甚至是网络通信代价。

在磁盘上存取数据的代价通常是主要代价。通过以下指标来对其进行度量：

搜索磁盘次数 * 平均寻道时间

读取的块数 * 平均块读取时间

写入的块数 * 平均块写入时间

写入一个块的代价通常大于块读取的代价，因为数据在写入后会被读取以确保写入正确

只用传输磁盘块数和搜索磁盘次数来度量查询计算计划的代价，忽略CPU时间，不包括将操作写回磁盘的代价。

假设tT为传输一个块的时间，tS为磁盘平均访问时间，传输b个块以及执行s次磁盘搜索的操作代价：

代价估算没有包括将操作的最终结果写回磁盘的代价

15.3 选择运算（A1~A6）

例题：代价估计

现有索引（X,Y），采用B+树搜索，查找10<X<30，最坏的情况下查询代价是什么（搜索出来的记录有n条，h为B+树高度）

最左匹配原则，索引(X,Y)，使用X搜索使用索引，但如果使用Y搜索不使用索引

由于考虑最坏情况，则假设X是辅助索引，考虑A6

Cost = (2h+n)*(tS+tT)

对B+树进行了两次检索，找到两个区间节点 2h*(tS+tT)

对返回的n条记录（默认均不在一个块上，辅助索引）进行传输和搜索，n*(tS+tT)

文件扫描

算法A1（线性搜索）：在线性搜索中，系统扫描每一个文件块，对所有记录都进行测试，看它们是否满足选择条件。

时间代价 = br 次磁盘块传输 + 1 次磁盘搜索

（br 代表文件中的磁盘块数）

对作用在码属性上的选择操作来说，系统在找到所需记录以后可以立即停止

时间代价 = (br /2) 次磁盘块传输 + 1 次磁盘搜索

利用索引的选择（索引扫描）

选择条件必须是索引的搜索码

算法A2（主索引，码属性等值比较）：对于具有主索引的码属性的等值比较，我们可以使用索引检索到满足相应等值条件的唯一一条记录。

Cost = (hi + 1) * (tT + tS) 遍历树的高度+1次I/O获取记录 1次寻道+1次块传输

hi表示索引的高度

算法A3（主索引，非码属性等值比较）：检索多条记录

Cost = hi * (tT + tS) + tS + tT * b 传到内存中搜索多条记录在多个块中

记录在文件中必然是连续存储的 b 代表包含具有指定搜索码值的记录的磁盘块数

算法A4（辅助索引，等值比较）：如果等值条件是码属性上的，该策略可以检索到满足条件的一条记录

Cost = (hi + 1) * (tT + tS)

若索引字段是非码属性，则可检索到多条记录

每个 n 匹配的记录可能在不同的磁盘块中

Cost = (hi + n) * (tT + tS)

查询代价非常大

涉及比较的选择

算法A5（主索引，比较）(A 上的关系是有序的)

Cost = hi * (tT + tS) + tS + tT * b

算法A6（主索引，比较）

Cost = (hi + n) * (tT + tS)

复杂选择

A7（使用一个索引的合取选择）

A8（使用复合索引的合取选择）

A9（使用标识符交集的合取选择）

A9（使用标识符并集的析取选择）

15.4 排序Sorting

排序：

SQL中指明了order by 连接操作的计算中有序数据很有用

对于适合内存的关系，可以使用快速排序等技术

对于内存中不能容纳的关系，外部归并排序是一个很好的选择

br是包含关系r的记录的块数

bb一次读取或写出的块数

假设有3块内存用于排序，即M=3; 一个块只能容纳一个元组，即fr=1 第一阶段生成4个初始归并段，每个初始归并段有M个元组第二阶段只能2路归并，使用2块内存做输入，1块内存做输出

考试可能会给公式去算

可能会让分析出一个公式之类的

15.5 连接运算

基于代价估算来选择合适的连接

例：

Student 的记录数: 5,000 takes: 10,000

Student 的磁盘块数: 100 takes: 400

连接运算有如下五种：

嵌套循环连接（Nested Loop Join）

嵌套循环连接是一种简单但效率较低的连接算法。它通过两个嵌套的循环来执行连接操作。对于左表中的每一条记录，都会与右表中的所有记录进行比较，找出满足连接条件的记录。这种算法适用于小规模数据集，但对于大规模数据集来说效率较低。

r 被称为连接的外层关系，而 s 称为连接的内层关系

nr是外层的元组数（记录数）

bs是内层的块数、br是外层的块数

在最坏的情况下，缓冲区只能容纳每个关系的一个数据块，这时共需：

nr * bs + br 次块传输

nr + br 次磁盘搜索

如果较小的关系能被放入内存中，使用它作为内层关系

这时共需 br + bs 次块传输和 2 次磁盘搜索

块嵌套循环连接（Block Nested Loop Join）

它是嵌套循环连接的一个变种，其中内层关系的每一块与外层关系的每一块对应，形成块对，在每一个块对中，一个块的每一个元组与另一个块的每一个元组形成组对，从而得到全体组对。适应于内存不能完全容纳任何一个关系时，如果我们以块的方式而不是以元组的方式处理关系，可以减少块读写次数。

最坏情况

br * bs + br 次块传输 + 2 * br 次磁盘搜索

对于外层关系中的每一个块，内层关系 s 的每一块只需读取一次

最好情况

br + bs 次块传输 + 2 次磁盘搜索

主要就是上面两种，下面的考的很少（没复习，考就寄✌）

索引循环嵌套连接

索引查找法可以替代文件扫描法，若

连接是自然连接或等值连接

内层关系的连接属性上存在可用索引可以为了计算连接而专门建立临时索引

对于外层关系 r 的每一个元组 tr ，可以利用索引查找满足与 tr 的连接条件的 s 中的元组

最坏的情况下: 缓冲区只能容纳关系 r 的一块和索引的一块，对于外层关系 r 的每一个元组，需要对关系 s 进行索引查找

连接的时间代价: br (tT + tS) + nr * c

c 是使用连接条件对关系 s 进行单次选择操作的代价

如果两个关系 r 和 s 上均有索引时，一般把元组较少的关系作外层关系时效果较好

归并连接（Merge Join）

归并连接是一种基于有序性的连接算法。它要求连接的两个表都已按连接属性进行排序。归并连接首先将两个表按连接属性进行合并排序，然后通过同时遍历两个排好序的表，找到满足连接条件的记录。这种算法适用于大规模数据集，但要求预先对表进行排序。

散列连接（Hash Join）

散列连接是一种基于散列函数的连接算法。它将连接属性的值作为输入，通过散列函数将记录分散到不同的散列桶中。然后，对于每个散列桶，将左表和右表中的记录进行比较，找出满足连接条件的记录。散列连接适用于大规模数据集，可以通过并行处理来提高性能。

15.7 表达式计算

计算一个完整表达式树有两种方法：

物化：输入一个关系或者已完成的计算，产生一个表达式的结果，在磁盘中物化它，重复此过程。

流水线：将一个正在执行的操作的部分结果传送到流水线的下一个操作，使得两操作可同时进行。

物化

物化计算: 从最底层开始，执行树中的运算，计算每个中间结果，然后用于下一层运算。

在任何情况下，物化计算都是永远适用的。但是将结果写入磁盘和读取它们的代价是非常大的，此时可以使用双缓冲技术设定两个缓冲区，一个用于连续执行算法，一个用于写出结果，以此允许CPU活动与I/O活动的并行。

流水线

流水线执行：同时执行多个操作，一个操作的结果传递到下一个。比实体化代价小很多，没有必要存储临时关系到磁盘，但并不总是可行的，例如对排序、散列连接。

流水线的执行方法有：

需求驱动/消极计算流水线：系统不停地向位于流水线顶端的操作发出需要元组的请求，为了输出自己的下一个元组，每个操作发出请求以获得来自孩子操作的下一个元组，迭代算子维护两次调用之间的执行“状态”，使得下一个next()调用请求可以获取下面的结果元组。

生产者驱动/积极计算流水线：各操作并不等待元组请求，而是积极地产生元组。

十六、查询优化

16.1 查询优化概述

一个执行计划准确地定义了每个运算应使用的算法，以及运算之间的执行应该如何协调。

基于代价的优化步骤：

使用等价规则产生逻辑上的等价表达式

注解结果表达式来得到替代查询计划

基于代价估计选择代价最小的计划

16.2 关系表达式的转换

一般情况下会出一个画语法树然后优化语法树的题目

如果两个关系代数表达式在所有有效数据库实例中都会产生相同的元组集，则称它们是等价的

元组的顺序是无关紧要的，不关心在违反完整性约束的数据库上是否产生不同的结果

基本的等价规则有：

合取选择运算可以被分解为单个选择运算的序列

选择运算满足交换律

一系列投影中只有最后一个运算是必需的，其余的可以忽略

选择操作可与笛卡尔积以及θ连接相结合

θ连接运算满足交换律。

a.自然连接运算满足结合律 b.θ连接运算具有结合律

选择运算在下面两个条件下对θ连接运算具有分配率

8.投影运算在下列条件下对θ连接运算具有分配率

9.集合的并与交满足交换律

集合的差运算不满足交换律

10.集合的并与交满足结合律

11.选择运算对 ∩, ∪ 和 – 运算具有分配率

12.投影运算对并运算具有分配率

下推选择

尽可能早地执行选择操作以减小被连接的关系的大小

下推投影

尽可能早地执行投影操作以减小被连接的关系的大小

16.3 代价估计

可能会考代价估计

nr：关系 r 的元组数

br：包含关系 r 中元组的磁盘块数

lr：关系 r 中每个元组的字节数

fr：关系 r 的块因子 ——即，一个磁盘块能容纳的关系 r 中元组的个数

V(A, r)：关系 r 中属性 A 中出现的非重复值个数，该值与 A(r) 的大小相同

16.4 执行计划选择

//略

十七、事务管理

17.1 事务概念

事务(transaction)是访问并可能更新各种数据项的一个程序执行单元(Unit)。

例子：从账户A过户$50到账户B的事务

事务通常由SQL或者高级程序设计语言通过嵌入式SQL的执行所引起。

事务主要解决两个问题：

各种故障（硬件故障和系统故障）

多事务的并发执行

事务必须保证以下性质(ACID 特性) ：

原子性（Atomicity）：事务的所有操作在数据库中要么全部正确反映，要么全部不反映。原子性由恢复系统实现。

也考过给实例说明事务的原子性

一致性（Consistency）：隔离执行事务时（即，在没有其他事务并发执行的情况下）保持数据库的一致性。一致性状态由用户负责，由并发控制系统实现。

在事务执行过程中，数据库可能会暂时的不一致；当事务执行完后，数据库必须是一致的。

隔离性（Isolation）：尽管多个事务可能并发执行，但系统保证每个事务都感觉不到系统中有其他事务在并发的执行。中间事务结果对其他并发执行的事务是隐藏的。隔离性通过并发控制系统实现。

隔离性可以保证串行地执行事务，但是并发执行事务能够显著提升性能。

持久性（Durability）：一个事务成功完成后，它对数据库的改变是永久的，即使系统可能出现故障。持久性通过恢复系统实现。

17.2 事务状态图

使用事务状态图描述事务的执行状态，包括如下状态：

活动的（active）：初始状态，事务执行时处于这个状态

部分提交的（partially committed）：最后一条语句执行后的状态

失败（failed）：发现正常的执行不能继续之后

提交（commited）：成功完成之后

中止的（aborted）：事务回滚并且数据库恢复到事务开始前的状态，此时系统有两种选择：

重启事务：引起事务终止是由于硬件错误或者不是由事务内部逻辑所产生的软件错误
杀死事务：由于事务的内部逻辑错误引起，需要重写应用程序

事务通过这两个操作访问数据：

read(X)：从数据库把数据项X传送到执行事务的局部缓冲区

Wtite(X)：将执行事务的局部缓冲区将数据项写会数据库

在实际数据库系统中，write操作不一定立即更新磁盘上的数据；write操作的结果可以临时存储在内存中，以后再写到磁盘上，当前假设write操作立即更新数据库，这是“恢复系统”提供的一系列机制

17.3 事务隔离性

并发执行

多个事务可以在系统中并发运行

优势：

提高吞吐量和资源利用率。可以得到更高的事务吞吐量比如，当一个事务在一张磁盘上上进行读写时，另一个事务可在CPU上运行

减少等待时间。短事务不需要等待前面的长事务完成

并发控制机制 – 保证隔离性的一系列机制

控制事务之间的交互，以防止它们破坏数据库的一致性

调度

调度(Schedule) – 表示指令在系统中执行的顺序

一组事务的一个调度，必须包含这一组事务的全部指令

必须保持指令在各个事务中出现的顺序

一次事务的执行成功地完成后，会有一条提交指令作为最后一条语句

默认情况下，事务假定执行提交指令，作为事务的最后一步

一次事务的执行没有成功完成，将会有一条中止指令作为最后一条语句

并发执行机制

多个事务可以在系统中并发运行，它的核心问题是保证一致性的前提下最大限度提高并发度，依靠并发控制机制（保证隔离性的一系列机制）实现。并发执行的优势有：

一个事务由不同的步骤组成，所涉及的系统资源也不同。这些步骤可以并发执行，以提高系统的吞吐量(throughput)。

系统中存在着周期不等的各种事务，串行会导致难于预测的延迟。如果各个事务所涉及的是数据库的不同部分，采用并行会减少平均响应时间(average response time)。

对于并发运行的多个事务，当这些事务操作数据库中相同的数据时，如果没有采取必要的隔离机制，就会导致各种并发问题，这些并发问题主要可以归纳为以下几类：

更新丢失：丢失修改是指事务1与事务2从数据库中读入同一数据并修改，事务2的提交结果破坏了事务1提交的结果，导致事务1的修改被丢失。

脏读：事务1修改某一数据，并将其写回磁盘，事务2读取同一数据后，事务1由于某种原因被撤消，这时事务1已修改过的数据恢复原值，事务2读到的数据就与数据库中的数据不一致，是不正确的数据，又称为“脏”数据。

不可重复读：不可重复读是指事务1读取数据后，事务2执行更新操作，使事务1无法再现前一次读取结果。

幻读：事务1读取某一数据后：

事务2删除了其中部分记录，当事务1再次读取数据时，发现某些记录神密地消失了。

事务2插入了一些记录，当事务1再次按相同条件读取数据时，发现多了一些记录。

也可以归结为不可重复读

事务的执行顺序称为一个调度(schedule)，表示事务的指令在系统中执行的时间顺序。一组事务的调度需要保证：

包含所有事务的操作指令

一个事务中指令的顺序必须保持不变

根据调度的执行方式，可以分为串行调度和并行调度。在串行调度中，属于同一事务的指令紧挨在一起，对于有n个事务的事务组，可以有n!个有效调度；在并行调度中，来自不同事务的指令可以交叉执行，并行调度等价于某个串行调度时，则称它是正确的。

17.4 可串行化

简述串行调度和可串行化调度的区别

如果多个事务依次执行，则称事务串行调度。

如果利用分时的方法，同时处理多个事务，则称为事务的并发调度。

如果一个并发调度的结果与某一串行调度执行结果等价，则称这个并发调度是可串行化调度。

可串行化是并发执行正确性的判定标准 (即：并发调度是正确的，当且仅当调度是可串行化的)

数据库系统的调度应该保证任何调度执行后数据库总处于一致状态。如果一个并发调度等价于一个串行调度，则该调度是可串行化的。

不同形式的等价调度：

冲突可串行化

视图可串行化

冲突指令

冲突指令：当两条指令是不同事务在相同数据项上的操作，并且其中至少有一个是write指令时，则称这两条指令是冲突的。非冲突指令交换次序不会影响调度的最终结果。

直观上指令之间的冲突，强迫它们之间具有时序顺序。

冲突可串行化

如果通过一系列非冲突指令的交换，调度 S 可以转换为调度 S´, 我们说 S 和 S´ 是冲突等价(conflict equivalent)的。

我们说调度 S 是冲突可串行化(conflict serializable )的，如果它与一个串行调度冲突等价。

可串行化判定

优先图：

一个调度S的优先图是这样构造的：它是一个有向图G=（V，E），V 是顶点集，E 是边集。顶点集由所有参与调度的事务组成，边集由满足下述条件之一的边Ti→Tj 组成：

在Tj 执行read(Q)之前，Ti 执行write(Q)

在Tj 执行write(Q)之前，Ti 执行read(Q)

在Tj 执行write(Q)之前，Ti 执行write(Q)

如果优先图中存在边Ti→Tj，则在任何等价于S 的串行调度S′中，Ti 都必须出现在Tj 之前。如果调度S的优先图中有环，则调度S是非冲突可串行化的。如果图中无环，则调度S是冲突可串行化的。

与冲突可串行化等价的串行顺序：串行顺序可由拓扑排序得到，求出与优先图的偏序相一致的线序

17.5 可恢复调度

事务的恢复：一个事务失败了，应该能够撤消该事务对数据库的影响。如果有其它事务读取了失败事务写入的数据，则该事务也应该撤消。

可恢复的调度(Recoverable schedule ) ：对于每对事务T1与T2，如果T2读取了T1所写的数据，则T1必须先于T2提交。

级联回滚——单个事务失败，导致一系列事务回滚，会导致大量工作撤销。

无级联调度(Cascadeless schedules) ——不会发生级联回滚; 对每一事务对 Ti 和Tj ，如果Tj 读取了Ti 所写的数据项, 则 Ti 必须在 Tj 的读操作之前提交。

无级联调度必是可恢复调度

17.6 并发控制

事务隔离

数据库必须提供一个机制，确保所有可能的调度或者是冲突可串行化，或者是视图可串行化，并且是可恢复的，最好是无级联的。

事务的隔离性实质上是数据库的并发性与一致性的函数。

按照隔离级别从低到高的顺序：

未提交读(Read uncommitted )：允许读取未提交数据，这是SQL允许的最低级的隔离性（当事务A更新某条数据时，不容许其他事务来更新该数据，但可以读取。）

可能出现脏读

已提交读 (Read committed ) ：只允许读取已提交数据，但不要求可重复读。连续读记录可能返回不同的值。比如，在同一个事务两次读取同一个数据项之间，其他事务可以更新并提交该数据项

可能出现不可重复读

可重复读(Repeatable read ) ：只允许读取已提交数据，在两次读取相同数据项之间，不允许其他事务更新这些数据项（可以看到其他事务已经提交的新插入的记录，但是不能看到其他事务对已有记录的更新。）。至于和其他事务之间不一定保证可串行化。

可能出现幻读

可串行化 (Serializable)

隔离级别的实现可以通过：

封锁：两阶段封锁，一种可以保证可串行化的技术

时间戳：为每个事务和每个数据项均分配时间戳，通过时间戳确定事务应该执行还是回滚

多版本和快照隔离：多版本：维护数据项的多个版本，允许事务读取数据项的旧版本；快照隔离：每个事务开始时拥有自己的数据库版本或者快照

基于锁的协议

确保可串行化的方法之一是要求对数据项的访问以互斥的方式进行。

封锁就是事务T在对某个数据对象（例如表、记录等）操作之前，先向系统发出请求，对其加锁，加锁后事务T就对该数据对象有了一定的控制，在事务T释放它的锁之前，其它的事务不能更新此数据对象。封锁是控制对数据项的并发访问的机制。

数据库加锁有两种锁模式：

排他锁（X，exclusive模式，写锁）：数据项既可以读又可以写。使用 lock-X 指令申请

共享锁（S，Shared模式，读锁）：数据项是只读的。使用 lock-S 指令申请

锁请求发送给并发控制管理器，只有在并发控制管理器授予所需锁后，事务才能继续其操作。

任何数量的事务在一个数据项上可以同时持有共享锁。但是如果任何的事务持有排他锁，其他事务不能持有该数据项上的任何锁。

如果没有被授予锁, 申请锁的事务需要等待，直到其他事务所持有的所有不相容的锁都已释放，锁才会被授予

封锁协议是在请求和释放锁时的一系列规则，适用于所有事务。封锁协议限制了可能的调度集。

大多数封锁协议都可能导致死锁，难以避免；如果并发控制管理器设计的不好，还可能造成饥饿/饿死。

一个事务在等待某数据项上的 X-lock, 同时一系列其他的事务在该数据项上请求授予 S-lock

一个事务由于死锁而不断回滚

要防止饥饿，可以对申请S锁的事务，如果有先于该事务且等待的加X锁的事务，令申请S锁的事务等待。

两阶段封锁协议

定义：每个事务分两个阶段，提出加锁和解锁申请阶段。

阶段 1: 增长阶段(growing phase)。事务可以获取锁，事务不能释放锁。

阶段 2: 收缩阶段(shrinking phase) 。事务可以释放锁，事务不能获取新锁。

封锁点（lock point）：事务最后加锁的位置，称为事务的封锁点, 记作Lp(T)。

该协议确保可串行化，可以证明事务按照它们的封锁点的顺序可串行化 (即事务获取最后一次封锁的时刻)。

并行执行的所有事务均遵守两段锁协议，则对这些事务的所有并行调度策略都是可串行化的。事务遵守两段锁协议是可串行化调度的充分条件，而不是必要条件。

两阶段封锁不能确保避免死锁，可能产生级联回滚。

为避免级联回滚，采用称为严格两阶段封锁协议：事务必须持有所有排他锁，直到事务提交或中止。

强两阶段封锁协议更加严格：事务提交或终止前，不能释放任何锁。在该协议中，事务按照提交的顺序可串行化。

两阶段封锁协议的证明：

定理：两阶段封锁协议保证调度冲突可串行化

证明：反证法，假设调度{T1,T2....,Tn}遵从两阶段封锁协议，但不冲突可串行化。

不冲突可串行化，优先图必有环。不妨假设T1,T2,...,TmT1是一个环。

如果优先图有边Ti→Tj，一定有Lp(Ti)<Ti.unlock(Q)<Tj.lock(Q)≤Lp(Tj)。即Lp(Ti)<Lp(Tj)。

即对上面的环，有Lp(T1)<Lp(T2)<⋯<Lp(Tm)<Lp(T1)存在矛盾，故假设不成立。

锁转换包括：

Upgrade：共享锁升级到排他锁

Downgrade：排他锁降级到共享锁

锁升级只能发生在增长阶段，降级只能发生在缩减阶段。

死锁处理

如果事务集中的每个事务在等待该集合中的另一个事务，则系统处于死锁状态

死锁预防协议确保系统不会进入死锁状态，一些预防策略：

要求每个事务在执行前封锁所有的数据项（预声明）

给所有数据项施加偏序关系，要求事务按照偏序关系封锁数据项(基于图的协议)

下面的策略采用时间戳来预防死锁

wait-die 模式 — 非抢占

老事务可以等待年轻事务释放数据项，年轻事务不等待老事务，而是直接回滚

在获取所需的数据项之前，事务或许会死若干次

wound-wait 模式 — 抢占

老事务不等待年轻事务，直接强制其回滚。年轻事务等待老事务

可能比 wait-die 模式回滚次数少

在wait-die 和wound-wait 策略下,回滚事务用它最初的时间戳重启，从而老事务比新事务有更高的优先级，避免了饥饿

基于超时的策略 事务等待封锁一定的时间，超时之后，事务回滚

死锁不会发生

易于实现；但是可能产生饥饿；也难以确定合适的超时时间

死锁检测

死锁可以用等待图G =(VE)描述

V 是顶点的集合(系统中所有的事务)

E 是边的集合；每个元素是一个有序对Ti →Tj

如果Ti →Tj 在E中,那么就有一条从Ti 到Tj的有向边，表示Ti 等待Tj 释放数据项

当Ti 请求当前Tj 所持有的一个数据项时，边Ti →Tj就被插入到等待图中。只有当Tj 不再持有Ti 所需的数据项时，边才从图中移除

系统处于死锁状态，当且仅当等待图存在环。必须定期的调用死锁检测算法来查找环

死锁解除

发现死锁时：

一些事务必须回滚 (牺牲) 来去除死锁，选择成本最小的那些事务作为牺牲品

回滚 – 回滚到何处

完全回滚：中止事务，重启动

部分回滚：回滚到解除死锁为止，这种方法更有效

如果同一事务总是被牺牲，会产生饥饿，把回滚次数作为成本因子，避免饥饿

基于时间戳的协议

简述时间戳排序协议

每项事务进入系统时，都将被赋予一个时间戳。如果老的事务Ti已经被赋予时间戳TS(Ti)，新的事务Tj 将被赋予一个时间戳TS(Tj)，并且有TS(Ti) <TS(Tj)

每个数据项Q需要与两个时间戳值相关联：

W-timestamp(Q)：表示成功执行write(Q)的所有事务的最大的时间戳

R-timestamp(Q)：表示成功执行read(Q)的所有事务的最大的时间戳

时间戳排序协议保证任何有冲突的read或write操作按时间戳顺序进行：

事务Ti 发出read(Q)：

如果TS(Ti)< W-timestamp(Q)，则Ti需读入的Q值已被覆盖。因此，read操作被拒绝，Ti回滚

如果TS(Ti)>= W-timestamp(Q)，则执行read操作，R-timestamp(Q)被设为R-timestamp(Q)和TS(Ti)两者的最大值

也就是如果事务时间戳小于上次写操作，则要读入的值已经被覆盖了，需要回滚重新执行。

事务Ti 发出write(Q)：

如果TS(Ti)< R-timestamp(Q)，则Ti产生的Q值是先前所需要的值，且系统已假定该值不会被产生。因此，write操作被拒绝，Ti回滚

如果TS(Ti)< W-timestamp(Q)，则Ti试图写入的Q值已过时。因此，write操作被拒绝，Ti回滚

否则，执行write操作，将W-timestamp(Q)设为TS(Ti)

也就是如果事务时间戳小于上次写（即将发生的写已经过时）或读操作，需要回滚重新执行。

针对若干数据项的、时间戳为1, 2, 3, 4, 5的事务的一个部分调度
TS(T1) < TS(T2) < TS(T3) < TS(T4) < TS(T5)
例：T2的read（Z）想读的是初始的Z，然而T3在这之前write（Z）修改了Z的值，因此T2执行的read操被拒绝，回滚
【T2发出read(Z)，TS(T2) < W-timestamp(Q) = TS(T3) 所以read操作被拒绝，回滚】
T4的read（W）想读的应该是T3write之后的，结果读到原始的了，T3执行write被拒绝，回滚
【T3发出write(W)，TS(T3) < R-timestamp(Q) = TS(T4) 所以write操作被拒绝，回滚】 — 针对若干数据项的、时间戳为1, 2, 3, 4, 5的事务的一个部分调度 TS(T1) < TS(T2) < TS(T3) < TS(T4) < TS(T5) 例：T2的read（Z）想读的是初始的Z，然而T3在这之前write（Z）修改了Z的值，因此T2执行的read操被拒绝，回滚【T2发出read(Z)，TS(T2) < W-timestamp(Q) = TS(T3) 所以read操作被拒绝，回滚】 T4的read（W）想读的应该是T3write之后的，结果读到原始的了，T3执行write被拒绝，回滚【T3发出write(W)，TS(T3) < R-timestamp(Q) = TS(T4) 所以write操作被拒绝，回滚】

往年考题(2022)：数据项Q的W-timestamp(Q)=R-timestamp(Q)=20，现有事务Ta和事务Tb，TS(Ta)=30,TS(Tb)=34，Tb先执行read(Q)，Ta再执行Read(Q)，问最后R-timestamp(Q)为多少，为什么

答：Tb执行read(Q), TS(Tb)不小于 W-timestamp(Q) ，因此可以正常执行， R-timestamp(Q)更新值为34 Ta执行read(Q), TS(Ta) > W-timestamp(Q)，因此可以正常执行，R-timestamp(Q) = max(R-timestamp(Q), TS(Ta) ) = 34 所以最后R-timestamp(Q)为34

17.7 恢复系统

故障分类

事务故障：

逻辑错误：因为某些内部错误条件导致事务不能完成

系统错误：因为某种错误条件(如死锁)导致数据库系统终止一个活跃事务

系统崩溃：停电故障或者其他软硬件故障导致系统崩溃。

故障-停止假设: 假设非易失性存储器的内容不会因系统崩溃而破坏。数据库系统通过许多完整性检查来防止磁盘数据被破坏。

磁盘故障：磁头损坏或类似的磁盘故障可能破坏全部或部分磁盘存储器。

假设损坏是可以检测到的: 磁盘驱动器使用校验和来检测故障

恢复算法：在正常事务处理时采取措施，保证有足够的信息用于故障恢复；故障发生后采取措施，将数据库内容恢复到某个保证数据库一致性、事务原子性及持久性的状态。

数据访问

物理块：位于磁盘上的块

缓冲块：临时位于主存中的块

磁盘和主存之间的块移动通过下列两个操作来引发：

input(B)：将物理块B传入主存。

output(B)：将缓冲块B传到磁盘，并且替换相应的物理块。

每个事务Ti都有自己的私有工作区, 用来保存它存取和更新的所有数据项的局部副本，对应数据项X的局部副本记为Xi。事务使用下列操作来在系统缓冲块和它的私有工作区之间传送数据项：

read(X)：将数据项X的值赋给局部变量。

write(X)：将局部变量的值赋给缓冲块中的数据项X。

output()不必紧随write(X)，系统可以选择在他认为适当的时机执行。

事务第一次访问X之间必须先执行read(X)，后续操作对局部副本进行；事务完成之前的任何时间可以执行write(X)。

恢复与原子性

为了在故障的情况下仍确保原子性, 我们首先向稳定存储器输出描述更新的信息（日志—），而不更新数据库本身。

基于日志的恢复

日志保存在稳定存储器上，日志是日志记录的序列，用来记录对数据库的更新活动。先写日志，后写数据库。

日志的组成包括：

事务标识符

数据项标识符

旧值

新值

当一个事务的commit日志记录输出到稳定存储器后，我们就说这个事务提交了。这时，所有更早的日志记录都已经输出到稳定存储器中。

不是在一个事务提交时必须将包含该事务修改的数据项的块输出到稳定存储器中，可以在以后的某个时间再输出。事务提交后虽然没真正写入，但可以认为完成了该事务。

基于日志的恢复有两种方法：

延迟修改：只有在事务提交时才执行更新（也就是commit时才write），简化了恢复的一些方面，但存在存储部分拷贝的开销。

立即修改：允许在事务提交之前，对还未提交的事务进行更新。

延迟修改

延迟修改技术只有在事务提交时才执行更新

简化了恢复的一些方面但存在存储部分拷贝的开销

一旦日志记录都写到了稳定存储器上，就真正执行更新，并且事务进入提交状态

延迟修改技术只需要数据项的新值

事务需要Redo操作，当且仅当日志中既包含记录又包含记录。

延迟修改的恢复机制：

: 将事务Ti更新的所有数据项的值设为新值。

Redo操作必须是幂等的。

立即修改

立即修改技术允许在事务提交之前，对还未提交的事务进行更新

更新的日志记录必须在数据库数据修改之前写入稳定存储器

事务需要Redo操作，当且仅当日志中既包含记录又包含记录

事务需要Undo操作，当且仅当日志中既包含记录不包含记录。

先写日志原则

对于尚未提交的事务，在将DB缓冲区写到外存之前，必须先将日志缓冲区内容写到外存去日志记录将要发生何种修改写入DB表示实际发生何种修改如果先写DB，则可能在写的中途发生系统崩溃，导致内存缓冲区内容丢失，而外存DB处于不一致状态，由于日志缓冲区内容已破坏，导致无法对DB恢复

Undo和Redo操作

数据库系统通过Undo和Redo操作配合日志实现恢复：

Undo 对于日志记录<Ti, X, V1, V2> 将X写为旧值V1

Redo 对于日志记录<Ti, X, V1, V2> 将X写为新值V2

对于事务，他的Undo和Redo是：

将事务更新过的所有数据项的值都恢复成旧值，从最后一条日志记录向前进行。每将数据项X恢复到旧值V，就写一个特别的日志记录。undo操作完成后写下日志记录。

将所有更新过的数据项的值都设置成新值, 从Ti 的第一条日志记录向后进行，不产生日志。

当事务启动时，会写入一条登记的日志记录，并在每次执行write(X)之前写入日志记录，完成最后一条语句后写入。

当从系统崩溃中恢复时:

需要对事务Ti 需要进行撤销，如果日志

包括<Ti start>记录,
但既不包括<Ti commit>也不包括<Ti abort>记录.

需要对事务Ti 进行重做，如果日志

包括<Ti start>记录
并且包含<Ti commit>或<Ti abort>记录

如果是延迟修改，有<Ti commit>需要redo(Ti)，如果没有，则说明没有执行更新，因为延迟修改是在事务提交时才执行更新，而根据先写日志原则，没有被提交就一定没有执行更新，此时不需要执行任何恢复操作。（这也是延迟修改不需要记录旧值的原因，因为用不到旧值）

检查点

重做/撤销日志中记录的所有事务会非常慢

如果系统运行了很长时间，要处理全部日志非常耗时

不需要重做已经输出了对数据库的更新的那些事务

通过定期执行检查点实现流水恢复过程

将当前位于主存的所有日志记录输出到稳定存储器

将所有修改了的缓冲块输出到磁盘

将一个日志记录< checkpoint L> 输出到稳定存储器，其中L是执行检查点时正活跃的事务的列表

检查点执行过程中，不允许事务执行更新操作。在检查点之前提交的事务，不予考虑。

恢复时仅需考虑在检查点之前启动的最近的事务，以及在之后启动的事务。从日志末尾反向扫描, 找到最近的 <checkpoint L>记录。只对在L中的事务，或是在需要重做或撤销的检查点之后开始的事务。