数据库系统复习

主要观看数据库系统实现网课1700后的内容所成笔记。

与数据库系统实现（机械工业出版社）所讲内容基本吻合，但在具体部分所讲的顺序有略有不同，但考虑到啃书（尤其是机翻工业出版社的书）有些困难，所以先过一边网课再啃书。
网课中得顺序有些与书中不同，这里需要注意。
[toc]

第二章辅助存储管理

01 存储体系回顾

（1）数据组织的基础–存储体系

将不同性价比的存储器组织在一起，满足高速度，大容量，低价格需求

CPU与内存直接交换信息，按存储单元（字）进行访问

外存按存储块进行访问，其信息先装入内存，才能被CPU处理。

（2）操作系统对数据的组织

FAT-目录-磁盘块/簇

FAT（文件分配表 File Allocation Table）

（3）内存管理

一条记录的地址=存储单元的地址=内存地址=页面：页面偏移量

页面 = 块

内存页面的分配

内存页面的置换

02 磁盘的结构与特性

（1）磁盘及磁盘容量

此处应为磁盘结构图

磁盘位置表述：盘面：磁道：扇区

磁盘读写单位：扇区(sector)->簇cluster/块(block)

（2）磁盘的访问

寻道时间(1-20ms)
旋转时间(0-10ms)
传输时间(每4KB页<1ms)

三个时间的和称为延迟

物理存取算法考虑的关键：降低I/O次数

降低排队等候时间<==>降低寻道/旋转延迟时间

同一磁道连续存储

同一柱面不同磁道并行块存储

多个磁盘并行块存储

（3）提高磁盘数据读写时间与存储可靠性的方法

RAID技术：Redundant Array of Independent Disk(独立磁盘冗余磁盘阵列)

主要思想：

并行处理：并行读取多个磁盘

比特级拆分：一个字节被拆分成八个比特位，不同比特位存储于不同磁盘
块级拆分：一个文件由多个块组成，不同块存储于不同磁盘

可靠性

扇区/块读写校验：对一个扇区/块读写做校验
多个磁盘间共同构成的信息读写做校验。

实现结果：

RAID0 块级拆分但无冗余
RAID2 镜像处理：每个磁盘有个一镜像磁盘
RAID3 位交叉纠错处理：4个磁盘存储4位+3个校验盘P存储3校验位
RAID4 位交叉检验：4个磁盘存储4位+1个校验盘存储1校验位，位拆分存储(借助于扇区读写校验判断出出错磁盘再根据校验盘进行纠错)
RAID5 块交叉检验：块拆分存储，其它同上
RAID6 快交叉分布式校验：块拆分存储，互为校验盘
更多复杂冗余

03 查询实现的基本思想

（1）数据存储的映射关系示意

查询操作算法 -->
文件管理/索引管理：数据逻辑结构 -->
内存-缓冲区管理 -->
磁盘-磁盘管理：读/写块 -->

（2）数据存储与查询实现的基本框架示意

04 记录与表在磁盘上的存储

（1）数据库概念与磁盘相关概念的映射示意

（2）数据库中记录的区分及记录属性值的区分

定长记录：按长度分记录
边长记录：按指针或标志区分记录

块头如何设计？

（3）数据库中的记录 vs.磁盘块

记录在磁盘中的存储：

非跨块存储：

浪费一些存储空间

磁盘块之间无关联可并行

跨块存储：靠指针连接

节省一些存储空间

磁盘间有关联需要串行

（4）数据库中的表 vs.磁盘块

表所占磁盘块的分配方法：

连续分配：数据块被分配到连续的数据块上(会存在扩展困难问题)

链接分配：数据块中包含指向下一数据块的指针(访问速度问题)

按簇分配：簇是若干连续的磁盘块，簇之间靠指针链接

索引分配：索引块中存放指向实际数据块的指针

05 四种文件组织方法

无序文件组织
有序文件组织
散列文件组织
聚簇文件组织

（1）数据组织与存取方法

数据组织要考虑更新(增删改)和检索需求

更新将涉及数据存储空间的扩展和回收问题
检索将涉及扫描整个数据库的问题，大批量处理数据问题
不同的需求要求不同的数据组织方法和存取方法

文件组织：指的是数据组织成记录，块和访问结构的方式，包括把记录和块存储在磁盘上的方式，以及记录块之间相互联系的方法。(可以理解为是一种数据结构)

存取方法：指的是对文件所采取的存取操作方法。（可以理解为在数据结构上使用的算法）

一种文件组织可以采用多种存取方法进行访问

（2）无序文件组织

特点：记录可存储于任意空间的位置，磁盘上存储的记录是无序的。更新效率高，但检索效率可能低。

如何建立？

方法1：新记录插入到文件尾部；删除记录时，可以直接删除该记录所在位置的内容，也可以在该记录前标记“删除标记”
方法2：在前者基础上，新增记录可以利用那些标记为“删除标记”的记录空间

频繁删增记录时会造成空间浪费，所以需要周期性重新组织数据库。

数据库重组是通过移走被删除的记录使有效记录连续存放，从而回收那些由删除记录而产生的未利用空间。

（3）有序文件组织

特点：记录按某属性或属性组值得顺序插入，磁盘上存储的记录是有序的。检索效率较高。

用户存储排序的属性通常称为排序字段，通常，排序字段使用关系中的主码，所以又称排序码

当按排序字段进行检索时，速度得到很大提升

问题：

有序记录文件的更新效率可能很低

因为：在更新时要移动其它记录，为插入记录流出空间

改进：

改进措施是为将来可能插入的元组预留空间，或者再使用一个临时的无序文件（被称为溢出文件）保留新增的记录。

当采取溢出文件措施时，检索操作既要操作主文件，也要操作溢出文件

因此需要周期性地重组数据库

数据库重组是将溢出文件合并到主文件中，并恢复主文件中的记录顺序。

（4）散列文件组织

特点：可以把记录按照某属性或属性组地值，依据一个散列函数来计算其应放位置：桶号（Bucket，块号或簇号等）。检索效率和更新效率都有一定程度的提升。

用于进行散列函数计算的属性通常称为散列字段，散列字段通常也采用关系中的主码，所以又称散列码。

不同记录可能被hash成同一桶号，此时需在顺序检索出某一记录。

优化：

链接法处理溢出

动态散列技术等

（5）聚簇文件组织

聚簇：将具有相同或相似属性值的记录存放在连续的磁盘簇块中

多表聚簇：将若干个相互关联的Table存储于一个文件中---这可以提高多表情况下的查询速度。

06 Oracle数据库物理存储简介

这个书上好像没有，先跳了

07 第二章总结

第三章索引结构

01 索引的概念和作用

（1）索引的概念

索引是定义在存储表基础上，有助于无需检查所有记录而快速定位所需记录的一种辅助存储结构，由一系列存储在磁盘上的索引项组成，每一项索引由两部分组成：

索引字段，由Table中某些列中的值串接而成。索引中通常存储了索引字段的每一个值，索引字段类似于词典中的词条。
行指针：指向Table中包含索引字段值的记录在磁盘上的存储位置，行指针类似于词条在数据，词典中出现的页码

存储索引项的文件为索引文件，相对应，存储表又称主文件

（2）索引的一般性特点

索引文件是一种辅助存储结构，其存在不改变存储表的物理存储结构，但可以明显提高存储表的访问速度

索引文件组织方式有两种：

排序索引文件：按索引字段值的某一种顺序组织存储
散列索引文件：依据索引字段值使用散列函数分配散列桶的方式存储

主文件组织有堆文件，排序文件，散列文件，聚簇文件等多种方式

在一个表上可以针对不同的属性值或属性组和建立不同的索引文件，可建立多个索引文件。索引字段的值可以是table中的任何一个属性的值或任何多个属性值的组合值

索引文件比主文件小很多，通过检索一个小的索引文件（可以全部装载进内存），快速定位后，再有针对性的读取非常大的主文件中的有关记录

有索引时，更新操作必须同步更新索引文件和主文件

（3）关于索引应用的评价问题

索引技术应用是检索效率大幅度提高，但同时也增加了存储空间，使维护负担加重

