2. 选择操作бS.Sno=SC.Sno ∧o=' c02'
选择操作执行时间 =中间结果文件读取时间 =运算中间结果写入磁盘时间 =5×104（s） 运算结果只有50条记录，可驻留内存。
3.投影操作πSN
对内存的50条记录进行操作，忽略不计。 查询Q1所需总时间 =105＋ 5×104 ＋ 5×104 =100105（s）≈ 27.8（h）
– 通过利用一些启发式规则，将一个代数表达式 转换为另一个不同的但等价的代数表达式，产 生可被进一步优化的查询执行计划。
• 关系代数表达式等价：指用相同的关系实例代替两 个表达式中相应的关系所得到的结果是相同的。
【例】在“学生-课程”数据库中查询选修了课程号为 “c02”课程的学生姓名。
<Query>
SELECT
<SelList> FROM <FromList> WHERE
<Condition>
<Attribute>
<RelName>
<Attribute> IN (
)
SN
S
SNO
<Query>
SELECT
<SelList> FROM <FromList> WHERE
第15讲 关系查询与优化
16
代数优化
• 代数优化的必要性
【例】分析实现“查询选修了课程号为‘c02’课 程的学生姓名”的两种关系代数查询树的执行效 率。
Q1：πSN (бS.Sno=SC.Sno ∧o='c02' (S×SC)) Q2：πSN (S ⋈πSno(бo=' c02' (SC) ))
第15讲 关系查询与优化
11
查询分析与预处理
• 生成关系代数初始查询树
– 查询预处理器采用一些相应的规则，用一 个或多个关系代数运算符替换语法树上的 结点与结构，生成一个对应是一个树数据结构，在 查询树中，查询的输入关系表示为叶结 点，关系代数操作表示为内部结点，一 元关系操作符只有一个子结点，二元关 系操作符有两个子结点。
S.SN
S
<RelName> SC <Condition>
AND
<Condition>
<Attribute>
= <Attribute>
<Attribute>
=
<Value>
S.SNO
SC.SNO
O
‘c02’
用查询语句Q1实现两个关系的连接查询的语法分析树 第15讲 关系查询与优化
9
查询分析与预处理
<Attribute>
=
<Value>
S.SNO
SC.SNO
O
‘c02’
第15讲 关系查询与优化
15
代数优化
• 由查询优化器将查询预处理器所生成的关 系代数初始查询树转换成一个预期所需执 行时间较小的等价的关系代数查询树，得 到一个可被转换成最有效的物理查询计划 的一个“优化”的逻辑查询计划。
– 代数优化 – 物理优化
第15讲 关系查询与优化
5
数据库系统的查询处理步骤
查询语句
查 询 处 理 器 的 组 成 和 查 询 处 理 的 典 型 步 骤
查询分析
查询解析器 语法分析树
SELECT Sn FROM S，SC WHERE S.Sno=SC.Sno AND o=' c02 ';
7
查询分析与预处理
【例】在“学生-课程”数据库中查询选修了课程号为 “c02”课程的学生姓名。 Q1: SELECT SN FROM S，SC WHERE S.Sno=SC.Sno AND o=' c02 '; Q2: SELECT SN FROM S WHERE Sno IN （SELECT Sno FROM SC WHERE Cno=‘c02’）
运算中间结果元组数= 1000*10000 = 107 运算中间结果需占用的磁盘块数=107 /10=106（块） 运算中间结果写入磁盘时间 = 107 /10/20 = 5×104秒
第15讲 关系查询与优化
22
代数优化
Q1：πSN (бS.Sno=SC.Sno ∧o='c02' (S×SC))
<RelName> , <FromList>
S.SN
S
<RelName> SC <Condition>
AND
关系代数优化查询树 查询代码生成器 查询计划的执行代码 执行引擎 执行结果
πSn (бS.Sno=SC.Sno ∧o=' c02' (S×SC))
<Attribute>
= <Attribute>
3
实例
【例】查询选修了“c02”课程的学生姓名 π Sn (бS.Sno=SC.Sno ∧o='2' (S×SC)) π Sn (бo=' 2' (S ⋈ SC))
π Sn (S ⋈ бo=' 2' (SC))
第15讲 关系查询与优化
4
关系查询与优化
• 查询处理步骤 • 查询优化技术
<Condition>
<Attribute>
<RelName>
<Attribute>
=
<Value>
SNO
SC
CNO
‘c02’
用查询语句Q2实现两个关系的嵌套查询的语法分析树 第15讲 关系查询与优化
10
查询分析与预处理
• 查询有效性检查
– 根据数据字典对合法的查询语句进行语义 检查。
• 检查语句中的数据库对象在所查询的特定数据 库模式中是否为有效且有语义含义的名字。 • 检查所有属性的类型是否与其使用相对应，以 及根据数据字典中的用户权限和完整性约束定 义对用户的存取权限进行检查。
第15讲 关系查询与优化
25
代数优化
• 代数优化
– 关系代数表达式（查询树）的优化就是指按照 一定的规则，改变关系代数表达式中操作的次 序和组合，将其转换为一个可以更高效执行的 关系代数表达式（查询树）。
• 基于代数等价的启发式优化
第15讲 关系查询与优化
26
代数优化
• 基于代数等价的启发式优化
≈
2.读S作连接和投影πSN (S ⋈πSno(бo=' c02' (SC) ))
读取关系S的磁盘块数= B(S)=100（块） 读数据时间=100/20=5（s） 在内存中，对读取的S元组与50个选课元组进行连接操作后投影， 时间忽略不计。
查询Q2所需总时间 = 5＋5=10（s）
第15讲 关系查询与优化
第15讲 关系查询与优化
8
查询分析与预处理
【例】在“学生-课程”数据库中查询选修了课程号为 “c02”课程的学生姓名。
<Query> SELECT <SelList> FROM <FromList> WHERE <Condition>
<Attribute>
<RelName> , <FromList>
<Query>
SELECT Sn FROM S，SC WHERE S.Sno=SC.Sno AND o=' c02 ';
查询预处理器
<Condition>
数据字典
SELECT
<SelList> FROM <FromList> WHERE
关系代数查询树 查询优化器
<Condition>
<Attribute>
第15讲 关系查询与优化
12
查询分析与预处理
【例】在“学生-课程”数据库中查询选修了课程号为 “c02”课程的学生姓名。
Q1：πSN (бS.Sno=SC.Sno ∧o='c02' (S×SC))
每个内部节点用关系操 作符来标记，每个叶子 结点用关系名来标记。 一元关系操作符只有一 个孩子，二元操作符有 两个孩子。
第15讲 关系查询与优化
23
代数优化
Q2：πSN (S ⋈πSno(бo=' c02' (SC) )) 1.读SC作选择和投影πSno(бo=' c02' (SC) )
读取关系SC的磁盘块数= B(SC)=100（块） 读数据时间=100/20=5（s） 在内存中，对读取的数据进行选择和投影操作，时间忽略不计。 满足条件的中间结果元组数=50，驻留内存，不必用中间文件。
24
代数优化
• 代数优化的必要性
– 对于实现同一查询的不同的关系代数表达式（ 查询树），其操作的次序不同，查询效率不同 ，查询时间相差很大。 – 有必要对查询预处理器产生的关系代数初始查 询树进行优化，得到较优的逻辑查询计划，而 不管用户书写的SQL查询是什么形式。
如何改变关系代数表达 式的操作次序，提高其 查询效率？
第15讲 关系查询与优化
第15讲 关系查询与优化
1
实例
• 应用实例
– 假设学生-课程数据库中有1000个学生，10000 个选课记录，其中选修“c02”课程的记录为50 个。 – 一个磁盘块能存储10个S元组，或100个SC 元 组。
• 用SQL语句表达查询：选修了“c02”课程的学生姓 名。 • 用多种等价的关系代数表达式来完成这一查询。 • 分析该查询在不同存储结构和索引结构的磁盘I/O次 数。