关系数据理论
关系查询处理和查询优化
基本概念
关系型数据库查询处理可以分为四个阶段：查询分析、查询检查、查询优化和查询执行。
查询优化按照其优化层次分为代数优化和物理优化。其总目标是选择有效的策略，求得给定关系表达式的值，使得查询代价最小（实际上是较小）。代数优化通过改变代数表达式的操作顺序和组合，使得查询更加高效；物理优化是指存取路径和底层操作算法的选择，一般有基于规则（rule based）的、基于代价（cost based）的和基于语义（semantic based）**的。
选择操作的主要实现算法有：全表扫描方法和索引（散列）扫描方法；连接操作的主要实现算法有：嵌套循环方法、排序-合并方法、索引连接方法和Hash Join 方法。
代数优化
关系代数的等价变换规则
- PASS
代数优化的启发式规则
典型的代数优化启发式规则有：
选择运算应尽可能先做。
把投影运算和选择运算同时进行。
把投影运算和其前后的双目运算结合起来。
把某些选择和其前面的笛卡尔积结合起来成为一个连接运算。
找出公共子表达式。
物理优化
物理优化的启发式规则
选择操作的启发式规则：
对于小关系，使用全表顺序扫描，即使选择列上有索引。
对于选择条件是
主键=值的查询，选择主码索引。对于选择条件是
非主键=值的查询、非等值查询、范围查询，估计查询结果的规模，比例较小（<10%）使用索引扫描，否则全表扫描。对于使用
AND连接的合取选择查询，优先索引扫描，否则使用全表扫描。对于使用
OR连接的析取选择查询，一般使用全表顺序扫描。
连接操作的启发式规则：
若两表均已按照连接属性排序，选用排序-合并方法。
若某一表在连接属性上有索引，选用索引连接方法。
若上述两条规则不适用，且其中一表较小，选用Hash Join 方法。
最后选用嵌套循环方法，选择占用块数较少的表作为外表。
基于代价的优化
- PASS
数据库恢复技术
事务
事务：用户定义的一个数据库操作序列，这些操作要么全做、要么全不做，是一个不可分割的工作单位。在SQL语言中，定义事务的语言有三条
BEGIN TRANSACTION、COMMIT和ROLLBACK，其使用方式如下：1
2
3
4
5
6
7
8
9
10BEGIN TRANSACTION
DO SOMETHING;
IF @@error <> 0 --发生错误
BEGIN
ROLLBACK;
END
ELSE
BEGIN
COMMIT;
END事务具有四个特性：原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）和持续性（Durability），简称ACID特性（ACID properties）。
事务的ACID特性遭到破坏的原因包括事务运行中强行停止和交叉并发。
数据库故障及数据恢复技术
数据库故障
- 数据库系统可能出现的故障大概分为四类：事务内部故障、系统故障、介质故障和计算机病毒。其中，系统故障又称为软故障，介质故障又称为硬故障。
数据恢复技术
数据恢复机制的基本原理是冗余，涉及到的两个关键问题是如何建立冗余数据和如何通过冗余数据实施数据库恢复。
建立冗余数据的常用技术是数据转储和登录日志文件。
数据转储即DBA定期地将整个数据库复制到磁带或另一个磁盘上保存起来的过程，这些备用数据称为后备副本（backup）或后援副本。按照转储时数据库工作状态可以将数据转储分为静态转储和动态转储；按照转储方式可将数据转储分为海量转储和增量转储。
日志文件是用来记录事务对数据库的更新操作的文件。日志文件可以用来实施事务故障和系统故障的恢复，也可以结合后备副本进行介质故障的恢复。
为保证日志文件可恢复，登记日志文件应遵循两条原则：
等级次序严格按照并发事务执行的时间次序。
必须先写日志文件，后写数据库。
数据恢复策略
事务故障的恢复策略是利用日志文件进行事务撤销（UNDO）操作，具体流程为：
反向扫描日志文件，查找该事务的更新操作。
执行该事务更新操作的逆操作。
继续反向扫描日志文件，查找该事务的其他更新操作并执行逆操作。
反复执行上述操作，直到读到此事务的开始标记，完成事务故障的恢复。
系统故障的恢复策略如下：
正向扫描日志文件，找出故障发生前已执行完成的事务，加入REDO队列；同时找出故障发生时为执行完成的事务，加入UNDO队列。
对UNDO队列中所有事务进行撤销处理。
对REDO队列中所有事物进行重做处理。
介质故障的恢复策略如下：
装入最新的数据库后备副本，使数据库恢复到最近一次转储时的一致性状态。
装入相应的日志文件副本，重做已完成的事务。
检查点技术
使用日志技术恢复数据库存在两个问题：搜索整个日志耗费大量时间、很多需要REDO的事务的正确结果实际上已经写入数据库了。为解决这样的问题，发展了具有检查点的恢复技术，这类技术在日志文件中增加一个新的记录检查点（checkpoint）记录，增加一个重新开始文件，并让恢复子系统在登录日志文件其间动态维护日志。
具有检查点的数据恢复策略如下：
对于在检查点之前提交的事务不做处理。
对于在检查点之前开始执行，在检查点之后故障点之前提交的事务执行REDO。
对于在检查点之前开始执行，至故障点尚未提交的事务执行UNDO。
对于在检查点之后开始执行，在故障点之前提交的事务执行REDO。
对于在检查点之后开始执行，至故障点尚未提交的事务执行UNDO。
数据库镜像技术
- 数据库镜像即根据DBA的要求，自动把整个数据库或其中的关键数据复制到另一个磁盘上。这样，一旦出现介质故障，可由镜像磁盘继续提供使用；没有出现故障时也可用于并发操作。
数据库并发控制
概述
- DBMS对并发操作要做出正确调度以保证事务的隔离性和一致性。否则，可能出现丢失修改、不可重复读和“脏”数据等问题。并发控制的主要技术有封锁、时间戳和乐观控制法。