衡量索引性能好坏： 1 访问时间 2 插入时间 3 删除时间 4 空间负载 5 支持存取的有效比

（4）索引相关概念的区分

字段，排序字段，索引字段

码（Key），主码，又称表键---具有唯一性

排序码：对主文件进行排序存储的那些属性或属性组

索引码：即索引字段，不一定具有唯一性

搜索码：在主文件中查找记录的属性或属性集

02 SQL语言中的索引创建与维护

书上没有，先跳了

03 稠密索引和稀疏索引

（1）稠密索引和稀疏索引概念

对于一个主文件中的每一个记录（形成的每一个索引字段值），都有一个索引项和它对应，指明该记录所在位置。这样的索引称为稠密索引

对于主文件中的部分记录(形成的索引字段值)，有索引项和它对应，这样的索引称为非稠密索引或稀疏索引

（2）稀疏索引如何定位记录

索引文件中不存在搜索码的值，不代表主文件没有对应搜索码的记录

定位索引字段值为K的记录，需要

首先找相邻的小于K的最大索引字段值对应的索引项
从该索引项对应的记录考试顺序进行table的检索

稀疏索引的使用要求--主文件必须是按对应检索字段属性排序存储

相比稠密搜索：空间占用更少，维护任务更轻，但速度较慢

平衡：索引项不指向记录指针，而是指向记录所在存储块的指针，即每一个存储块有一个索引项，而不是每条记录有一个索引项

（3）稠密索引如何定位记录

候选键属性的稠密索引：先查索引，然后再根据索引读主文件。

非候选键属性的稠密索引：

第一种情况：索引文件中索引字段值是不重复的；主文件按检索字段排序且索引字段不是候选键。

第二种情况：索引文件中索引字段值有重复；主文件未按索引字段排序且索引字段不是候选键。

第三种情况：引入指针桶处理非候选键索引的多记录情况；主文件未按检索字段排序且检索字段不是候选键。

04 主索引与辅助索引

（1）主索引

主索引通常是每一存储块有一个索引项，索引项的总数和存储表所占的存储块数目相同，存储表的每一存储块的第一条记录，又称为锚记录，或者称为块锚。

主索引的索引字段值为块锚的索引字段值，而指针指向其所在的存储块

主索引是是按索引字段值进行排序的一个有序文件，通常建立在有序主文件的基于主码的排序字段上，即主索引的索引字段与主文件的主码有对应关系

主索引是稀疏索引

（2）辅助索引

辅助索引是定义在主文件的任意或者多个非排序字段上的辅助存储结构。

辅助索引通常是对某一非排序字段上的每一个不同值有一个索引项；索引字段既是该字段的不同值，而指针则指向包含该纪录的块或该记录本身

当非排序字段为索引字段时，如果该字段值不唯一，则要采用一个类似链表的结构来保存包含该字段值的所有记录的位置

辅助索引是稠密索引，检索效率有时相当高

（3）差别

一个主文件只有一个主索引，但可以有多个辅助索引

主索引通常建立在主码/排序码上；辅助索引建立在其他属性上

可以利用主索引重新组织主文件数据，但辅助索引不能改变主文件数据

主索引是稀疏索引，辅助索引是稠密索引

05 其他索引

（1）聚簇索引与非聚簇索引

聚簇索引：是指索引中邻近的记录在著文件中也是临近存储的
非聚簇索引：是指索引中邻近的记录在主文件中不一定是临近存储的

（2）倒排索引

正排：一个文档包含了哪些词汇
倒排：一个词汇包含在哪些文档中

（3）其它索引

多级索引：当索引想比较多时，可以对索引再建立索引，形成多级索引。常见多级索引有B树/B+树，以树形数据结构来组织索引项。

多属性索引：索引字段由table的多个属性值组合在一起形成的索引

散列索引：使用散列技术组织的索引

网格索引：使用多索引字段进行交叉联合定位与检索

06 B+树索引（书上是B树）

（1）多级索引

当索引较多时，可以对索引再建立索引

（2）B+树的基本概念

B+树索引：一种以树形数据结构来组织索引项的多级索引

一块中索引项的组织：
Ki:索引字段值
Pj：指针，只想索引块或数据块或数据块中记录的指针

索引文件的叶子节点的指针指向主文件的数据块

B+树能自动保持与主文件大小相适应的树的层次，每个索引块指针的利用率都大于50%

（3）B+树的存储约定

B+树有一个参数n，决定了树的所有存储块的状态

一块中有 n-1 个索引项（<索引字段值Ki，指针Pi>） + 1个指针（Pn）

示例：存储块=4096B，整数型索引字段值=4B，指针=8B
则n应该满足 4（n-1) + 8n < 4096,n取341为最大值

指针情况：

索引字段值x在 $k_{i-1}<x<k_i$ 的由 $p_i$ 指向；而 $k_i<x<k_{i+1}$ 的由 $P_{i+1}$ 指向非叶节点指针指向索引块，叶子节点指向主文件的数据块或数据记录
叶子节点的最后一个指针始终指向其下一个数据块
一个索引块实际使用的索引指针个数d满足(n/2<d<n)
根节点至少两个指针被使用
索引字段值重复出现于叶节点和非叶子节点
指向主文件的指针仅出现在叶子节点
所有叶子节点即可覆盖所有键值的索引
索引字段值在叶子节点中是按顺序排列的

B+树级数相同–平衡，如何保证？

插入删除记录时，伴随着节点的分裂和合并
分裂和合并将调整部分节点块中的索引项，需要算法支持

(4) 利用B+树建立不同的索引

1：利用B+树建立键属性稠密索引
索引字段是主文件的主键，索引是稠密的。主文件可以按逐渐排序，也可以不按逐渐排序。指针指向的是记录
2：利用B+树建立键属性稀疏索引
索引字段是主文件的逐渐，索引是稀疏的。主文件必须按逐渐排序。指针指向的是数据块。

（5） B树

不同：

索引字段值仅出现一次
主文件的指针也可出现在非叶子节点
所有节点才能覆盖所有的键值索引
分裂新增节点原理相似，细节不一样

（6） B+树相关算法

检索算法，增加记录的算法，删除记录的算法

07 B+树之键值插入与节点分裂示意

（1）插入

关键：

分裂（当插入节点全满时）
由叶子节点向根节点逐层处理
能够自动保持与主文件大小相适应的书的层次
每个索引块的指针利用率可以在50%以上
指针调整

（2）删除

先定位待删除键值的叶子节点，从根节点向下
删除键值及其主文件记录
如指针数目不小于规定数目，则可以结束；否则，需要合并。
1. 从相邻节点能否转移一些键值到该节点，如果可以，则转移，并更新父节点的相应键值
2. 否则考虑节点合并，合并后调整父节点的键值及次序，调整叶子节点的指针链接
3. 如果父节点在删除索引项及指针后，指针数目小于规定，则继续步骤2，直至根节点；如果不小于规定则结束
如果删除位置是第一个，还需更新父节点键值

08 散列索引

（1）散列的基本概念

由m个桶，每个桶是具有相同容量的存储地，称为主桶，溢出后可设置溢出桶
散列函数h（k），可以将键值k映射到{0,1,…m-1}中的某一个值
将具有键值k的记录Record（k）存储到对应的h（k）编号的桶中（此处映射应尽可能均匀）

（2）散列索引

内存数据可采用散列确定存储页，主文件可采用散列确定存储块，索引亦可用散列确定散列项的存储块
m个桶，一个桶可以是一个存储块，也可以是连续存储块

（3）散列索引的插入和删除

插入键值d的索引项：

计算h（d）=2
如2号桶有空间，则将索引项d插入2号桶
如没空间，则申请一溢出桶，插入d

删除键值f的索引项：

计算h（f）=2
删除2号桶中的键值f
将溢出桶中的值放入主桶，删除溢出桶

（4）散列的问题

散列索引的目标：最好是没有溢出桶，每一个散列值仅有一个桶。读写每一个键值都只写一个存储块。

均匀分布如何做到？
桶的数目m如何确定？

如果桶数m固定----静态散列索引
如果m过大，则浪费，过小则产生更多溢出桶，增加索引检索时间
桶的数目随键值增多动态增加—动态散列索引

