数据库系统期末复习笔记

type

status

slug

summary

事务管理 Transactions

重要考纲

主要内容：

事务是数据库管理系统进行并发控制和恢复的基本单位。讲解事务的基本概念、事务的ACID性质、事务并发执行（日志记录规则）的好处和潜在问题，以及并发事务的可串行性和可恢复性。

课外学习

1）事务的并发执行有哪些好处？

2）如果不进行恰当的并发控制，多个事务并发执行可能产生哪些潜在的问题？

知识点的学习

🦄

事务是访问数据项、并可能更新数据项的程序执行单元。

事务的ACID属性

atomicity原子性：要么事务的所有操作都正确反映在数据库中，要么没有。
consistency 一致性：在隔离状态下执行事务，可以保证数据库的信息一致性。保证数据库内容的正确性。
isolation 隔离性：尽管有多个事务同时执行，但每个事务必须不知道其他同时执行的任务。必须对其他并发执行的事务隐藏中间的事务结果。即一个事务不会被另一个事务所影响。

满足隔离性，最理想的情况就是一个事务执行完毕后再执行下一个事务。但是出于性能上的考虑，往往实际上是多个事务并发执行。这就要求事务执行的过程中，不受并行执行的事务影响。例如，不能读取到另一个还没有commit的事务写入的值。

durability 持久性：事务成功完成后，即使系统出现故障，事务对数据库的影响也应当永久存在。

事务通过两种操作访问数据

read

write

每个事务，都有一个工作空间。工作空间中有该事务需要访问到的数据。这些数据，在某些内存块的里面。如果是write，修改好了这些数据以后，会再写回到内存中去

通过转账记录进行说明：

上述操作，在T1事务没有提交的时候，就进行T2事务的话，就会得到A+B的总和为150的结果，从而不符合隔离性的要求

事务状态转移

active：事务在正常执行的状态。 partially committed：如果事务的操作，已经执行了最后一条语句，就进入准备提交阶段。 failed：事务提交失败。

committed：事务已经提交，那么就要保持它的持久性。 aborted：事务提交失败后，进入失败状态，要将该事务进行过的所有操作全部清空。

并发执行中的异常

丢失修改

对数据库的多次修改，最终产生的结果只有最后一次修改，称为丢失修改问题

读脏数据

一个事务读取了另一个事务中写入的，还没有提交的脏数据。假设另一个事务最终没有提交那个脏数据，而是产生回滚，那么读取脏数据的事务对数据库产生的修改将是不正确的

不可重复读

在事务T2没有提交的时候，T1就进行读取。这样，由于隔离性的要求是：在一个事务没有提交时，其他的任何事务都不会影响这个事务。但是，此时T2事务却影响了T1事务读取数据的结果，不满足数据库隔离性的要求。

幽灵问题

同样，在事务T2没有提交的时候，T1就又进行了一次查询。此时T2的插入操作，影响了T1在一个事务当中的查询结果，使前后两次查询结果不一致，因此产生幽灵问题，不满足隔离性的要求。

🦄

幽灵问题和不可重复读问题的区别是：

不可重复读是针对一个数据的前后两次读取值不一致的情况，这个数据本身就是存在于数据库中的。

而幽灵问题是指前后两次相同的查询，会多出一些记录，或者少掉一些记录来。

不可重复读问题比较好解决，只需要在事务T1第一次对数据A进行读取时，加上一个S锁即可。那么事务T2将不能对A进行更改。

但是幽灵问题解决起来比较困难，代价比较高

引入事务执行的调度 Schedules

一组事务执行的顺序。
这两个事务完全是串行执行的，这是串行调度。

serial schedule一定满足隔离性

也是一个串行调度，交换了顺序。

显而易见，串行调度一定是满足隔离性的。

通过上述变化，最终结果中，A+B仍然是200。这是由于，二者在时间上交错的部分都是不矛盾的，也就是说，交错的部分进行互换，是不影响结果的。因此，这就等价于例1。

同样，这个事务的调度满足隔离性要求。
隔离性是指一个事务不会被另一个事务所影响。

下面的两个事务之间存在着丢失修改的问题

事务T1的write(A)在事务T2的write(A)之后，且无法交换。

访问相同的数据时，Read和Read操作可以交换，Read和Write操作、Write和Write操作均不能交换。

serializability 可串行化

如果一个（可能是并发执行的）计划（事务集合），可以等同为一个串行的计划，那么这个计划称为可串行化的。
分类

冲突可串行化
视图可串行化

冲突可串行化 conflict serializability

指从冲突操作的角度考虑，是可串行化的。例如Schedule 3中，将交叉执行的两个事务转化为串行执行的两个事务的过程中，两两进行交换的操作，没有产生前后依赖关系（即冲突）的，最终转化称为两个串行执行的事务，这就叫做冲突可串行化。

此外，如果一个交叉调度是冲突可串行化的，那么串行化以后事务的顺序是由其中一对冲突的操作的先后次序决定的。哪一个事务的冲突操作在前，哪一个事务串行化以后的先后次序就在前。

不是冲突可串行化的例子

判断冲突可串行化的算法

通过考察所有冲突的操作对，画出一个有向图。

如果事务Ti有一个操作和Tj的某个操作冲突，如果Ti的这个操作在Tj的对应冲突的操作之前，那么Ti这个节点就和Tj这个节点之间，存在一条Ti指向Tj的有向边。

如果有向图存在环，那么这些事务将不是冲突可串行化的。如果有向图不存在环，那么这些事务将是冲突可串行化的，并且串行化以后这些事务的执行顺序是对有向图进行拓扑排序的顺序。

视图可串行化 view serializability

条件如下：

1. 一个交叉调度是视图可串行化的，必要条件之一是：这个交叉调度与其对应的串行调度之间，读到各个数据的初始值的是同一些事务。

一个交叉调度是视图可串行化的，必要条件之一是：假设其对应的串行调度中的事务Ti执行了Read（Q）操作，并且Q的值是由串行调度中的事务Tj产生的，那么这个交叉调度中，事务Ti执行了Read（Q）操作，Q的值也应当是对应的事务Tj产生的。

一个交叉调度是视图可串行化的，必要条件之一是：这个交叉调度与其对应的串行调度之间，写入各个数据的终末值的是同一些事务。

上面这个交叉调度不是冲突可串行化的，因为T27与T28之间存在环。

但是，上面这个交叉调度是视图可串行化的。它串行化得到的串行调度是T27->T28->T29。

这个交叉调度的该串行调度满足上述视图可串行化的三个条件

🦄

重要结论：每一个冲突可串行化的调度，都是视图可串行化的。反之未必。

有些视图，不是冲突可串行化的，也不是视图可串行化的，但是它是可串行化的。

加减操作可以

可恢复调度 recoverable schedule

如果在一个调度中，事务B读取了事务A先前写入的数据，那么事务A的提交操作，出现在事务B之前，这就称为可恢复调度。

T9读取了T8写入的数据，然而，T9的提交操作在T8之前。如果之后T8进行了回滚，那么T9事务将向用户显示了不一致的数据库状态。这就会产生“读脏数据”的问题。

因此，数据库必须保证调度是可恢复的。

cascading rollback

上面这个例子中，T11读取了T10写入的值（脏数据），T12又读取了T11写入的值（脏数据）。

因此，T10发生回滚后，T11也要发生回滚，过后T12也要发生回滚。

非级联调度（Cascadeless Schedules）

① 级联回滚必须不能发生。

② 对于任意一对事务A与B，如果事务B读取了事务A之前写入过的数据，那么事务A的提交操作一定发生在事务B的提交操作之前。

数据库必须提供一种机制

冲突或视图可序列化
可恢复的，最好是非级联调度的

并发控制协议

并发控制协议允许并发调度，但是要确保并发调度是冲突（或视图）可序列化的，并且是可恢复也是无级联回滚的）

弱一致性水平

一些应用程序愿意接受较弱级别的一致性，允许部分不可序列化的调度，以减少代价。例如，想要获得所有账户的大致总余额的只读交易；又例如，为查询优化计算的数据库统计数据可能是近似的。

数据库中的隔离级别

最高：串行化

意味着四种问题（幽灵问题、不可重复度、读脏数据、丢失修改）都不能存在。

次高：可重复读（不关心幽灵问题）

三种问题会被解决，除了幽灵问题。

再次：读提交（不关心幽灵问题，也不关心不可重复读问题，但要保证不读脏数据）

只读别的事务已经提交的数据。

最低：读非提交

别的事务未提交的更改过的数据也可以读（连脏数据也允许读）。

事务的并发控制协议

考试范围

主要内容：

并发控制保证多个事务并发执行如同串行调度一样获得正确的运行结果。讲解基于锁的并发控制协议的主要思想、两阶段封锁协议（2PL）、死锁及解决办法、多粒度锁, 以及数据删除和插入情况下的并发控制。什么是死锁预防，什么是死锁避免

课外学习：

1）事务的并发执行有哪些好处？

2）如果不进行恰当的并发控制，多个事务并发执行可能产生哪些潜在的问题？

3）证明2PL是保证事务调度冲突可串行性的充分条件，而非必要条件。

重要的知识点

每个并发事务都自觉遵守这个协议，那么就会自发形成一种相互等待关系，形成一种调度，而这种调度可以证明都是可串行的、可恢复的。

基于锁的协议

共享锁（读锁）（S锁）
独占锁（写锁）（X锁）

基于时间戳的协议

事务执行的时候，都给事务一个时间戳。越早产生的事务，越排在串行事务的前面。

基于验证的协议

对并发控制保持乐观态度。
访问数据，或者修改数据后，在要提交的时候，验证一下和其他事务是否冲突。（在partially committed阶段）
所有正在做的事务都放在内存中，不影响数据库。

基于锁的并发控制

访问数据之前，要申请相应的锁。
排他锁：（X）

写数据时，需要申请排他锁。

共享锁：（S）

读数据时，需要申请共享锁

一个事务可以分为两个阶段。

前一个阶段称为锁的增长阶段。

后一个阶段称为锁的释放阶段。

lock point

锁的增长阶段的结束点；

也是最后一个锁已经被申请获得了的时间点。

一些事务可以按照其lock point的顺序，进行冲突可串行化的调度

证明：如果在前驱图中Ti对Tj有一条指向的有向边，那么Ti的lock point一定小于Tj的lock point。因为，如果Ti对Tj有一条指向的有向边，那么Ti和Tj之间肯定有一对冲突的操作访问相同的数据。
只有Ti将这个数据的锁放掉后，Tj才可以给这个数据加锁。由于lock point过后，事务不会再加锁，因此此时Ti放锁一定处于Ti lock point之后，Tj加锁一定处于Tj lock point之前。因此，Ti的lock point 一定小于Tj的lock point。
因此这些事务的前驱图中一定没有环。因此这些事务可以进行冲突可串行化的调度（按照拓扑排序的顺序）。

基本两阶段封锁 basic tow-phase locking

刚刚所述的两阶段封锁协议就是基本两阶段封锁，分为加锁阶段和放锁阶段。

严格两阶段封锁 strict two-phase locking

X锁加的时间更长，X锁要到事务即将提交或者即将回滚的时候再放开，以防止读脏数据的问题。

好处：保证可恢复性，防止读脏数据的问题
坏处：代价是X锁的时间更长，其他事务等待的时间变长，会降低并发度

强两阶段封锁：rigorous two-phase locking

所有锁都要加到即将提交或者即将回滚的时候再放开。

下面需要说明的是：

🦄

两阶段封锁协议，不是冲突可串行化的必要条件，也就是说，有些冲突可串行化的事务，并不满足两阶段封锁协议。

这些事务的前驱图是

因此，这些事务可以按照T3->T1->T2进行冲突可串行化的调度。这些事务的加锁与放锁操作如下：

T1事务放锁之后，又进行了加锁操作

因此，T1事务不满足两阶段封锁协议

🦄

因此，事务满足两阶段封锁协议，是可以进行冲突可串行化调度的充分条件，而不是必要条件。

也就是说，满足两阶段封锁协议，那么一定是冲突可串行化调度

但是如果是冲突可串行化调度，不一定会满足两阶段封锁协议

带有锁转换的两阶段封锁协议：

有些时候，访问数据库数据时，我们需要先读数据，再修改数据。

如果我们读取数据加上S锁，修改数据先放掉S锁，再加上X锁，就不满足两阶段封锁协议，导致事务之间可能不能冲突可串行化。

假如一开始就加上X锁，又会降低并发度。

因此，解决方案是：一开始加上S锁，等到要修改数据时，将S锁升级为X锁。

现在两阶段封锁协议变为：

第一阶段可以进行加锁操作，也可以进行锁升级操作。

第二阶段可以进行放锁操作，也可以进行锁降级操作。

带有锁转换的两阶段封锁协议，也可以保证事务按照lock point排序，是可以实现冲突可串行化调度的。

数据库中实现锁的机制：

基于锁的并发控制容易造成的问题：死锁

假如下面两个事务都要遵守两阶段封锁协议：

事务T1: write(A), write(B)

事务T2：write(B), write(A)

加锁放锁的流程图如下：

由于要遵循两阶段封锁协议，因此T1给A加锁了以后，在没有给B加锁之前，不会将A的锁放掉；T2给B加锁了以后，在没有给A加锁之前，不会将这B的锁放掉；

产生了互相等待，然而此时T1不会把A的锁放掉，T2也不会把B的锁放掉，从而互相等待是无限循环。

1. Deadlock Prevention（死锁预防）

定义： 死锁预防协议确保系统永远不会进入死锁状态。

预防策略：

要求每个事务在开始执行之前锁定其所有数据项（预声明）。

解释： 这一策略确保在事务执行之前，事务已经声明了它需要的所有资源，防止在事务执行过程中因为等待资源而造成死锁。

对所有数据项进行部分排序，并要求事务只能按照指定的部分顺序锁定数据项（基于图的协议）。

解释： 这一策略通过对资源进行部分排序，确保资源的获取顺序是固定的，从而避免了环路依赖的产生，从而防止死锁。

2. Timeout-Based Schemes（基于超时的方案）

定义： 在这种方案中，事务只等待锁定一段指定的时间。

详细说明：

事务只等待锁一段指定的时间。 超过这个时间后，等待超时，事务回滚。

解释： 通过设置一个等待时间，如果事务在这段时间内未能获取锁，它将放弃当前操作并回滚，重新尝试或选择其他操作。

因此，死锁是不可能的。

解释： 由于没有事务会无限期等待锁，因此死锁不会发生。

实现简单，但可能出现饥饿。

解释： 尽管这种方法实现起来比较简单，但可能会导致某些事务总是无法获取所需资源，从而长期处于等待状态，即饥饿。

确定超时间隔的最佳值也很困难。

解释： 设置合适的超时值是一项挑战，因为值设得太短可能导致频繁回滚，而设得太长则可能无法有效防止死锁。

Deadlock Detection（死锁检测）

死锁描述：

死锁可以用一个等待图（wait-for graph）来描述，该图包含一个对 (G = (V, E))：

V 是顶点集合（系统中的所有事务）。
E 是边集合，每个元素是一个有序对 Ti -> Tj。

等待图中的边（Edge in the Wait-for Graph）：

如果 Ti -> Tj 在 E 中，那么存在一条从 Ti 到 Tj 的有向边，这意味着 Ti 正在等待 Tj 释放一个数据项。

边的插入和删除（Insertion and Removal of Edges）：

当 Ti 请求一个当前由 Tj 持有的数据项时，Ti -> Tj 被插入到等待图中。只有当 Tj 不再持有 Ti 需要的数据项时，这条边才会被删除。

表示的内容是Ti等待Tj，然后Ti→Tj，表示一个等待图

死锁状态（Deadlock State）：

如果且仅当等待图中存在环（cycle）时，系统处于死锁状态。

解释： 环的存在意味着有一组事务互相等待对方释放资源，导致所有这些事务都无法继续执行。

死锁检测算法（Deadlock-Detection Algorithm）：

