系统概论王珊_系统概论第五版_系统概论(5)

第二种情况下执行查询的总读写数据块 2100+ 103 +103 其执行代价大约是第一种情况的488分之一 一个实例（续） 3.第三种情况 Q3 πSname Student σSC.Cno '2' SC （1）先对SC表作选择运算，只需读一遍SC表，存取 100块，因为满足条件的元组仅50个，不必使用中 间文件。 （2）读取Student表，把读入的Student元组和内存中 的SC元组作连接。也只需读一遍Student表共100 块。 （3）把连接结果投影输出 一个实例（续） 3.第三种情况（续） 第三种情况总的读写数据块 100+100 其执行代价大约是第一种情况的万分之一，是第二种情况的20分之一 一个实例（续） 假如SC表的Cno字段上有索引 第一步就不必读取所有的SC元组而只需读取Cno ‘2’的那些元组 50个 存取的索引块和SC中满足条件的数据块大约总共3～4块 若Student表在Sno上也有索引 不必读取所有的Student元组 因为满足条件的SC记录仅50个，涉及最多50个Student记录 读取Student表的块数也可大大减少 一个实例（续） 把代数表达式Q1变换为Q2、 Q3 Q1 πSname σStudent.Sno SC.Sno∧Sc.Cno '2' Student×SC Q2 πSname σSc.Cno '2' Student SC Q3 πSname Student σSC.Cno '2' SC 有选择和连接操作时，先做选择操作，这样参加连接的元组就可以大大减少，这是代数优化 实例: 小结 在Q3中 SC表的选择操作算法有全表扫描或索引扫描，经过初步估算，索引扫描方法较优。

对于Student和SC表的连接，利用Student表上的索引，采用索引连接代价也较小，这就是物理优化。 第九章 关系查询处理和查询优化 9.1 关系系统的查询处理 9.2 关系系统的查询优化 9.3 代数优化 9.4 物理优化 *9.5 查询计划的执行 9.6 小 结 9.3 代 数 优 化 9.3.1 关系代数表达式等价变换规则 9.3.2 查询树的启发式优化 9.3.1 关系代数表达式等价变换规则 代数优化策略：通过对关系代数表达式的等价变换来提高查询效率 关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的 两个关系表达式E1和E2是等价的，可记为E1≡E2 * 关系代数表达式等价变换规则（续） 常用的等价变换规则： 1.连接、笛卡尔积交换律 设E1和E2是关系代数表达式，F是连接运算的条件，则有 E1 × E2≡E2 × E1 E1 E2≡E2 E1 E1 E2≡E2 E1 2.连接、笛卡尔积的结合律 设E1，E2，E3是关系代数表达式，F1和F2是连接运算的条件 E1 × E2 × E3≡E1 × E2 × E3 E1 E2 E3≡E1 E2 E3 E1 E2 E3≡E1 E2 E3 * 关系代数表达式等价变换规则（续） 3.投影的串接定律 E ≡ E E是关系代数表达式 Ai i 1，2，…，n ，Bj j 1，2，…，m 是属性名 A1，A2，…，An 构成 B1，B2，…，Bm 的子集 4.选择的串接定律 E ≡ E E是关系代数表达式，F1、F2是选择条件 选择的串接律说明选择条件可以合并,这样一次就可检查全部条件 * 关系代数表达式等价变换规则（续） 5.选择与投影操作的交换律 σF E ≡ σF E 选择条件F只涉及属性A1，…，An。

若F中有不属于A1，…，An的属性B1，…，Bm有更一般规则： σF E ≡ σF E * 关系代数表达式等价变换规则（续） 6. 选择与笛卡尔积的交换律 如果F中涉及的属性都是E1中的属性，则 σF E1×E2 ≡σF E1 ×E2 如果F F1∧F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性，则由上面的等价变换规则1，4，6可推出： σF E1×E2 ≡ E1 × E2 若F1只涉及E1中的属性，F2涉及E1和E2两者的属性，则仍有 σF E1×E2 ≡ E1 ×E2 它使部分选择在笛卡尔积前先做。 * 关系代数表达式等价变换规则（续） 7. 选择与并的分配律 设E E1∪E2，E1，E2有相同的属性名，则 σF E1∪E2 ≡σF E1 ∪σF E2 8. 选择与差运算的分配律 若E1与E2有相同的属性名，则 σF E1-E2 ≡σF E1 -σF E2 9. 选择对自然连接的分配律 σF E1 E2 ≡σF E1 σF E2 F只涉及E1与E2的公共属性 * 关系代数表达式等价变换规则（续） 10. 投影与笛卡尔积的分配律 设E1和E2是两个关系表达式，A1，…，An是E1的属性， B1，…，Bm是E2的属性，则 E1×E2 ≡ E1 × E2 11. 投影与并的分配律 设E1和E2有相同的属性名，则 E1∪E2 ≡ E1 ∪ E2 An Introduction to Database System 系统概论 An Introduction to Database System xx大学信息学院 第九章 关系查询处理 和查询优化 第三篇 系统篇 讨论管理系统中查询处理和事务管理的基本概念和基础知识 第9章 关系查询处理和查询优化 第10章 恢复技术 第11章 并发控制 第12章 管理系统 第九章 关系查询处理和查询优化 9.1 关系系统的查询处理 9.2 关系系统的查询优化 9.3 代数优化 9.4 物理优化 *9.5 查询计划的执行 9.6 小 结 关系查询处理和查询优化（续） 本章内容： 关系管理系统的查询处理步骤 查询优化的概念 基本方法和技术 查询优化分类 ： 代数优化：指关系代数表达式的优化 物理优化：指存取路径和底层操作算法的选择 9.1 关系系统的查询处理 9.1.1 查询处理步骤 9.1.2 实现查询操作的算法示例 9.1.1 查询处理步骤 关系管理系统查询处理阶段 ： 1. 查询分析 2. 查询检查 3. 查询优化 4. 查询执行 查询处理步骤（续） 查询计划的执行代码 代数优化 物理优化等 查询语句 词法分析 语法分析 语义分析 符号名转换 安全性检查 完整性初步检查 代码生成 查询执行计划 查询树 query tree 查询分析 查询检查 查询优化 查询执行 数据字典 1. 查询分析 查询分析的任务：对查询语句进行扫描、词法分析和语法分析 词法分析：从查询语句中识别出正确的语言符号 语法分析：进行语法检查 2. 查询检查 查询检查的任务 合法权检查 视图转换 安全性检查 完整性初步检查 根据数据字典中有关的模式定义检查语句中的对象，如关系名、属性名是否存在和有效 如果是对视图的操作，则要用视图消解方法把对视图的操作转换成对基本表的操作 2. 查询检查 根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查 检查通过后把SQL查询语句转换成内部表示，即等价的关系代数表达式。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25972-5.html