09 可扩展散列索引与线性散列索引

先略过，书上有，开卷考现场学来得及

以下第三章书上有，视频里没有

10 多维索引（3.4）

多维索引的应用：对地理数据的处理。

利用传统索引执行范围查询，效果甚微，如果数据小点还可以。

大多数支持多维数据查询的数据结构归于以下两类

类散列表方式
类树方式

11 多维数据的散列结构

（1）网格文件

一种比单维索引性能好的最简单的数据结构。在每一维上用网格线将空间分成条状，被分成的每个区域可以看成是散列表的一个桶，以此来进行插入和删除.

（2）分段散列函数

散列函数可以接受属性值的一个列表作为参数，以此可以将高维转换到一维。

这种方法其实在最近邻查询和范围查询中没什么用，点之间的物理距离没有通过桶号反应，否则就是网格文件了。

12 多维数据的树结构

（1）多键索引

一种简单的树模式，它的每一层的节点是一个属性的索引。

性能：
部分匹配查询：如果属性可以按树的从浅到深的属性索引给出，效率很高，否则很低。
范围查询：单个索引在他们本身支持范围查询，效果很好
最近邻查询：即为若干个范围查询

（2）kd-树

kd树概念

kd树（k维搜索树）是把二叉搜索树推广到多维数据的一种主存数据结构。

kd树是一个二叉树，它的内部节点有一个相关联的属性a和一个值V，它将数据点集分为两个部分：左子树是a值小于V的部分，右子树是a值大于等于V的部分。
并增加以下定义：

内部节点只有一个属性，该属性具有一个划分值和指向左右子树的指针
叶子节点是块，快空间存放着尽可能多的记录

kd树操作

查找：同二叉树

插入：先做一个查找，找到对应的叶子节点，如果叶子节点中的块还有空间，就将新的数据放在那里；否则将块分裂成两个，并根据所在层属性再次划分。最后，我们创建了一个新的内部节点：它的子节点分别为我们分裂得到的两个新块，并且给该内部节点一个相应的划分值。

kd树优化

内部节点多分支。kd树内部节点可以有多个键-指针对，让其更像B树节点。
聚集内部节点到块。可以把多个内部节点压缩到一个块中，减少遍历路径访问的块的数量。

（3）四叉树

在四叉树中，每个内部节点对应于二维空间中的一个正方形区域，或是k维空间的k维立方体。在二维的情况，一个节点的子节点即为它二维平面的四个象限。

（4）R-树

R树是一种利用B-树的某些本质特征来处理多维数据的数据结构。

R树表示由二维或更高维区域组成的数据，我们把它称为数据区，R树的一个内部节点对应于某个内部区域，运行子区域有重叠，但应尽量小。

13 位图索引

略，看书，考场现编

第四章查询执行

1901 查询实现算法概述

（1）数据库查询的基本思想

基本动作：

关系模型的基本运算
- 并，差，积，选择，投影

用户语言实现关系模型基本元素的基本组合，随后数据库管理系统（程序执行机构）解释这种组合，并按次序调用基本动作予以执行

（2）查询实现 vs. 查询优化

SQL语句经过编译得到关系代式；
关系代式先经过逻辑优化；
在经过物理优化（为每一个关系代数才做选择优化的执行例行程序，形成物理查询计划）；
最后经过执行引擎运行（依物理查询计划调用的例行程序进行处理，并返回结果）

（3）查询算法总览

数据库的三大类操作
- 以此单一元组的一元操作
  - 选择，投影
- 整个关系的一元操作
  - 去重，group by，排序
- 整个关系的二元操作
  - 集合的并交差
  - 包的并交差
  - 积，连接

1902 连接操作的实现算法

（1）连接操作的逻辑实现算法

两个for循环即可

（2）连接操作的物理实现算法

关系是存储在磁盘上的，磁盘是以磁盘块为操作单位的，首先要装载进内存(I/O操作)，然后在进行元组的处理

一些参数
- $T_R$ ：关系R的元组数目
- $B_R$ ：关系R的磁盘数目
- $M$ ：主存缓冲区的页数（主存每页容量等于一个磁盘的容量）
- $I_R$ ：关系R的每个元组的字节数
- $b$ ：每个磁盘的字节数

需要错做的Byte数 $B_{R\times S}=T_RT_S(I_R+I_S)/b$

（3）连接操作的基本实现算法

对于关系R，S的连接，一次分别将R和S的一个块从磁盘中移到内存中进行连接
复杂度 $B_R+B_R*B_S$ ,但只需要内存三个块

（4）连接操作的全主存实现算法

将两个关系都撞入内存中进行连接，此时内存页数需要大于两个关系的内存块数。
复杂度 $B_R+B_S$

（5）连接操作的半主存实现算法

内存只能装入一个关系的所有块的条件下

先将一个装入内存，再将另一个关系的所有快一个个的放入内存进行连接

（6）连接操作的大关系实现算法

此时内存不能装入任一关系的所有快。

此时先将内存装一个关系得所有快，每次装得只剩两个块得位置，装入多次，剩下两个一个用作输出，一个依次输入另一个关系得所有快，依次来进行连接操作

（7）连接操作的其他方法

归并排序
散列排序
索引连接算法

1903 利用迭代器构造查询实现算法

（1）迭代器算法的提出

查询实现的两种策略
- 物化计算策略：每一步将所有中间值得出再进行下一步
- 流水线计算策略，每得到的元组依次经过查询条件得到结果
区别
- 是一个关系操作还是一组关系操作
- 中间的结果是否完整的存储

迭代器算法在流水线计算策略中实现

（2）迭代器算法基础

迭代器：迭代的读取一个集合中的每一个元素，而封装其读取细节

有一个抽象类：

class iterator{
  void Open();
  tuple GetNext();
  void Close();
  iterator &inputs[];
}

所有的关系操作可继承此迭代器进行构造。
不同操作，可以构造不同的Open(),GetNext(),Close()函数

（3）迭代器的构造

迭代器示例：表空间扫描发–读取关系

Open(){
  b:=R的第一块
  t:=b的第一个元组
}
GetNext(){
  IF(t已经超过块b的最后一个元组){
    将b前进到下一块
    IF(没有下一块)
      return NotFound;
    ELSE/*b是一个新块*/
      t:=b的第一个元组
  }
  oldt:=t
  将t前进到b的下一元组
  RETURN oldt;
}
Close(){}

迭代器示例：R并S算法

Open(){
  R.Open();
  CurRel:=R;
}
GetNext(){
  IF(CurRel==R){
    t:=R.GetNext();
    IF(t<>NotFound)
      RETURN t;
    ELSE{
      s.Open();
      curRel:=S;
    }
  }
  RETURN S.GetNext();
}
Close(){R.close();S.close();}

1904 数据库查询的一趟扫描算法

（1）什么是一趟算法

内存能放下关系的所有块，即只需要调用一次数据库的算法。

（2）关系/表数据的读取

聚簇关系

下文中B（R）是R的存储块的数目，T（R）是R的元组数目，M是内存能放下的块的数目

关系的元组集中存放（一个块中仅是一个关系的元组）
- TableScan® 表空间扫描算法
  扫描结构未排序：B（R）
- SortTableScan®
  扫描结构排序：3B（R）
- IndexScan® 索引扫描算法
  扫描结果未排序：B（R）
- SortIndexScan®
  扫描结果排序 B® or 3 B®

非聚簇关系

关系的元组不一定集中存放
扫描结果未排序：T®
扫描结果排序：T®+2B®

（3）整个关系的一元操作算法

需要在内存中保存已经处理过的元组
当新元组到达时，需要和之前处理过的元组进行比较
建立不同的内存数据结构，来保存之前处理过的数据，以便快速处理整个关系上的操作
算法复杂性：B（R）
应用条件：B(&R)<=M
去重复 &®，分组聚集
可以在内存中采取散列的数据结构，达到快速插入，快速定位的效果

（4）整个关系的二元操作实现算法

扫描一个关系，再扫描另一个关系
集合的操作需要去重；包的操作需要做计数
算法复杂度：B®+B(S)
应用条件:min(B®,B(S))<=M