必须定期调用死锁检测算法来查找环。

解释： 死锁检测算法通过分析等待图来识别是否存在环，从而确定系统是否处于死锁状态。

如何避免无限循环

一个事务要进行，申请的锁要么全部给这个事务，让这个事务进行，要么一个都不给这个事务，让这个事务不要进行，防止与其他事务形成死锁。

对数据的访问规定一种次序（偏序集）（有向无环图），那么就不会产生死锁（循环等待）。

下面是一个例子

例如，假设有两个事务： T1: A-50 B+50 T2: B-10 A+10

我们可以执行作： T1: A-50 B+50 T2: A+10 B-10 这样，可以降低出现死锁的概率

死锁检测：

每隔一定时间，数据库后台会有一个进程定期检查数据库中是否出现死锁。

在数据库中，死锁的检查利用了“等待图”。

等待图中，箭头表示，Ti在等待Tj事务的锁。

如果在等待图中存在环，表示出现了死锁

练习题

上面是一个Lock Table的例子。存在六个事务，存在七个需要被访问的数据。事务和事务之间的箭头表示等待的关系。已经获得锁的事务用实心框表示，还在等待的事务用空心框表示。

(a)哪些事务产生了死锁？

作出等待图，查看环。（T1/T2/T6）

(b)为了解决死锁问题，哪个事务需要被roll back？（假如要求为：回滚掉的事务，需要释放出最多的锁）

在环中选择一个事务进行回滚。(T2)

有没有不满足两阶段封锁协议的方式，同样使得事务之间满足冲突可串行化？

假如我们知道，数据库中数据的访问是按照某种偏序关系进行的（如上图），那么不满足两阶段封锁协议，也有可能能够使事务之间满足冲突可串行化。

更简单的一种基于图的协议：树协议

只有一种锁：X锁

第一个锁可以加在树结构的任意一个结点上。

但是，后面要在某一个结点上加锁的前提是，父节点已经被锁住了。

一个结点上的锁，在数据访问完毕后，可以在任何时候放掉。

🦄

树协议的性质：虽然不是两阶段封锁协议，但是保证冲突可串行化的，同时，又是不存在死锁的。 树协议的好处：一个数据的访问的锁，访问完毕就可以释放，因此可以提高并发度，降低锁上面的等待时间。并且，不会产生死锁。 树协议的缺点：不能保证可恢复性，允许读脏数据。因此，基于锁的并发控制协议中，为了保证可恢复性，一个事务如果读取了另一个事务写入的数据，那么这个事务的commit操作，一定要在另一个事务之后。

多粒度

一个锁可以将一条记录锁起来，也可以直接把整个表格锁起来。

数据库里面的数据项，根据其大小可以分为粗粒度和细粒度。

粗粒度：例如，DataBase层面、Table层面等。

细粒度：例如，记录、属性层面。

其中S锁、X锁可以加到细粒度的层面上，也可以加到粗粒度的层面上

那么，有一个问题：粗粒度上面的锁和细粒度上面的锁如何进行有效的判断？细粒度上假如已经加了一个S锁或X锁，那么粗粒度上加锁是否冲突？

为了解决上述问题，在粗粒度上，引入了三种锁：IS锁、IX锁、SIX锁。

如果一个事务，要在某一个细粒度数据（如记录）上面加上S锁，那么这个事务必须要在这个细粒度数据的父节点（如表）这一粗粒度数据上加上IS锁。

如果一个事务，要在某一个细粒度数据（如记录）上面加上X锁，那么这个事务必须要在这个细粒度数据的父节点（如表）这一粗粒度数据上加上IX锁。

SIX锁，是S锁和IX锁的结合。例如，一个表的某些记录需要直接读取，有些记录可能产生更改，就在表层级上加上SIX锁，这样表中需要读的记录不用再加上S锁了，表中需要写的记录需要加上X锁。

如果粗粒度（如表）上已经加了IX锁，表示表的子节点的某条记录加上 X锁。此时如果想对整个表加上S锁，那么S锁会和IX锁产生冲突。

事务T用如下规则锁定结点Q:

必须遵守锁的兼容性矩阵。

首先，要锁定树的根，即最粗的粒度，可以以任何方式进行锁定。假如只读，就加上S锁，如果要进行修改，就加上X锁。

如果要在一个结点Q上加上S或者IS锁，那么其父节点一定要加上IX锁或者IS锁。

如果要在一个结点Q上加上X锁、SIX锁或IX锁，那么其父节点一定要加上IX锁或SIX锁。

事务T遵循两阶段封锁协议

解锁结点Q的时候，必须保证Q没有孩子正在被锁定。

直观来说，上锁是从根节点向下上锁的，放锁是从叶子结点一层层向上放锁的。

先在根节点上加上IX锁，表明下面的结点可能会产生修改

再在左子节点上加上IX锁，表明下面的结点可能会产生修改。

然后，在表这个粒度上，对表Fa加上SIX锁，表明要读取整个表的信息，同时可能对表中某些记录产生更改。

最后，在记录这个细粒度上，对某些记录上加上X锁，表示要更改这条记录

对于加了X锁的这条记录，可以去更改；但是对于其他的记录，不用再加上S锁了，可以直接去读。

对上面的兼容性矩阵的理解

S和X是对当前粒度加锁，表示所有子粒度全部加当前的锁。
IS和IX表示子粒度中有些加上了S或者X锁。
SIX表示当前粒度加S锁，子粒度有些加上了X锁，也就是所有子粒度都加上S锁，部分加上X锁。

🦄

例如，同一个结点上，SIX锁为什么和S锁冲突？ 因为SIX锁表明这个结点有些孩子加了X锁，但是这个结点加S锁表明这个结点的所有孩子都加上S锁。因此孩子中，加S锁会和加X锁产生冲突。因此，同一个父节点不可能同时申请到SIX锁和S锁。

如果要在一个结点Q上加上S锁或者是IS锁，那么其父节点一定要加上IX锁或者是IS锁👇

那么父节点不可能加S锁，因为S锁会加在父节点的更低层级。此时，父节点只能加IS锁或者IX锁。

如果要在一个结点Q上加上X锁、SIX锁或IX锁，那么其父节点一定要加上IX锁或SIX锁

如果要在一个结点Q上加上X锁、SIX锁或者IX锁，表示这个结点的全部子节点或者部分子节点上加X锁。那么父节点不可能加X锁，因为X锁会加在父节点的更低层级。此时，父节点只能加上IX锁或者SIX锁。

数据恢复

考试范围

主要内容：

数据库管理系统确保在系统发生各种故障的情况下，数据库能恢复到正常状态。讲解各种故障类型、基于日志的恢复策略、提高恢复效率的checkpoint方法,以及业界采用的ARIES恢复算法。不同的阶段（Phase）意义;脏表更新和checkpoint的关系；每一个phase的buffer里面存什么

课外学习：

ARIES算法如何在DBMS恢复效率和系统正常运行时效率两方面取得平衡？

主要内容

记录日志实现数据恢复

① 先记录日志，再修改数据库。

② 重演历史，然后进行Undo操作。

Stable Storage

理想的存储介质，现实中并不存在。任何故障中，都不会丢失数据。可以近似实现为：利用多个存储介质进行备份。

在这里，我们假设日志都会记录到Stable Storage中，不会丢失。

🦄

基本两阶段封锁协议可以保证冲突可串行化，但是无法保证数据可恢复性

因为假如事务A和事务B保持基本两阶段封锁协议，那么假如A要进行数据写入，会在写入之后立马放开X锁，那么事务B就有可能读取A的脏数据。假设B先提交，A再回滚，那么B提交的数据将不可恢复

🧘‍♂️

在这里我们假设，事务采取严格两阶段封锁协议，即X锁要保持到事务提交的时候再放开。

首先记录日志

T2的abort是用户正常执行的操作，T2事务回滚。回滚时，会记录Undo List，将T2事务已经做过的动作全部设置为旧值。

在<T2 abort>这一句话的后面，数据库发生了掉电等crush。

那么此时，首先需要重演历史，全部重演一遍（这是没有影响的），把数据库的状态恢复到crush之前的状态（回到现场）。与此同时，在重演历史的过程中，可以记录下来，哪些事务在crush的时候还没有用户手动提交或者回滚，生成一个Undo List。

然后，就要对Undo List 中的T4进行一系列Undo操作。从数据库发生crush的地方，Undo到事务T4刚开始的地方。在进行Undo操作的同时，要记录补偿日志，如图中的<A,100>。最后记录<T4,abort>。

checkpoint

刚刚我们重演历史的过程，是从日志的头部开始重演，一直重演到我们发生crush的地方。

每隔一定的时间，或者每隔一定日志的量，就会设置一个检查点。检查点的作用是确认一下，检查点之前的所有数据和操作，都已经正确反映到数据库里面了。

设置检查点的时候，需要将数据库中的数据强制刷盘一下。

设置检查点时，有以下三个步骤：

将所有日志中的记录存储到稳定存储器中。

把所有修改过的内存块写回到磁盘中。

在日志文件中写入一条记录：<checkpoint L>。其中，L表示处于该checkpoint的时候，恰好正在活跃的事务。

例如：

如图所示，设置checkpoint的同时，记录了当前正在活跃的事务。与此同时，还要将所有处于内存中的脏块写回。

重演历史的时候，从最近的一个checkpoint开始重演。重演历史的时候，要记录Undo List，Undo List的初始值就是checkpoint中保存的正在活跃的事务。

得到Undo List后，要进行Undo操作。进行Undo操作，直到T4事务刚开始的时候。与此同时，需要记录补偿日志。

设置了checkpoint，活跃的事务的初始值是T0和T1。重演历史的时候，从这个checkpoint开始即可。在重演历史的过程中，发现T1 commit，T0 abort。但是T2 start且没有commit或abort。因此，最终我们得到的Undo List只有T2

Undo 到T2开始的地方，并且记录补偿日志即可。

Group List

如果不用这种方式，每次commit日志一旦在内存中生成，立马就得写到磁盘中。采用这种方式，内存中的commit日志放满后，才一并写入到磁盘中。

非强制：事务commit后，不要求内存中的数据立即写入到磁盘中。（较好的方式）

强制：事务commit后，要求内存中的数据立即写入到磁盘中。（不好的方式）

模糊check point

本来，设置check point的时候，要求此时进行的事务全部停下来，然后把在内存中的脏页全部写出去，这样做其实限制比较大。

Fuzzy CheckPoint：做check point的时候，把内存中的脏页全部记下来，后面慢慢写回到磁盘去即可。

check point设置之后，脏页慢慢写回到磁盘中去的过程中，当脏页全部写出后，该check point变为一个成功的check point）在硬盘上面，有一个指针，指向最后一个成功的check point。重复历史的时候，从最后一个成功的check point开始。

尽早解锁的数据恢复

刚刚，我们采取的是严格两阶段封锁协议（不读脏数据），即在一个事务提交之前，这个事务修改过的数据不会被其他事务读取或写入。

现在，我们可以针对一般两阶段封锁协议，提供数据恢复算法。一般两阶段封锁协议，支持一个事务还未提交的时候，其写入过的数据就可以被其他事务再次写入。

此时，我们不能恢复旧数据，但是我们可以恢复做过的操作。例如，事务A把数据X从100加上50变成150；事务B把数据X的150读取，然后变成250，然后B事务提交。此时，我们如果按照前面的恢复方式，会对事务A进行Undo，把X设置回100，但这个结果是不对的。因此，我们可以对加上50这个操作进行恢复，例如对250这个数据减去50，这叫做逻辑Undo。

例如，对C进行更改的时候，做了一个+（-100）的操作。这时候，要记录一个日志：

operation-end后面跟的(C, +100)表示，要恢复这个操作，需要给C加100。（要撤销操作应怎么做）。

这样记录的原因是：假如给C减去100的操作没有完成，即还未记录的时候，就发生了crush。那么，此时就要对C进行物理Undo，直接把C由600恢复为旧数据700即可。

在这句话后面：

T0事务决定abort。

此时，对T0事务进行Undo操作，并记录补偿日志如下：

C加上100，而不是恢复为700。

发生crush之后，先从check point开始向下重现历史，得到Undo List：T1、T2。

然后，从crush的地方，Undo到T1事务开始的地方。由于crush的地方操作O5还没有完成，因此对C数据进行恢复的时候，进行物理Undo就可以。

因此，先做物理Undo，将C设置回400，然后补偿日志中记录<T2 abort>；再回滚操作O4，对C自增300，因此此时C变为700，也要记录在补偿日志中；然后在补偿日志中记录<T1, O4, operation-abort>。

最后，将B设置回2050，并记录在补偿日志中。最后，记录<T1 abort>。

ARIES 恢复算法

1. 每一个日志项，都有一个日志编号（LSN）。每一个数据页里面，都会记录一个LSN编号。数据页中记录的LSN编号表示：最近这个数据页中，反映的是哪一个日志中的操作。

LSN的特点：① 顺序递增

② 每一个内存页中，都有一个Page LSN，用来标记这个页最近反映的是哪一个日志项修改的结果。

脏页表：Dirty Page Table：

脏页表记录在日志当中，在设定CheckPoint的时候，当前的内存中脏页的表，需要记录下来。

每一个脏页表中的页，都有一个Page LSN，反映当前页是哪一个日志项最后修改了它；

每一个页还会记录一个Rec LSN，反映这个数据页到达了内存之前，是哪一个日志项最后修改了它。

LSN表示该条日志的编号；

TransID表示该条日志对应的事务是什么

UndoNextLSN表示，如果要Undo这一个事务，下一个需要Undo的日志项是什么。把所有相同事务的Undo项串起来，方便Undo的加速。

RedoInfo表示重复历史的相关信息。

上面，日志项一项一项地记下来，4’为4 Undo的结果，也就是4的补偿日志。4’指向3表示，记录完补偿日志4’，下一个需要Undo的日志项是3。

例如上述例子。在Stable Data中，也就是正确反映到数据库中的内容，对于ID为7200的页，最后更改这一页的日志的编号是4404。但是在数据内存中，对于ID为7200的页，最后更改这一页的日志的编号是7565，这表示这一页在内存中，又被日志更改。

在Stable Log中，例如7565这条日志记录，表示对于事务T143，将编号为7200的页的第二个数据，由60改为80。

日志记录，有在Stable Storage的，也有在内存中的；

例如，对于编号为4894的数据页，数据内存中显示最后对这一数据的更改是编号为7567的日志项，对应了Log Buffer中编号为7567的日志项

脏页表：表示缓冲区中，哪些数据是脏的。

例如，记录7200 7565 7565表示，缓冲区中page_ID为7200的页是脏的，最新修改它的是7565这个日志，并且从7565这条日志之后的更改，都没有反映到数据库系统之中。

又例如，4894 7567 7564表示，缓冲区中page_ID为4894的页是脏的，最新修改它的是7567这个日志，但是，从7564这个日志开始，更改就没有反映到数据库中了。

🧘‍♂️

因此我们可以大胆的进行理解：

可以理解为：Rec LSN记录的是磁盘中，最后一次对该数据产生更改的日志项编号；

Page LSN记录的是日志内存中，最后一次对该数据产生更改的日志项编号。

做Check Point的时候，要记录下来

① 当前活动事务表

② 脏页表

③ 对于每一个当前活动的事务，要记录下来该事务最近的一个日志项是什么。LastLSN。

ARIES算法的数据恢复：

分为三个阶段：

① 分析阶段：

从最近的check point开始，分析一下。

（i）得到一个Undo List。

（ii）还要得到一个Dirty Page Table。由于在Check Point得到的Dirty Page Table不是最新的，因此首先希望得到发生crush的时候，最新的脏页表。因此，要从check point开始向下更新。

