数据管理基础
第九章 关系查询处理和查询优化
查询处理
查询分析
- 对查询语句进行扫描、词法分析和语法分析
查询检查
- 合法权检查
- 视图转换
- 安全性检查
- 完整性初步检查
根据数据字典中有关的模式定义检查语句中的数据库对象，如关系名、属性名是否存在和有效
如果是对视图的操作，则要用视图消解方法把对视图的操作转换成对基本表的操作
根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查
检查通过后把SQL查询语句转换成内部表示，即等价的关系代数表达式。
关系数据库管理系统一般都用查询树，也称为语法分析树来表示扩展的关系代数表达式。
查询优化
- 代数优化/逻辑优化：指关系代数表达式的优化
- 物理优化：指存取路径和低层操作算法的选择
选择依据：
- 基于规则
- 基于代价
- 基于语义
查询执行
依据优化器得到的执行策略生成查询执行计划
代码生成器生成执行查询计划的代码
两种执行方法：
- 自顶向下
- 自底向上
实现查询操作
选择操作典型实现方法：
- 全表扫描方法
- 对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出
- 适合小表不适合大表
- 索引扫描方法
- 适合于选择条件中的属性上有索引(例如B+树索引或Hash索引)
- 通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组
连接操作的实现：
连接操作是查询处理中最耗时的操作之一
- 嵌套循环算法
- 排序-合并算法
- 索引连接算法
- Hash Join算法
查询优化
关系系统的查询优化是关系数据库管理系统实现的关键技术优势关系系统的有点所在，减轻了用户选择存取路径的负担
关系查询优化是影响关系数据库管理系统性能的关键因素
由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性
查询优化的优点：
查询优化的总目标：
有选择和连接操作时，先做选择操作，这样连接的元组可以大大减少，这就是代数优化
采用索引可以减少连接时间，这就是物理优化
代数优化
- 策略：才有等价变换来提高查询效率
- 关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的
- 两个关系表达式E1和E2是等价的，可记为E1≡E2
常用的等价变换规则：
启发式规则
查询树的启发式优化
一个例字
物理优化
代数优化改变查询语句中操作的次序和组合，不涉及底层的存取路径，对于一个查询语句有许多存取方案，它们的执行效率不同， 仅仅进行代数优化是不够的 ，物理优化就是要选择高效合理的操作算法或存取路径，求得优化的查询计划
优化方法：
- 基于规则的启发式优化（遇到A做$A_1$，遇到B做$B_1$）
- 启发式规则是指那些在大多数情况下都适用，但不是在每种情况下都是最好的规则
- 基于代价估算的优化
- 优化器估算不同执行策略的代价，并选出具有最小代价的执行计划
- 两者结合的优化方法
- 常常先使用启发式规则，选取若干较优的候选方案，减少代价估算的工作量，然后分别计算这些候选方案的执行代价，较快地选出最终的优化方案
启发式规则
选择操作
连接操作
基于代价的优化
启发式规则优化是定性的选择，适合解释执行的系统
- 解释执行的系统，优化开销包含在查询总开销之中
编译执行的系统中查询优化和查询执行是分开的
- 可以采用精细复杂一些的基于代价的优化方法
第十章 数据库恢复技术
事务的基本概念
事务
用户定义的一个数据库操作序列，这些操作要么全做，要么全不做，是一个不可分个的工作单位
一个事务可以是一条SQL语句，一组SQL语句或整个程序。一般来讲一个程序中包含多个事务
- 事务是恢复和并发控制的基本单位
定义事务一般有三条：
1 | BEGIN TRANSACTION; |
事务通常以BEGIN TRANSACTION开始。COMMIT表示提交，ROLLBACK表示回滚，即在运行过程中发生某种故障，事务不能继续执行，系统将事务中对数据库的所有已完成的操作全部撤销，回滚到事务开始时的状态。
事务的ACID特性
- 原子性（Atomicity）：事务是数据库的逻辑工作单位，事务中的操作要么都做，要么不做
- 一致性（Consistency）：事务执行的结果必须使数据库从一个一致性状态准移到另一个一致性状态。当数据库只包含成功事务提交结果时数据库处于一致性状态。如果发生故障，有些事务完成部分就被迫中断，而这些事务对数据库的修改已经有一部分写入物理数据库，这是数据库就处于一种不确定状态
- 隔离性（Isolation）：一个事务的执行不能被另一个事务干扰
- 持续性（Durability）：也称永久性，事务一旦提交，对数据的修改就是永久性的
保证事务ACID特性是事务管理的重要任务。
数据库恢复
故障
- 事务内部的故障有的可以通过事务程序本身发现，有的是非预期的（占大部分，一般事务内部的故障用来指这类故障），不能由事务程序发现。
- 事务撤销：在不影响其它事务运行的情况下，强行回滚该事务，即撤销该事务已经对数据库作出的修改。
- 系统故障（软故障）是指造成任何系统停止运转的任何事件，使得系统要重新启动。这类错误影响所有正在运行的事务，但不破坏数据库。此时主存内容，特别是数据库缓冲区（在内存）中的内容都已被丢失，所有运行事务都非正常终止
- 介质故障（硬故障）指外存故障。
- 计算机病毒
恢复
建立冗余数据最常用的技术是数据转储和登记日志文件
数据转储
- 转储是指数据库管理员定期地将整个数据库复制到磁带、磁盘或其他存储介质上保存起来的过程
- 备用的数据称为后备副本或后援副本
- 当数据库遭到破坏后可以将后备副本重新装入，但重装后的副本只能将数据库恢复到转储时的状态
静态转储：在系统中无运行事务时进行的转储操作，开始时处于一致性状态，转储期间不允许对数据库的任何存取操作、修改活动，得到的也是一个数据一致性的状态
- 转储必须等待事务结束，新的事务也需要等待转储结束。会降低数据库的使用性
- 实现简单
动态转储：允许转储期间对数据库进行存取或修改，即转储和用户事务可以并发执行
- 不用等待用户事务结束，也不影响新的事务的运行
- 不能保证副本中的数据正确有效。在转储期间的某时刻Tc ，系统把数据A=100转储到磁带上，而在下一时刻T**d ，某一事务将A改200，后备副本上的A过时了
- 需要把动态转储期间各事务对数据库的修改活动登记下来，建立日志文件。后备副本加上日志文件就能把数据库恢复到某一时刻的正确状态
海量转储与增量转储
日志文件
日志文件的格式和内容
日志文件是用来记录事务对数据库的更新操作的文件
- 以记录为单位的日志文件
- 以数据块为单位的日志文件
作用
用来进行事务故障恢复和系统故障恢复，并协助后备副本进行介质故障恢复
登记日志文件
为保证数据是可恢复的，登记日志文件必须遵循两条原则
- 登记的次序严格按并发事务执行的时间次序
- 必须先写日志文件，后写数据库
- 先写数据库如果没有写上日志文件则无法恢复，而先写日志文件即便没有写数据库，也只是恢复时多执行一次不必要的UNDO操作
恢复策略
事务故障的恢复
- 事务在运行至正常终止点前被终止，这时恢复子系统应利用日志文件撤销此事务对数据库进行的修改
- 系统自动完成，对用户透明
- 系统的恢复步骤：
系统故障的恢复
- 撤销故障发生时未完成的事务，重做已完成的事务。
- 系统自动完成，无需用户干预：
介质故障的恢复
- 重装数据库，然后重做已完成的事务。
- 需要数据库管理人员的介入，只需重装最近转储的数据库副本和有关的各日志文件副本，然后执行系统提供的恢复命令即可，具体的恢复操作仍由数据库管理系统完成
检查点
两个问题：
搜索整个日志耗费大量时间
重做很多不必要的事务，浪费大量时间
具有检查点的恢复技术
增加检查点记录
- 建立检查点时刻所有正在执行的事务清单
- 这些事务最近一个日志记录的地址
增加重新开始文件
- 记录各个检查点记录在日志文件中的地址
恢复子系统在登录日志文件期间动态地维护日志
- 周期性地执行建立检查点、保存数据库状态的操作
- 具体步骤：
- 恢复子系统定期或不定期地建立检查点，保存数据库状态
使用检查点方法可以改善恢复效率：当事务T在一个检查点之前提交，在恢复处理时没有必要对事务T执行重做操作。
数据库镜像
介质故障对系统影响最为严重，恢复费时；数据库管理人员必须周期性地转储数据库；技术发展，容量成本下降，为了避免磁盘介质出现故障影响数据库的可用性 —-> 数据库镜像
频繁地复制数据会降低系统运行效率，实际应用中只选择对关键数据和日志文件镜像。
第十一章 并发控制
概述
事务并发执行带来的问题
- 会产生多个事务同时存取统一数据的情况
- 可能会存取和存储不正确的数据，破坏事务隔离性和数据库的一致性
数据库管理系统必须提供并发控制机制，并发控制机制是衡量一个数据库管理系统性能的重要标志之一
多事务执行方式
事务串行执行
- 每个时刻只有一个事务运行，其他事务必须等到这个事务结束以后方能运行
- 不能充分利用系统资源，发挥数据库共享资源的特点
交叉并发方式（Interleaved Concurrency）
- 在单处理机系统中，事务的并行执行是这些并行事务的并行操作轮流交叉运
- 单处理机系统中的并行事务并没有真正地并行运行，但能够减少处理机的空闲时间，提高系统的效率
同时并发方式（simultaneous concurrency）
- 多处理机系统中，每个处理机可以运行一个事务，多个处理机可以同时运行多个事务，实现多个事务真正的并行运行
- 最理想的并发方式，但受制于硬件环境
- 更复杂的并发方式机制
并发控制
事务是并发控制的基本单位
并发控制机制的任务
- 对并发操作的正确调度
- 保证事务的隔离性
- 保证数据库的一致性
并发操作带来的数据不一致
丢失修改
不可重复读
读“脏”数据
数据不一致性及并发控制
- 数据不一致性：由于并发操作破坏了事务的隔离性
- 并发控制就是要用正确的方式调度并发操作，使一个用户事务的执行不受其他事务的干扰，从而避免造成数据的不一致性
- 对数据库的应用有时允许某些不一致性，例如有些统计工作涉及数据量很大，读到一些“脏”数据对统计精度没什么影响，可以降低对一致性的要求以减少系统开销
并发控制的主要技术
- 封锁(Locking)
- 时间戳(Timestamp)
- 乐观控制法
- 多版本并发控制(MVCC)
封锁
封锁是实现并发控制的一个非常重要的技术
事务T在对某个数据对象操作前请求加锁，在T释放锁之前其它事务不能更新数据对象。
封锁类型
- 排它锁（写锁）（X锁）
- 事务T对A加X锁，其它事务不能加任何锁
- 其它事务不能读取和修改A
- 共享锁（读锁）（S锁）
- 事务T对A加S锁，其它事务可以加S锁不能加X锁
- 其它事务可以读取但不能修改A
封锁协议
对数据对象加锁时需要约定一些规则：
- 何时申请X锁或S锁
- 持锁时间
- 何时释放
三级封锁协议：
一级封锁协议：事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。（包括正常结束和非正常结束）
- 可防止丢失修改，并保证事务T是可恢复的
如果仅仅读数据而不对其进行修改，是不需要加锁的，所以不能保证可重复读和不读“脏”数据
二级封锁协议：在一级协议的基础上增加事务T在读取数据R之前必须先对其加S锁，读完后可释放S锁
可以防止读出的数据是一个临时数据
防止了丢失修改，还可进一步防止脏数据
不保证可重复读
三级封锁协议：在一级协议的基础上增加事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放
- 防止丢失修改和读“脏”数据，保证不可重复读
三级协议的主要区别在于什么操作需要申请封锁以及合适释放锁（即持锁时间）
不同的封锁协议使事务达到的一致性级别不同，封锁协议级别越高，一致性程度越高
加锁的粒度越大，事务之间互相等待的概率越高
活锁
事务T1封锁了数据R
事务T2又请求封锁R，于是T2等待。
T3也请求封锁R，当T1释放了R上的封锁之后系统首先批准了T3的请求，T2仍然等待。
T4又请求封锁R，当T3释放了R上的封锁之后系统又批准了T4的请求……
T2有可能永远等待，这就是活锁的情形
避免活锁的简单办法是采用先来先服务的策略（还有许多调度算法）
死锁
事务T1封锁了数据R1
T2封锁了数据R2
T1又请求封锁R2 ，因T2已封锁了R2 ，于是T1等待T2释放R2上的锁
接着T2又申请封锁R1 ，因T1已封锁了R1 ， T2也只能等待T1释放R1上的锁
这样T1在等待T2 ，而T2又在等待T1 ， T1和T2两个事务永远不能结束，形成死锁
死锁的预防
产生死锁的原因是两个或多个事务都已封锁了一些数据对象，然后又都请求对已为其他事务封锁的数据对象加锁，从而出现死等待。预防死锁的发生就是要破坏产生死锁的条件
一次封锁法：每个事务必须一次将所有要使用的数据全部加锁，否则不能继续执行
缺点：
扩大封锁范围，降低了系统的并发度
- 难以事先精确确定每个事务要封锁的数据对象，为此扩大封锁范围，进一步降低了系统的并发度
顺序封锁法：预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实施封锁
- 缺点
- 维护成本高：数据库系统中封锁的数据对象极多，并且随数据的插入、删除等操作而不断地变化，要维护这样的资源的封锁顺序非常困难，成本很高
- 事务的封锁请求可以随着事务的执行而动态地决定，很难事先确定每一个事务要封锁哪些对象，因此也就很难按规定的顺序去施加封锁
死锁的诊断
与操作系统类似，一般采用超时法或事务等待图法
超时法：一个事务等待时间超过了规定的实现就认为发生了死锁
优点是实现简单
可能误判
- 时限设置的太长死锁发生后不能及时发现
等待图法：并发控制子系统周期性地生成等待事务图，并进行检测。如果发现图中存在回路，则表示系统中出现了死锁
- 事务等待图是一个有向图G=(T，U)
- T为结点的集合，每个结点表示正运行的事务
- U为边的集合，每条边表示事务等待的情况
- 若T1等待T2 ，则T1 ， T2之间划一条有向边，从T1指向T2
死锁的解除
选择一个处理死锁代价最小的事务，将其撤销，释放此事务持有的所有锁，使其它事务得以继续运行下去。
事务调度
并行调度的可串行性
可串行调度：对个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行这些事务时的结果相同。
可串行性：
- 是并发事务正确调度的原则
- 一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度
冲突可串行化
判断可串行化调度的充分条件
冲突操作：指不同的事务对同一数据的读写操作和写写操作
不能交换的动作：
- 同一事务的两个操作
- 不同事务的冲突操作
一个调度Sc在保证冲突操作的次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一个调度Sc’，如果Sc’是串行的，称调度Sc是冲突可串行化的调度
若一个调度是冲突可串行化，则一定是可串行化的调度，因此可以用这种方法来判断一个调度是否是冲突可串行化的
两段锁协议
数据库管理系统普遍采用两段锁协议的方法实现并发调度的可串行性，从而保证调度的正确性
- 在对任何数据进行读、写操作之前，事务首先要获得对该数据的封锁
- 在释放一个封锁之后，事务不再申请和获得任何其他封锁
两段锁的含义:事务分为两个阶段：
- 第一阶段是获得封锁，也称为扩展阶段
- 事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁
- 第二阶段是释放封锁，也称为收缩阶段
- 事务可以释放任何数据项上的任何类型的锁，但是不能再申请任何锁
事务遵守两段锁协议是可串行化调度的充分条件，而不是必要条件
若并发事务都遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的
若并发事务的一个调度是可串行化的，不一定所有事务都符合两段锁协议
两段锁协议与防止死锁的一次封锁法
一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行，因此一次封锁法遵守两段锁协议
但是两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁
封锁粒度
封锁对象的大小称为封锁粒度
封锁对象：逻辑单元、物理单元
- 封锁的粒度越大，数据库所能够封锁的数据单元就越少，并发度就越小，系统开销也越小
- 封锁的粒度越小，并发度较高，但系统开销也就越大
多粒度封锁
在一个系统中同时支持多种封锁粒度供不同的事务选择
选择封锁粒度，同时考虑封锁开销和并发度两个因素，适当选择封锁粒度
- 需要处理多个关系的大量元组的用户事务：以数据库为封锁单位
- 需要处理大量元组的用户事务：以关系为封锁单元
- 只处理少量元组的用户事务：以元组为封锁单位
多粒度树
多粒度封锁协议：
允许多粒度树中的每个节点被独立地加锁
对一个节点加锁意味着这个节点的所有后裔节点也被加以同样类型的锁
两种方式封锁
- 显示封锁：直接加到数据对象上的封锁
- 隐式封锁：是该数据对象没有独立加锁，是由于其上级结点加锁而使该数据对象加上了锁
- 两种方式效果一致
系统检查封锁冲突时，要检查显示封锁和隐式封锁
对某个数据对象加锁，系统要检查
- 该数据对象
- 有无显式封锁与之冲突
- 所有上级节点
- 是否与该数据对象上的隐式封锁冲突
- 所有下级节点
- 看上面的显式封锁是否与本事务的隐式封锁冲突
- 该数据对象
意向锁
目的：提高对某个数据对象加锁时系统的检查效率
如果对一个节点加意向锁，说明该节点的下一层节点正在被加锁
对任意结点加基本锁，必须先对它的上层结点加意向锁
意向共享锁（IS锁）
- 如果对一个数据对象加IS锁，表示它的后裔结点拟（意向）加S锁
- 例如：事务$T_1$要对$R_1$中某个元组加S锁，则要首先对关系$R_1$和数据库加IS锁
意向排它锁（IX锁）
如果对一个数据对象加IX锁，表示它的后裔结点拟（意向）加X锁。
例如：事务$T_1$要对$R_1$中某个元组加X锁，则要首先对关系$R_1$和数据库加IX锁
共享意向排它锁（SIX锁）
如果对一个数据对象加SIX锁，表示对它加S锁，再加IX锁，即SIX = S + IX。
例：对某个表加SIX锁，则表示该事务要读整个表（所以要对该表加S锁），同时会更新个别元组（所以要对该表加IX锁）。
具有意向锁的多粒度封锁方法
