数据库复习笔记
本文是2017年秋季北大研究生课程《数据库原理与技术》的复习笔记。视角为数据库系统自身的设计与实现，主要包括存储、索引、查询处理/优化、事务、并发处理、恢复系统、并行数据库7个部分。
基础概念
关系代数6个基本操作
选择，投影，并，差，笛卡尔积，重命名
建表代码
create table department (
dept_name varchar(20),
building varchar(10),
budget int);
insert into department values
('Comp. Sci.', 'Taylor', 100000);
create table instructor (
id varchar(5),
name varchar(20),
dept_name varchar(20),
salary int);
insert into instructor values
('33456', 'Gold', 'Comp. Sci.', 75000);
select dept_name, id, name
from department natural join instructor;
select department.dept_name, instructor.name
from department, instructor
where department.dept_name = instructor.dept_name
视图（子查询）
从一个或多个表导出的虚拟的表，其内容由查询定义。具有普通表的结构，但是不实现数据存储。
例子：
create view v_id as select id from instructor;
select * from v_id;
drop view v_id;
存储和文件结构
RAID（Redundant Array of Independent Disk）
高效性、可靠性；RAID 1、RAID 5
文件组织
块的概念
定长记录：空闲链表
变长记录：单条记录的结构（空位图）+ 多条记录的结构（分槽的页结构）+ 记录间的顺序（堆、顺序、散列）
多表聚簇文件组织：优缺点
数据字典（数据库元数据）
数据库缓冲区
缓冲区概念：内存中用于存储磁盘块拷贝的那一部分。
缓冲区替换策略：LRU、CLOCK、MRU的适用场景
索引和散列
顺序索引
索引项按序存储
分类：主索引/辅助索引，稠密索引/稀疏索引
顺序索引的插入/删除，多级索引
B+树索引
顺序索引的缺点：（不考虑重组）随数据规模增大，查找性能下降；不适合频繁的插入/删除
B+树定义，查找
插入：1. 分裂时upper(n/2)个key给左边； 2.分裂后，右边节点的第一个key需要上移（如果是叶节点则copy up，非叶节点push up）
删除：1. 叶节点合并时，父节点先考虑和兄弟合并，合并不了需要拉上祖父节点重新分配指针；2. 如果合并时发现兄弟节点已满，则在两个节点间重新分配指针，这时候往往只需要再修改父节点中的key值
删除操作可能导致B+树非叶节点含有叶节点中并不存在的key值
通过复合多个码来解决单一码对应记录不唯一的问题
静态散列
哈希函数会把记录映射到一个固定大小的桶集合，桶溢出时采用溢出桶方案。随着数据的增长效率会变差，解决方案：为每个桶预留x%空间，定期重组（代价很高）
动态散列（可扩展散列、线性散列）
在静态散列的基础上增加一个桶地址表，根据记录数量动态选取哈希值的前缀，哈希值先映射到地址表中的表项在映射到桶，插入/删除会增加桶，视情况决定是否需要增加桶地址项。（在数据倾斜严重时，也需要溢出桶）
线性散列与可扩展散列的区别在于桶地址表的扩大速度，前者每次增加一项，后者翻倍。同时，线性散列分裂的未必是当前溢出的桶。
位图索引
适用于记录中那些只能取少量属性值的属性，如：性别，工资分档。如有n条记录，为每个可取的属性值建立一个n维的0-1向量。（有时，B+树的叶子节点存储这个搜索码的位图会比存储记录的地址节省空间
查询处理
磁盘平均访问时间Ts，磁盘传输时间Tr
查询处理代价衡量：访问磁盘次数，传输的磁盘块数
选择操作
假设索引使用B+树，树高度为H，以下操作的代价：
| 编号 | 需求 | 代价 |
|---|---|---|
| 1 | 线性搜索 | Ts+b*Tr（所有记录占b个块） |
| 2 | 主索引/辅助索引+码属性+等值比较 | (H+1)*(Tr+Ts) |
| 3 | 主索引+非码属性+等值比较 | H*(Tr+Ts)+Ts+b*Tr（符合条件的记录占连续的b块） |
| 4 | 辅助索引+非码属性+等值比较 | (H+n)*(Tr+Ts)（符合条件的记录分散在n个块上） |
| 5 | 主索引+区间搜索 | 理论上同3，实际可使用1 |
| 6 | 辅助索引+区间搜索 | 理论同4，实际可使用1 |
排序
外排序（M路归并排序，内存大小为M+1个块）
连接
对表s和表r做自然连接，表s在磁盘上占S个块，表r占R个块(S<R)，内存大小M个块。
块嵌套循环连接
朴素的二重循环，在小表可以放入内存时，作为内层循环可以提高效率；否则应当把小表放在外层循环减少磁盘访问时间（Ts>>Tr）
| 内存大小 | 代价 |
|---|---|
| M<S | (S*R+S)*Tr+2S*Ts |
| M>S | (S+R)*Tr+2Ts |
索引嵌套循环连接
在内层循环时，使用索引而非遍历来查找对应记录，如果用B+树组织索引，这样磁盘访问次数会正比于记录数，在实际中未必比朴素的二重循环快。
假设r为外表，有Nr条记录，B+树高度为h
| 内存大小 | 代价 |
|---|---|
| M<S | (Nr*(h+1)+R)*(Tr+Ts) |
归并连接（sort-merge join）
对表r和s先按照连接属性排序，再类似归并排序的方法读进内存合并。假设一次读进Br个r表块和Bs个s表数据块:
| 代价(排序之后) |
|---|
| (S+R)*Tr+(S/Bs+R/Br)*Ts |
散列连接
在连接属性上建立散列函数，只有被分到同一个桶的记录才需要考虑连接。对于在同一个桶内的r表记录和s表记录，为其中一个创建哈希索引（build phase），用另外一个的记录来探查连接值相等的记录（probe phase）
递归划分/混合散列连接
表达式计算
两种方式：物化和流水线
查询优化
为了找到代价最小的查询执行计划，查询优化器需要以下三步：1）产生逻辑上与给定表达式等价的表达式；2）对产生的表达式已不同的方式做注释，产生不同的查询计划；3）估计执行代价，选择代价最小的一个计划
表达式等价转换
关系代数层面，如：连接操作的交换律、结合律
表达式结果集大小估计
数据库会存储一些统计信息：
| 符号 | 含义 |
|---|---|
| Nr | 关系r的元组数 |
| Br | 包含关系r元组的磁盘块数 |
| Lr | 关系r中每个元组的字节数 |
| V(A, r) | 关系r中属性A出现的非重复值个数 |
| Histogram | 每个属性的取值分布直方图 |
以及索引的一些统计信息（如：B+树深度）用于估计查询中中间结果的大小
执行计划选择
1）基于代价的的搜索：通常搜索范围大，在特定问题（如：连接顺序）上可用巧妙的算法优化；
2）基于启发式规则的：尽早做选择，投影（规则并不一定能减少代价，但是会不考虑数据情况直接使用）
3）其他优化方法：嵌套子查询的优化，物化视图，top-K，连接极小化，多查询优化，参数化查询优化
事务
ACID
原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）、持久性（Durability）
事务状态
| 状态 | 描述 |
|---|---|
| 活动的（active） | 初始状态 |
| 部分提交的（partial commited） | 最后一条语句执行后 |
| 失败的（failed） | 发现不能正常执行后 |
| 中止的（aborted） | 事务回滚并且恢复到数据库在事务执行前的状态后 |
| 提交的（commited） | 事务成功执行后 |
冲突可串行化
I和J是不同事务在同样的数据项上的操作，如果I、J中至少有一个是写操作，则称I和J是冲突的。在调度S中，如果相邻的两条指令没有冲突，那么可以调换这两条指令的顺序得到一个等价的新调度S'。如果可以通过一系列的指令调换从当前调度S得到某个串行的调度S'，那么称S是冲突可串行化的。
检测方法：拓扑排序
可恢复调度和无级连调度
可恢复调度：如果事务Tj读取了事务Ti写的值，那么Tj必须在Ti提交之后提交
无级连调度：如果事务Tj读取了事务Ti写的值，那么Ti的提交必须在Tj这一读操作之前
事务隔离性级别
可串行化，可重复读，已提交读，未提交读。前三种都只允许读已提交的数据，已提交读不要求同一事务内对同一数据项两次读的结果一样，只要求读已提交的数据。许多数据库默认的隔离性级别就是已提交读。
并发控制
锁的基本概念
共享锁：事务T获得了数据Q上的共享锁，则T可读但不可写Q
排他锁：事务T获得了数据Q上的排他锁，则T可以读也可以写Q
死锁的例子，读写数据项完成后立即释放锁可能带来的不一致现象，饿死的处理方法
两阶段锁协议
该协议要求事务按照两个阶段申请/释放锁：1）增长阶段（growing phase）：事务可以申请锁，不能释放锁；2）缩减阶段（shrinking phase）：事务可以释放锁，但不能申请锁。
封锁点：遵守两阶段锁协议的事务获得最后一把锁后的时间点。
| 性质 | 解决方案 |
|---|---|
| 可串行化 | 基础的两阶段锁协议就可以保证 |
| 死锁 | 无法避免，杀死并回滚其中一个事务 |
| 级联回滚 | 要求排他锁在事务提交后方可释放 |
变种：严格两阶段锁协议，强两阶段锁协议，带锁升级的两阶段锁协议
死锁处理
分为死锁预防、死锁检测/恢复两类方案。
死锁预防
1）要求事务开始时申请所有需要的锁，结束后统一释放
2）在数据项上强制加上偏序关系，如树形协议
3）wait-die协议：基于非抢占机制。事务Ti需要事务Tj持有的数据项时，如果Ti老，那么Ti等待，否则Ti回滚
4）wound/wait协议：基于抢占机制。事务Ti需要事务Tj持有的数据项时，如果Ti年轻，那么Ti等待，否则Tj回滚（Tj被伤害）
死锁检测/恢复
有向图的环检测算法+选择代价最小的事务回滚
多粒度
应允许事务在不同粒度的数据上加锁，如：数据库、表、记录。这些数据可以组织成一棵树，每次加锁时不仅需要给当前节点加锁，还要给从当前节点到根节点路径上的所有节点加锁，因此引进了3种新的意向锁：
1）共享型意向锁（IS）：表示当前节点的后代节点中有共享锁
2）排他型意向锁（IX）：表示当前节点的后代节点中有排他锁
3）共享排他型意向锁（SIX）：表示当前节点为根的子树显示加了共享锁，在后代节点持有排他锁。
兼容性矩阵：
| 空 | IS | IX | S | SIX | X |
|---|---|---|---|---|---|
| IS | true | true | true | true | false |
| IX | true | true | false | false | false |
| S | true | false | true | false | false |
| SIX | true | false | false | false | false |
| X | false | false | false | false | false |
基于时间戳的协议
每个事务T开始执行前被赋予一个时间戳TS(T)，时间戳决定了串行化顺序，如果TS(Ti)<TS(Tj)，系统需保证产生的调度等价于事务Ti在事务Tj前的某个串行调度。实现中，每个数据项Q维护两个值：
1）W-timestamp(Q)：成功执行write(Q)的所有事务的最大时间戳
2）R-timestamp(Q)：成功执行read(Q)的所有事务的最大时间戳。
事务根据自身时间戳和这两个值决定回滚还是成功执行并更新。
| 性质 | 解决方案 |
|---|---|
| 可串行化 | 基础的时间戳协议就可以保证 |
| 死锁 | 不存在，但存在饿死 |
| 可恢复性 | 不能保证 |
| 级联回滚 | 可能发生 |
Thomas写规则与视图可串行化
Thomas写规则：一个事务T发出写请求write(Q)时，如果W-timestamp(Q)>TS(T)，在基础时间戳协议中，事务T需要回滚。Thomas写规则认为此时的写操作可以直接忽略。对于任何事务T'，如果TS(T')<W-timestamp(Q)，则应当回滚，如果TS(T')>W-timestamp(Q)，应当看到的Q应当是W-timestamp(Q)对应事务的写结果，而不是事务T中写操作的结果。
Thomas写规则得到的调度不是冲突可串行化的，但是视图可串行化的，简而言之，两个调度中每个事务都读取相同的值，最后写的结果一致，那就是视图等价的。下面这个调度和串行调度<T1, T2>是视图等价的，而不是冲突等价的：
T1 T2
read(Q)
write(Q)
write(Q)
基于有效性检查的协议
每个事务分为三阶段执行：1）读阶段，事务读入局部变量，写操作只对局部变量进行；2）有效性检查阶段；3）通过检查的事务把结果写回，否则事务执行失败。
根据步骤2）开始的时间TS(T)排序，得到一个等价的串行化调度，在检验中，满足TS(Ti)<TS(Tj)的事务必须满足两个条件之一：
1）Tj开始读阶段前，Ti已经写回；2）Ti的写阶段在Tj的检验开始之前完成，并且Ti写的内容和Tj读的内容不相交。
| 性质 | 解决方案 |
|---|---|
| 可串行化 | 可以保证 |
| 死锁 | 不存在，但存在饿死 |
| 可恢复性 | 可以保证 |
| 级联回滚 | 可以保证 |
多版本协议
每个数据项有一个版本序列 <Q1, Q2,..., Qn>，每一项包含三个属性：
1）这个版本的值；2）W-timestamp(Qi)，创建这个版本的事务时间戳；3）R-timestamp(Qi)读过这个版本的最大事务时间戳
优势：读操作从不失败并且不等待
劣势：引入了额外的R-timestamp更新；事务间的冲突完全靠回滚而没有等待解决。
多版本两阶段锁协议
将事务分为只读事务和更新事务，只读事务不需要锁，直接读创建时间戳小于自己时间戳的版本值；更新事务在读操作时，需要加共享锁，在写操作时，需要加排他锁，并创建一个时间戳为正无穷的版本，在更新事务提交后，再把时间戳改为自己的时间戳。这样相当于确保了写操作在最后执行。因而可恢复，无级联。
恢复系统
日志
事务Ti开始：<Ti start>；事务修改了数据项A：<Ti, A, old value, new value>；事务提交：<Ti commit>；事务undo结束：<Ti abort>
系统崩溃后，在恢复时会根据日志执行redo和undo行为，redo把数据项更新为new value，undo把数据项恢复成old value。给定一份日志，对于有<Ti start>/<Ti commit>或<Ti start>/<Ti abort>对的事务，执行redo，对于只有<Ti start>的事务执行undo，undo时会写新的日志，以<Ti abort>结束。
检查点
检查点是为了避免每次扫描所有日志，产生大量不必要的redo。朴素检查点的做法是：
1）把所有位于内存的日志输出到稳定存储中；
2）把所有缓冲块的内容输出到稳定存储中；
3）记录所有当前活跃的事务列表L，在日志中写入<checkpoint L>；
下次恢复时，只需要恢复L中的所有事务，以及所有在写入<checkpoint L>后开始的事务；
举例：日志中所有事务的集合是{T1, T2, ..., T10}，最后一次检查点内容为<checkpoint T7 T9>，那么下次系统重启只需要恢复{T7, T9, T10}，并且可以清除T1-T6所有的日志内容
朴素检查点要求在检查点执行过程中，事务不能再往主存中写入新的日志和数据项。
模糊检查点放宽了这一要求，因为步骤2）可能非常耗时。模糊检查点策略中先写checkpoint日志，再进行缓冲块输出，在输出过程中，允许事务更新那些不相关的缓冲块。这样的问题在于如果在2）步骤发生故障，checkpoint记录的L列表有可能是不完全的，因此引入了一个last_checkpoint指针，它指向最后一个完成步骤2）的checkpoint位置。
并行数据库
架构：Share-memory，Share-disk，Share-nothing
数据划分方式：
| 方法名 | 优点 |
|---|---|
| range partition | 快速等值连接，区间查询，group-by操作 |
| hash partition | 快速等值连接，group-by操作 |
| round robin partition | 负载均衡 |
range-partition的问题主要在数据倾斜上，可以用直方图等统计信息帮助均衡
并行的数据库操作：
1）选择：如果数据划分依据查询的属性，那么只要找相关的节点就可以了，否则并行的查找所有的；
2）排序：range-partition sort，parallel external merge-sort
3）连接：等值常采用hash join，非等值的采用fragment-and-replicate join
练习
1. 哈希连接和归并连接分别在什么情况下效率更高
答：哈希连接和排序归并连接在时间复杂度上相同，但是哈希连接需要的内存更小。因此大部分情况下哈希连接更有效，但排序归并连接在以下情况更有效：
1）输入表有序；2）要求输出表有序；3）非等值连接；4）哈希中数据偏斜严重
2. 举一个启发式规则：“尽早做选择操作”失效的例子
答：考虑查询：σ_θ(R⋈S)，θ是R表的属性，满足下面两个条件时，先在R上做选择操作未必能加速查询：
1）R表比S表小很多；2）R表的θ属性上没有索引，但是R和S的连接属性上有索引。
3. 结合一个简单事务说明ACID特性的含义及保证措施：
T1: Read(A)
A := A - 50
Write(A)
Read(B)
B := B - 50
Write(B)
答：一致性在本例中指A+B在事务执行前后不会改变。如果本例理解为银行过户行为，一致性要求余额不会凭空产生或消失。一致性是由编写事务的程序员保证的；
原子性是指事物要么不执行，要么所有操作全部执行。原子性的保证是由恢复系统保证的，对于事务中要写的数据，log中会记录事务发生前的值，如果事务未能完全执行，需要恢复系统根据log恢复；
持久性是指一旦事务成功执行，任何系统故障都不能导致这次事务执行的结果丢失。持久性同样是由恢复系统保证，事务成功执行后，要么结果已经写回磁盘，要么相关的更新信息写回磁盘，下次系统启动时可以根据这些信息重新执行事务；
隔离性是指单个事务的执行不应该收到其他事务影响。隔离性是由并发控制系统保证的，必须保证多个事务并发执行的效果等价于某个串行事务序列执行的效果。