1905 基于索引的算法

（1）基于索引的选择算法

选择条件中有涉及到索引属性时，可以使用索引，辅助快速索引
聚簇和非聚簇索引，使用时效率不一样
可能在多个属性上都存在索引

索引应用分析示例：
假设B®=1000，T®=20000，即有20 000 个元组放到1000个块中。a是R的一个属性，在a上有一个索引，考虑 $\sigma_{a=0}(R)$ 操作

如果R是聚簇的，且不使用索引，查询代价1000I/O
如果R不是聚簇的，且不使用索引，查询代价20000
如果V(R,a)=100（表示a只有100个不同的大小）,且索引是聚簇的，查询代价即a=0d的元组所在的总共的块数，平均1000/100=10。
如果V(R,a)=100且索引是非聚簇的，查询代价平均20000/100=200
如果V(R,a)=20000，即a是关键字，查询代价为1

（2）基于有序索引的连接算法（Zig-Zag连接算法）

略难，跳，对应书P122

1906 回顾

查询实现算法的基本思维
连接的逻辑实现算法
连接的物理实现算法
- 如何降低磁盘I/O
- 充分利用内存，减少循环量
- 如何降低内存的查找量
- 建立合适的数据结构
一趟算法：只要有一个关系能够全部装入内存即可实施
需要用一些算法
- 迭代器算法
- 基于散列的算法
- 基于排序的算法
- 基于索引的算法

2001 两趟扫描算法的基本思想

（1）整个关系操作存在的问题

对于一个关系，可能不能将整个关系都放入内存中，一趟算法已经不能实施

（2）两趟算法的基本思路

第一趟：划分子集，使得子集具有某种特性，如有序或相同散列值
第二趟：处理全局性内容的操作，形成结果关系。如多子集间的归并排序，相同的散列值子集的操作等

可实现原因：大数据集上的操作可以等价于子集上操作的并集

2002 两阶段多路归并排序

（1）内排序和外排序

内排序问题：待排序的数据可以一次性地装入内存中，即排序者可以完整地看到和操纵所有数据。内存中的排序算法：插入排序，冒牌排序
外排序问题：待排序的数据不能一次性地装入内存，即排序者不能一次完整地看到和操纵所有地数据，需要将数据分批次装入内存分批处理地排序问题。

（2）两阶段多路归并排序

全称TPMMS， Two-Phase Multi-way Merge Sort based join
两阶段多路归并排序是一种外排序。
现在假设内存大小x块，待排序数据要y块，y>x。

首先将要排序的数据划分为n份，x*n>y
依次将分好的子集放入内存中进行内排序
随后将排序好的子集，对于所有的子集每次取一块放入内存中，将最小值或最大值取出后放入内存，原来的数据删除
内存中存在个子集中最小的元素，此时进行内排序，排序后的结果输入到新的外部存储中
重复4，5直至数据全部排序完

算法效率：

子集和排序阶段读一遍写一遍
归并阶段读一遍写一遍
总I/O次数4B®
算法应用条件：
- 子集合数< $B_{mermory}$
- 子集和块数< $B_{mermory}$
- 大数据集块数< $B_{mermory}^2$

（3）更大规模的多阶段归并算法

设内存大小 $B_{mermory}=3$
待排序数据 $B_{problem}$ =30$

基本策略

30块数据集->10个子集和，每个子集合3块，排序并存储
10个已经排序的子集合再分为5组进行二路归并排序，得到5个排序好的子集合
5个集合再分为3组，进行归并排序；最后得到3个排好序的子集和
再归并即可得到最终的排序

2003 基于排序的两趟扫描算法

（1）操作

去重复，聚集复杂度等同TPMMS

并
- 包上直接合并即可，无需两趟
- 集合上需要两趟，需要去重
  - 效果同TPMMS
交，差
- 包上和集合上都要两趟，需要处理出现次数或者去重复，效果同TPMMS
连接运算 $R\Join_{R.Y=S.Y} S$
- 第一趟：划分R和S的子表并进行子表排序，排序均基于Y属性排序
- 第二趟，归并时注意是R的输入还是S的输入。R和S的两路输入之间进行连接检查后连接后输出
- 又称“排序-连接”算法

2004 基于散列的两趟扫描算法

（1）基本思想

第一趟：散列子表，用散列函数 $h_p$ 将原始关系划分为 $M-1$ 个子表并存储（剩一个用来输出）
第二趟：处理每个子表，用另一散列函数 $h_r$ 将子表读入内存并建立内存结构，进行不同操作的处理

（2）实例

去重复操作
- $H_p$ 计算元组部分属性的值 $modM$ ,将可能重复的元组散列到同一子表中
- $H_r$ 计算整个元组的值 $modM$ ，将可能重复的元组散列到同一内存中
- 元组在子表上不重复，则在大关系中不重复
- 算法复杂度：4B®
分组操作
- 第一趟：将原始关系通过 $h_p$ 散列成m-1个子表，并进行存储
- 第二趟：处理每个子表。将每个子表读入内存，并用另一函数 $h_r$ 形成散列数据结构，进行分组聚集操作。
- 应选择不同的 $h_p,h_r$
并操作
- 包的并无需两次，直接合并即可
- 集合的并需要两趟，需要去重复。
- 第一趟：以相同的散列函数将R和S形成M-2个子表 $R_i,S_i$
- 第二趟：将 $S_i$ 再整体散列读入内存中，再依次处理 $R_i$ 的每一块，如判断 $R_i,S_i$ 都出现元组t，则仅输出t的一个副本，否则输出 $S_i,Ri$
交叉操作类似并操作
连接操作
- $R\Join_{R.y=S.y} S$
- 以连接属性Y作为散列关键字，设计散列函数
- 第一趟：使用相同的散列函数散列两个操作对象R和S，形成R1…Rm,S1…Sm
- 第二趟：将Si再整体散列读入到内存中，再依次处理Ri的每一块，进行连接

第五章查询编译器

2101 什么是查询优化

（1）为什么需要查询优化

关系数据库的执行效率问题
关系代数操作执行次序对效率的影响

（2）什么是查询优化

如何使数据库查询时间最短
三个层面进行优化
- 语义优化：利用模型的语义及完整性规则，优化查询
- 语法优化—逻辑层优化：利用语法结构，优化操作执行顺序
- 执行优化—物理层优化：存取路径和执行算法的选择与执行次序优化

2102 查询优化的总体思路

（1）语义优化–内容等价性

sql层优化，不在这里进行讨论，此处需要用户取想办法，相关研究再进行了

（2）语法优化（逻辑层优化）–内容等价性

基本思想：改变关系代数的操作次序：尽可能地早做选择和投影运算
关系代数地五种基本操作中哪些能够交换次序
次序变化前后两个表达式地等价性问题
关系代数表达式的等价变换定理及证明（略）
关系代数表达式的优化算法？逻辑查询计划形成

（3）执行优化（物理层优化）

获取数据库的相关信息（定期统计）
实现同一关系操作的不同例行程序
选择相应的例行程序
依据相关信息进行代价估算，选择代价最少的例行程序及确定相应的参数
形成查询计划：以基本的例行程序为基本，确定这些例行程序的执行顺序

（4）查询优化的总过程

用户书写sql语言
转化为关系代数
逻辑查询计划–逻辑层优化
- 关系代数操作顺序的优化
物理查询计划–物理层优化
- 代价估算
- 算法选择与装配次序
由执行引擎解释并调用算法（程序）予以执行

2103 逻辑层优化策略

（1）一个待优化的实例背景

考虑一个图书馆的关系数据库
$BOOKS(TUTLE,AUTHOR,PNAME,LC\_NO)$
$PNAME$ 为出版社名， $LC\_NO$ 为图书馆图书编号
$PUBLISHERS(PNAME,PADDR,PCITY)$
出版社名字，出版社地址，出版社城市
$BORROWERS(NAME,ADDR,CITY,CARD\_NO)$
$CARD\_NO$ 为图书证号
$LOADS(CARD\_NO,LC\_NO,DATE)$

（2）用语法树表达关系代数表达式

由树叶向树根反映了操作的先后次序

（3）逻辑优化的策略