（iii）得到Redo LSN，即真正的Redo操作，应当从哪里开始。（也就是重复历史操作，应当从哪里开始）。在ARIES算法当中，Redo可能是在Check point 之前，并不一定从Check point开始。所有Rec LSN的最小值，就是Redo的起点。（这是因为，Rec LSN记录的是，磁盘中最后一次对该数据产生更改的日志编号，Rec LSN之前的日志项，都已经正确反映到数据库中了）。

② Redo 阶段

从所有脏页表中Rec LSN中最小的那个日志项开始，重现历史。

③ Undo 阶段

和前面的原理相同，利用Undo List，直到Undo到Undo List中所有事务到达开始的地方。

check point中，记录了：

① 活动事务表：T145，并且最后对事务T145进行修改的LastLSN是7567。

② 脏页表：

最新对页号4894的页产生更改的是日志项7567，而正确反映到磁盘中的最后一个对4894页产生更改的日志项是7564；

最新对页号7200的页产生更改的是日志项7565，而正确反映到磁盘中的最后一个对7200页产生更改的日志项是7565；

阶段一：分析阶段

从最近的检查点开始，分析到crush的地方。在这个过程中更新脏页表，并且得到Undo List，以及Redo LSN。

例如，首先碰到T146 begin, 因此在活动事务表中记录一项T146；然后碰到T146的修改操作，然后在脏页表中记录一项T146。

阶段二：Redo阶段

Redo的起点，是更新过后的脏页表中，Rec LSN的最小值。

阶段三：Undo

Undo的结束点，在Undo List中开始最早的事务的开始点，并且对于每一个事务的Undo，由于各个事务的日志项都是串起来的，因此Undo的时候不用一条一条地Undo，只需要根据串起来的日志项向前Undo即可。Undo的起点，是更新过后的活动事务表中，记录的LastLSN的那条最小值。

🧘‍♂️

下面我们对ARIES算法进行一个详细的总结：

在生成CheckPoint的时候，CheckPoint中会记录当前活动事务表，和脏页表。

在当前活动事务表中，记录了活动事务，以及最后一次对该事务的更改，处于哪一个日志项当中；

在数据恢复的过程中

1. 第一阶段是分析阶段，从上一个有效的检查点开始，一直分析到crush发生的地方。

在分析的过程中，不断更新当前活动事务表，以及脏页表。假如遇到一个事务开始了，那么就在当前活动事务表中增添一项，遇到一个事务commit或者abort了，就在当前活动事务表中减少一项；

假如遇到某个日志项对某一页产生了更改，就要更新脏页表中的Page LSN，假如遇到某个日志项对脏页表中没有的页号的页产生了更改，就要在脏页表中添加一项，Page LSN和Rec LSN设置为当前日志项。

最后，当分析到crush的地方，我们就得到了一个更新后的活动事务表，作为Undo List，并且得到了一个更新后的脏页表。

2. 第二阶段是Redo阶段，Redo阶段的起点是更新后的脏页表中，Rec LSN的最小值的日志项。一直Redo到crush的地方。

3. 第三阶段是Undo阶段，Undo阶段的起点是活动事务表中，记录的Last LSN中的最大值，从Last LSN开始，对活动事务表中的每一个事务向前进行串在一起的指针遍历，直到Undo到各个事务都经过了<start>。

索引

考试范围

索引是数据库管理系统提高数据访问速度的主要措施之一。介绍稠密索引和稀疏索引的原理和区别，重点讲解B+树索引, 以及面向写优化的索引(buffer tree、LSM tree)。

课外学习：

1）假如已知B+-树索引项的数目，如何估算B+-树的高度和结点总数？

2）LSM树索引相比B+树索引有什么优势？

主要内容

索引：加速数据库数据查找的设施

主索引

辅助索引

稠密索引

每一个数据文件中的索引值，都要出现在索引文件里面。

稀疏索引

未必每一个数据文件中的索引值，都要出现在索引文件中。

多级索引

如果主索引不适合内存，那么访问会变得十分昂贵。

解决方案：将保存在磁盘上的主索引（索引文件很大）看作一个顺序文件，在主索引上进一步构造稀疏索引。

外部索引—主索引的稀疏搜索；主索引—主索引文件的搜索；

如果外部索引仍然太大，可以针对外部索引进一步创建索引，以此类推。从记录文件中插入或者删除时，必须更新所有级别的索引。

b+树索引

B+树的每一个节点的大小和磁盘的一个块的大小是一样的

例如是4K的大小。因此B+树的分叉可以有很多个（除了根节点以外，其余节点最少含有n/2上取整个value，最多含有n个value，最多含有n-1个key）。

叶子结点也是最少含有n/2上取整个孩子指针，因此最少含有n/2下取整条记录。

下面给出相应的一些数据进行思考：

n：3

内部结点指针最大个数：3

内部结点指针最小个数：2

叶子结点孩子最多个数：2

叶子结点孩子最少个数：1（n/2下取整） 2. n：4

内部结点指针最大个数：4

内部结点指针最小个数：2

叶子结点孩子最多个数：3

叶子结点孩子最少个数：2（n/2下取整） 3. n：5

内部结点指针最大个数：5

内部结点指针最小个数：3

叶子结点孩子最多个数：4

叶子结点孩子最少个数：2（n/2下取整） 4. n：6

内部结点指针最大个数：6

内部结点指针最小个数：3

叶子结点孩子最多个数：5

叶子结点孩子最少个数：3（n/2下取整）

假如一共有K个索引项，每个结点的分叉最多是n个，最少是二分之n上取整个，那么B+树的最大高度为：

加一是因为算上根节点，根节点最少可能是二叉。

B+树的最小高度是

b+树的插入操作

🧘‍♂️

和ADS课上的讲的比较像

b+树的删除操作

当一个block中的记录被删除时，判断此时这个叶节点中记录的数量是否大于二分之n下取整，如果小于了，那么首先寻求和兄弟结点合并。如果可以和兄弟结点合并，就要在合并以后，判断父节点的指针数目此时是否大于二分之n上取整，以此进行类推；如果不能合并（兄弟结点中记录的数量加上这一被删除记录后的结点的记录数量超过了n），那么就从兄弟结点中借一条记录，补充到这个结点中。

🧘‍♂️

注意需要关注的是插入和删除之后的叶节点中的value的个数还有父节点指针的个数一个是n/2下取整，一个是n/2向上取整

相应的b+树的计算

🧘‍♂️

这是一道重要的例题，下面给出比较详细的解析

假设一个block的大小是4K，每一个person的大小是68，因此一个block中的记录数量是60个。为了记录1000000个person，我们需要16667个block。

下面也就是最为关键的b+树的n值如何进行计算

🧘‍♂️

联系primary key和指针的大小进行运算

下面计算B+树的n。由于B+树的一个块是4096大小，包含n个指针（大小为4），与n-1个关键字大小（为pid，大小为18），因此计算公式为：（4096-4）/(18+4) + 1 = 187。

因此，对于内部结点，其孩子指针最多有187个，其孩子指针最小有94个（187/2上取整）；对于叶子结点，其值最多有186个，最少有93个(187/2下取整)。

因此可以计算出指针和叶节点中value的个数大小

🧘‍♂️

指针注意进行向上取整，value注意进行向下取整

接着，对于三层高的B+树，最少能够索引的记录的数量为：2（根节点）94（第二层）93 = 17484条； 最多能够索引的记录数量为：187187186 = 6504234条。两层太少，四层太多，可以判断出，表示1000000个person，需要这样的B+树恰好是三层。接着，求出用三层的n为187的B+树来表示1000000个person，结点数目的最小值和最大值

最大值：对于叶节点，由于叶子结点最少有93个值，因此叶节点最多个数可以用1000000除以93，得到10752.59，注意这里要进行下取整，否则将至少有一个叶节点的值的数量小于93个。其余第二层与根节点的计算以此类推，由于第二层的孩子个数最少为94个，因此第二层将10752除以94，并且向下取整。

最小值：对于叶节点，最多有186个值，因此叶节点最少个数可以用1000000除以186，得到5736.344，注意这里要进行上取整，否则将至少有一个叶结点包含的值大于186个。其余第二层与根节点的计算以此类推，由于第二层的孩子个数最多为187个，因此第二层将5377除以187，并且向上取整。

🧘‍♂️

然后针对每一层进行逐层递归计算的操作

B+树文件组织：

B+树的叶子结点不再放入记录指针，而是放入记录本身。

B+树索引可以有多种建立方式：

例如，可以根据二元组甚至多元组建立索引。

B+树批量装载与自下而上构建：

方案一：将数据按照Search Key先排一下序，然后再进行插入。

好处：可以减少IO操作。

缺点：大多数叶节点是半满的，B+树效率较低。

方案二：自下而上构建B+树。

首先将数据按照Search Key排一下序，然后尽量将叶子节点从左到右放满。

上述排序过程，存在问题：假如需要排序的索引能够放在内存当中，那么内部排序一次排好。假如需要排序的索引不能放在内存中，那么需要使用外部排序方法。

自底向上构建B+树构建完成后，如何写回到磁盘中？可以一次性写回去，也可以边构建边写回去。

最好的方式：一层一层写回去，从叶子层开始，层序向上遍历。

这样做的代价是：

这样的好处是：假如我们要顺序访问所有的索引项，这些索引项是全部放在磁盘的同一区域的，且是连续放置的。

假如有两颗B+树，都是由底向上构建起来的，那么此时如果我们想要Merge这两颗B+树，如何做？

我们直接重建一个新的B+树就可以了，在重建之前，我们需要先对叶子结点的键值进行排序

这两颗B+树的叶子结点都是有序且连续在磁盘中存放的。因此，我们对这两个B+树叶子结点的键值直接进行一次Seek，再进行简单的Merge操作，就可以一次排好序了。

例如：假如我们要将下面的键值，和刚刚的那个已经写回到磁盘中的B+树Merge起来：

第一步：先对这些键值排好序。

第二步：从磁盘中读取上一个B+树的所有叶子结点，进入内存当中，由于上一个B+树的叶子结点都是连续存放的，因此需要1次Seek，6次Block Transfer。

在我们意识到，内存和磁盘的传输块大小较大，为4k左右、cache和内存的传输块大小较小，为64B左右，我们可以用一种较为巧妙的结构，来利用cache的这种块传输特性。

例如，把B+树的结点和指针分开来排列；又例如，把B+树的每一个结点上，建立一个小B+树，用来快速查找键值。 • Index On Flash 闪存索引

写优化树结构：LSM-tree

首先，内存中有一个B+树L0；内存中的B+树写满了以后，马上写到磁盘中去。而且这个写操作，只需要把B+树叶子结点上的这些块写进磁盘，可以做到刚刚所述的 1次Seek，然后连续写入。

下次，内存中的B+树又满了，就可以和磁盘中的B+树进行合并，相当于内存中B+树的叶子，要和磁盘中B+树的叶子合并。因此，需要两次Seek，加上合并好的树的结点数目个Transfer + 磁盘中B+树叶节点块数个Transfer

在磁盘中，如果L1这个B+树满了（磁盘中对各个大小的B+树都有大小限制），那么就会自动拷贝到L2的位置，把L1的位置空出来，以此类推。

在内存中B+树的构建，都是先将叶子结点键值排序，然后利用从底向上方法构建B+树的。

🧘‍♂️

LSM的好处是：顺序读写，磁盘访问次数变少。

LSM的坏处是：假如我们要查找一个键值，本来我们只需要在一个B+树中查找，现在我们要在L0、L1、L2…这些B+树种，都要查找，查询代价增大。

但是，上述方法还有一个缺陷，就是每次内存种的B+树满了以后都需要合并，合并次数太多。

因此，有一种优化结构，如下：

内存中的B+树满了，先写到磁盘中；下次内存中B+树又满了，又写到内存中

直到磁盘中L0级别大小的B+树达到K个以后，再一起合并成一个大的L1。

上述优化结构，虽然减少了Merge的次数，且由于每次合并是顺序访问，减少磁盘I/O的次数；但是缺点是查找更加麻烦。

上述优化结构，使得磁盘中B+树的数量更多，因此查找一个键值，需要每一个B+树都查找一遍。

为此，可以在磁盘上每一个B+树上加上一个不容过滤器。每次要查找一个键值时，首先判断一下这个键值可不可能在这棵树中；若不可能，那么这棵树根本不用去查找。

buffer tree

向B+树中插入一个键值时，不是直接向下传输，传到叶节点中，而是先放在内部节点中的一个小小的Buffer中。

缓冲区满了以后，插入的内容会移动到更低的级别，也就是下一层，这一层的子节点的buffer。

假如一个buffer tree的内部结点需要分裂，那么缓冲区中的内容也会分裂，各自分裂进入各自的部分。

好处：可以减少查询开销。每次查询有可能不必查询到叶子结点才能得到结果。

坏处：相比LSM树在磁盘中顺序存放的结构，Buffer Tree的磁盘I/O开销增大。

查询处理

考试范围

查询处理是数据库管理系统的主要功能之一。介绍关系数据库管理系统查询处理的主要过程，关系数据库基本操作（选择，连接，排序等）的算法实现及代价估算，以及关系表达式的求值方式。Nest join, hash; merge

课外学习：1）关系表达式求值的流水线方式有什么优点？是否所有的关系操作都可以采用流水线方式处理？

主要内容

查询流程优化逻辑优化

选择运算尽量向叶子节点推、连接代价小的先连。

基础流程优化、物理优化

例如，选择操作是一个算子，但是具体实现这一算子的算法有很多，例如：线性扫描、B+树索引等。通过代价估算，来选择最优的算法。

再例如，自然连接，也有很多算法，例如：Merge join、Hash join等。执行方式，可以是顺序执行，也可以是流水线的。

代价估算

代价主要以时空的花费来衡量，在这里，为了简单起见，我们只估算硬盘I/O的时间。

主要涉及的到的内容是：

该操作会引起多少次磁盘的寻找 seek（把读写头定位到扇区）

该操作会引起多少个块的读操作

该操作会引起多少个块的写操作（一般写操作要比读操作代价要高些）

为了简单起见，我们将读写合并，作为一次“传输”操作。

🧘‍♂️

因此，我们只是用磁盘的块传输次数与寻道次数作为成本的度量。

传输一个块的时间tT与一次搜索的寻道时间tS取决于数据存储的位置（具有4KB大小的块）。

磁盘与固态硬盘的这两种时间：

可以看到，由于搜索（磁盘的寻道）是机械运动，因此往往都比一个块进行Transfer的时间大数倍。

且为了简单起见，我们忽略了CPU成本。并且，我们在成本公式中忽略了将输出写入磁盘的成本。

衡量算法代价，还有一点要说明的是：真正进行执行时，内存（缓冲区大小）是有限的。假设内存足够大，可以把整个数据库都装到内存中，那么就只需要一次磁盘的seek操作，然后全部读进内存中就好。

但是实际上，我们衡量算法代价时，考虑的往往不是最优情况，相反是最坏情况。可用的缓冲区实际内存量取决于其他并发查询和操作系统进程，只有在执行过程中我们才知道有多少缓冲区的大小可以用。

我们经常使用最坏情况估计，假设只有操作所需的最小内存量可用。

并且，我们假设我们需要的数据都必须在磁盘中去读，并没有在内存（缓冲区）中命中

首先是选择操作

线性扫描

算法A1：线性搜索。扫描磁盘中的每个文件块并测试文件块中的所有记录，看它们是否满足选择条件。把每一个文件块，一块一块读到内存中来。

最差情况成本：

我们假定这些块在文件中是连续存放的（一次磁盘查找/定位操作，就可以找到文件的头）。假如说我们对Student这个关系进行查询，这个关系在文件中有br块，这br块在文件中是连续存放的。那么，我们只需要在文件中进行一次定位操作，再将这br块一块一块读到内存中就可以了。

因此，最差情况成本是：

假定，我们查找的是Key，例如，查找学号是3210100000的学生。那么，当我们找到了这个记录时，查询操作就可以停止了。

因此，我们需要一次磁盘读写头的Seek定位操作，加上平均起来br/2次块传输操作。因此，此时最差情况成本是：

