《查询优化一般算法》由会员分享，可在线阅读，更多相关《查询优化一般算法（7页珍藏版）》请在金锄头文库上搜索。
1、4.5 查询优化一般算法 本节主要讨论关系数据库中查寻优化的实现机理，从而得到查询优化的一般算法。 4.5.1 语法树 关系代数表达式的查询优化是由 DBMS 的 DML 编译器自动完成的。因此，查询优化 的基本前提就是需要将关系代数表达式转换为某种内部表示。常用的内部表示就是所谓的 关系代数语法树，简称为语法树。其实现的过程是先对一个关系代数表达式进行语法分析， 将分析结果用树的形式表达出来，此时的树就称之为语法树。语法树具有如下特征： (1) 树中的叶结点表示关系。 (2) 树中的非叶结点表示操作。 有了语法树之后，再使用关系表达式的等价变换公式对于语法树进行优化变换，将原 始语法树变换为
2、标准语法树(优化语法树)。按照语法树的特征和查询优化的规则，语法树 变换的基本思想尽量使得选择运算和投影运算靠近语法树的叶端。 4.5.2 关系代数表达式优化算法 按照上述考虑，就有关系代数表达式的优化算法如下。 ? 算法输入：关系代数表达式对应的语法树。 ? 算法输出：计算该表达式的一个优化程序。 ? 算法步骤：依次执行下述的每一步。 1. 应用选择运算串接公式和投影串接公式 使用选择串接公式将形如的表达式进行分解： F1Fn(E)?F1FnF1F2Fn(E)(E)? 使用投影串接公式将形如A1,A2,An (B1,B2,Bm (E) 的表达式进行分解： A1,A2,An (B1,B2,Bm
3、 (E) B1,B2,Bm (E) 其中A1,A2,An是B1,B2,Bm的子集。 这样做的目的是将选择或者投影运算串接成单个选择或者单个投影运算，以方便地和 有关二元运算进行交换与分配。 2. 应用选择运算和其他运算的交换公式与分配公式 这样做的目的是为了将选择运算尽量向下深入而靠近关系(即移至语法树的叶结点)。 例如，利用选择和投影的交换公式将表达式转换为一个选择后紧跟一个投影，使得多 个选择、 投影能同时执行或者能在一次扫描中完成。 再例如， 只要有可能， 就要将F(E1E2) 转换为F(E1)E2 或E1F(E2)，尽早执行基于值的选择运算可以减少对中间结果进行排序 所花费的开销。 数
4、据库理论及应用基础 33 3. 使用投影运算与其他运算的交换公式与分配公式 这样做的目的是将投影运算尽量向内深入靠近关系(即移至语法树叶结点)。 具体做法是： (1) 利用投影串接公式使得某些投影消解。 (2) 利用选择与投影的交换公式把单个投影分解成两个，其中一个先投影后选择的运 算(选择运算块)就可进一步向内深化。 4. 使用笛卡尔乘积与连接的转换公式 如果笛卡尔乘积之后还必须按连接条件进行选择操作，就将两者结合成连接运算。 5. 添加必要的投影运算 对每个叶结点添加必要的投影运算，用以消除对查询无用的属性。 6. 将关系代数语法树进行整形 通过上述步骤得到的语法树的内结点(非根结点和非叶
5、结点)或者为一元运算结点，或 者为二元运算结点。对于三个二元运算“、-”中的每个结点来说，将剩余的一元运算结点按照下面的方法进行分组。 (1) 如果一元运算结点 或是该二元运算结点的父结点，则父结点与该点同组。 (2) 如果二元运算的子孙结点一直到叶结点都是一元运算 或，则这些子孙结点与 该结点同组。 但是对于笛卡尔乘积来说，如果其子结点不是与它组合成等价连接的选择运算时，这 样的选择子结点不与该结点同组。 7. 由分组结果得到优化语法树 即一个操作序列，其中每一组结点的计算就是这个操作序列中的一步，各步的顺序是 任意的，只要保证任何一组不会在它的子孙组之前计算即可。 例例 4-3 对例 4-
6、1 中查询。 Q1 =Sn(S.S#=SC.S#SC.C#=C5(SSC) 将其进行语法分析后得到语法树如图 4.2 所示。 错误！错误！错误！错误！：Sn ：S.S#=SC.S#SC.C#=C5SCS 图 4.2 Q1 查询的原始语法树 数据库理论及应用基础 34 现在对 Q1 查询的原始语法树进行优化变换。 (1) 用选择串接公式S.S#=SC.S#SC.C#=C5 = S.S#=SC.S#(SC.C#=C5)将语法树变换成图 4.3： 错误！错误！错误！错误！：Sn ：S.S#=SC.S# SCS ：SC.C#=C5图 4.3 对选择运算应用串接公式进行分解 (2) 使用选择与笛卡尔运算
7、的分配公式SC.C# =C5 (SSC)= S(SC.C# =C5 SC)，将上述语法 树变换成图 4.4 所示： 错误！错误！错误！错误！：Sn ：S.S#=SC.S# SCS ：SC.C# =C5图 4.4 使用选择操作关于笛卡尔乘积的分配公式 (3) 空。 数据库理论及应用基础 35 (4) 将选择运算与笛卡尔乘积转换为连接运算公式。 S.S# = SC.S#(S(SC.C# =C5 SC)= S?SC.C# =C5 SC 将(2)中语法树变换为如图 4.5 所示。 错误！错误！错误！错误！：Sn ?：S?SC.C# =C5(SC) SCS ：SC.C# =C5图 4.5 使用笛卡尔乘积
8、与连接的转换公式 (5) 空。 (6) 按照分组的原则，步骤 3 所示的操作序列构成一组。 (7) 按照分组，即可生成程序。 例例 4-4 设有 S(供应商)、P(零件)和 SP(供应关系)3 个关系，它们相应的关系模式如下： S(SNUM,SNAME,CITY) P(PNUM, PNAME, WEICHT, SIZE) SP(SNUM, PNUM, DEPT, QUAN) 其中， SNUM 表示供应商数， SNAME 表示供应商名称， CITY 表示供应商所在的城市， PNUM 表示零件数， PNAME 表示零件名称，WEICHT 表示零件重量，SIZE 表示零件大 小；DEPT 表示被供应
9、零件的部门，QUAN 表示被供应的数量。 设有如下查询语句 Q： SELECT SNAME FROM S,P,SP WHERE S.SNUM = SP.SNUM AND SP.PNUM = P.PNUM AND S.CITY = NAMEING AND P.PNAME = BOLT AND SP.QUN 10000 则此时的对应的关系代数表达式为Q =SNAME(c(SP)SP)，其中 C ：S.SNUM = SP.SNUM SP.PNUM = P.PNUM S.CITY = NAMEING P.PNAME = BOLT SP.QUN 10000 原始语法树如图 4.6 所示。 数据库理论及应
10、用基础 36 错误！错误！错误！错误！：SNAME S P ：cSP 图 4.6 原始语法树 (1) 使用串接公式将选择操作分为相继的单个选择操作。 (2) 使用选择运算关于笛卡尔乘积分配率的一组公式，将选择操作尽量移向叶端，由 此可得变换后的语法树如图 4.7 所示。 错误！错误！：SMAME S：S.CITY = NANJING ：SP.PNUM = P.PNUM：P.PNAME =BOLT：S.SNUM = SP.SNUMSPP ：SP.QUN 10000错误！错误！ 图 4.7 使用选择运算关于笛卡尔乘积分配律的一组公式，将选择操作尽量移向叶端 数据库理论及应用基础 37 (3) 空。
11、 (4) 将选择运算和笛卡尔乘积组合成连接操作，得到相应语法树如图 4.8 所示。 错误！错误！错误！错误！：SMAME ?：SP.PNUM = P.PNUM：P.PNAME =BOLT S ?： S.SNUM = SP.SNUMSP：S.CITY = NANJING：SP.QUN 10000P ?图 4.8 将选择运算和笛卡尔乘积组合成连接操作 我们还可以由原始语法树得到另一种查询语法树形式如图 4.9 所示。 错误！错误！错误！错误！：SNAME ?： C? SPS P 图 4.9 另一种形式的查询语法树 (5) 使用投影操作，消除查询无用的属性，得到如下的语法树如图 4.10 所示。 数据库理论及应用基础 38 错误！错误！错误！错误！：SNAME ?： SP.PNUM = P.PNUM：PNUM：SNUM，SNAME ?：S.SNUM = SP.SNUM ：SNUM，PNUM：P.PNAME =BOLT P ：SP.QUN 10000：S.CITY = NANJING SP S ?图 4.10 添加投影操作以消除无用属性
