文档介绍：数据库系统概论第4章DataBase
关系系统的分类 （续）
数据结构
数据操作
完整性
表式系统
表
(最小)关系系统
表
选择、投影、连接
关系完备的系统
表
全关系系统
考虑I/O时间
中间结果大小 = 1000*10000 = 107 (1千万条元组)
写中间结果时间 = 10000000/10/20 = 50000秒 
②б
读数据时间 = 50000秒 
③П
总时间 =105＋50000＋50000秒 = 100105秒
=
An Introduction to Database System
查询优化的必要性（续）
2. Ｑ2＝ ПＳname(=' 2' (Student SC))
 ①
读取总块数= 2100块
读数据时间=2100/20=105秒
中间结果大小=10000 （减少1000倍）
写中间结果时间=10000/10/20=50秒 
②б
读数据时间=50秒 
③П 
总时间＝105＋50＋50秒＝205秒=
An Introduction to Database System
查询优化的必要性（续）
3. Ｑ2＝ ПSname(Student =' 2' (SC)) 
①б
读SC表总块数= 10000/100=100块
读数据时间=100/20=5秒 
中间结果大小=50条 不必写入外存 
②
读Student表总块数= 1000/10=100块
读数据时间=100/20=5秒 
③ П 
总时间＝5＋5秒＝10秒
An Introduction to Database System
查询优化的必要性（续）
4. Ｑ2＝ ПＳname(Student ='2' (SC))
假设SC表在Cno上有索引，Student表在Sno上有索引
 ①б
读SC表索引=
读SC表总块数= 50/100<1块
读数据时间 
中间结果大小=50条 不必写入外存
An Introduction to Database System
查询优化的必要性（续）
②
读Student表索引=
读Student表总块数= 50/10=5块
读数据时间
③ П
总时间<10秒
An Introduction to Database System
查询优化的一般准则
选择运算应尽可能先做  
目的：减小中间关系
在执行连接操作前对关系适当进行预处理
按连接属性排序
在连接属性上建立索引 
投影运算和选择运算同时做
目的：避免重复扫描关系
将投影运算与其前面或后面的双目运算结合
目的：减少扫描关系的遍数
An Introduction to Database System
查询优化的一般准则 （续）
某些选择运算＋在其前面执行的笛卡尔积
===> 连接运算
例：= (Student×SC)
 
  Student SC
提取公共子表达式
An Introduction to Database System
关系代数等价变换规则
关系代数表达式等价
指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的
上面的优化策略大部分都涉及到代数表达式的变换
An Introduction to Database System
常用的等价变换规则
设E1、E2等是关系代数表达式，F是条件表达式
l. 连接、笛卡尔积交换律
E1× E2≡ E2×E1
E1 E2≡E2 E1
E1 F E2≡E2 F E1
An Introduction to Database System
关系代数等价变换规则（续）
2. 连接、笛卡尔积的结合律
(E1×E2) × E3 ≡ E1 × (E2×E3)
(E1 E2) E3 ≡ E1 (E2 E3)
(E1 E2) E3 ≡ E1 (E2 E3)
F F F F
An Introduction to Database System
关系代数等价变换规则（续）
3. 投影的串接定律
π