索引扫描——使用索引的搜索算法

算法A2：（主B+树索引/聚类B+树索引，key上相等）。检索满足相应相等条件（Key上的等值查找）的单个记录。

B+树的树节点一般在磁盘中是不连续分布的，因此，访问到每一个节点，包括最后在实际存储数据的文件，都需要进行一次Seek操作（读写头定位）。

算法A3：（主B+树索引/聚类B+树索引，非key相等）。

检索满足相应相等条件（非Key上的等值查找）的单个记录。

虽然，对于非Key，这样的记录可能有多条，但是好在有一个前提：就是对于我们要查找的这个不是Key的属性，它在文件中已经排好序了。

因此，我们在查找完树高次B+树节点后，只需要在进行一次定位即可将文件中这些非Key的记录全部查找到。

其中，b表示，匹配的记录所占块的个数。

例如，上面的例子中，文件中的块已经按照查询的条件排好序，连续存放，而匹配的记录一共四条，占用两个块，因此b = 2。

算法A4：（辅助B+树索引，Key上相等）

对于辅助索引，与主索引相比，特点是，在查找的属性上面，文件中的存储并不是排好序的。例如，我们要查找的Key是学号，而在文件存储中，是按照系名进行排序的。

但是，如果此时是Key上相等，而由于Key对应的记录是唯一的，因此，查找Key时，辅助索引与主索引是没有区别的。

算法A4’：（辅助B+树索引，非Key上相等）

如果是辅助索引，还是搜索的还是非Key。这说明我们搜索的东西在文件中既不是排好序的，而且还不是唯一的，这样就麻烦一些。

那么，首先我们对树高那么多的块进行搜索，由于树节点在文件中不是连续存放的，因此每次我们都要进行一次磁盘读写头重定位tS与一次块的传输tT。

然后，我们搜索m个放置实际记录指针的块。最后，我们对这m个放置实际记录指针的块中的指针，进行n条记录的查找。此过程需要（m+n）个磁盘读写头重定位tS与块的传输tT。

范围查找，涉及比较的选择

可以用线性文件扫描与二分搜索，即不利用针对该查找属性建立的B+树索引。也可以利用针对该查找属性建立的B+树索引，通过以下方式使用索引，完成范围查找。

算法A5：（主B+树索引，比较）

查找该属性大于等于A的记录，可以在B+树中找到等于A的第一个块，然后对剩下的进行连续的扫描。（因为这个属性在文件中是主索引，因此是记录是按照该属性排好序连续存放的）

b表示，符合这个大于等于的条件的记录存放于多少个块中。（需要在查找前进行估算）

因此，需要进行树高次读写头重定位操作与块传输操作，与一次读写头重定位操作找到大于等于A的第一个块，然后b次块传输操作，进行连续的扫描。

查找该属性小于A的记录，不需要利用B+树索引，只需要对放置记录的文件，重头开始连续扫描，直到第一个该属性大于A的记录。（因为查找的属性对应的是主索引，记录在文件中是按照该属性排好序，连续存放的。）

此时，需要的cost只有ts 加上 b*tT。

算法A6：（辅助B+树索引，比较）

查找该属性大于等于A的记录，使用索引查找到第一个大于等于A的记录的叶节点，从这个叶节点开始，依次对该属性的B+树的叶节点向右扫描，得到每一个指向记录的指针。

查找该属性小于A的记录，直接从头开始扫描该属性的B+树叶节点，直到第一个该属性大于等于A的地方，找到这之间的所有的指向记录的指针。

在这种范围查找，且对应查找属性是辅助索引的情况下，线性查找往往花费更少。

多个查询条件的查询

算法A7：（使用一个索引，联合选择）

先对其中一个选择条件进行选择（这可以用前面说到的A1算法到A6算法的任何一种）。选择的结果要过滤尽可能多的记录。

例如，用第一个限制条件可以过滤百分之90的记录，用第二个限制条件可以过滤百分之99的记录，要先用第二个限制条件进行选择。

然后，把这个限制条件选择后的这些记录读取到内存（buffer）中去，然后在内存中去测试其他条件。

算法A8：（使用复合索引，联合选择）

优先使用已经建立好的复合索引。最好的情况就是，要选择的这几个条件刚好就有一个已经建立好的复合索引。

算法A9：（通过标识符的交集进行联合选择）

对每一个条件，都利用前面说到的A1到A6算法，找到相应符合的记录集合，然后再取交集。

或条件的查询

算法A10：（通过标识符的并集进行析取选择）

请确保所有限制条件对应的属性，都有建立相应的索引，否则，要利用线性扫描来进行上述查询。

对每一个条件，都利用前面说到的A1到A6算法，找到相应符合的记录集合，然后再取并集。

排序操作——simple version

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

对于不适合内存的关系，利用外部排序。假设初始的关系非常大，没办法全部放入内存：

因此，将初始的关系分成一段一段，读到内存里面，然后就可以对这一段一段的关系进行内部排序算法，例如快速排序等。每一段在内存中排好序了，要先写出去，生成一段一段的归并段。

对于这个过程的cost:

首先，对于传输操作。

假设存储这个关系的文件一共有br个块；内存中最多放入的块一共有m个块。因此，我们要将br个块分为br/m上取整个段，一段一段地放入内存中进行内部排序。这个过程中，每一个文件中的块都一定会进入到内存中一次。

接下来，在文件中进行内部排序完成后，每一个块都会写出来一次。因此，这个过程传输操作的cost是2*br。

然后，对于磁盘读写头重定位操作。

要将br个块分为br/m上取整个段，一段一段地放入内存中进行内部排序，在读入的时候需要br/m上取整次磁盘读写头重定位操作。因为每次是要把一个段放入内存中进行内部排序，下次就要重新定位下一个段。此外，对于每一个段，在内存中排好序了要写出来。因此，重定位操作的cost是2*br/m上取整。

生成了小的归并段，如何归并呢？

仍然假设这个关系共有br个块，内存中最大容量为m个块，因而有br/m上取整个归并段。

分为两种情况。

（1）归并段的数量严格小于内存最大容量的块数

假设生成的小的归并段的数量为N，内存中最大块的数量是M。假设N<=M-1,那么只需要单次合并，就可以解决。

此时，在内存中，使用N个块作为输入缓冲块，使用1个块作为输出缓冲块。将每次运行的第一个块，读取到输入缓冲块中。

最初，将刚刚生成的br/m上取整个归并段，每一段的第一个块（即该属性值最小的块）放到内存中（一共有N个，N=br/m上取整），在内存中保留一个块作为输出缓冲块。然后，进行归并，把归并的结果写到输出缓冲块中。一旦某一条记录被归并掉，那么这条记录就会从它所属的内存中的那个输入缓冲块中删除。如果内存中某个输入缓冲块的内容被删除空了，那么就将对应的归并段的下一个块拿上来。

对于输出缓冲块，每当它被写满了，就将其写出来，写到磁盘中。

例如，假设生成了2个归并段。每一个段中有4个块，这说明内存中最多存放4个块，这个关系一个有8个块。

此时，由于2<4，所以一次归并就可以解决问题。首先，将这两个归并段的第一个块放到内存里面。(1,3,5)、(2,4,6)，进行归并。先在输出缓冲块中写入1，对应删除(1,3,5)中的1。直到输出缓冲块写满，具有(1,2,3)，下一个元素4写入时，就要先把输出缓冲块中的内容写到磁盘中。

接着，输出缓冲块要写入5，此时有一个输入缓冲块变空了。这个输入缓冲块的内容就要被(7,9,11)来代替。

（2）归并段的数量大于等于内存最大容量的块数

需要用到多轮次的合并。

在每一个轮次中，M-1个归并段被归并起来。

例如，假设M为11，原本有90个归并段。那么每次放入10个归并段，合为1个。最后会产生9个较大的归并段。将这9个较大的归并段放入内存中，再进行一次归并，就会最终得到一个归并结果。

代价分析：

Transfer：

最初始，生成的最小归并段的数目：

由于每一轮次（将小的归并段，通过归并和为一些大的归并段称为一轮。例如，刚刚90个小归并段，和为9个大的归并段，这个过程叫做一轮）的运行结果，可以将归并段的数目减少到原来的M-1分之1，因此，轮数可以表示为：

刚刚说过，生成初始的归并段需要2*br次的传输tT，与2*br/m上取整次的读写头重定位tS。

其实，每一轮次发生的事情都要将所有记录的块读入到内存中一次，还要写出到磁盘中一次。因此，每一轮次，都需要2*br次的传输tT。

因此，我们在整个归并过程中，产生的块传输次数tT如下表示：

Seeks：

最初，我们生成最小归并段的数目：

刚刚说过，生成初始的归并段需要2*br/m上取整次的读写头重定位tS。

在对初始的归并段进行归并的每一轮过程中，每一个块的读写，都需要一个单独的读写头重定位Seek操作（这是因为，读写操作是不知道顺序的。读入块的顺序也是不清楚的）。因此，在每一轮过程中，发生的读写头重定位Seek操作次数就是2*br。

同时，我们假定最后一个轮次生成的归并结果不再写回到磁盘中。

因此，最终我们得到，在整个归并的过程中，产生的读写头重定位次数tS如下表示：

减一是因为最后一次归并完成后，生成的结果我们不再写回到磁盘中，因此少了br次读写头重定位操作。

排序操作——advance version

为每一个归并段，分配多块输入缓冲区。

假设我们为每一个归并段，分配bb个输入缓冲区块。这样以来，原来一次Seek操作，只能读写进去一块；现在一次Seek操作，能读写进去bb块。

但是，这会导致轮次增加。因为，原来一次归并，能够处理M-1个归并段，现在由于给每一个归并段都分配bb块输入缓冲区，现在一次归并只能够处理

M/bb - 1个归并段了（输出缓冲块的块数也变成bb个）。

由于现在一次归并能够处理M/bb(下取整)-1个归并段，因此，轮次表示为：

Transfer：

但是传输操作是没有改变的，每一轮都要进行一次所有块的读入，都要进行一次所有块的写出。因此每一轮的传输操作次数依旧是2*br。

因此，对于这个版本，传输操作tT所用的次数一共是：

（假设最后一次轮次生成的归并结果不再写回到磁盘中去）

传输次数增大了，因为轮次增加。

Seeks：

最初我们将原始记录文件，生成初始的归并段需要2*br/m上取整次的读写头重定位tS，这是不变的。

然后，每一轮，我们需要的读写头重定位次数现在变为了：

因为，一次Seek可以读写bb个块。

总轮次：

因此，对于这个版本，读写头重定位的总次数为

什么都按照大的算（对于取整）。

bb的增加，虽然会减少每一轮运行时的读写头重定位次数，从br次到br/bb次，但是会增加轮数，因此还会增加数据传输的次数。

求导数，来获得bb最佳应该设置为多少。

连接操作（重点关注） 不用再从内存读出来

双重循环连接

假设外循环的对应的关系为r，对应的块数为br；内循环对应的关系为s，对应的块数为bs。

那么代价分析如下：

Transfer：

这个算法要把外循环关系的记录每一条和内循环关系中的每一条记录进行比较，因此

外循环关系的每一块，都只需要进入到内存中一次。但对于外循环关系的每一个记录，内循环关系的每一块都要进入内存一次进行匹配。

因此，传输次数表示如下

其中，nr为外循环关系记录的数目。

Seeks：

原因是：由于外循环中，每一个块都要进入到内存中一次。因此对于外循环关系r，读写头重定位的次数是br。但是对于内循环，它是可以去遍历内循环的文件的，内循环的文件s是连续存储的，因此每次进入内循环，只需要读写头重定位一次。退出内循环后，回到外循环，需要重新对外循环关系进行读写头重定位。因此，外循环进行多少次，内循环关系的读写头就重定位多少次。上述算法中，外循环每一个元组都要和内循环关系的整个关系进行匹配，因此外循环关系有多少个元组nr，外循环就要进行多少次，内循环关系的读写头就要重定位多少次。

因此，Seek的总次数为nr + br。

块嵌套循环连接

内部关系的每个块都与外部关系的每个块配对。

对于外循环的每一个块，将内循环关系的每一个块读进内存中。然后在内存中针对这两个块进行充分的连接。

transfer:

因此，最坏情况下，传输操作会发生的次数为：

这是因为，外循环关系的每一个块肯定要进入内存中一次。对于外循环关系的每一个块，内循环关系的每一个块进入到内存一次，这需要br*bs次传输。

Seeks：

对于内循环，一次定位即可将内循环关系的文件顺序地读到内存中去。因此，外循环进行几次，对于内循环关系就会发生多少次读写头重定位操作。

但是每次退出内循环，回到外循环时，都需要对读写头重新定位，以使得外循环关系的文件的下一块进入到内存中。

因此，外循环有多少个块，对于外循环关系文件的读写头重新定位就会发生多少次，对于内循环关系文件的读写头重新定位就会发生多少次。

因此，Seek操作总共发生的次数为：

因此，选择块数少的关系作为外关系比较好。这样不仅能够减少seek的次数，还能够减少Transfer的次数。

最好情况：假设内存空间足够大，这样两个表都直接读进内存中去（Transfer为br+bs次），读写头重定位两次（找到这两个表）即可。

假设用于连接每个关系的缓冲区不止一个，有多个。

我们每次退出内循环，回到外循环时，都要进行一次读写头重定位操作。为何不让这次读写头重定位操作一次读取多个块？

现在，假设内存中最大容量是M个块。留一个块作为输出缓冲区，只需要留一个输入缓冲块留给内循环关系（因为不管留几个块给内循环，内循环都是只需要重定位一次，就可以全部读进来），剩下M-2个块全部留给外循环，作为输入缓冲区。

Transfer：

此时，外循环的每一个块还是必须要读入内存中一次。这消耗br次Transfer。

但是，每一轮循环，外循环关系读进内存的有M-2个块，因此循环次数变成了原来的M-2分之一。现在循环次数变为：

对于每一轮循环，都需要将内循环关系的所有块全部读进来，因此，Transfer的Cost为：

Seeks：

对于外循环关系文件，由于循环进行次数为：

因此，进行每一轮循环时，要进行一次外循环关系的读写头重定位。

对于内循环，在每次执行内循环的时候，要进行一次内循环关系的读写头重定位。

因此，Seek的总次数为：

① 如果连接的属性是内关系的Key，只要连接上了，就可以停止内循环了。

② 内关系的循环，正序遍历与倒序遍历交替进行。提高缓冲区的命中率。

索引嵌套连接

需要连接的属性上，内循环关系针对该属性有一个B+树索引。那么，就没必要每次去遍历内循环的每一个元组。我们只要根据外循环该条记录对应的属性值，在内循环的B+树索引中查找即可。

① 假如外关系在内存中分配1个缓冲区

Transfer：

对于外关系，每一个块都会传输进入内存中，因此需要这需要br次Transfer操作。

对于内关系，不用将它读入内存中，直接利用B+树查找即可。内关系不需要传输操作。

Seek：

对于外关系，每一次退出内循环，接着外循环进行时，都要进行一次读写头重定位。因此，需要br次Seek操作。

② 假如外关系在内存中分配M-2个缓冲区

Transfer：

对于外关系，每一个块都会传输进入内存中，因此需要br次Transfer操作。

Seek:

对于外关系，每一次退出内循环，接着外循环进行时，都要进行一次读写头重定位，因此，读写头重定位的次数与循环的轮数相等。

因此需要br/M-2上取整次Seek操作。

（4）归并连接

假如两个关系是按照等值连接的属性排好序的，那么就可以使用归并连接。

① 假如每一个关系，在内存中只分配一个输入缓冲区：

Transfer:由于两个关系的每一个块一定会进入内存一次，因此，代价为br+bs。

Seek：Merge操作中，两个关系中的块进入内存的顺序是不固定的，因此，最坏情况每一个块进去内存都要进行读写头重定位。因此代价为br+bs。