尽可能地早做选择和投影
- 可以使得中间结果变小，减小几个数量级的执行时间
把选择和投影串接起来：
- 一元运算序列可以一起执行，只需对整个关系扫描一遍
把投影与其前后的二元运算结合起来
- 在第一次用关系时去掉一些无关属性，可以避免多次扫描整个关系
把某些选择与其前的笛卡尔积合并成一个连接
- 当 $R\times S$ 前有选择运算且期中有条件是R，S属性间的比较运算时，可将其转化为连接运算可节省时间
执行连接运算前对关系适当预处理
- 文件排序，建立临时索引等，可以使得俩关系公共值高效连接
找出表达式里的公共子表达式
- 若公共子表达式结果不大，可以预先计算，以后可读入此结果，节省时间较多，在试图情况下尤其有用

2104 关系代数操作次序交换的等价性

（1）等价性

定义：

设 $E_1,E_2$ 是两个关系操作表达式，若 $E_1,E_2$ 表示相同的映射，记当 $E_1,E_2$ 的同名变量带入相同的关系后产生相同的结果(影响几何)，则说 $E_1,E_2$ 是等价的，记为 $E_1\equiv E_2$

（2）哪些关系操作次序可以交换

定理L1：连接与连接，积与积的交换律

$E_1 \Join_F E_2\equiv E_2 \Join_F E_1$
$E_1 \Join E_2\equiv E_2 \Join E_1$
$E_1 \times E_2\equiv E_2\times E_1$

并，交运算也有交换律

定理L2：定理L1：连接与连接，积与积的结合律

$(E_1\Join_{F1}E_2)\Join_{F_2}E_3\equiv E_1\Join_{F1}(E_2\Join_{F_2}E_3)$
$(E_1\Join E_2)\Join E_3\equiv E_1\Join (E_2\Join E_3)$
$(E_1\times E_2)\times E_3\equiv E_1\times (E_2\times E_3)$

并，交运算也有结合律

定理L3：投影串接率

设属性集合 ${A_1,..A_n}\subseteq {B_1..B_m}$ , $E$ 是表达式，则有：

\pi_{A_1,..A_n}(\pi_{B_1,..B_m}(E))\equiv \pi_

此定理可以双向使用
- 正向可以将两遍扫描变为一边扫描
- 逆向可以将属性扩展便于投影操作的移动

定理L4：选择的串接率

若 $E$ 是关系代数表达式， $F_1,F_2$ 是条件，则有

\sigma_{F1}(\sigma_{F2}(E))\equiv \sigma_{F_1\wedge F_2}(E)

此定理可以双向使用
- 正向可以将两遍扫描变为一边扫描
- 逆向可以将属性扩展便于选择操作的移动

定理L5：选择和投影的交换律

设条件F只涉及属性 ${A_1...A_n}$ , $E$ 是关系表达式，则有

\pi_{A_1..A_n}(\sigma_{F}(E))\equiv\sigma_F(\pi_{A_1..A_n}(E))

更一般地，若

F

还涉及不属于

{A1,..A_n}

的属性

{B_1,..B_m}

,则

\pi_{A_1,...A_n}(\sigma_F(E))\equiv\pi_{A_1,..A_n}(\sigma_F(\pi_{A_1,..A_n,B_1,..B_m}(E)))

尽可能地早做选择

定理L6：选择合积的交换律

设 $E_1,E_2$ 是关系代数表达式

(1):若条件F只涉及 $E_1$ 中的属性：则有
$\sigma_F(E_1\times E_2)\equiv \sigma_{F}(E_1)\times(E_2)$
(2):若 $F=F_1\wedge F_2$ , $F_1$ , $F_2$ ,分别只涉及 $E_1,E_2$ 中属性，则有：
$\sigma_F(E_1\times E_2)\equiv \sigma_{F_1}(E_1)\times \sigma_{F_2}(E_2)$
(3):若 $F=F_1\wedge F_2$ , $F_1$ 只涉及 $E_1$ 中属性，而 $F_2$ 涉及 $E_1,E_2$ 中属性，则有
$\sigma_F(E1\times E2)\equiv \sigma_{F_2}(\sigma_{F_1}(E_1)\times E_2)$

定理L7:投影和积的交换律

设 $E_1,E_2$ 为俩关系的代数表达式， $A_1,...A_n$ 是出现在 $E_1$ 或 $E_2$ 中的一些属性，其中 $B_1,..B_m$ 出现在中 $E_1$ ，剩余的属性 $C_1,..C_k$ 出现在 $E_2$ 中，则有

\pi_{A_1..A_n}(E_1\times E_2)\equiv \pi_{B_1,..B_m}(E_1)\times \pi_{C_1,..c_k}(E_2))

定理L8:选择和并的交换律

设关系代数表达式 $E=E_1\cup E_2$ ， $F$ 是条件，则有：

\sigma_{F}(E_1\cup E_2)\equiv \sigma_F(E_1) \cup \sigma_F(E_2)

定理L9:选择和差的交换律

设关系代数表达式 $E=E_1-E_2$ ， $F$ 是条件，则有：

\sigma_{F}(E_1 - E_2)\equiv \sigma_F(E_1) - \sigma_F(E_2)

定理L10:投影和并的交换律

设关系代数表达式 $E=E_1\cup E_2,A_1...A_n$ 是 $E$ 中的一些属性，则有

\pi_{A_1..A_n}(E_1\cup E_2)\equiv \pi_{A_1..A_n}\cup \pi_{A_1..A_n}(E_2)

2105 基于关系代数的查询优化算法及示例

算法：关系代数表达式的优化算法
input：一个关系代数表达式的语法树
output：计算该表达式的程序
method：
- 依据定理L4,把形如 $\sigma_{F_1\wedge F_2\wedge ...\wedge F_n}$ 的选择表达式变成串接形式 $\sigma_{F1}(\sigma_{F2}(...(\sigma_{Fn}(E))))$
- 对每个选择，依据定理L4-L9，尽可能把它移动到树的底部
- 对每个投影，依据定理L3,7,10,5,尽可能的移到书的底部。如果一个投影是对表达式的所有属性进行的，则可以删去
- 依据定理L4，5把串接的选择和投影组合为单个选择，单个投影，或者一个选择后跟一个投影
- 对修改后的语法树，将其内节点按以下方式分组：
  - 每个二元运算节点和其所有的一元运算的直接祖先放在一组；对于所有的后代节点，若后代节点是一串一元运算且树叶为终点，则将这些一元运算节点放在改组中；如该二元运算节点是笛卡尔积，则其后代节点不能和它组合成连接，则不能将后代节点归入改组
- 产生一个程序：它以每组节点为一步，但后代组先执行

2106 物理层查询优化

（1）物理查询优化–总体思路

获取数据库的相关信息（定期统计）
实现同一关系操作的不同例行程序
选择相应的例行程序
依据相关信息进行代价估算，选择代价最少的例行程序及确定相应的参数
形成查询计划：以基本的例行程序为基本，确定这些例行程序的执行顺序
物理查询运算符
- 获取关系元组的操作
  - 表空间扫描法
  - 表空间扫描排序法
  - 索引扫描法
  - 索引扫描排序法
- 关系操作的各种实现算法
  - 一趟算法，两趟算法
  - 基于索引算法，基于散列算法，基于排序算法
- 迭代器构造–流水化，物化

物理查询运算符通常是关系代数操作符的一个特定实现

（2）衡量一个物理查询计划

依据数据库中的一些统计信息–存放在数据字典或系统目录中的

$T_R$ 或 $T(R):$ 关系R的元组数目
$B_R$ 或 $B(R):$ 关系R的磁盘块数目
$I_R$ 或 $I(R):$ 关系R的每个元组的字节数
$f_R$ 或 $f(R):$ R的块因子，即一个块中能够储存的R的元组数目
$V(A,R):$ R中属性A出现不同值的数目
$SC(A,R):$ R中属性A的选择基数，满足A上等值条件的平均记录数
$b:$ 每个磁盘块的字节数
…

DBMS依据上述统计信息对DB操作的各种物理查询计划进行评估，以确定最优的计划予以执行。

（3）如何收集这些信息

