关系系统的查询优化是关系数据库管理系统实现的关键技术，又是关系系统的优点。因为，用户只要提出“干什么”，不必指出“怎么干”。在关系代数表达式中需要指出若干关系的操作步骤，问题是怎样做才能保证省时、省空间、效率高，这就是查询优化的问题。

需要注意的是，在关系代数运算中，笛卡儿积、连接运算最费时间和空间，究竟应采用什么样的策略，节省时间空间。这就是优化的准则。

1.优化的准则

优化的准则有如下6条：

(1)提早执行选取运算。对于有选择运算的表达式，应优化成尽可能先执行选择运算的等价表达式，以得到较小的中间结果，减少运算量和从外存读块的次数.

(2)合并乘积与其后的选择运算为连接运算。在表达式中，当乘积运算后面是选择运算时，应该合并为连接运算，使选择与乘积一道完成，以避免做完乘积后，需再扫描一个大的乘积关系进行选择运算。

(3)将投影运算与其后的其他运算同时进行，以避免重复扫描关系。

(4)将投影运算和其前后的二目运算结合起来，使得没有必要为去掉某些字段再扫描一遍关系。

(5)在执行连接前对关系适当地预处理，就能快速地找到要连接的元组。方法有两种：索引连接法、排序合并连接法。

(6)存储公共子表达式。对于有公共子表达式的结果应存于外存(中间结果)，这样，当从外存读出它的时间比计算的时间少时，就可节约操作时间。

2.关系代数表达式的等价变换规则

优化的策略均涉及关系代数表达式，所以讨论关系代数表达式的等价变换规则显得十分重要.常用的等价变换规则有如下10种。

1)连接、笛卡儿积交换率

设吗和是关系代数表达式，尸是连接运算的条件，则有：

E^E2 M&XEJ

EI XIE2 =E2 XlEi

F F

2)连接、笛卡儿积结合率

设吗、Ez、与是关系代数表达式，为、死是连接运算的条件，则有：

(耳X &) X鸟=耳X (归2 X EJ

(£] =£]

Fl F2 Fl Fl

3)投影的串接定律

设E是关系代数表达式，也,…,]和片。…，勾,是属性名，且是也,・七4的子集。

则有:

财,...4(%...耳(幻)=%...4(£)

该规则的目的是使一些投影消失。

4）选择的串接定律

设E是关系代数表达式，％、旦是选取条件表达式，选择的串接定律说明选择条件可以

合并，则有：

% （% （£）） = %人处（E）

5）选择与投影的交换律

设E是关系代数表达式，F是选取条件表达式，并且只涉及属性，则有：

°>%一.4（£）） = %—4 （土㈤）

若F中有不属于&,•••,4属性，,那么有更一般的规则：

（E）） = （%（螺.…4』"（砌）

该规则可将投影分裂为两个，使得其中的一个可能被移到树的叶端。

6）选择与笛卡儿积的交换律

若F涉及的都是当中的属性，则：

0>（片 X旦）=（TF（EI）X E2

如果F = F[M，并且，耳只涉及Ei中的属性，码只涉及舟中的属性，则有：

bF（£iXE2）= %（E】）X%（£2）

7）选择与并的交换律

设E = E^E2, EI、E2有相同的属性，则：

b.（Ei U 鸟）=<Tj?（^i）U <yp（E2）

8）选择与差的交换律

设.、&有相同的属性,则：

6 国-旦）（瓦）-ap （E2 ）

9）投影与笛卡儿积的交换律

设EL、之是两个关系表达式，也,•••,，《是Ei中的属性，是珀中的属性，则：

兀％...，4,时瓦（E] 乂佑）=%...，4 （片）X%..瓦㈤）

10）投影与并的交换律

设巴、日2有相同的属性，则：

（耳 U鸟）=%,...,q （耳）U 兀a，..”%,（也）

3.查询优化的算法

利用上述的等价变换规则可以对关系代数表达式进行优化，使得优化后的关系代数表达式符合上述的6条基本优化的准则。

算法：关系代数表达式的优化，

输入：一个关系代数表达式的语法树。

输出：计算该表达式的程序