- 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）
思维：
- 如果参加连贯的表没有排好序，首先对
Student表和SC表按连贯属性Sno排序 - 取Student表中第一个
Sno,顺次扫描SC表中具备雷同Sno的元组，把它们连接起来 - 当扫描到
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表并与之相匹配的元组连接起来。
发表回复