当一个表装入内存和创建索引的时候，统计信息不是被自动收集的，必须有DBA使用特定的命令来完成信息统计，这些命令就是收集统计信息并把其存入系统目录中的实用程序
随着表的更新操作。统计信息可能会过时，过时的统计信息会使DBMS确定方案时决策错误，因此要求DBA定期的对有频繁更新操作的Table进行统计
DBA要熟悉统计信息收集命令的使用，并定期执行

2107 代价估算

（1）投影运算的代价估算

投影运算并未减少行数，但可能有效地减少了存储结果关系地块数

（2）选择运算地代价估算

估算选择运算 $S=\sigma_{A=c}(R)$ 的大小

$T(S)$ 介于0 到 $T(R)-V(R,A)+1$ 之间
- 最多：A属性不同值的元组都只存在一个，剩余的都是 $A=c$ 的分组
估计： $T(S)=T(R)/V(R,A)$
- A属性的不同值的元组假设是平均分布的
当不知道 $V(R,A)$ 时，估计： $T(S)=T(R)/10$

估算选择运算 $S=\sigma_{A<c}(R)$ 的大小

一般取 $T(S)=T(R)/3$

估算选择运算 $S=\sigma_{C1 or C2}(R)$

$T(S)=n(1 - (1-\frac{m1}{n})(1-\frac{m2}{n}))$ ,m1为满足 $C1$ 的个数，m2为满足 $C2$ 的个数，R有n个元组

（3）连接运算的代价估算

估计连接运算 $S=R(X,Y) Natural Join S(Y,Z)$ 的大小

$T(S)=\frac{T(R)T(S)}{max(V(R,Y),V(S,Y))}$

2108 回顾

以往关系型数据库被认为是不可能的，因为连接会产生巨大的中间数据，但在查询优化后，中间数据变得可以接受，使得关系型数据库成为了现实。

查询优化
- 逻辑层优化
  - 关系代数操作次序优化
- 物理层优化
  - 代价估算
  - 算法选择和装配次序

第七章并发控制及第八章再论事务管理

2201 为什么要进行并发控制

（1）数据库可能存在不一致

三种典型不一致
- 丢失修改
- 不能重复读
- 脏读

（2）并发控制的缘由

graph LR
A(DB共享)-->B(多应用程序使用);
B-->C(可能同时使用);
C-->D(数据的不一致性);
D-->E(不一致性的类型);
E-->F(并发控制);
F-->G(并发控制方法);

（3）并发控制及相应的事务处理技术是DBMS的核心技术

核心概念：事务，并发控制，封锁

2202 深入认识事务

（1）事务的概念

事务（Transaction）
事务是数据库管理系统提供的控制数据操作的一种手段，通过这一手段，应用程序员将一系列的数据库操作组合在一起作为一个整体进行操作和控制，以便数据库管理系统能够提供一致性状态转换的保证。

（2）事务的宏观性和微观性

事务的宏观性（应用程序员看到的事务）

一个存取或改变数据库内容的一次执行，或者说一条或多条SQL语句的一次执行被看作一个事务
事务一般是由应用程序员提出，因此有开始和结束，结束前需要提交或撤销
一个事务可以处理一个数据或一条记录
复杂的事务可以处理一批数据或一批记录
一段程序语言，可能会循环执行，执行中，由SQL语句引出事务，直到事务结束，每次循环都将产生一个事务

事务的微观性（DBMS看到的事务）

对数据库的一系列基本操作（读，写）的一个整体性执行
事物的并发执行：多个事务在宏观上看是并发执行，但其在微观上的基本操作则可以是交叉执行的

（3）事务的特性

宏观独立性
微观交错执行
并发控制就是通过事务微观交错执行次序的正确安排，保证事务宏观的独立性，完整性和正确性
事务的特性 ACID
- 原子性（Atomicity）:DBMS能够保证事务的一组更新操作是原子不可分的，即对DB而言，要么全做，要么不做
- 一致性（Consistency）:DBMS保证事务的操作状态是正确的，符合一致性的操作规则，不能出现三种典型的不一致性。它是进一步由隔离性来保证的。
- 隔离性（Isolation）:DBMS保证并发执行的多个事务之间互相不受影响。例如两个事务T1，T2，既是并发执行，也相当于依次执行
- 持久性（Durablity）:DBMS保证已提交的事务影响是持久的，被撤销事务的影响是可以恢复的
具有ACID特性的若干数据库基本操作的组合体称为事务

（4）DBMS对事务的控制

2203 事务调度的可串行性

（1）基本概念

事务调度：一组事务的基本步（读，写，其它控制操作比如加锁，解锁等）的一种执行顺序称为对这组事务的一个调度。
并发调度：多个事务从宏观上看是并发执行的，但是其微观上的基本操作(读写)则是交叉执行的。
并发调度的正确性：当且仅当在这个并发调度下所得到的新数据库结果与分别串行地运行这些事务所得到地新数据库完全一直，则说调度是正确的。
可串行性：如果不管数据库初始状态如何，一个调度对数据库状态的影响都和某个串行调度相同，则我们说这个调度是可串行化的或者说可序列化的。
可串行化调度一定是正确地并行调度，但正确的并行调度，却未必第一事故可串行化的调度
并行调度的正确性是指内容上的结果正确性，而可串行性是指形式上结果正确性
可串行化的等效串行序列不一定唯一

（2）一种简单的事务调度的标记模型

$r_T(A):$ 事务T读A. $w_T(A):$ 事务T写A

（3）冲突的串行性

冲突：调度中的一对连续的动作，他们满足：如果它们的顺序交换，那么涉及的事务中至少有一个事务的行为会改变
有冲突的两个操作是不能交换次序的，没有冲突的两个事务是可交换的
几种冲突情况
- 同一事务的任何两个操作都是冲突的
- 不同事务对同一元素的两个写操作是冲突的
- 不同事务对同意元素的一读一写操作是冲突的
冲突可串行性：一个调度，如果通过交换两个相邻的无冲突的操作能够转换到某一个串行的调度，则称此调度为冲突可串行化的调度。
冲突可串行化是比可串行化更严格的概念
满足冲突可串行化，一定满足可串行性

（4）冲突可串行性判别算法

（1）问题

并发调度的正确性：当且仅当在这个并发调度下所得到的新数据库结果与分别串行地运行这些事务所得到的新数据库完全一致，则说调度是正确的
问题1：怎样判断一个并发调度是正确的
- 解决：通过判断是否为冲突可串行性
问题2：怎样产生一个正确的并发调度

（2）算法表达

构造一个前驱图（有向图）
节点是每一个事务 $T_i$ ，如果 $T_i$ 的一个操作与 $T_j$ 的一个操作发生冲突，且 $T_i$ 在 $T_j$ 前执行，则绘制一条边，由 $T_i$ 指向 $T_j$ ，表示 $T_i$ 要在前 $T_j$ 执行
测试检查：如果该有向图没有环，则是冲突可串行化的

2204 基于封锁的并发控制方法

（1）问题

怎样产生一个冲突可串行化的调度
- 基于封锁的并发控制
- 基于时间戳的并发控制
- 基于有效性确认的并发控制

（2）什么是“锁”

“锁”是控制并发的一种手段
- 每一数据元素都有一个唯一的锁
- 每一事务读写数据元素前，要获取锁
- 如果被其他食物持有该元素的锁，则要等待
- 事务处理完成后要释放锁

$L_i(A):$ 事务 $T_i$ 对数据元素 $A$ 加锁
$U_i(A):$ 事务 $T_i$ 对数据元素 $A$ 解锁

事务调度器拥有锁表，来管理锁
- 利用锁来保证冲突的可串行性
- 对所有事务的操作产生一个读写操作序列
- 保证事务的一致性
锁本身并不能保证冲突可串行性
锁为调度提供了控制的手段，但如何用锁，仍需说明，并采用不同的协议

（3）封锁协议需要考虑什么

封锁协议之锁的类型
- 排他锁（又称X锁）
  - 只有一个事务能读，写，其它任何事物不能读写
- 贡献锁
  - 所有事务都可以读，但任何事务都不能写
- 更新锁
  - 初始读，以后可升级为写