② 假设每一个关系，在内存中分配bb个输入缓冲区： Transfer次数不变，依旧是br+bs。 Seek代价减少，变为：

因为，一次Seek，可以读进内存bb个块。

③ 假设内存上限为M块，怎么分配输入缓冲区的块数（s关系分配k块，r关系分配M-k块），从而使得Seek的代价最少？

Transfer的代价是和刚刚一样的，因为不管怎么分配内存中输入缓冲区的块数，两个关系每一个块都要输入到内存中一次。

但此时Seek的次数为：

对于关系r，一次读写头重定位可读进内存xr块，对于关系s，一次读写头重定位可读进内存xs块。

答案：应该如下分配：

哈希连接

通过计算一个哈希函数，对关系r的连接属性与关系s连接属性，通过计算哈希值进行分片。

把大的关系分成一片一片的小关系。

原理是：能够连接上的两条记录（等值连接），利用对应的连接属性（在两个关系中值相等）算出来的哈希值是相同的。

因此，将关系s分片中的分片0，与将关系r分片中的分片0，其中包含了所有哈希值为0的，能互相进行等值连接的记录。

我们只需要对关系s算出的分片0与关系r算出的分片0进行连接、对关系s算出的分片1与关系r算出的分片1进行连接、对关系s算出的分片2与关系r算出的分片2进行连接……最后再进行组合就可以了。而不需要考虑关系s算出的分片0与关系r算出的分片1进行连接等，因为哈希函数是相同的，假设s中某一个记录该属性的值被映射到片0，r中某一个记录该属性的值被映射到片1，那么s中的这一个记录和r中的这一个记录在连接属性上一定不相等，因此，s的片i与r的片j（i!=j）一定不需要考虑。

同时，需要保证的是，其中一个关系（例如关系s）的分片大小，能够放入到内存中去。

将关系s的每一个分片，直接一次性的读到内存中去，（例如此时读入片0），然后再对关系r中的片0，对于每一个块，或者每一个记录，与s关系的片0在内存中直接进行匹配连接。

这样以来，每一个分片，例如r的分片0与s的分片0，都只需要传输进入内存一次。

（对r的片0的每一个块进行循环读入，将每一个块和已经全部在内存中的s的片0进行匹配。）因此，s的分片0不需要在每次r的片0的每一个块读进去的时候，重新循环读入一次，而是一直存在于内存中，等待r的一块一块读进来进行匹配。

此外，在后面进行分片的join操作时，这是在内存中进行的。对于关系r的分片i的每一个块，去跟已经在内存中的关系s的分片i进行连接。这个过程可以利用内存中关系s的分片i的哈希索引进行。

可以在内存中建立起比较有效的哈希索引。在对关系r的分片i的每一条记录的连接属性值，在关系s的分片i中进行查找进行等值连接的时候，通过这个哈希索引函数计算一下，就能在关系s的分片i查找到符合等值连接的记录。

哈希函数应当如何设计？也就是说，我们应当将关系r与关系s至少分为多少片？

应当满足：

即分片的个数，至少应当保证关系s的每一片能够装到内存中去。

还有一个问题：假如表s很大。M相对来说很小。

此时，利用哈希函数，将关系s分片时，分的片数就要很多。那么，假如内存不够大，一次无法分配出来这么多的分片，应当怎么办？ （为什么内存不够大就无法分出来这么多的分片：因为，假设我们一次要把关系s分为N个分片，那么每一个分片在内存中都要具有一个块大小的输入缓冲区。第i个缓冲区的作用是：接受哈希值为i的记录，当第i个缓冲区写满了以后，就要写出去。因此，假设N>M，那么内存中块的个数不够N，就无法将关系s分为N个分片，因为输入缓冲区的个数不够。）

多次分片。假设第一次分片，我们把关系r和关系s分为了4个分片，但这些分片大小还太大，放不进去内存中。此时需要再次进行细分，递归地分割。

几个定义：

能够被分片，分片一次性放入到内存中的那个关系（如上述例子中的关系s），叫做build input（建立输入）。

对于上述例子中的关系r，叫做probe input（探针输入）。

哈希连接的伪代码：

① 对于关系r，使用一个哈希函数h，进行分片。对于每一个分片，内存中都需要一个输入缓冲块。

② 对于关系s，使用相同哈希函数h，进行分片。对于每一个分片，内存中都需要一个输入缓冲块。

③ 对于每个i：

(a)将si加载到内存中去，然后针对si的等值连接属性，构建一个内存哈希索引。这个内存哈希索引，使用与刚刚分片时不同的哈希函数h’。

(b)从磁盘中依次读入ri的每一个元组tj（其实是将ri的块一块一块的读进内存中，对于ri的每一块进行循环），在内存中与si进行匹配连接。对于每一个元组tj，利用刚刚对于分片si构建好的内存哈希索引，在si中匹配对应的属性上的等值元组tk，将tj与tk进行连接，输出连接的结果。

哈希连接的代价估算：

首先，我们刚刚说过，我们分片的时候要保证对于build input，分片的大小要能够放到内存中去，因此，我们分片的个数不少于：

但是实际上，利用hash函数进行分片，其分出来的片不一定是均匀的。

因此，实际上，我们一般要分出更多的片数，从而保证build input的每一个分片都能够放入到内存中。一般而言，我们分出的片数不少于：

其中f称为修正因子，其值大约在1.2附近。

然后，对于递归的分割：（即因为内存大小不够大，需要分割出来的最小片数n，大于了内存的最大块数M，因此需要分割出来的片数n不能每一片都在内存中有一个输入缓冲区）不需要递归的分割的情况：需要分割的片数小于内存中最大存放的块的个数，即每一个片都可以在内存中获得输入缓冲区：

而最小需要分割的片数n又必须满足：

上述公式很重要。满足上述公式，便不需要递归的分割了。

例如：

有了上面的前提，接下来对哈希函数的Cost进行估算：

① 如果没有使用递归的分割：

Transfer:

最开始，利用哈希函数进行分割时，关系r和关系s的每一个块都要读入到内存的输入缓冲区一次，然后再写出来，这样要消耗2(br+bs)次数据的传输操作。在后面进行连接的时候，对于每一个分片i，我们将build input的si读入到内存中。对于这个si，我们将ri中一块一块读到内存来。这样最终的结果是，关系r与关系s的每一块都读到了内存中一次。

因此，传输操作的总次数为：

Seek:

在这里，假设我们对关系r与关系s的每一个分片，在内存中分有bb块输入缓冲区，而不仅仅一块。

因此，在进行分片时。例如对关系r，原本我们要一块一块地将关系r读入到内存中的输入缓冲区，一次重定位仅仅能够输入一块。然后在内存中，对这一块的每一条记录，用哈希函数映射到输出缓冲区中再进行输出；

但此时，我们一次读写头重定位，就能读入内存bb块。相当于一次读入bb块后，在内存中将这bb块的所有记录进行映射，放到输出缓冲区中输出。

由于对于关系r与关系s，进行分片操作都需要将全部的块读入到内存中一次，然后读出来一次。因此，读写头重定位的成本是：

② 如果使用了递归的分割：

是理想情况下应当分成的片数。但是，假如内存中没有个块，就要使用递归的分割。

假设每次分片，对于每一个关系（r或者s）的每一个分片，内存中都分配bb块作为输入缓冲区，同时内存中还留有一个bb块大小的输出缓冲区。

那么一次分片可以分得的最大个数，就和输入缓冲区的个数相等。为：

因此，我们进行分片进行的轮数为：

每一次分片，都让原来的每一个分片的大小变为原来关系中分片大小的分之一。

Transfer：

每一轮分片，都需要将r关系的所有块读到内存中一次，再从输出缓冲块中输出来一次；s关系也一样。因此，对于有递归的分割的过程，数据传输的总次数为：

对于接下来进行连接的过程，和前面是一样的。

对于每一个分片i，我们将build input的si读入到内存中。对于这个si，我们将ri中一块一块读到内存来。这样最终的结果是，关系r与关系s的每一块都读到了内存中一次。

因此，传输操作的总次数为：

Seek：

对于分片的过程，我们一共进行的轮数为：

在每一轮的过程中，例如对于r关系读到内存中的过程，由于对于每一个分片，输入缓冲区一共有bb块，因此一次读写头重定位就可以读进去bb块。并且对于每一个分片，由于输出缓冲区也有bb块，因此一次读写头重定位就可以输出bb块。

因此，每一轮对s与r的分片，其读写头重定位的总次数为：

再乘以分片的轮数，得到Seek操作的总次数：

查询优化

考试范围

查询优化是关系数据库管理系统的核心功能之一。讲解查询优化的两个阶段的基本步骤，即代数优化和物理优化；介绍关系代数表达式的等价变换规则，以及基于代价估算的查询优化的基本原理。

课外学习：

1）查询优化为什么要用到数据库的统计信息？

2）数据库应用的运行会带来统计信息的变化，这对查询优化会产生怎样的影响？

主要内容

等价关系代数表达式

两个关系代数表达式等价是指：形式不同，但产生的OUTPUT是完全相同的。

等价规则：

合取选择

交换选择

投影省略

条件连接的转化

连接操作可交换（不考虑属性次序的情况）

(a)连接操作可结合

(b)条件连接可结合

(a) 选择操作可分配

体现出的是：选择运算要尽量先做，先选择，使结果规模下降，然后再进行连接。

(b)选择操作分别分配

也体现出选择运算尽量先做。

投影运算可分配

这体现的是：投影运算也应该尽量先做。投影运算与选择运算都能降低结果的规模。

9. 集合的并与交可交换

10. 集合并与交可分配

11. 针对集合的选择操作是可分配的

集合的并对投影操作可分配

分组操作和选择操作可交换

全连接与左右外部连接的交换性

选择操作对左右外部连接可分配

代价估算

代价估算，需要用到数据库的统计信息。（不用太精确，过一段时间刷新一次）。

数据库中，下面这些统计信息是很重要的：

nr：关系r中元组的个数。

br：关系r所占据的块数。

Ir：关系r中，一个元组占据的大小。

fr：关系r中，一个块能放入多少个元组。

V(A,r)：对于关系r中的属性A，有多少个不同的值。这也等价于对关系r中属性A进行投影，得到的结果集合大小。

如果关系r中的元组在文件中的存放是连续的，那么有：

即存放的块数为总的元组个数除以一块中元组个数，并上取整

一般来说，对于一个关系r中的属性A，它有V(A,r)个不同的值，那么最好有一个直方图，能够表示对于这些不同的值，表中分别有多少个元组。查询时，根据查询的范围，就知道查询结果的规模有多大。

但是我们往往没有这样的直方图，因此，我们对每一个不同的值进行估计的时候，都采取平均分配的估计。对于每一个值，估计它在表中有nr/V(A,r)个元组对应

1. 对于单个值的选择操作的代价估算：

若选择的这个属性A的这个值v不是key，那么就用总元组数除以这个属性的不同值的个数进行估计；如果选择的这个属性A是key，那么估算为1

对于范围查找 A≤v

采取线性平均的方式进行估计。用总元组个数，乘上这个值减去min的值，比上max减去min的值。

但是，假如数据库没有维护max或者min这些信息，只能将所有的小于等于操作或者大于等于操作得到的结果，估算为nr/2了

中选率

选择操作中，一个元组满足该选择条件的概率。

假如对多个条件联合选择，那么最终得到的结果集合的大小估算：

假如对多个条件进行析取选择，那么最终得到的结果集合的大小估算：

上述公式都有一个重要假设：即满足的各个条件是相互独立的（不相干的）

对于连接操作的代价估算

① 首先，对于两个表相乘，得到的元组个数应当为nr*ns，每一个元组有sr+ss个字节。

② 假如连接表R与S没有公共属性，那么就相当于做笛卡尔积，返回nr*ns个元组。

③ 假如连接属性是R的Key，那么R的每一个Key最多对表S中的对应属性值连接一次。那么最终连接后的结果，元组个数不会超过ns。（因为有些表S中的属性值并没有与R的Key连接上，因此会出现小于的情况）

④ 假如连接属性不仅是R的Key，而且还是一个从S指向R的foreign key，那么最终连接后的结果元组个数刚好是ns。

这是因为，由于连接属性是R的Key，因此R中对应的每一个Key值都只和S中对应的值连接一次。与此同时，S表中对应属性值由于是外键，因此一定会出现在R的对应属性值中

⑤ 假如连接的属性不是某一个表的Key

更精确的估计值，是上述两个计算公式的最小值。

原因是：例如对于第一个公式。站在表r的角度，表r的每一个元组，会和s中的多少个元组连接上？而s中能和r的这个元组连接上的元组，对应的属性值应当相等。因此，用ns/V(A,s)（总元组数除以不同属性值个数）表示，与连接属性相等的元组大概有多少条。因此，上述公式得到的就是自然连接过后大致的结果规模。

因为有时候r中的一个元组对应属性值在s中没有，出现了连接不上的情况，但是这样的情况我们仍然算在了总共的估计规模中，估算结果偏大。因此，选择上述两种估计中的最小值是较为合适的。

对于其他操作的代价估算

① 投影：

返回的结果就是不同属性值的个数。

② 分组：

返回的结果就是不同属性值的个数。

③ 对集合大小的上限估算：

④ 对于外部连接的代价估算：

外部连接比自然连接多出的是：假如是左外部连接，那么左边的关系没有连接上的部分，也要放入到结果集合中。因此结果集合的上限估算，就再加上r的元组个数。

⑤ 对于中间结果，在某个属性上不同值的个数

（i）例如，估算下面这个选择操作中间结果在A属性上不同值的个数：

估计结果：

原来未筛选的表在A属性上不同值的个数，和选择出来的结果条目的个数取最小值。

（ii）估算下面这个连接操作中间结果在A属性（可能是组合属性）上不同值的个数：

若A属性都来自于r：

若A属性中包括属于r的属性集合A1，与属于s的属性集合A2：

执行方案选择

最关心的，是连接操作的次序问题。

在这里，对执行方案的选择不是枚举，不可能把每一种连接操作的次序进行遍历。

通过动态规划的方式，进行连接。比如要连接五个表，确定要先连接前三个表。在前三个表中选择最优的方案（12选1）得到结果表，然后把剩下的3个表选择最优的方案（12选1）进行连接。

每次将要连接的表序列分为两个子序列，递归进行。每次选择两个子序列连接的最优方式（在所有连接的方式中进行选择（哈希、Merge等））。

利用上述算法，选择最佳的执行方案，其时间复杂度为：，空间复杂度是

左深连接树

左深连接树中，左边可以是一个关系或者一个中间结果，但右边一定是一个关系。

构建左深连接树，对最初始的连接序列S，每次选取最后一个关系，将S分为S-r和r，而不是对于S的任意一个非空子集进行分割。

对于上述算法求得最佳的连接方案，其时间复杂度为：

🧘‍♂️

启发式优化：应用一些规则，对查询操作进行优化

尽早进行选择操作。（减少中间结果元组个数）

尽早进行投影操作。（减少中间结果属性个数）

把限制条件最严格的选择操作与限制条件最严格的条件连接操作优先做。（减少中间结果规模）

利用左深连接树进行连接。即在为连接操作序列选择最优方案的时候，每次将序列S分为S-r与r，对这两个表选择最优连接方案。(减少时间复杂度)

优化嵌套查询

对于每一个教师，把教师的ID在teaches表中进行循环，查看是否有条件满足的记录。

这相当于一个两重循环。外循环是instructor表，内循环是teaches表，效率较低。

假如说嵌套的查询中，没有出现外面的表中的某个属性，例如这里出现的instructor.ID，那么就不是两重循环。可以预先把里面那个查询做好，外面的表只需要一重循环遍历即可。

使用半连接进行优化。（r半连接s的含义是：为了选择r的元组，看r的元组和s的元组是否满足连接条件。r中满足连接条件的元组保留，不满足连接条件的舍弃）

那么，上述嵌套查询可以写成

其中，P21是与外循环有关的属性，P22是只与内循环有关的属性。

