关系查询处理及其查询优化.doc

关系查询处理及其查询优化
关系查询处理及其查询优化
关系查询处理及其查询优化
第九章 关系查询处理及其查询优化
章
节
9．1 关系数据库系统的查询处理
关系数据库系统的查询优化
9．3 代数优化
9.　 　 　 　 　 　　 　 　 　 　 　
执行策略１
Ｑ1= Пsｎame　(＝SC．Sｎｏ∧='2' (Student×SC）） 
①　计算笛卡尔积Stｕdｅnt×SC
读取总块数= 读Student表块数　+ 读ＳC表遍数*每遍块数
ﻩﻩ =１000／10+(100０/（1０×5）) ×(100０0/10０）
　　 　 =100+20×100=2１00
读数据时间=2１00／２０＝10５秒
关系查询处理及其查询优化
关系查询处理及其查询优化
关系查询处理及其查询优化
中间结果大小 ＝ 1０00*10０00 =　107 (１千万条元组）
写中间结果时间　=　10０00０0０/１０/２0　＝ ５000０秒 
②做选择运算б
读数据时间　= 50０00秒 
③做投影运算П
　 　总时间 ＝１05＋50000+50000秒 = 100１０5秒= 2７．8小时
执行策略2
２。　Q2= ПSname（бSC．Cnｏ=’ ２' （Studenｔ　 SC)）
①计算自然连接
读取总块数＝ 2100块
读数据时间＝2100/20=10５秒
ﻩ中间结果大小=10000 （减少1００0倍)
写中间结果时间=1000０/１0／２0＝5０秒 
②执行选择运算б
ﻩ读数据时间=50秒 
③执行投影П 
　 总时间=105＋5０＋5０秒=205秒分 
执行策略3
3。 Q2= ПSname（StudｅｎtбSC。Cno＝’　2’ (SC)） 
①б
ﻩ读SC表总块数= 10000/100=100块
读数据时间＝1０0/2０=5秒 
关系查询处理及其查询优化
关系查询处理及其查询优化
关系查询处理及其查询优化
中间结果大小=5０条 不必写入外存 
②　连接运算
ﻩ读Student表总块数＝ 1000/10=100块
读数据时间=１0０/20=５秒 
③ 投影П 
　　总时间=5+5秒=１0秒　
执行策略4
9. Q2＝ ПＳnamｅ(Stuｄｅnt 　 =＇2’　（SC))
假设SC表在Cno上有索引,Studｅnt表在Sｎｏ上有索引
 ①б
ﻩ读SC表索引Ｃnｏ=‘２’的元组。
ﻩ读SC表总块数=　５0/100<１块
读数据时间更小。
中间结果大小＝５0条　 不必写入外存
②
读Stuｄｅnt表索引
ﻩ读Ｓtudeｎt表总块数= 50/10=5块
读数据时间大大减少。
③ П
总时间＜10秒
代数优化
。1 关系代数等价变换规则
关系查询处理及其查询优化
关系查询处理及其查询优化
关系查询处理及其查询优化
关系代数表达式等价
指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的
　两个关系表达式E1 和E2 是等价的，记为： Ｅ1≡E２
常用的等价变化规则有：
1. 连接、笛卡尔积交换律
ﻩﻩE１× E2≡　Ｅ2×E1
ﻩE1 E2≡Ｅ2　 Ｅ1　
ﻩE1 Ｆ 　Ｅ2≡Ｅ2　 Ｆ　 E1
　 F为连接条件。
２。 连接、笛卡尔积的结合律
　(E１×Ｅ2） × Ｅ3 ≡ E1　× (E２×E3)
　　(Ｅ1 　 E2)　 　E3　≡ E1 　(E２ 　 Ｅ3)
　 （E１ 　 E2） Ｅ3 ≡　E1 （Ｅ2 　Ｅ3）　
ﻩ 　F 　 　 F 　　 　　 　　 　　 　 　 F 　 　 F
３. 投影的串接定律
π　A１，A２,　L,Ａn(π　B1,B2,　L，Bm(E）)≡　π A１，A2, L,An （Ｅ)
假设：
１） E是关系代数表达式
2）ﻩAi（i=1，2，…,n）,　Bｊ(j=l，2，…，ｍ)是属性名
3)｛A1, A2, …, Ａｎ}构成｛Bl，B2,…，Bm}的子集
９.　选择的串接定律
бF1 ( б　F2（E)）≡ бＦ1∧ Ｆ2（E)
关系查询处理及其查询优化
关系查询处理及其查询优化
关系查询处理及其查询优化
　选择的串