- 增量锁
  - 增量更新
  - 区分增量更新和其他类型的更新
封锁协议之相容性矩阵
- 当某事务对一数据对象持有一种锁时，另一事务再申请对该对象加某一类型锁时，时允许还是不允许
封锁协议之解锁和加锁的时机
- SQL之隔离性级别
- 读未提交
- 读已提交
- 可重复读
- 可串行化
封锁协议之封锁力度
- 封锁力度指封锁数据对象的大小
- 粒度单位：属性值-元组-元组集合-整个关系-整个DB某索引项-某个索引
- 从前往后：并发度变小，封锁开销小，从后往前相反

（4）两端封锁协议

什么是两段封锁协议

读写数据之前要获得锁。每个事务中所有封锁请求先于任何一个解锁请求
两阶段：加锁段，解锁段。加锁段中不能有解锁操作，解锁段中不能有加锁操作。
两段封锁协议可以保证冲突可串行化
归纳法证明P215
两端封锁协议可能产生死锁

2205 基于时间戳的并发控制

（1）什么是时间戳

一种基于时间的标志
时间戳具有唯一性和递增性
事务T启动时，系统将该时刻赋予T，为T的时间戳
时间戳可以表征一系列事务执行的先后顺序：时间戳小的事务先执行，大的后执行
利用时间戳，可以不用锁来进行并发控制

（2）基于时间戳并发控制的基本思路

借助时间戳，强制使一组并发事务的交叉执行，等价于一个特定顺序（时间戳从小到大）的串行执行
如何强制：执行判断冲突
- 如无冲突，予以执行
- 如有冲突，则撤销事务，并重启该事务
  此时该事务获得了一个更大的时间戳，表明是后执行的事务
有哪些冲突
- 读读无冲突
- 读写或写读冲突
- 写写冲突

（3）基于时间戳的简单调度

对DB中的每个元素x，系统保留其上最大的时间戳

RT（X）即R-timestamp（x）
- 读过该数据事务中最大的时间戳，即最后读x的事务的时间戳
WT（X）即W-timestamp（x）
- 写过该数据事务中最大的时间戳，即最后写x的事务的时间戳
事务的时间戳
- TS（T）：即TimeStamp
读写并发：
- 若T事务读x，则将T的时间戳TS与WT（x）比较：
  - 若TS大（T 后进行），则允许T操作，并且更改RT（x）为max(RT(x),TS)
  - 否则，有冲突，撤回T，重启T
- 若T事务写x，则将T的时间戳TS与RT（x）比较
  - 若TS大（T后进行），则允许T操作，并且更改WT（x）为max(WT(x),TS)
写写并发
- 若T事务写x，则将T的时间戳TS与WT（x）比较
  - 若TS大，则允许T写，并且更改WT（x）为T的时间戳
  - 否则有冲突，T撤回重做

（4）（3）的改进

新增标志：

C（x）：x的提交位
- 该位为真，当且仅当最近写x的事务已经提交
- C（x）的目的是避免出现事务读另一事务U所写数据然后U还未写完终止这样的情况
对来自事务T的读写请求，调度器可以
- 同意请求
- 撤销或终止T，并重启具有新时间戳的T(终止+重启，称为回滚)
- 推迟T，并在以后决定是终止T还是同意请求(如果请求是读，且此读可能是脏的)

调度规则

假设调度器收到请求 $r_T(x)$
- (1)如果TS(T)>=WT(x)，此读是事实上可实现的
  - 如果C(x)为真，同意请求。如果TS(T)>RT(x),置RT(x):=TS(T);否则不改变RT(x)
  - 如果C(x)为假，推迟T直到C(x)为真或写x的事务终止
- (2)如果TS(T)<=WT(x),此读是事实上不可实现的
  - 回滚T（过晚的读）
假设调度器收到请求 $w_T(x)$
- (1)如果 $TS(T)>=RT(x)$ ，且 $TS(T)>=WT(x)$ ，此写是事实上可实现的
  - 为x写入新值，置 $WT(x):=TS(T),C(x)=false$
- (2)如果 $TS(T)>=RT(x)$ ，但是 $TS(T)<WT(x)$ ，此写是事实上可实现的，但x已经有一个更晚的值
  - 如果 $C(x)$ 为真，那么前一个x的写已提交，则忽略T的写
  - 如果 $C(x)$ 为假，则我们推迟T，直到 $C(x)$ 为真或x的事务终止
- (3)如果 $TS(T)<RT(x)$ ，此写事实上是不可实现的
  - T必须回滚
假设调度器收到提交T的请求
- 它必须找到T所写的所有数据库元素x，并置 $C(x):=true$
- 如果有任何等待x被提交的事务，这些事务就被允许继续进行
假设调度器收到终止T的请求
- 向前面步骤一样回滚T。
- 那么任何等待T所写元素x的事务必须重新读或写，看这一动作现在的T的写被终止后是否合法

2206 基于有效性确认的并发控制方法

（1）思想

事务在启动时刻被赋予唯一的时间戳，以示其启动顺序
为每一个活跃的事务保存其读写数据集合，RS(T):事务T读数据的集合，WS(T):事务T写数据的集合
通过对多个事务的读写集合，判断是否有冲突，即有效性确认，来完成事务的提交与回滚，强制事务以可串行化的方式执行

（2）调度器的运行

事务分三个阶段进行

读阶段：事务从数据库中读取读集合中的所有元素，事务还在其局部地址空间计算它将要写的值
有效性确认阶段：调度器通过比较该事务与其它事务的读写集合来确认该事务的有效性
写阶段：事务往数据库中写入其写集合元素中的值
每个成功确认的事务是在其有效性确认的瞬间执行的
并发事务串行的顺序即事务有效性确认的顺序

调度器维护三个集合：

start集合：已经开始但尚未完成有效性确认的事务集合，对此集合中的事务，调度器维护start(T)，即事务T开始的时间
val集合，已经确认有效性但尚未完成第三阶段写的事务，对此集合中的事务，调度器维护start(T),val(T)，即T确认的时间
FIN集合，已经完成三阶段的事务，对于这样的事务T，调度器记录start(T),val(T),fin(T),即T的完成时间

（3）有效性确认的规则

（1）对于所有已经经过有效性确认，且在T开始前没有完成的U，即对于满足 $FIN(U)>START(T)$ 的U，检测
- $RS(T)\cap WS(U)$ 是否为空
- 若为空，则确认，否则不予确认
（2）对于所有已经经过有效性确认，且在T有效性确认前没有完成的U，即对于满足 $FIN(U)>VAL(T)$ 的U，检测
- $WS(T)\cap WS(U)$ 是否为空
- 若为空，则确认，否则不予确认

第六章系统故障对策

2301 数据库的故障及其影响

（1）基础需要需要知道的

DBMS运行方式
- DBMS利用内存和外存这样的存储体系来进行数据库管理
- 在内存中，又分为程序数据和系统数据
事务
- 上一章已经提及

（2）数据库的故障类型

事务故障
- 某一个程序自身运行错误所引起的故障
- 影响该程序本身
系统故障
- 由于掉电，非正常关机等所引起的故障
- 影响正在运行的事务以及数据库缓冲区，数据库缓冲区将涉及正在运行和已经运行的事务
介质故障
- 由于介质损坏等引起的故障
- 影响是全面的，既影响内存中的数据，也影响介质中的数据

2302 数据库回复的宏观思路

数据库故障回复
把DB由当前不正确状态恢复到已知为正确的某一状态
需要保证事务的
- 原子性：事务的所有操作，要么全部执行，要不全都不执行
- 持久性：已经提交的事务对数据库产生的影响是持久的，未提交的事务对数据库不应该有影响

（1）事务故障的回复

事务故障可以通过重做事务(Redo)和撤销事务(Undo)来恢复。重做事务可保证已经提交事务的持久性，而撤销事务则消除未提交事务的影响。

（2）系统故障恢复

运行日志：