利用半连接，优化为：

先利用teaches_year对teaches表格进行筛选，然后，再利用TID进行分组，在每一组中算出教课的数目。半连接时，实际上被半连接的表是一个只有两个属性的表：TID,cnt

利用这个表，对instructor的元组进行筛选，将半连接条件设置为ID = TID& 1 < cnt。因此，instructor表中满足这个条件的ID所在的行元组就会被保留，不满足的行元组会被舍弃。

最后，对半连接结果（即选择后的instructor表）进行投影，得到最终的结果。

（2）物化视图

增量视图维护

差分，把视图中更改的增量算出来即可。

例如，最初，两个表连接结果如下：

那么，需要将新增的这条记录和s表做连接，并将连接的结果加入到物化视图中，以维护视图信息的正确性。

假如不是连接操作，这个物化视图是由另一个表r的选择操作得出的。那么假如表r插入了一条新元组，为了维护物化视图，只要把插进去的那个元组利用相同的选择条件进行选择，如果选择上了，就把它并到物化视图中。

假如物化视图是由对A属性对表r进行分组，然后进行count计算得到的，那么假设表r新插入了一条元组，假设这个元组的分组属性的值在分好组的分组属性值的集合中，那么就把对应物化视图的这个count值加1。假设这个元组的分组属性的值不在分好组的分组属性值中，那么就在物化视图中插入新的一行，包括这个元组的分组属性值，对应的count置为1。

数据存储

考试范围

数据持久存放于以磁盘为代表的存储设备中，处理时需读入主存。磁盘和主存之间存在着巨大的访问速度鸿沟。讲授以块为单位的内外存数据传输、缓冲区管理与替换策略、记录在块中的存放方式，以及数据文件组织的主要形式。

课外学习：1）磁盘和主存之间存在着多大的访问速度鸿沟？为克服这样的鸿沟，数据库管理系统采取了哪些措施？2）比较行存和列存的优缺点。

主要内容

物理存储的分类

易失存储：内存、CPU中的高速缓存（cache）。

非易失存储：磁盘、硬盘、闪存、固态硬盘、光盘等。

衡量各种存储介质的标准：

访问数据的速度：通常是易失存储较快，非易失存储慢。

价格；

可靠性。

存储级别

存储级别中，从上到下访问速度依次减慢，单价与可靠性依次下降。一级存储的访问数据速度最快，但是是易失的。二级存储是连在计算机系统中，随时可以访问到的。而三级存储主要是用于备份，要访问数据较为不便。

磁盘的结构

柱面：同一个磁道上，多个磁盘共同组成的一个柱面。假如一共有五片磁盘，有5G的数据需要存储，如何存储是最优的？应将数据存在同一个柱面上，arm在定位时，会定位到相同的位置，只需要一次定位就够了。

磁盘的时间

访问时间：从读写指令发出来，到读写头定位到正确的扇区，开始读数据所经历的时间。

访问时间包含：

① 寻道时间：寻找要读取的信息在哪一个磁道上面。（毫秒级别）

② 旋转延迟：把需要读的扇区旋转到读写头下面。

磁盘的数据传输率

定位到正确的磁道与扇区后，才开始进行数据传输，对应有数据传输率。

内外存之间数据的传输，是以块为单位的。

即使想访问磁盘中的一个整数，也要将磁盘中的一个块读到内存中去

两种访问模式：

顺序访问模式：如果连续的读写请求，涉及到的扇区，是在连续的块中。（理想的访问模式）（效率高）

随机访问模式：

如果连续的读写请求，涉及到的扇区，不在连续的块中。

IOPS，每秒I/O操作数

衡量磁盘的访问速度的指标。每秒钟能够支持多少个随机的读操作。

MTTF，平均故障时间

平均故障时间是指，平均多长时间，存储介质会发生一次故障。

磁盘块访问的优化措施：

① Buffering 缓存

假设我们只读磁盘中的一个Byte，也要把磁盘中的一个块（很多连续的扇区）读到内存中去。

将一个块读入内存中（耗时较长）后，如果直接将这个块丢弃，是很可惜的。因此，可以将这个数据块缓存在内存中。希望后面的数据访问也在这个块中读取，加快读取数据的速度。

② Read-ahead 预取技术

我们访问一个数据，要将这个数据在磁盘中对应的数据块读到内存中来。但同时，我们预测未来的数据访问可能会在这个数据块后连续的几个数据块中，就顺便将后续的几个数据块读到内存中。

③ Disk-arm-Scheduling

按照电梯算法，来移动读写头，使之位于不同的磁道上。重新将读写头收到的读写请求进行排序，以最小化读写头的移动。

④ File Orgnazation

将分散在磁盘中的文件碎片，重新写在一个连续的块中，使得访问这个文件的数据时，效率提高。（反碎片化）

⑤ Nonvolatile write buffers 非易失性写缓存

一般情况下，要向磁盘中写入数据，需要等待向磁盘中写好之后，再进行下一步操作。现在可以把写的数据，先写到一个快速的存储介质里面，但是这个存储介质又是掉电不丢的（非易失性写缓存）。写到快速存储介质后，就可以立即进行下一步操作。

例如：NVM：非易失性写缓存

⑥ Log Disk 日志磁盘

把对磁盘块的修改，以日志的形式，记在一个专门的日志磁盘中，这个磁盘只支持顺序访问。

闪存（SSD 固态硬盘可以用来做闪存）

① 每次按照页进行读操作。

② 在对数据进行重新写入之前，需要先擦除数据。

磨损均衡：我们访问上层的时候有一个逻辑页号，映射到物理页号的映射方式是可以变化的。假如我们访问一个逻辑页号是“热数据”（经常访问的数据），那么可以通过改变物理页号映射方式达到磨损均衡。

定长记录

第i条记录从第n*(i-1)个字节开始，其中n是每一条记录的定长（占用的空间大小）。如果一个块有4096个字节，一个记录需要100个字节来存放，那么最多只能放下40条记录，而舍去最后的96个字节。否则会造成一条记录存在于两个块中的麻烦情况

删除一条记录;

方法一：将i+1条记录到n条记录，依次向下移动，移到i条记录到n-1条记录的位置。

方法二：将第n条记录移到第i条记录的位置。

方法三：不移动记录，在一块的头部留下一点空间，用于放置空链表指针，将所有被删除的位置连接在一起。

不定长记录：

如果将不定长字符串(varchar)都按照定长字符串来进行管理，存储效率将不高，存在空间浪费。

将不定长的字符串存放在后面。

空位图：表示这些属性是否为null（空）。如空位图为0000，表示四个属性都不是空。

表示中，前面用两个整数分别表示位置与长度，“65000”是定长字符串，0000是空位图，表达属性是否为空，这些都是定长的。

后面的不定长属性按照实际的长度，依次存放。

这里按行存放，也可以按列存放，各有优劣。

将不定长记录放到一个block块中:分槽页结构

块的头部放置的是定长的部分，块的尾部放的是不定长的部分，即不定长的行元组记录。

文件的组织：

要插入一条记录，要知道插入到文件的哪一个块的哪一个位置。

这就取决于文件的组织方式。

① 堆

文件中有位置，就将这条记录插进去。

一个文件由很多个数据块（page）组成，我们可以在第一个page中记录元信息，对于文件中每一个块，（例如用3个或者4个bit）来表示这个块中的空闲程度。

例如，first level中，4表示4/8空闲，2表示2/8空闲，等等。

当我们需要插入一组记录时，可以看一看那些数据块的空间足够插入这些记录。

由于如果只有第一层，顺序访问较为低效；我们可以新加一层，第二层中的一个3bit的记录对应于第一层的四个3bit的记录，用来表示第一层中，那四个3bit的记录中，最空闲的块的空闲程度。

② 按照次序

使用指针来维护次序。

③ B+树文件组织

④ 哈希结构

⑤ 多重组织结构

先存放系的记录，紧跟着该系的老师的记录。这样以来，做两个表的连接操作就很方便，但是对单独表进行遍历或者查找就不便。

Table Partition

如果一个表太大，会存在弊端（访问冲突）。

将所有的老师，分为各个系的老师放在小的表中；或把属性分割出来等。

·缓冲区管理

上层模块访问数据时，先要知道要访问的数据在哪一块。得到块号后，如果这一块恰好在缓冲区中，直接将这一块的地址给到上层即可。如果这一块不在缓冲区中，那么要在磁盘中取一块到缓冲区中，然后再将这一块的地址给到上层。

这样以来，缓冲区会被逐渐占满。新进来缓冲区的块要考虑替换掉哪些缓冲区中已经有的块。

使用LRU策略。

Least Recently Used。最近最少用到。

把最近访问到的块，提到缓冲区的最上层。每次缓冲区溢出时，替换掉缓冲区最下层的块。例如在访问2时，替换掉了缓冲区最下层的块4。这里还要考虑一个问题：假如块4读到缓冲区后，是只读没有修改过的，那么将块4拿出缓冲区，是没有问题的。假如块4读到缓冲区后，被进行了修改，那么就要先将块4写到磁盘中去，然后才能将块4拿出缓冲区。

如果上面的程序正在访问缓冲区中的某一个块，那么要进行Pin的操作，钉住这个块，不让它离开缓冲区。

当上层的程序访问完毕，即Pin count = 0（Pin count表示上层有多少个程序正在访问缓冲区的这个块）时，进行UnPin的操作，解除钉住这个块，那么这个块将变成候选的可以被替换出去的块。

Buffer Manager还涉及一个比较复杂的问题，当一个块进入到缓冲区以后，上层的某些程序可能在读它，有些程序可能在修改它，则会涉及共享区域的冲突访问问题。解决方案：加锁。读与读之间不冲突，但读与写、写与写之间都是冲突的。

缓冲区管理的MRU策略：

在某些情况下，缓冲区管理的LRU策略有可能不是最优的策略。例如如下情况：

对于内循环来说，最近最少用到的元素是内循环的第一个记录，但是内循环的第一个记录会在下一个内循环中，优先被访问到。最近最多用到的元素是内循环的最后一个记录，但内循环的最后一个记录会在下一个内循环中最后被访问到。因此我们需要MRU策略：Most Recently Used。

最近最少策略LRU的一种简单实现：

所有的磁盘块，可以看作是组成一个环。但每一块只对应一个bit，是0或者1。

算法如下：

不断循环，如果环中的某一块Pin count = 0，表示在上一次循环中，没有外部程序访问这一块，那么这一块就可以作为候选块被替换出去。现在，新进来一个块，放到刚刚被替换出去的块的位置，它的Reference bit被置为1。或者，假如在循环过程中，哪一块被访问到，就将对应的reference bit置为1。对于环中的每一块，如果它的Reference bit为1，那么将其置为0；如果碰到Reference bit为0的，就将这一块替换出去。

ER模型

考试内容

实体-联系模型（Entity-Relationship Model）是一种概念模型，用于数据库分析阶段为现实世界建模。它使用ER图描述现实世界的实体（Entity）以及实体之间的联系（Relationship）。实体用以描述现实世界中可以区分的对象。实体所具有的特征称为实体的属性（Attribute）。实体之间存在着各种联系。

通过实体-联系方法得到现实世界的一个抽象模型，但这一模型并不能为数据库管理系统接受。要完成从现实世界到信息世界的转化，还必须将实体—联系方法所得的ER图转化为关系模式，并用SQL语句定义相应的表。

讲授实体-联系模型的各种要素，重点掌握采用实体-联系方法为现实世界建模的一般过程和要点。讲授ER模型中实体（包括弱实体）和联系（包括一对一、一对多、多对多联系）等的转换方法。

课外学习：

1)采用实体-联系方法为现实世界建模时，有些信息既可以用实体来表达，也可以用联系来表达，这两种方式的选择依据是什么？

2）一对多的联系既可以转换成一个独立的关系，也可以和实体对应的关系合并，这两种转换方法各有什么优缺点？

主要内容

一个大学的关系模式：

矩形框：实体。

菱形框：关系（relationship）。

一对多关系：一个系有多个老师，但一个老师只对应一个系。

• 每一个实体（如instructor、department）都要单独转换为一个关系模式。

对于每一个关系来说（如关系inst_dept）

可以将这个关系单独拿出来作为一个关系模式：

create table inst_dept (ID , dept_name).

将两边的主键拿出来作为关系模式中的属性。

由于教师对系属于多对一的关系，因此利用教师的ID才能唯一确定一个元组，因此在关系inst_dept中，主键为ID。

但是，更常用的做法是：直接省略这个关系inst_dept，将多对一的那个一的主键加入到多的关系当中。

变为：

instructor (ID , name, salary, dept_name)

其中ID为主键。

双横线：全参与。教师用双横线指向关系inst_dept，说明每一个教师都要参与这个关系，意思是：每一个教师都要有一个系。

此外，注意到关系inst_dept使用单横线指向department，表明每一个系不一定要参与到inst_dept这个关系当中，意思是：每个系不需要都有教师。

假设关系inst_dept使用双横线指向department，则说明每一个系都一定要有至少一个教师。

单横线：非全参与。学生用单横线指向关系advisor，表明不是所有学生都要参与advisor这个关系，意思是：可以有学生没有导师。

例如：instructor与section之间的关系：

多对多，但每个教学班必须有老师教（全参与），每个老师不一定教教学班（非全参与）。

双向箭头：一对一关系。

单项箭头：多对一关系。

无箭头：多对多关系。

一个实体自己与自己之间也可以有联系：

例如课程：

课程与预修课程之间有多对多的关系。

弱实体：弱实体中的属性不能够唯一确定一个元组，它是依赖于其他实体的。

section 需要依赖 course中的course_id，才能唯一确定一个元组。

双框：双框表示联系着一个弱实体集，并且它连接的另一端的实体集，就是这个弱实体集依赖的实体集。（弱实体集的属性中加入弱实体集依赖的实体集的主键，才能够唯一确定一个元组）。（转换为关系模式时，加入依赖的实体集的主键）

Relationship上也可以携带属性：

花括号：表示多个值。（多值属性）

time_slot表中，主键为time_slot_id，确定了一个时间的id。这个时间id对应的时间段可能有多个值，例如周一3、4节，周二5、6节等。

section用双横线指向这个关系，说明每一个课程都需要有一个时段。time_slot用单横线指向这个关系，说明有些时段可以没有课程。由于是单向箭头，因此表明一个时段可以有多门课，一门课只能有一个时段

ER图转换为关系模式：

将多元联系转化为二元联系。

复合属性：（composite attribute）

派生属性：（Derived attribute）

可以由其他属性导出的属性，在ER图中加上括号表示。

例如，年龄可以由出生日期导出，因此在ER图中用age()进行表示：

多值属性：（multi-valued attribute）

利用花括号进行表示，表达可以有多个值。

• 多对多联系的主键，是两端实体的主键的组合。

关系advisor是需要进行转换的，在关系advisor中，主键是教师ID与学生ID。

假设关系advisor上携带了属性，那么关系advisor进行转化后，携带的属性要带上。

多对一联系的主键，是那个多的主键。

关系inst_dept不用转换，而是将那个“一”的主键dept_name直接加入到那个“多”的属性中。

• 弱实体集的主键，要拷贝它依赖的强实体集的主键

关系sec_course不用转换，将course_id拷贝到关系section中即可。

在关系sec_course上如果携带了属性，要将携带的属性都转移到弱实体集section的属性列表中。

多值属性的转换

例如{ phone_number }：每一个多值属性，都必须单独转换为一个关系表：

设计时，可以选择多种设计方案：

如果电话号码一个教师只留一个，设计如下

如果表达一个教师有多个电话号码，一个电话号码可以有多个教师使用，还要表达电话号码相关的其他信息，设计如下：

特化与概化：

特化：从上向下。

概化：从下向上。

可能有重叠：每个子类使用单箭头指向父类。

不会有重叠：每个子类连接起来，用一个箭头指向父类。

partial：不是所有人一定会分为员工与学生两类，也就是说，员工与学生两类的并集不能涵盖所有人。

