=100+20×100=2100
读数据时间=2100/20=105秒 中间结果大小 = 1000*10000 = 107
(1千万条元组)
写中间结果时间 = 10000000/10/20 = 50000秒
②б : 读数据时间 = 50000秒
③П : 总时间 =105＋50000＋50000秒 = 100105秒 = 27.8小时
(E1×E2) × E3 ≡ E1 × (E2×E3)
(E1 E2) E3 ≡ E1 (E2 E3)
(E1 E2) E3 ≡ E1 (E2 E3)
F1
F2
F1
F2
§4.2.3 关系代数表达式等价变换
3. 投影的串接定律
π A1,A2, π ,An( B1,B2, ,Bm(E))≡ π A1,A2, ,An (E)
σo=‘2’ ПL ( σs.sno=sc.sno (S X SC))= ПL ( σs.sno=sc.sno (σo=‘2’ ( S X SC)) )
§4.2.5 关系代数查询优化实例
当选择条件θ0的所有属性只涉及参与连接运算 的表达式之一(E1)时：
σθ0(E1 X E2) = (σθ0(E1)) X E2
§4.2.5 关系代数查询优化实例
Sname
Cno = ‘ 2 ’
L S.sno=SC.sno
S
SC
§4.2.5 关系代数查询优化实例
1 将合取选择运算可分解为单个选择运算的序列。
σs.sno=sc.sno σo=‘2’
2 利用规则将选择运算尽量向树的叶端靠拢 σθ1∧θ2(E)=σθ1(σθ2(E))
上面的优化策略大部分都涉及到代数表达式 的变换
§4.2.3 关系代数表达式等价变换
设E1、E2等是关系代数表达式，F是条件表达式
l. 连接、笛卡尔积交换律
E1× E2≡ E2×E1 E1 E2≡E2 E1 E1 F E2≡E2 F E1
§4.2.3 关系代数表达式等价变换
2. 连接、笛卡尔积的结合律
义任何存取路径
关系系统的分类
表式系统 (最小)关系系统 关系完备系统 全关系系统
§4.1 关系系统
表式系统
仅支持关系(即表)数据结构，不支持集合级的操作。
(最小)关系系统
即前面定义的关系系统。它们仅支持关系数据结构和三种 关系搡作。许多微机关系数据库系统如FoxPro等就属于这 一类
算造成多次扫描文件。
§4.2.2 查询优化策略
♦ 进行连接运算前，对关系适当预处理 ♦提取公共表达式，储存中间结果，减少重
复计算。 (适合于结果数据量少、但计算量大的
公共表达式，对此公共表达式的调用越频 繁，效益就越大)。
§4.2.3 关系代数表达式等价变换
关系代数表达式等价
指用相同的关系代替两个表达式中相应的关 系所得到的结果是相同的
读Student表总块数= 50/10=5块
读数据时间
③П 总时间<10秒
通过分析可知：采用不同的等 价关系表达式其存取时间差别很大， 因而必须优化。
§4.2.2 查询优化策略
♦ 尽早进行选择运算 ♦ 尽早进行投影运算 ♦ 避免进行笛卡尔积运算，把笛卡尔积与其后的
选择运算合并成一个连接运算 ♦同时计算一串选择和投影的操作，以免分开运
§4.2.1 查询优化问题提出
一个用户查询，系统实现时均使用一个与之相应 的关系代数表达式去求解，同一查询等价关系代数表 达式的不同，就会出现不同的求解路线。 如：求选修了2号课程的学生姓名，SQL语句
Select sname from s,sc where s.sno=sc.sno AND o=‘2’
§4.2.4关系代数表达式的优化算法
算法：关系表达式的优化的非形式描述 输入：一个关系表达式的语法树。 输出：计算该表达式的程序。 方法：
（1）分解选择运算 利用规则4把形如бF1 ∧F2 ∧ … ∧ Fn (E)变换为 бF1 (бF2(… (бFn(E))… ))
§4.2.4关系代数表达式的优化算法
§4.2.1 查询优化问题提出
Q2= Пsname ( σo=‘2’ (S |><| SC) )
① 读取总块数= 2100块 读数据时间=2100/20=105秒 中间结果大小=10000 （减少1000倍） 写中间结果时间=10000/10/20=50秒
②б : 读数据时间=50秒 ③П
关系上完备的系统
这类系统支持关系数据结构和所有的关系代数操作(功能 上与关系代数等价)。90年代初的许多关系数据库管理系 统属于这一类
全关系系统
这类系统支持关系模型的所有特征
§4.2 数据库查询优化
查询优化问题的提出 查询优化策略 关系代数等价变换 查询优化算法 查询优化步骤和示例
第四章 关系系统及其查询优化
4.1 关系系统
4.2 数据库查询优化
作业P166 1、4
查询处理概述
查询优化问题的提出
关系代数等价变换
查询优化策略
查询优化示例
查询优化步骤
§4.1 关系系统
关系系统的定义
一个系统可定义为关系系统，当且仅当它： 支持关系数据库（关系数据结构） 支持选择、投影和连接运算，对这些运算不必定
假设1：外存： Student:1000条,SC:10000条, 选修2号课程:50条
假设2：一个内存块装元组:10个Student, 或100个SC,
内存中一次可以存放: 5块Student元组, 1块SC元组和若干块连接结果元组
假设3：读写速度：20块/秒 假设4：连接方法：基于数据块的嵌套循环法
§4.2.4关系代数表达式的优化算法
（6）生成程序
生成一个程序，每组结点的计算是程序中的一步。 各步的顺序是任意的，只要保证任何一组的计算
不会在它的后代组之前计算。
§4.2.5 关系代数查询优化实例
求选修了2号课程的学生姓名 S（SNO，SNAME，AGE，SEX） SC（SNO，CNO，GRADE） 用关系代数表达式
ПL ( σs.sno=sc.sno (σo=‘2’ ( S X SC)) )= ПL ( σs.sno=sc.sno (S X σo=‘2’ ( SC)) )
投影运算的级联：
∏L1(∏L2(…(∏Ln(E))…))=∏L1(E)
Пsname (ПL ( σs.sno=sc.sno (S X σo=‘2’ ( SC)) )) ПSNAME ( σs.sno=sc.sno (S X σo=‘2’ ( SC)) )
§4.2.4关系代数表达式的优化算法
（5）对内结点分组 把上述得到的语法树的内节点分组。 每一双目运算(×， ，∪，-)和它所有的直 接祖先为一组(这些直接祖先是б，π运算)。 如果其后代直到叶子全是单目运算，则也将 它们并入该组，但当双目运算是笛卡尔积 (×)，而且其后的选择不能与它结合为等值 连接时除外。把这些单目运算单独分为一组。
F2只涉及E2中的属性
бF(E1×E2) ≡б F1(E1)×бF2 (E2)
§4.2.3 关系代数表达式等价变换
(3) 假设： F=F1∧F2， F1只涉及E1中的属性， F2涉及E1和E2两者的属性
бF(E1×E2)≡б F2(бF1(E1)×E2)
它使部分选择在笛卡尔积前先做
§4.2.3 关系代数表达式等价变换
π A1,A2, …,An,B1,B2, …,Bm （E1×E2)≡ π A1,A2, …,An（E1)× π B1,B2, …,Bm(E2)
§4.2.3 关系代数表达式等价变换
l0. 投影对并的分配律
假设：E1和E2 有相同的属性名 π A1,A2, …,An(E1∪E2)≡ π A1,A2, …,An(E1)∪ π A1,A2, …,An(E2)
§4.2.1 查询优化问题提出
读取Student和SC表的策略
Student表
内存缓冲区
SC表
… …
… …
第
第1－10个元组
一第11－20个元组个来自五块第
二 个 五 块
共 一 千 个
学
生
记
录
10个Student元组 100个SC元组
10个连接后的元组
中间文件
第1－100个元组 第一块 第101－200个元组 第二块
（2）通过交换选择运算，将其尽可能移到叶端 对每一个选择，利用规则4～8尽可能把它移到树的
叶端。
（3）通过交换投影运算，将其尽可能移到叶端 对每一个投影利用规则3，9，l0，5中的一般形式尽 可能把它移向树的叶端。
§4.2.4关系代数表达式的优化算法
（4）合并串接的选择和投影，以便能同时执行或在一 次扫描中完成 利用规则3～5把选择和投影的串接合并成单个选 择、单个投影或一个选择后跟一个投影。 使多个选择或投影能同时执行，或在一次扫描中 全部完成
7. 选择对并的分配律
假设：E=E1∪E2，E1，E2有相同的属性名 бF(E1∪E2)≡ бF(E1)∪ бF(E2)
8. 选择对差运算的分配律
假设：E1与E2有相同的属性名
бF(E1-E2)≡ бF(E1) - бF(E2)
§4.2.3 关系代数表达式等价变换
9. 投影对笛卡尔积的分配律
假设：E1和E2是两个关系表达式， A1，…，An是E1的属性， B1，…，Bm是E2的属性
等价关系代数表达式如下： Q1=Пsname ( σs.sno=sc.sno ^ o=‘2’ (S X SC)) Q2= Пsname ( σo=‘2’ (S |><| SC) ) Q3= Пsname (S |><| σo=‘2’ ( SC) )
§4.2.1 查询优化问题提出