运行日志是DBMS维护的一个文件，该文件以流水的形式记录乐每一个事务对数据库的每一次操作及操作顺序
运行日志直接写入介质存储上，会保持正确性
当事务对数据库进行操作时：先写运行日志，写成功后，再与数据库缓冲区进行信息交换
系统故障可以通过运行日志来恢复
- 按照运行日志记录的事务操作来重做事务（当事务在发生故障时已经正确结束）或撤销事务（当事务在故障发生时未结束）
但故障恢复是需要时间的
- 运行日志保留了若干天的记录，故障发生时应从哪个点开始恢复呢？
DBMS在运行日志中定期的设置和更新检查点
- 检查点是这样的时刻：在该时刻，DBMS强制使内存DB Buffer中的内容和介质DB中的保持一致，即将DB Buffer更新的所有内容写回DB
- 检查点表征了，在检查点之前内存中数据和介质中数据是保持一致的
系统故障的恢复
- 检查点之间结束的书屋不需要恢复(已经写回DB)
- 检查点之后结束或发生的事务需要依据运行日志进行恢复(不能确定是否写回DB)：故障点前结束的重做，故障点时刻未结束的撤销

（3）介质故障恢复

副本
- 在某一时刻，对数据库在其他介质存储上产生的令一份等同记录
- 用副本替代被损坏的数据库
介质故障的恢复
- 用副本替换被破环的数据库
- 由于介质故障影响全面，用副本恢复后还需要根据运行日志进行恢复
如何确定备份的时刻：转储点
- 过频，影响系统工作效率；过疏，会造成运行日志过大，也影响系统性能
- 备份转储周期与运行日志的大小密切相关，应注意防止衔接不畅而引起的漏洞

（4）小结

三种类型故障：事务故障，系统故障，介质故障
三种恢复手段：事务的撤销和重做，运行日志，备份
两个重要时刻：检查点和转储点

2303 运行日志的概念

（1）日志所记录的

每个事务都会读/写某些元素
- READ(X,t):将元素X读到事务的局部变量t中
- WRITE(X,t):将事务局部变量t写回元素X中
- INPUT(X):将元素X从磁盘读入到内存缓冲区中
- OUTPUT(X):将元素X写回到磁盘中
每个事务都以提交或者撤销结束
- COMMIT：事务提交
- ABORT：事务撤销
DBMS保证事务的：
- 持久性：已提交的事务对数据库产生的影响是持久的，未提交的事务对数据库不应用影响
  - 已提交的事务—缓冲区内容保证写回磁盘
  - 未提交的事务—缓冲区的内容不能影响磁盘
- 原子性：事务的所有操作，要么全都执行，要么全不执行

（2）不同的缓冲区策略影响事务的持久性

缓冲区处理策略

Force：内存中的数据最晚在commit的时候写入磁盘
No Steal：不允许事务commit之前把内存中的数据写入磁盘
No force：内存中的数据可以一直保留，在commit之后过一段时间在写入磁盘(此时在系统崩溃的时候可能还没写入到磁盘，需要redo)—灵活
Steal：允许事务commit之前把内存中的数据写入磁盘（此时若系统commit之前崩溃时），已经有数据写入到磁盘时，要恢复到崩溃前的状态，需要Undo）—灵活

（3）事务故障影响事务的原子性

在事务运行时故障，事务会中断，影响原子性

（4）怎样记录日志

日志

一个包含日志记录的只能追加的顺序文件，不同事务的日志交错存储，按事件发生顺序存储
发生系统故障时，使用日志进行恢复
- 故障时已提交的事务，重做（Redo）
- 故障时未提交的事务，撤销（Undo）
日志记录的信息
- < Start T >表明事务T已经开始
- < Commut T >表示事务T已经完成
- < Abort T >事务T未成功，被终止
- < T,x,v1 >或< T,x,v2 >，< T,x,v1,v2 >事务T改变了数据库元素X，X原来的值为v1，新值为v2
三种日志：Undo型日志，Redo型日志，Undo/Redo型日志

（5）缓冲区处理策略和日志恢复策略的关系

	No Steal	Steal
No Force		最快
Force	最慢

	No Steal	Steal
No Force	只需Redo 无需Undo	需要Redo 需要Undo
Force	无需Redo 无需Undo	无需Redo 只需Undo

2304 Undo型日志及其故障恢复

（1）Undo型日志的记录规则

对于任一事务T，按下列顺序像磁盘输出T的日志信息
- 首先<T,x,v>被写入日志中
- 其次，OUTPUT(x)
- 最后,<COMMIT T> 或<ABORT T>被写入到日志中
注意：undo型日志仅保留旧值。<T,x,v>，v为X原来的值
Undo型日志：“将事务改变的所有数据写到磁盘前不能提交该事务”

（2）利用Undo型日志进行恢复

首先，确定每一个事务是否已经完成
- start T,commit T = yes
- start T,abort T = no（已结束，但未完成）
- start T… = no
然后，从日志的尾部开始按日志记录的反序，处理每一日志记录，撤销未完成事务的所有修改
- commit T:标记T已完成
- abort T:标记T已经结束但未完成
- T,x,v:如果T未完成，则将X=v写回磁盘，否则跳过
- Start T:跳过

（3）检查点及其使用

检查点

静止检查点：周期性地对日志设置检查点
- 停止接受新的事务，等到所有当前活跃事务提交或终止，并在日志中写入COMMIT或ABORT记录后
- 将日志刷新到磁盘，写入日志记录<CKPT>,并再次刷新日志
非静止检查点
- 在设置检查点时不必关闭系统，允许新事务进入
- 在写入一条<CKPT(T1,…Tk)>（其中T1，…Tk）是所有活跃的未结束的事务
- 继续正常的操作，直到T1…T_k完成时，写入<END CKPT>

恢复时恢复到第一个检查点的位置，即恢复到第一个<END CKPT>或<CKPT>的位置

2305 Redo型日志及其故障恢复

（1）Redo型日志的日志记录规则

Undo型日志的问题“将事务改变的所有数据写入磁盘前不能提交该事务”
Redo型日志记录信息：
对于任一事务T，按下列顺序向磁盘输出T的日志信息
- 首先 T,x,v被写入到日志中
- 其次，COMMIT T被写到日志中
- 最后，OUTPUT(X)
注意：redo型日志保留新值，T,x,v，v为更新后的值
与undo型的差别，往后两步，先写提交记录输出，还是先输出再写提交记录

（2）利用redo日志进行恢复

首先，确定每一个事务是否已经完成
- start T,commit T = yes
- start T,abort T = no（已结束，但未完成）
- start T… = no
从日志的起始位置开始按日志记录的正序处理每一日志记录，重做已经提交事务的所有修改
- commit t：标记t已经完成
- abort t：标记t已结束但未完成
- t，x，v：如果t已经完成，则将x=v写回磁盘，否则跳过
- start t：跳过

（3）检查点及其应用

静态检查点（同Undo）
非静态检查点
- 再进行检查点设置时不必关闭系统，允许新事务进入
- 写入一条 start ckpt(t1,…tk)，其中t1,…tk是所有活跃的未结束的事务
- 将所有已提交的事务写回磁盘
- 继续正常的操作，直到t1,…tk都完成时，写入end ckpt
step1：寻找到最后的end ckpt
step2：从start ckpt里的事务的最早开始处开始恢复，忽略更早的提交事务

2306 Undo/Redo结合型日志及其故障恢复

（1）单种日志的问题

Undo型日志
- OUTPUT必须先做
- 如果 COMMIT T 可见，T确定地已经将所有其数据写回磁盘，因此不必重做
- 但可能引起性能下降（因为频繁的写磁盘）
Redo型日志
- OUTPUT必须后做
- 如果 COMMIT T不可见，T确定地没有将任何数据写回到磁盘，因此无需撤销
- 但灵活性差，数据必须在COMMIT后才可见
更好地—Undo/Redo 型日志

（2）Undo/Redo结合型日志记录规则

对于任一事务T，按下列顺序向磁盘输出T的日志信息
- 第一步，<T,X,u,v>被写到磁盘中
- 第二步，COMMIT T 或 OUTPUT T 都可以
Undo/Redo结合型日志既保留新值v，也有旧值u。

（3）Undo/Redo结合型日志进行恢复

自前向后地，按日志记录的正序，重做所有已经提交的事务；
自后向前地，按日志记录地反序，撤销所有未完成事务地修改