total：所有员工一定会分为教工与后勤人员。

• 假设多值属性单独转化为一个关系模式，是下面的这种情况：

理论上，应当对于time_slot表的多值属性，单独建立一个关系模式，如下：

在time_slot表中拿掉那个多值属性。

然后新建一个表，主键为time_slot表的主键，加上各个多值属性。

但是，此时由于拿掉了多值属性，表time_slot中只有单独一个主键元素了，因此我们可以将其进行简化，简化为只有一个表。

关系数据库的设计

考试范围

一个不好的关系数据模式会产生数据冗余、数据更新异常等问题。通过函数依赖的概念分析关系模式的规范化程度，并把不规范的关系模式分解为规范化的关系模式。讲授函数依赖的概念、Armstrong公理系统、关系模式的候选关键字（candidate key）以及关系模式分解的原则，即无损连接的分解和保持函数依赖的分解。

BCNF是函数依赖范畴内规范化程度最高的关系模式，而3NF是比BCNF低的规范化形式。一个关系模式总能无损连接地分解为BCNF 的关系模式，但不一定能保持函数依赖；若要求分解既是无损连接的又是保持函数依赖的，则保证可以分解为3NF。通过考察多值依赖，还可以获得更高规范化的关系模式，即4NF。讲授函数依赖的相关概念，以及3NF和BCF的定义、分解为BCNF和3NF的算法；介绍多值依赖及4NF的概念。

课外学习：

1）一个不好的关系模式会产生哪些问题？如何消除这些问题？

2）3NF和BCNF有何区别？如何把关系模式分解为BCNF的关系模式？举例说明4NF。

主要内容

“坏的”关系带来的问题：

在上面的关系中，ID决定name、salary、dept_name，而dept_name又决定building与budget。

不满足BCNF的关系。（只有Key能够决定其他的属性，不是Key的属性不能够决定其他的属性）。

信息重复（信息冗余）

插入异常（假如有一个新设的系，没有老师，由于老师ID是primary key，因此不为空，故新设的系插不进去）

更新困难（由于信息冗余，造成更新的困难。假如要进行更新，要放在一个原子性的事务中进行。因此，更新较麻烦）

无损连接分解（Lossless-join）：

将关系R分为关系R1与关系R2：

关系R的分解是无损的，如果R1与R2的自然连接正好等于关系R。

关系R的分解是有损的，如果R是R1与R2的自然连接的一个子集。（多出来的元组，造成了表达信息的不确定性，时原本R中的信息减少。）

判断一个分解是无损连接的：

将关系R分解为关系R1与关系R2，关系R1与关系R2之间有公共属性。这些公共属性如果要么是关系R1的Key，要么是关系R2的Key，则一个分解的是无损连接的。

假如将关系R分解为多个关系，要证明分解是无损的，只要找出一条路径就可以了。

函数依赖关系

函数依赖的定义是在应用层面的，通过数据库的实例，不能证明某个函数依赖关系，只能证伪某个函数依赖关系。例如存在实例A:1 B:2与实例A:1 B:3，则说明A->B不成立，但只能说明B->A可能成立。

平凡的函数依赖关系：属性的全集决定属性的子集。

函数依赖的闭包（Closure）：

函数依赖集合F的闭包F+，表示所有能够从函数依赖集合F推导出来的（包括F自身）集合。F+中，也包含一些平凡的函数依赖。

函数依赖的推导定理

这些公理是正确有效的与完备的。

使用这些公理进行推导：

函数依赖的推导引理

属性集合的闭包（Closure）：

一个属性集合通过函数依赖关系，能够决定的所有属性的集合，称为属性集合的闭包。

计算一个属性集合的闭包的算法：

计算一个函数集合的闭包的算法：

对任意一个关系R中的集合a（有2^m-1个），根据函数集合F计算出这个集合a的闭包a+。

然后，对于闭包a+中的任意一个子集S（有2^n个），生成一个函数依赖关系a->S。合起来就是函数集合F的闭包。

正则覆盖：（Canonical cover）：

不存在冗余的函数依赖，也不存在冗余的属性的函数依赖集合。

正则覆盖需要满足的条件：

F逻辑蕴含Fc中所有的函数属性

Fc逻辑蕴含F中所有的函数属性

Fc中没有一条函数依赖（不管是左边还是右边）包含多余属性

左边的多余属性，例如：

• Fc中任何一条函数依赖的左边都是唯一的

例如，A->C, A->D应合并为A->CD。

无关属性（Extraneous Attributes）：

BCNF：

定义：一个关系模式R，它是BCNF的，如果它的函数依赖集合的闭包F+中的每一条函数依赖a->b满足：

或者 a->b 是平凡的；

或者 a->b 中，a是super key（包含 key）。

分解时，从叶子结点开始分解！

依赖保持：

定义：如果通过检验分解后的单一关系上的函数依赖，就能确保所有的函数依赖关系成立，那么这样的分解就是依赖保持的。

或者可以说，原来关系R上的每一个函数依赖，都可以在分解后的单一关系上得到检验（primary key）或者推导得到。

意为：F中的每一条函数依赖，都可以在分解得到的Fi中得到检验。

假如，我们有（ID，dept_name, salary），存在函数依赖ID->dept_name, dept_name->salary，那么假如我们分解这个关系为（ID,dept_name）与(ID，salary),那么就无法在分解后的关系中利用key的定义验证dept_name->salary。此时，如果要检验dept_name->salary，只能将R1与R2连接在一起，检验不存在两个元组，它们的dept_name相同，而它们的salary不同。

BCNF的关系是，每一个函数依赖的左边都是超级键。 super key

BCNF分解做的事情是：把函数依赖中每一个不符合上述条件的函数依赖，单独构成一个关系模式。把函数依赖的右边从原来的属性集合中去掉，把函数依赖的左边不去掉。

但有些关系通过上述BCNF分解的方法并不能做到依赖保持。例如：

其主键有：JK与JL。它不是BCNF关系，因为L不是超级键。按照上面的分解方式，应该将R分解成(J,L)与(L,K)。

但这样分解后的关系并不能做到依赖保持，因为通过主键无法直接验证函数依赖JK->L。 • 3NF：

β-α本质上就是右边的β。因为函数依赖两边如果有公共属性，可以将它去掉。

要么α->β是平凡的，要么α是超级键，要么β包含在一个候选键中。

🧘‍♂️

任何一条非平凡的函数依赖，要么它的左边是一个超级键，要么它的右边包含在一个候选键中。

上面的关系是一个三范式。JK是超级键，且K包含在候选键中。

在对关系做分解时，尽量无损地将其分解为BCNF的集合，要再去判断一下，分解的结果是不是依赖保持的。如果不能做到无损且依赖保持，只能将关系分解为3NF的集合。

①首先，计算出函数依赖集合的正则覆盖Fc。 ②然后，对于Fc中的每一条函数依赖（共有n条），将左边与右边拼起来，作为一个单独的关系模式。

③假如上一步分解出来的关系模式中，没有任何一个包含关系R的候选键，那么将R的任意一个候选键拿出来，作为一个新的关系模式即可。

因此，现在分解出的关系模式一共有n个（①中分解出的关系模式中有包含候选键的）或n+1个（①中分解出的关系模式中没有包含候选键，需要额外添加任意一个的）。 ④去除分解出的关系模式中重复的。例如，分解出了（A,B,C）与（A,B），则保留(A,B,C)，舍掉(A,B)。

BCNF关系的问题：

假如在一个关系中，存在两种以上不相干的多值依赖，那么就会产生插入异常、信息冗余等问题。

进行分解：把不相干的多值依赖分解出来。（4NF）

4NF：

除了BCNF的要求之外，还要求不存在非平凡的多值依赖。

🧘‍♂️

平凡的多值依赖：主键决定一个多值属性，且除了这个多值属性以外，主键不决定其他多值属性。

例如，ID多值决定了phone_number后，不能再多值决定child_name。

在关系R中的所有函数依赖当中，要么α决定β是平凡的（要么β属于α，要么α并β等于整个关系R（包含多值依赖与普通函数依赖）），要么α是R的一个超级键。

或者说，在关系模式中存在的任何一个多值依赖，要么退化为一个左边为超级键的函数依赖，要么必须是一个平凡的多值依赖，即R中除了α和β的并集，没有其他属性。

① 给出E上的非平凡函数依赖与多值依赖。

② 列出E的候选键：A、B、C

③ 证明E不是4NF的

其实E连BCNF的都不是。因为E中存在一条函数依赖A->D，而A不是候选键(最小的超码）。且E中存在多值依赖A->->B，而A与B的并集不是整个关系R。因此E不是4NF的。

④ 说明关系E中可能存在的问题：

信息冗余、更新困难、插入异常。

⑤ 将E分解为4NF范式：

把每一个多值依赖，都单独拿出来分解，最后剩下非多值的依赖，按照BCNF分解的方法分解。

SQL语言

考试范围

主要内容：

数据模型是数据库系统的一个根本特性。关系数据模型因为其简单有效而在数据库领域占据主导地位。讲授关系模型的数学模型，包括关系模型的数据结构、数据完整性、数据操作；重点讲授关系代数及基本关系操作及附加关系操作，学习用关系代数表达式表达数据查询要求。

课外学习：关系代数有哪些基本操作？关系代数的查询表达能力如何？

主要内容： 基本SQL查询

SQL(Structured Query Language) 是关系数据库标准语言,包括数据定义、数据操纵、数据控制一体化管理功能。SQL是一种陈述式的语言。讲授SQL的表定义，包括：SQL基本数据类型、primary key、foreign key和check定义，以及SQL DML语句的基本用法，包括select、from、where、group by、having各子句。

课外学习：SQL作为一种陈述式语言，它和过程式语言（如C）有什么区别？SQL的数据完整性定义功能有什么优点？

主要内容：

讲授SQL嵌套子查询构成的复杂查询。

讲授SQL数据更新语句，包括insert、delete、update语句.

SQL视图(view)和索引(index)分别对应数据库三级模式中的用户模式和物理模式。用户可以象查询基本表一样查询视图中的数据，在特定情况下可通过视图更新基本表中数据。索引可以加快数据库查询处理的效率。讲授视图的语法和用法，以及可更新视图的概念。通过具体例子讲解视图的优点。讲授索引的作用、索引的类型SQL索引定义的语法。

课外学习：1)构想一个数据库应用，用SQL定义数据库中的表，并构思若干查询要求，写出对应的SQL语句。2)举例说明视图的优点。3)如何选择在数据库表上建立哪些索引？

主要内容：

数据完整性包括primary key、foreign key、check和断言(Assertion，即一个数据库必须满足的条件谓词)。触发器(Trigger)是数据库表更新时自动触发执行的动作，也是维护数据完整性的一种手段。安全性控制是数据库中不可缺少的功能。SQL中的安全性控制包括用户身份鉴别、权限管理和审计三方面。事务（transaction）是构成一个完整的逻辑工作单元的数据库操作的集合，是数据库系统进行并发控制和恢复的基本手段。Basic operations, additional operations, extended operations三者的关系，是否可替代？

课外学习：1)触发器在数据库系统中有哪些用处?　2)数据库安全控制有哪些方面？3)SQL 中和事务相关的语句有哪些？

主要内容：

嵌入式SQL是应用程序调用数据库的一种方式。SQL和高级程序设计语言(如C语言)存在着基本数据类型和执行方式两方面的不匹配。嵌入式SQL通过游标(cursor)等方式处理这些不匹配的问题。讲授嵌入式SQL的基本原理，包括不带cursor的SQL语句和带cursor的嵌入式SQL语句、静态嵌入式SQL、动态嵌入式SQL、ODBC、JDBC。

课外学习：SQL和C语言在数据类型和执行方式上存在哪些不匹配的地方？嵌入式SQL如何处理这些不匹配? ODBC比起嵌入式SQL有什么优缺点？

主要内容

数据类型

时间类型

创建表格

dept_name指向department表中的Primary key。意为，在instructor这个表中的所有dept_name的值，都要存在于department这个表的dept_name列中。

插入数据

如果插入学生的时候没有给tot_cred一个给定的值，那么该值为default给定的值。

foreign key 的删除和更新操作

delete：

course表中的dept_name值必须存在于department表中的dept_name这一列。但因为某种原因，某个department撤销，这时，某些存在于course表中的dept_name将不存在于表department中。

此时对于删除操作，有如下四种策略：

cascade：所有指向被删除元素别的表的元素也一并删除。例如，如果某一个系撤销了，那么所有在course中利用外键指向这个系的课程信息也一并删除（连锁反应）。

set null：所有指向被删除元素的别的表的元素置为null，但是，如果即将要被置为null的元素，在完整性约束当中已经约束为“not null”,这样做就是不合法的。

restrict：不允许删除已经被别的表的foreign key指向的元素。无操作。

update： 因为某种原因，某个department改名，这时，某些存在于course表中的dept_name将不存在于department中。

此时对于更新操作，有如下四种策略：

cascade：所有指向被改名元素别的表的元素也一并改名。例如，如果某一个系改名了，那么所有在course中利用外键指向这个系的课程也更改系名（连锁反应）。

set null：所有指向被改名元素的别的表的元素置为null，但是，如果即将要被置为null的元素，在完整性约束当中已经约束为“not null”,这样做就是不合法的。

restrict：不允许更改已经被别的表的foreign key指向的元素。无操作。

set default：所有指向被更改名字的元素的别的表的元素置为设定好的default值。

删除表、删除表中内容、或更改表中列

distinct会对选择出来的元素进行去重操作，all选出来的元素可能是多重集。

select的内容中可以添加属性的算数表达式

between

where中可以进行元组的比较

natural join

自然连接：两个表中公共属性相等的做等值连接，其余不相等的行去除掉。

注意区分直接卡特兰乘积

例：找到上了不是自己系的课程的所有学生：

join (name) using (属性X) 指的是用属性X做两个表的连接

图中，如果将（student natural join takes）表格与课程表格做自然连接，将利用course_id与dept_name两个属性做自然连接，这就变成了学生所在的系和上的课程所在的系必须相同，这是不符合实际的。

因此，只用course_id做自然连接，选出学生所在系与所上课程所在系不同的学生名字。

更改名字 as

字符串比较的选择操作：like

但是如果需要选择出字符串‘100%’，不能仅仅写： where name like ‘100%%’ 否则会引起歧义。应该使用转义字符(escape char): where name like ‘100#%’escape ‘#’ 此处表明‘#’后跟的‘%’应当作正常字符进行看待。

针对字符串的其他操作

排序 order

直接使用order by表示升序排列，若为字符串那么就会按照字典序的顺序进行排列；若过为数字类型，就会按照数字大小的顺序从小到大的顺序排列

降序排列：order by () desc。对多个元素排序：先按照第一个元素排序，第一个元素相同时再按照第二个元素排序，以此类推。

对多个元素排序：先按照第一个元素排序，第一个元素相同时再按照第二个元素排序，以此类推。

limit短语

用于找到工资排名前几（后几）的老师。

对工资进行降序排列。 limit a,b 指的是，从下标为a的地方开始，保留b个。直接用limit b，表明从下标为0的地方开始，保留b个。

集合操作：并(union)、交(intersect)、差(except)

这三种集合操作都是按照集合的标准定义的，会去除得到的集合中重复的元素。

如果不想去除重复的元素，可以使用union all、intersect all、except all来合并、取交、取差所有元素。

空值 null

聚合函数

在上面例题中，如果不加上distinct，那么2010年春有多少门课，那么count(ID)的结果就是多少，而不能反映2010年春有多少老师教了课。

也就是有多少行

分组 group by

下面的这个语句是错误的

🧘‍♂️

因为，在select挑选出来的属性中，除了聚合函数计算得到的属性以外，其余的属性必须在分组属性group by后面出现。

选择聚合函数的结果：having

把符合having后面条件的统计行保留下来。

havig和where 有什么区别？

🧘‍♂️

