基于锁的协议（Lock-Based Protocols）

• 锁是一种控制对数据项并发访问的机制。
• 数据项可以以两种模式进行锁定：
  1. 独占（X）模式：数据项既可以读取也可以写入。使用 lock-X 指令请求 X 锁。
  2. 共享（S）模式：数据项只能读取。使用 lock-S 指令请求 S 锁。
• 锁请求发送给并发控制管理器。只有在请求被授予后，事务才能继续进行。

故障分类

• 事务故障：
  • 逻辑错误：由于某些内部错误条件（例如 A 的余额不足，无法扣款），事务无法完成。
  • 系统错误：数据库系统必须由于错误条件（例如死锁）终止活动事务。
• 系统崩溃：
  • 由于电源故障或其他硬件或软件故障，系统崩溃。
• 停止故障假设：
  • 假设非易失性存储内容在系统崩溃时不会被破坏。
  • 数据库系统具有许多完整性检查来防止磁盘数据的损坏。
• 磁盘故障：
  • 磁头碰撞或类似的磁盘故障破坏了全部或部分磁盘存储。
  • 假设破坏是可检测的：磁盘驱动器使用校验和来检测故障。

基于锁的协议（Lock-Based Protocols）

• 锁是一种控制对数据项并发访问的机制。
• 数据项可以以两种模式进行锁定：
  1. 独占（X）模式：数据项既可以读取也可以写入。使用 lock-X 指令请求 X 锁。
  2. 共享（S）模式：数据项只能读取。使用 lock-S 指令请求 S 锁。
• 锁请求发送给并发控制管理器。只有在请求被授予后，事务才能继续进行。

故障分类

• 事务故障：
  • 逻辑错误：由于某些内部错误条件（例如 A 的余额不足，无法扣款），事务无法完成。
  • 系统错误：数据库系统必须由于错误条件（例如死锁）终止活动事务。
• 系统崩溃：
  • 由于电源故障或其他硬件或软件故障，系统崩溃。
• 停止故障假设：
  • 假设非易失性存储内容在系统崩溃时不会被破坏。
  • 数据库系统具有许多完整性检查来防止磁盘数据的损坏。
• 磁盘故障：
  • 磁头碰撞或类似的磁盘故障破坏了全部或部分磁盘存储。
  • 假设破坏是可检测的：磁盘驱动器使用校验和来检测故障。

基本概念

• 索引机制用于加速对所需数据的访问。例如，图书馆中的作者目录。
• 搜索键（Search Key）是用于在文件中查找记录的一组属性。
• 索引文件由记录（称为索引条目）组成，形式为：

search-key	pointer

• 索引文件通常比原始文件小得多。
• 基本的两种索引类型：
  • 有序索引（Ordered indices）：搜索键按排序顺序存储。
  • 哈希索引（Hash indices）：使用“哈希函数”，将搜索键均匀分布在“桶”中。

查询处理的基本步骤

1. 语法分析与翻译
2. 优化
3. 执行
   

语法分析与翻译

• 将查询转换为内部形式，然后将其转换为关系代数。
• 解析器检查语法，验证关系。

执行

• 查询执行引擎接收查询执行计划，执行该计划，并返回查询的结果。

优化

• 关系代数表达式可能有许多等价的表达式。
  例如，等价于 。
• 每个关系代数操作可以使用多种不同的算法进行执行。相应地，关系代数表达式可以以多种方式进行执行。指定详细执行策略的注释表达式称为执行计划或计算计划(evaluation-plan)。
• 例如，可以使用薪水索引来查找薪水小于 75000 的讲师，或者执行完整的关系扫描并丢弃薪水大于等于 75000 的讲师。
• 查询优化(Query Optimization)：在所有等价的执行计划中选择成本最低的计划。
• 成本是使用数据库目录中的统计信息进行估算的。
• 例如，每个关系中的元组数量、元组大小等。

简介

• 优化给定查询的方法：
  • 等价表达式(整体优化)
  • 对每个操作的不同算法(局部优化)
• 执行计划(evaluation plan)定义了每个操作要用什么算法完成以及如何协调操作的执行
• 查询的不同评估计划之间的成本差异可能是巨大的。例如，在某些情况下可能是秒级别与天级别的差异。
• 基于成本的查询优化的步骤如下：
  1. 使用等价规则生成逻辑上等价的表达式。
  2. 对生成的表达式进行注释，以获取备选的查询计划。
  3. 根据估计的成本选择最便宜的计划。
• 计划成本的估算基于以下因素：
  • 关系的统计信息，例如元组数量，属性的不同值数量等。
  • 中间结果的统计估计，用于计算复杂表达式的成本。
  • 使用统计数据计算的算法的成本公式。

简介

• 事务(Transaction)是程序执行的一个单位，它访问并可能更新各种数据项。
• 例如，从账户 A 转账 50 美元到账户 B 的事务：
  1. 读取(A)
  2. A := A - 50
  3. 写入(A)
  4. 读取(B)
  5. B := B + 50
  6. 写入(B)
• 处理的两个主要问题是：
  • 各种类型的故障，如硬件故障和系统崩溃。
  • 多个事务的并发执行。

基本概念

• 索引机制用于加速对所需数据的访问。例如，图书馆中的作者目录。
• 搜索键（Search Key）是用于在文件中查找记录的一组属性。
• 索引文件由记录（称为索引条目）组成，形式为：

search-key	pointer

• 索引文件通常比原始文件小得多。
• 基本的两种索引类型：
  • 有序索引（Ordered indices）：搜索键按排序顺序存储。
  • 哈希索引（Hash indices）：使用“哈希函数”，将搜索键均匀分布在“桶”中。

查询处理的基本步骤

1. 语法分析与翻译
2. 优化
3. 执行
   

语法分析与翻译

• 将查询转换为内部形式，然后将其转换为关系代数。
• 解析器检查语法，验证关系。

执行

• 查询执行引擎接收查询执行计划，执行该计划，并返回查询的结果。

优化

• 关系代数表达式可能有许多等价的表达式。
  例如，等价于 。
• 每个关系代数操作可以使用多种不同的算法进行执行。相应地，关系代数表达式可以以多种方式进行执行。指定详细执行策略的注释表达式称为执行计划或计算计划(evaluation-plan)。
• 例如，可以使用薪水索引来查找薪水小于 75000 的讲师，或者执行完整的关系扫描并丢弃薪水大于等于 75000 的讲师。
• 查询优化(Query Optimization)：在所有等价的执行计划中选择成本最低的计划。
• 成本是使用数据库目录中的统计信息进行估算的。
• 例如，每个关系中的元组数量、元组大小等。