关于数据库:数据库系统概论王珊第九章关系查询处理和关系优化第一节查询处理

• pdf 下载：明码 7281
• 专栏目录首页：【专栏必读】（考研复试）数据库系统概论第五版（王珊）专栏学习笔记目录导航及课后习题答案详解

查询处理是关系数据库管理系统执行查问语句的过程，其工作是把用户提交给关系数据库管理系统的查问语句转换为高效的查问执行打算

一：查询处理步骤

关系数据库管理系统查询处理能够分为 4 个阶段：

• 查问剖析
• 查问查看
• 查问优化
• 查问执行

（1）查问剖析

工作：对查问语句进行扫描，剖析词法、语法是否合乎 SQL 语法规定

• 如果没有语法错误转入下一步
• 如果有语法错误则在报告中显示谬误

（2）查问查看

工作：

• 对非法的查问语句进行 语义查看 ，即依据数据字典中无关的模式定义查看语句中的数据库对象，如 关系名、属性名是否存在和无效
• 如果是对视图的操作，则要用 视图消解办法 把对视图的操作转换成对根本表的操作
• 还要对 权限 、 完整性束缚 进行查看，如果违反则回绝查问
• 查看通过后，把 SQL 查问语句转化为外部示意，也即等价的关系代数表达式
• 在此过程中，要把数据库对象的内部名称换为外部示意
• RDBMS 个别用 查问树 （又称为 语法分析树）来示意扩大的关系代数表达式

（3）查问优化

工作：每个查问都会有许多可供选择的执行策略和操作算法，查问优化就是抉择一个高效执行的查询处理策略。依照优化的档次个别能够将查问优化分为

• 代数优化 ：是指 关系代数表达式 的优化，也即依照肯定规定，通过对关系代数表达式进行 等价变换 ，扭转代数表达式中操作的 秩序和组合，使查问更高效
• 物理优化 ：是指 存取门路 和底层操作算法 的抉择。抉择根据能够是 基于规定的 (rule based)、 基于代价的(cost based)、基于语义的(semantic based)

（4）查问执行

根据优化器失去的执行策略生成查问执行打算，由 代码生成器(code generator) 生成执行这个查问打算的代码，而后加以执行，回送查问后果。

二：实现查问操作的算法示例

（1）抉择操作的实现

以简略的单表抉择为例，如下

SELECT* FROM STUDENT WHERE< 条件表达式 >

< 条件表达式 >能够有以下几种状况

• $case1$：无条件
• $case2$：Sno=’201215121′
• $case3$：Sage > 20
• $case4$：Sdept=’CS’ AND Sage > 20

抉择操作只波及一个关系，典型的实现办法有

①：全表扫描

思维：假如能够应用的内存块为 $M$ 块

• 依照物理秩序读 Student 的 $M$ 块到内存
• 查看内存的每个元组 $t$，如果 $t$ 满足抉择条件，则输入 $t$
• 如果 Student 还有其余块未被解决，反复即可

优缺点：

• 长处：只须要用很少的内存（起码为 1 块）就能够运行，且管制简略。实用于规模较小的表
• 毛病：对于规模大的表进行程序扫描，当选择率低时会使效率很低

②：索引（或散列）扫描

思维：如果抉择条件中的属性上有索引（例如 $B$+ 树索引或 $hash$ 索引），能够用索引扫描。通过索引先找到满足条件的元组指针，再通过元组指针在查问的根本表中找到元组。 一般来说，当选择率低于 10% 时建设索引才有意义

• 以 $case$ 2 为例：Sno=’201215121’，并且 Sno 上有索引，则能够应用索引失去 Sno 为 ’201215121’ 元组的指针，而后通过元组指针在 Student 表中检索到该学生
• 以 $case$ 3 为例 ：Sage>20，并且 Sage 上有 B + 树索引，则能够应用 B + 树索引找到 Sage=20 的索引项，以此为入口点在 B + 树的程序集上失去 Sage>20 的所有元组指针，而后通过这些元组指针到Student 表中检索到所有年龄大于 20 的学生
• 以 $case$ 4 为例 ：Sdept=’CS’ AND Sage>20, 如果Sdept 和Sage 上都有索引，一种算法是 ，别离用下面两种办法找到 Sdept=’CS’ 的一组元组指针和 Sage>20 的另一组元组指针，求这两组指针的交加，再到 Student 表中检索，就失去计算机系年龄大于 20 岁的学生； 另一种算法是，找到 Sdept=’CS’ 的一组元组指针，通过这些元组指针到 Student 表中检索，并对失去的元组查看另一些抉择条件(如 Sage>20) 是否满足，把满足条件的元组作为后果输入

（2）连贯操作的实现

连贯操作是查询处理中最罕用也是最耗时的操作之一 。不失一般性，这里通过例子简略介绍 等值连贯(或天然连贯) 最罕用的几种算法思维

SELECT * FROM Student,SC WHERE Student.Sno=SC.Sno;

①：嵌套循环办法（nested loop）

思维：对外层循环 (Student 表)的每一个元组，检索内层循环 (SC 表)中的每一个元组，并查看这两个元组在连贯属性(Sno) 上是否相等。如果满足连贯条件，则串接后作为后果输入，直到外层循环表中的元组解决完为止

②：排序 - 合并办法（sort-merge join）

思维：

1. 如果参加连贯的表没有排好序，首先对 Student 表和 SC 表按连贯属性 Sno 排序
2. 取 Student 表中第一个 Sno,顺次扫描 SC 表中具备雷同 Sno 的元组，把它们连接起来
3. 当扫描到 Sno 不雷同的第 一个 SC 元组 时，返回 Student 表扫描它的下一 个元组，再扫描SC 表中具备雷同 Sno 的元组，把它们连接起来

反复上述步骤直至 Student 扫描结束

③：索引连贯（index join）

思维：

• 在 SC 表上曾经建设了属性 Sno 的索引
• 对 Student 中每一个元组，由 Sno 值通过 SC 的索引查找相应的 SC 元组
• 把这些 SC 元组和 Student 元组连接起来

循环执行第二步和第三步，直至 Student 中的元组处理完毕

④：哈希连贯（hash join）

思维：它把连贯属性作为 hash 码，用同一个 hash 函数把 Student 表和 SC 表中的元组散列到 hash 表中

• 划分阶段（创立阶段）：即创立 hash 表。对蕴含较少元组的表 (如Student 表)进行一遍解决，把它的元组按 hash 函数 (hash 码是连贯属性) 扩散到 hash 表的桶中
• 试探阶段（连贯阶段）：对另一个表 (SC 表)进行一遍解决，把 SC 表的元组也按同一个 hash 函数 (hash 码是连贯属性) 进行散列，找到适当的 hash 桶，并把 SC 元组与桶中来自Student 表并与之相匹配的元组连接起来。