where是在分组之前，对表中的行进行筛选，筛选掉的不参与分组；having是在分组之后，对分好的组进行筛选。

例题

找出没有重名学生的系

例题

嵌套语句

in 和 not in 的关系

有时，in或not in语句也可以判断一个元组是否在给定表的行当中：

some 与 all 的关系和操作

选出十倍年薪超过所在系的预算的教师名字：

在这里，由于department.dept_name定下来了，因此budget也确定下来了，因此保证了在嵌套查询的子查询中，返回的数值只有一个。此时，可以直接写where salary*10 >（子查询）。

如果不能保证子查询返回的数值只有一个，则需要用where salary*10 > all（子查询）或where salary*10 > some（子查询），否则会发生错误。

🧘‍♂️

在SQL中，ALL 和 SOME（也可以用 ANY 替代 SOME）是用于子查询结果集的比较运算符。它们允许我们对查询结果集中的每一个值进行条件测试。下面详细说明它们的用法和区别。

ALL 的用法

ALL 运算符用于检查条件是否对子查询结果集中的所有值都为真。换句话说，给定的条件必须适用于子查询返回的每一个值。

SOME 或 ANY 的用法

SOME 和 ANY 运算符用于检查条件是否对子查询结果集中的至少一个值为真。换句话说，给定的条件只需要适用于子查询返回的一个或多个值。

针对子查询中的一些部分情况和全部情况进行研究

exists与 not exists

只要exists后面跟的括号中的子查询是一个非空集合，那么就返回True

生物系所有课程id减去要选择的这个学生上过的所有课的id，得到的集合不存在元素。表明这个学生上了生物系所有课程。

只要not exists后面跟的括号中的子查询是一个空集合，那么就返回True

unique

查找2009年最多开过一次的课程：

只要unique后面跟的括号中的子查询返回的结果没有重复的元素，返回值就是True。

对于上面的语句，假设选择出的课程在2009年没有开过，那么unique后面跟着的子查询返回的结果就是null，但也同样没有重复的元素，因此是True。故该语句选择出的是2009年最多开过一次的课程。

🧘‍♂️

unique常常用来查询“最多一次”。

与 PRIMARY KEY 的区别

PRIMARY KEY：不仅确保唯一性，而且不允许 NULL 值。每个表只能有一个 PRIMARY KEY。

UNIQUE：确保唯一性，但允许 NULL 值。一个表可以有多个 UNIQUE 约束。

查找2009年恰好开过一次的课程：unique and exists

查找每个学期最多开过一次的课程

🧘‍♂️

一般使用unique来解决最多一次的问题使用unique and exists来解决恰好只有一次的问题

删除 delete

插入 insert

Insert 操作还有一个重要的写法：将一些查询的结果，利用子查询语句插入到表中：

更新 update

假设我们要工资小于100000的涨5%，将工资大于100000的涨3%，下面的写法是错误的，因为与两个语句的次序有关。

正确的写法应该是：

join

假设有下面两个关系

左外部连接

左外部连接（Left Outer Join）是一种用于从多个表中获取数据的SQL联接类型。左外部连接返回左表（左连接表）中的所有记录以及两个表中连接字段匹配的记录。如果右表中没有匹配的记录，结果集中的右表记录将包含NULL值。

语法

或者可以简化为：

示例

假设我们有两个表：Customers 和 Orders。

Customers 表：

Orders 表：

我们希望获取所有客户及其订单，即使某些客户没有任何订单。可以使用左外部连接来实现：

结果

在这个结果集中，Bob 没有订单记录，因此对于 Bob 的订单信息，OrderID 和 OrderDate 列返回 NULL。

总结

左外部连接：从左表返回所有记录，以及两个表中连接字段匹配的记录。如果右表中没有匹配的记录，右表中的记录返回 NULL。

用法：当我们希望从一个表中获取所有记录，即使在另一个表中没有对应的匹配记录时，使用左外部连接。

左外部连接非常有用，尤其是在处理需要保留主表中所有记录的查询时。例如，在客户和订单的例子中，即使某些客户没有任何订单，我们仍然希望在结果集中看到这些客户。

右外部连接

全外部连接

🧘‍♂️

全外部连接可以用using表达做全外部连接的属性：

内部连接：

只对on后面条件说明的属性做等值连接，其余不相等的元组全部舍弃。（没有连接上的就不保留下来）

自定义数据类型：

大对象类型：

图片、音频等大对象类型：blob。

文本大对象类型：clob。

当查询操作返回一个大对象类型的结果，那么将会返回大对象的指针，而不是直接返回大对象本身。

完整性约束

not null

unique

unique后面用括号括起来一些属性，表明这些属性的组合能够唯一确定一个元组。因此，这些属性的组合构成一个超级键（没有必要是最小的主键）。例如：primary key(学生ID),unique（电话号码）。

check:校验条件，元组的值要满足约束条件。

将约束检查推迟到事务结束

view 视图

create view V as （子查询）；

例如：一个没有工资的教师视图

（view名字后面可以不带属性列表）

例如：一个学院总薪水的视图

（view名字后面也可以带上属性列表）

也可以在一个view上再定义其他的view：

视图view的更新

向view中插入一行，相当于向实际的表中插入一行，缺失的属性填写null。但如果实际的表中对应属性有完整性约束not null，则无法插入这一行。

但如果实际的表中对应属性有完整性约束not null，则无法插入这一行。

索引 index

Index就是在属性上面建立了一个B+树索引：

事务

原子事务：要么完全被执行，要么向从未发生过一样回退。并发事务具有相关性。例如银行转账，一个账户的钱减少，必然伴随另外一个账户钱增加。如果另一个账户的钱还没有增加的时候，就被打断，此时第一个账户的钱必须加回来，就像没有发生转账操作过一样。

大多数的数据库的默认设置是，每一个SQL语句就是一个事务，会自动递交（commit）。对此，可以关闭自动递交。 SET AUTOCOMMIT = 0；在一个事务结束后，我们可以手动输入：commit；，从而保证事务的原子性。如果没有commit，那么退出数据库重新进入，数据会恢复到没有改变的状态。

授权Authorization：

权限：在表上允许做什么事情。

grant语句：授权。

<user list>可以是一个用户名、可以是公众、也可以是一个角色。

on后面可以是表的名字，也可以是view的名字。

all privileges on <表名> 表明这个表上所有的权限。

revoke语句：回收授权

角色role：角色可以看成一组权限的集合。

利用create role <角色名> 来创造一个角色。

将这个角色授予给一个用户：

将一些权力授予给这个角色：

角色可以授予给其他角色，被授予角色获得授予角色的一切权力：

角色链：

将在视图上搜索的权限授予给某个用户：

权限的传递：

1.with grant option:

表明Amit可以把获得的权限传递下去。

2.revoke……cascade

从Amit、Satoshi这里收回相应权限，cascade表示，所有之前由Amit、Satoshi授权的这一权限，全部收回。（级联反应）

3.revoke……restrict

这表示，加入Amit、Satoshi已经将相应的权限传递下去了，那么就不能收回Amit、Satashi的相应权限。

4.revoke grant option

表示收回Amit传递相应权限的权力，但没有收回Amit在表上查询的权力。

API:用于程序与数据库服务器的交互

应用程序调用数据库的过程：

① 连接数据库服务器。

② 向数据库服务器发送SQL命令。

③ 将结果的元组一个一个提取到程序变量中。

ODBC：开放式数据库连接

可与C、C++、C#配合使用。

JDBC：Java数据库连接

Embedded SQL：C语言中的嵌入式SQL

SQLJ：Java语言中的嵌入式SQL

JPA：Java持久性API – Java的OR映射

JDBC

上述程序中，Connection是一个类，conn是一个类中的对象，获得一个Java程序与数据库之间的连接。

Statement也是一个类，stmt是一个代表语句的对象，程序真正要做的事情在Do Actual Work处，做完后，要先将对象stmt关闭掉，再将对象conn关闭掉。

try……catch语句是一种异常处理的机制，在try部分中所有的函数与方法的错误，都会抛出到catch中被捕获。

• 更新数据库

如果插入不成功，catch部分会抛出错误。

• select语句：

ResultSet是一个类，里面有一个对象rset，用来获得select的结果。 while(rset.next())循环中，指针最开始指向第一个元组的上一个，rset.next()让指针指向下一个元组。 rset.getstring（“dept_name”）表示拿到字符串类型的列名为dept_name的一个元素； rset.getfloat（2）表示拿到浮点数类型的第二列的一个元素。rset.getstring（“dept_name”）与rset.getstring（1）是等价的。 System.out.printin是用来打印的函数。

如果返回值是空的（rset.wasNull），那么就打印出一行：Got Null value。

Prepare Statement（预编译语句）

预编译的时候可以留出占位符。在实际使用的时候，利用setString函数，直接在相应的位置上填入值。

例如，pStmt.setString(1,“88877”)表示，给第一个参数的位置放上88877。

pStmt.executeUpdate（）表示运行，插入四个参数。 - 注入攻击（SQL 注入）

例如，本来一条SQL语句的模板如下：

用户恶意输入：

从而使字符串变为：

因此，通常来说，通过用户的输入来构造一条完整的SQL语句是不保险的。可以利用prepare statement进行预编译，用户输入不合法的输入可以检测出来。 • 元数据（Metadata）

在运行一条语句，得到了一个ResultSet类中的对象rs，可以通过调用rs.getMetaData（）函数，来获取元数据。

有时写程序时，可能不知道会返回几个属性（列），也不知道列的名字与类型。利用类ResultSetMetaData

创建一个类ResultSetMetaData的对象rsmd；getColumnCount()表示获取结果集合中列的数目；getColumnName(i)表示获取第i列的列名； getColumnTypeName(i)表示获取第i列的列类型。 • Database Metadata

getColumns中，先是目录的名字(null)，再是Schema的名字（univdb），再是表的名字(department)，（%）表示返回这个表全部的列，最后将结果表放入类ResultSet的对象rs当中去。如果要遍历结果表中所有的行元组，仍然可以用ResultSet类中rs对象的next（）函数遍历：

前面，我们获得的是ResultSet的元数据，这里，我们获得的是数据库Database的元数据。

JDBC中的事务管理

在JDBC中，事务管理(Commit,Rollback)等，是通过调用对象的方法来实现的。

关闭自动提交：

手动提交/回退：

ODBC

首先，调用SQLAllocEnv（&Env）,获得一个环境。然后，调用SQLAllocConnect（Env，&conn）;在这个环境中，生成一个连接。这个驱动程序可能不止为C语言服务，还可能为其他语言服务。SQL_NTS的意思是：字符串的结束方式是‘\0’。当实际的工作做完以后，要将conn关闭掉、回收掉,要将env回收掉。 • 通过程序向数据库发送SQL命令： • 得到结果元组：

将C语言的变量绑定到查询得到的结果

ODBC程序

AllocStmt在conn这个连接中，分配一个代表语句的对象。 SQLExecDirect用来执行sqlquery字符串表达的语句，其中参数SQL_NTS表明，这个字符串是以‘\0’结尾而结束的。其中，SQLExecDirect的返回值保存在变量error中。如果error为SQL SUCCESS，表示上述语句已经执行成功了，返回的两列dept_name与sum(salary)已经存在了，然后，SQLBindCol函数将C语言的变量绑定到查询返回的结果。例如：

思为：把语句stmt中的第一列，传到变量deptname中，变量deptname的最大长度是80，实际的长度填写到lenOut1中。

意思为：把语句stmt中的第二列，传到变量salary中，将变量salary的长度传到lenOut2中。

如果变量salary为空，那么lenOut2中置为-1，否则置为它实际的长度。

然后，利用SQLFetch函数，将返回结果stmt利用循环，将一行一行的元组依次抓取，如果抓取成功，那么就打印出这一行的deptname、salary的值。

在程序的最后，还需要回收掉代表语句的对象stmt。

ODBC中的预编译Prepare语句

预编译的时候可以留出占位符。

prepare语句：

在SQL语句中，可以留出占位符：例如：

将参数传入：（将每一个占位符代表的参数与C语言中的变量绑定起来）

运行语句：

对于返回结果retcode，依照上述方法进行处理：

嵌入式SQL

概念

被嵌入SQL的语言称为宿主语言。

C语言中的识别符号：

EXEC SQL CONNECT TO语句连接上了数据库。 EXEC SQL 语句后面直接接上SQL语句即可。 • delete

其中，SQLCA.sqlcode表达的是运行上述语句时是否发生错误，如果不为0则发生错误。 • update • select

返回的结果可能是空的，为了指示这个问题，用一个额外的变量mask进行指示。如果指示变量为0，表示正常；如果指示变量小于0，表示返回结果为空；如果指示变量大于0，表示返回的字符串被截断了（定义的用来保存返回字符串的变量长度不够，导致无法完全存放返回的字符串）。

• select multiple records

先输入姓名customer_name，然后利用游标循环，将得到的查询结果一行一行地赋给account_number与balance。相当于把列和变量绑定了起来。当遍历到行的结尾时，SQLCA.sqlcode变为不等于零，循环退出。

• 删除或者更新游标所指向的当前记录

SQL过程化补充

SQL函数

传入一个系的名字，返回该系的老师的人数。有了上述函数后，在SQL语句中可以这样写：

• SQL过程（procedure）

含有输入参数与输出参数：

call完procedure后，整数d_count中就有了系名为物理系的老师的个数。

• 循环：while/repeat/for

这个for循环的意思是，对寻找表中dept_name为Music的每一行进行循环，做do后跟的操作。

条件判断语句

Trigger 触发器

定义了一个触发器，触发发生在我们对account表的balance属性做更新后。如果存款金额超过200000元，或者取款金额超过50000元，那么就要在account_log表中插入一行数据，记录下这次存款/取款操作。

触发器的例子

由于属性time_slot_id不是表timeslot的主键，因此我们不能利用属性time_slot_id创造一个从课程section表指向timeslot的表的外键。但是，课程表中的time_slot_id又必须存在于表timeslot中，这属于参照完整性。

🧘‍♂️

在触发器的定义中，每次触发在对课程表section进行插入新行的操作后。如果新行的时间不在timeslot表中，就回退，从而保证课程表section中的time_slot_id都在表timeslot中。

此外，我们在对表timeslot做更新时，如果删去了表timeslot中的一个time_slot_id,此时在课程中的某一行的time_slot_id可能就无法在表timeslot中找到。由于属性time_slot_id不是表timeslot的主键，我们也不能定义on delete cascade等完整性约束。我们可以用触发器来实现参照完整性。

如果旧的这一行的time_slot_id不能在表timeslot中找到，说明被删除的一个time_slot_id是最后的一个。如果此时并且旧的这一行的time_slot_id同时在课程表section中，那么就会引发参照完整性的问题。因此，触发器在对表timeslot做删除操作后触发，如果出现了上述的情况，就会回退，不让这个删除操作发生。效果等价于on delete ristrict。

• 触发器例子：

这个触发器在对takes表中的grade列进行更新后触发，如果新行中成绩及格并且不是空、旧行中成绩不及格或成绩为空，那么就进行一个原子过程。这个原子过程是：更新表student中的总学分tol_cred，让总学分加上该课程的学分。

for each row

对于每一行的修改，都会触发一次触发器。

for each statement

对于一个导致触发的语句，触发一次触发器。

例如，对于如下触发器：

假设是for each row，那么更新表account的每一行的balance值时，都会触发一次触发器，做相应的操作。

假设时for each statement，那么尽管一次update语句能够更新多行的balance值，但是执行这一个语句，触发器只会在语句执行完毕后触发一次。

如果是for each statement，那么就没有old row与new row的概念了，而是old table与new table。

每次对表takes的属性grade做更新后（不管更新了几条数据），如果有平均成绩小于六十分的教学班，那么就回退。这个触发器在执行完update语句后，触发一次。

🦄

事实证明真的可以在一周的时间内，学完一门课程数据库的东西真的好多好多呜呜呜🥹