|
|
查询处理的代价通常取决于磁盘访问，磁盘访问比内存访问速度要慢得多。对于一个给定的查询，通常会有许多可能的处理策略，也就是可以写出许多等价的关系代数表达式。就所需磁盘访问次数而言，策略好坏差别很大，有时甚至相差几个数量级。因此，系统多花点时间在选择一个较好的查询处理策略上是值得的，即便该查询语句只执行一次。 |
1.查询优化问题
①在关系代数表达式中需要指出若干关系的操作步骤。那么，系统应该以什么样的操作顺序，才能做到既省时间，又省空间，而且效率也比较高呢？这个问题称为查询优化问题。
②在关系代数运算中，笛卡儿积和连接运算是最费时间的。若关系R有m个元组，关系S有n个元组，那么R×S就有m×n个元组。当关系很大时，R和S本身就要占较大的外存空间，由于内存的容量是有限的，只能把R和S的一部分元组读进内存，如何有效地执行笛卡儿积操作，花费较少的时间和空间，就有一个查询优化的策略问题。 |
2.实例
设关系R（A，B）和S(C，D)都是二元关系，若有一个查询可用下列关系代数表达式表示：
E1=ΠA(σB=C∧D='99'(R×S))
求E1的值，要先做R和S的笛卡儿积。如果R和S各有103个元组，那么R×S的值就有106个元组，占据了大量的存储空间。根据等价变换，可把条件“D='99'”移到笛卡儿积中关系S的前面：
E2=ΠA(σB=C(R×σD='99'(S))
这里，S的元组有103个，但σD='99'(S)的元组可能只有10个，这样笛卡儿积的结果就只有104个，占据的空间大为减少。再仔细分析可看出，笛卡儿积与其后的选择条件“B=C”可以合并成等值连接形式，更能减少占据的空间，得到：
E3=ΠA(R σD='99'(S))
上述三个关系代数表达式是等价的，但执行的效率大不一样。可以看出，如何安排选择、投影和连接的顺序是个很重要的问题。 |
3.两个关系代数表达式的等价
两个关系代数表达式等价是指用同样的关系实例代替两个表达式中相应关系时所得到的结果是一样的。也就是得到相同的属性集和相同的元组集，但元组中属性的顺序可能不一致。两个关系代数表达式E1和E2的等价写成E1≡E2。 |
|
|
1.引言
(1)现在，许多系统都是采用启发式优化(heuristic optimization)方法对关系代数表达式进行优化。
(2)这种优化策略与关系的存储技术无关，主要是讨论如何合理安排操作的顺序，以花费较少的空间和时间。
(3)在关系代数表达式中，最花费时间和空间的运算是笛卡儿积和连接操作。 |
2.三条启发式规则
(1)尽可能早地执行选择操作；
(2)尽可能早地执行投影操作；
(3)避免直接做笛卡儿积，把笛卡儿积操作之前和之后的一连串选择和投影合并起来一起做。 |
3.说明
(1)通常选择操作优先于投影操作比较好，因为选择操作可能会大大减少关系，并且选择操作可以利用索引存取元组。
(2)关系代数表达式的启发式优化是由DBMS的DML编译器完成的。对一个关系代数表达式进行语法分析，可以得到一棵语法树，树中叶子是关系，非叶子结点是关系代数操作。利用启发式规则可以对关系代数表达式进行优化。 |
4.关系代数表达式的启发式优化算法
(1)输入：一个关系代数表达式的语法树
(2)输出：计算表达式的一个优化序列
(3)方法：依次执行下面每一步。
①把每个形为σF1∧…∧Fn(E)的子表达式转换成选择级联形式：σF1(…(σFn(E))…)
②在语法树中，尽可能把每个选择操作下推到最早可能执行的地方（即移向树的叶端）。
例如，只要有可能，σF(R×S)转换成σF(R)×S或R×σF(S)。尽早执行基于值的选择运算可以减少对中间结果进行排序的代价。
③对每个投影操作，尽可能把投影操作往下推，移向树的叶端。可能使某些投影操作消失，也可能把一个投影分成两个投影操作，其中一个将靠近叶端。如果一个投影是针对被投影的表达式的全部属性，则可消去该投影操作。
④把选择和投影合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择、投影能同时执行或在一次扫描中同时完成。
⑤将上述步骤得到的语法树的内结点分组。
每个二元运算（×、∪、－）结点与其直接祖先（不超过别的二元运算结点）的一元运算结点（σ或Π）分为一组。如果它的子孙结点一直到叶都是一元运算符（σ或Π），则也并入该组。但是，如果二元运算是笛卡儿积，而且后面不是与它组合成等值连接的选择时，则不能将选择与这个二元运算组成同一组。
⑥生成一个序列，每一组结点的计算是序列中的一步，各步的顺序是任意的，只要保证任何一组不会在它的子孙组之前计算。 |
5.实例
(1)对于教学数据库中的关系
教师关系：T(T#,TNAME,TITLE)
课程关系：C(C#,CNAME,T#)
学生关系：S(S#,SNAME,AGE,SEX)
选课关系：SC(S#,C#,SCORE)
(2)问题
检索学习课程名为OS的女学生学号和姓名。
(3)关系代数表达式
ΠS#,SNAME(σCNAME=’OS’∧SEX=’F’(C SCS))
(4) 符号用Π、σ、×操作表示
ΠS#,SNAME(σCNAME=’OS’∧SEX=’F’(ΠL(σC.C# = SC.C#∧SC.S# = S.S#(C×SC×S))))
此处L是(C.C#,CNAME,T#,SCORE,S.S#,SNAME,AGE,SEX)。
该表达式构成的语法树
 |
(5)使用优化算法对语法树进行优化
①将每个选择操作分裂成两个选择运算，共得到四个选择操作：
σCNAME=’OS’ σSEX =’F’ σC.C# = SC.C# σSC.S# = S.S#
②使用等价变换规则，把四个选择操作尽可能向树的叶端靠拢。据规则可以把σCNAME=’OS’和σSEX =’F’移到叶端C和S处。
σSC.S# = S.S#不能再往叶端移动了，因为它的属性涉及到两个关系SC和S，但σC.C# = SC.C#还可向下移，与笛卡儿积交换位置。
然后根据规则，再把两个投影合并成一个投影ΠS#,SNAME。
原来的语法树变成了新的形式
③尽可能把投影移向叶端。也就是在每个选择操作后尽可能做投影操作，只挑选对后面操作有用的属性，来尽量减少中间结果。
这样就形成新的语法树
再以二元运算笛卡儿积为中心，用虚线划分了两个运算组。
④执行时从叶端依次向上进行，每组运算只对关系一次扫描。 |
|
|
