分解查询的优化方法全面分析

　　第一节中介绍了通过关系代数表达式变换对查询优化的方法。但是我们并不知道每一步变换是否真会得到好处，也就是不知道是否真会使执行查询的代价降低。这一节中我们介绍另一种优化方法。这种方法是把查询分解执行，根据对所付出代价的多少来决定如何分解，如何执行。这套方法是E，Wong等人提出的，他们在实现INGRES中采用了这种方法。
　　为介绍方便，先给出一个例子，我们在整节中都要用到它。
　　
　　* 例12.3
　　关系：供应商 SUPPLIER(S#,SNAME,CITY)
　　零件 PARTS(P#,PNAME,SIZE)
　　项目 PROJECT(J#,JNAME,CITY)
　　库存 INVENTORY(S#,P#,QOH)
　　供货情况 SUPPLY(S#,J#,P#,QU)
　　其中QOH：现有数量　　 QU：要用的数量
　　
　　查询：
　　RANGE OF (S,P,J,V,Y) IS (SUPPLIER, PARTS, PROJECT, INVENTORY, SUPPLY)
　　RETRIEVE (S.SNAME)
　　WHERE (S.S#=V.S#) AND (S.S#=Y.S#) AND (S.CITY=J.CITY)
　　AND (P.P#=V.P#) AND (V.P#=Y.P#) AND (J.J#=Y.J#)
　　AND (V.QOH>Y.QU) AND (P.PNAME='BOLTS')
　　AND (P.SIZE='#6') AND (Y.QO>100)
　　这个查询是找出：所有为同城市中某些项目提供#6螺丝，提供量大于100并且现有量比提供量多的供应者名字。
　　此查询可用图12-4表示。
　　 SNAME ┌─┐　　 CITY　　　┌─┐
　　　　 ←─┤S ├────────┤J │
　　　　　　 └┬┘　　　　　　　　└┬┘
　　　　　　　 │S#　　　　 S#　　　 │J#
　　　　　　　 │　　　　　　　　　　│
　　　　　　 ┌┴┐　　QOH>QU　　┌┴┐ QU>100
　　　　　　 │V ├────────┤Y │←──
　　　　　　 └─┘　　　 P#　　　 └─┘
　　　　　　　　　 P#
　　　　　　　　　　　　┌─┐
　　　　　　　　　　　　│P │←── PNAME='BOLTS'
　　　　　　　　　　　　└─┘　　　 PSIZE=’#6’
　　　　　　　　　 图12-4　例12.3的查询示意图
　　　　执行此查询的最笨的方法：
　　　　(1)形式卡氏积S×P×J×V×Y
　　　　(2)从卡氏积中限制筛选出满足限定条件的元组
　　　　(3)在S.SNAME上投影
　　　　若假定各关系的元组数如下：
　　　　┏━━━━━━━━━┯━━━━━━━━━━┓
　　　　┃　　 关系　　　　 │　　元组数　　　　　┃
　　　　┠─────────┼──────────┨
　　　　┃　 SUPPLIER　　　│　　　　10　　　　　┃
　　　　┃　 PARTS　　　　 │　　　 100　　　　　┃
　　　　┃　 PROJECT　　　 │　　　　10　　　　　┃
　　　　┃　 INVENTORY　　│　　　 100　　　　　┃
　　　　┃　 SUPPLY　　　　│　　　 400　　　　　┃
　　　　┗━━━━━━━━━┷━━━━━━━━━━┛
　　
　　那么，卡氏积的元组总数为4×108 。这个算法显然是太坏了。
　　另外，我们会注意到此查询涉及到5个变元S,P,J,V,Y,我们把它称为5元查询，涉及一个变元的查询我们称为一元查询。
　　
　　2.1分解
　　前面的例子中所指出的主要问题是当查询涉及到卡氏积时，卡氏积的元组数会组合性地增长。这样不仅需要大量的存贮空间，而且执行查询的时间很长。因此优化应把主要注意力放在，第一，减小组合复杂性上；第二，把一个关系上的一元运算（一元查询）映象为一个存取调用的序列时，应找出存取次数最少的方法。下面讨论这两点，以第一点为主。
　　查询的处理过程分为两步：分解和一元查询处理。分解是动态的，如何分解受到一元查询处理结果的影响。处理的过程如图12-5所示。其中DECOMP负责把查询分解为一些一元查询。此部分的性能可通过它所产生出一元查询的数目多少来大体估计。此部分的第一个目标是要减少产生出一元查询的数目。
　　查询　┌──── ┐　　　┌───────── ┐　　┌───────┐
　　──→│DECOMP ├──→│OVQP(一元查询处理)├─→│AMI(存取接口) │
　　　　　└──── ┘　　　└───────── ┘　　└─┬─┬───┘
　　　　　　　　↑　　　　　　　　　　　　　　　　　　　　　│　│↑
　　　　　　　　└────────────────────　┘　↓│
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　│　　　│
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　│存贮的│
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　│ 数据 │
　　　　　　　　　 图12-5　查询处理过程示意图
　　是否每个查询都可分解呢？回答是肯定的。任一n元查询Q(X1 ，X2 ，...,Xn ），其中Xi 的范围是关系Ri 。如果我们从Rn 中取出一元组α代入Xn ，那么得到一个n-1元查询Q(X1 ，X2 ,...，Xn-1 ,α）。如果Rn 有K个元组，则元组代入使Q变为K个n-1元查询。由此可见，无论付出代价如何，通过元组代入总可以把任何查询分解成一些一元查询。
　　另外一个问题是：除了元组代入以外是否还有其它分解方法呢？这里介绍两种：
　　(1)一元子查询提取：Q被替换为一个一元查询Q'和一个在其后执行的查询Q"。
　　Q ──→(Q',Q")
　　(2)化简：Q被替换为两个查询Q'和Q"，Q"在Q'执行后执行，它们只有一个公共变元。
　　X1 ,X2 ,...,Xm , Xm ,...,Xn
　　Q'　　　　 Q"
　　Q'(X1 ,X2 ,...,Xm ),Q"(Xm ,...,Xn )
　　*例12.4　考虑对例12.3的查询分解。例12.3中的查询可以分出两个一元查询：
　　RETRIEVE PARTS1(P.P#)
　　WHERE (P.PNAME='BOLTS') AND (P.SIZE='#6')
　　和
　　RETRIEVE SUPPLE1(Y.S#,Y.J#,Y.P#,Y.QU)
　　WHERE(Y.QU>100)
　　于是，查询变成：
　　RANGE OF (S,P,J,V,Y) IS (SUPPLIER,PARTS1, PROJECT,
　　INVENTORY,SUPPLY1)
　　RETRIEVE(S.SNAME)
　　WHERE(S.S#=V.S#)AND (S.S#=Y.S#)
　　AND (S.CITY=J.CITY)AND (P.P#=V.P#)
　　AND (V.P#=Y.P#)AND (J.J#=Y.J#)AND (V.QOH>Y.QU)
　　图12-6给出了这个查询的示意图。从图中可以看出，这个查询可以很容易地化简一个涉及（P,V）的查询和在其后执行的、涉及（S,J,Y,V）的查询。
　　
　　 SNAME ┌─┐　　 CITY　　　┌─┐
　　　　 ←─┤S ├────────┤J │
　　　　　　 └┬┘　　　　　　　　└┬┘
　　　　　　　 │S#　　　　 S#　　　 │J#
　　　　　　　 │　　　　　　　　　　│
　　　　　　 ┌┴┐　　QOH>QU　　┌┴┐
　　　　　　 │V ├────────┤Y1│
　　　　　　 └─┘　　　 P#　　　 └─┘
　　
　　　　　　　　　　 P#
　　　　　　　　　　　　┌─┐
　　　　　　　　　　　　│P1│
　　　　　　　　　　　　└─┘
　　　　　　　　　 图12-6　提取一元子查询后的示意图
　　
　　综上所述，在分解中可以采用3种方法：
　　(1)一元子查询提取
　　(2)化简
　　(3)元组代入
　　(1)几乎总会得到好处，因为在关系之间的运算之前尽可能减少关系的体积对减少付出的代价起很大作用。这一点我们在第一节中已经介绍过了。(2)常常会得到好处（但并不是总会得到好处）。(3)则是必须的，但又是我们最不希望采用的方法。当别无其它方法时必须用这种方法来分解。我们在后面要给出综合使用这三种方法分解查询的算法。
　　
　　2.2 一元子查询的提取
　　考虑n元的情况，假定x1 ,x2 ,...,xn 是查询Q的变元，xi 的变换范围是Ri 。一般地说来，Q有两部分，即结果属性表T1 和限定条件C。假定C是合取范式形式的，即
　　C=C1 ∧C2 ∧...∧Ck
　　其中Ci 是析取式，我们称Ci 为限定条件的子句。假定有一些子句Cm+1 ,Cm+2 ,...Ck ，其中每个都只涉及一个变元，那么对应这些变元的那些关系就可以分别被对应的限定条件缩小它们的体积。换句话说，如果限定条件C是合取式，那么就可以用只涉及一个变元的布尔因子作为限定条件来缩减对应的关系。如果只需要关系的某些属性，则在需要的属性上投影也可能会减少关系的元组数（因为去掉了冗余）。对于每个变元，第一个问题是要确定可以做哪些限制筛选、可以做哪些投影。
　　对关系Ri 的限定条件越多，Ri 就会被限制得越少。所以我们应尽可能加上一些限制条件。有时通过传递性可以推导出一些新的限定条件，如：
　　(a=b) AND (b=c) => (a=c)
　　(a>b) AND (b>c) => (a>c)
　　*例12.5　考虑从例12.3的查询推导出新的一元子句。
　　例12.3中的查询的条件子句(V.QOH>Y.QU)和(Y.QU>100)可以推出(V.QOH>100)。推出的子句可以作为一元子句来限制V所对应的关系INVENTORY。
　　一元子查询提取算法：
　　(1)把限定条件变成合取范式。
　　(2)加入所有由传递性推导出的一元子句。
　　(3)对于每个变元Xi ，确定：
　　1)涉及到Xi 的一元子句，
　　2)Ri在结果属性表中涉及到的属性和查询Q中多元子句中所涉及的属性。
　　(4)为每个Xi 形成一个一元查询Qi ，此查询相当于对(3) 2)所确定的那些属性投影用(3) 1)中确定的子句作为限定条件进行限制筛选。如果(3) 1)中没有一元子句并且(3) 2)中确定的属性是Ri 的所有属性，那么就去掉这个Qi 。因为这种情况下的结果就是Ri 。
　　*例12.6 把一元子查询提取算法用于例12.3的查询。
　　对例12.3的查询用此算法的第(3)步结果如下：
　　
　　┏━━━━━━┯━━━┯━━━━━━━━┯━━━━━━━━━━━━┓
　　┃　关系　　　│ 变元 │　 一元子句　　 │　　需要的属性　　　　　┃
　　┠──────┼───┼────────┼────────────┨
　　┃SUPPLIER　 │　 S　│　　无　　　　　│(S#,SNAME,CITY)即所有的┃
　　┃PARTS　　　│　 P　│(P.NAME='BOLTS')│　　　　P#　　　　　　 ┃
　　┃　　　　　　│　　　│ AND(P.SIZE='#6' │　　　　　　　　　　　 ┃
　　┃PROJECT　　│　 J　│　　无　　　　　│(CITY,J#)　　　　　　　 ┃
　　┃INVENTORY │　 V │ (V.QOH>100)　　│(S#,P#,QOH)即所有的　　┃
　　┃SUPPLY　　 │　 Y │ (Y.QU>100)　　 │(J#,S#,P#,QU)即所有的　　┃
　　┗━━━━━━┷━━━┷━━━━━━━━┷━━━━━━━━━━━━┛
　　
　　注：(1)变元S对应的关系SUPPLIER上既没有限定条件也没有投影。
　　(2)涉及V的一元子句是通过传递闭色推导出的。
　　(3)在PROJECT上只有投影而没有限定条件。
　　可以提取出的一元子查询如下：
　　(1)RETRIEVE PARTS1(P.P#)
　　WHERE (P.PNAME='BOLTS') AND (P.SIZE='#6')
　　(2)RETRIEVE PROJECT 1(J.J#,J.CITY)
　　(3)RETRIEVE INVENTORY1(V.S#,V.P#,V.QOH)
　　WHERE (V.QOH>100)
　　(4)RETRIEVE SUPPLY1(Y.J#,Y.S#,Y.P#,Y.QU)
　　WHERE (Y.QU>100)
　　这个算法能提取所有的一元子查询，但没有考虑代价的问题。有些一元子句提取出来并不一定有利。
　　
　　比如(1)显然会使PARTS中的元组数大大减少，是应该提取的；
　　
　　(2)就很可能不会减少PROJECT的元组数。实际上可以把J.J#看成是关系PROJECT的“主关键字”。因此(2)不应该提取。
　　在一般情形下，我们怎样通过计算来确定哪些一元子查询应该提取、哪些不应提取呢？给定一个一元子查询q(Xi )，要决定是否提取出来执行，我们需要知道：
　　
　　(1)处理q(Xi )的代价，
　　(2)这样做带来的好处。
　　处理 q(Xi )的代价可用下列函数来计算：
　　
　　C0 (Ri )=α0 +α1 pg(Ri )+α2 |Ri |log|Ri |
　　↑　　 ↑　　　　↑
　　开销 扫描Ri 的　　 结果重新分类　　　　　　　　　　 (12.1)
　　代价　　　　 排序的代价
　　其中 |Ri |=Ri 中元组个数，
　　pg(Ri )=Ri 所占页数。
　　为了计算提取这个一元子查询后得到的好处，
　　假定Q(X1 ,X2 ，...，Xn )只有一个一元子查询q(Xi )。
　　把Q(X1 ，...，Xn )替换为 (q(Xi )，Q'(X1 ，X2 ，...，Xi '，...Xn ))是相同的。在关系Ri 上执行q(Xi )后得到的结果关系Ri '作为Xi '的变化范围关系。
　　B=C(Q)-C(Q')　　　　　　　　　　　　　　　(12.2)
　　其中,C(Q)是不做提取一元子查询直接用元组代入法执行Q的代价; C(Q')是用元组代入法执行Q'的代价。查询Q和Q'的差别只在于Xi 和Xi '不同, 而处理Q(X1 ,X2 ,...,Xi =α,...,Xn )和Q'(X1 ,X2 ,...,Xi '=α,...,Xn )是相同的。因此，差别只在需要代入元组的数量上。所以：
　　B = C(Q)-C(Q')
　　= (|Ri |-|Ri '|)•C(Q(X1 ,X2 ,...,Xi =α,...,Xn )　　　 (12.3)
　　因此，我们只要能计算出：
　　|Ri |-|Ri '|（执行q(Xi )后Ri 中减少的元组数目)和
　　C(Q(X1 ，X2 ，...，Xi =α，...，Xn )
　　就可以了。对于|Ri |-|Ri '|的计算我们以后讨论。这里讨论后一个代价。
　　实际上，要计算一个一般性的n-1元查询的代价是非常困难的。代价的大小取决于查询的性质。但是我们可以取一个不十分精确但
　　可靠的下界来估计：
　　
　　max C0 (Rj )≤C(Q(X1 ，X2 ，...，Xi =α，...，Xn )
　　j≠i　　　　　　　　　　　　　　　　　　　　　　　 (12.4)
　　这里的C0 (Rj )是在Rj 上执行一元查询的代价，其值可用(12.1)来估计。
　　
　　于是我们得到下面的结果：
　　
　　若 (|Ri |-|Ri '|)max C0 (Rj ) > C0 (Ri )　　　　　　　　　(12.5)
　　j≠i
　　则提取q(Xi ),　否则不提取q(Xi )
　　这也就是说，只有当提取一元子查询得到好处时才做这种提取。另外，从这个式子中我们应该注意到，如果Ri 不是最大的关系，那么只要 q(Xi )可以把Ri 减少一个元组，也要把它提取出来执行。
　　但是，上述结果是在假定了Q(X1 ，X2 ，...，Xn )中只有一个一元子查询q(Xi )的情况下才得到的，而通常在Q中会有许多一元子查询。所以必须把(12.5)改为：
　　
　　若 (|Ri |-|Ri '|)max C0 (Rj ') > C0 (Ri )
　　j≠i
　　则提取q(Xi ),　否则不提取q(Xi )　　　　　　　　　　　 (12.6)
　　其中，Rj '是因涉及Xj 的一元子查询 q(Xj ) 缩减了关系Rj 而得到的关系。
　　(12.6)中不等式左端，也就是提取出 q(Xi )得到的好处，是低估计的，因此如果此式成立应毫不犹豫地提取出 q(Xi )执行。当然，这种低估有时会使应该提取出来的一元子查询没能得到提取。但这时一般说来得到的好处与代价差不多，因此，这种情况下不做提取是无关紧要的，不会引起很大的损失。
　　
　　2.3　化简
　　我们还记得化简是把一个查询分解为只有一个公共变元的两个查询。如果一个查询既没有一元子查询又不能化简，我们就称它是不可化简的。可能有人会问到为什么强调只能有一个公共变元，为什么不能两个或多个。这有几个原因：
　　
　　(1)需要元组代入的最大变元数不会增加。
　　只有一个公共变元的化简把一个n元查询替换为两个查询，一个m元，另一个n-m+1元。需要在n元查询中代入的变元总数为n-1。因为(m-1) + (n-m) =n-1，所以化简并未增加这个数目。但如果把一个查询分为两个有k个公共变元(k≥2)的查询，其结果就不一样了。一个查询有m个变元，另一个 有n-m+k个，需要代入的最大数目为
　　(m-1)+(n-m+k-1)=n+k-2>n-1。
　　
　　(2)每个经化简后的范围关系都是以前那个关系的子关系。
　　因为Q(X1 ，X2 ,...,Xn )被替换为Q'(X1 ，X2 ，...,Xm )和Q"(Xm ',Xm+1 ,...,Xn )。唯一出现的新范围关系是Xm '的范围关系，而它是Rm 的一个子关系。如果Q'和Q"有k个公共变元，处理Q'的结果就不是一个关系的子关系了，而是k个关系的卡氏积的子关系，这可能相当大。
　　
　　(3)对于检查可化简性来说相对容易。
　　只有一个公共变元的化简唯一地定义了一个查询的不可化简部分；有k个公共变元的情况就不是这样了，还可以继续化简。
　　
　　(4)在实际中，查询往往都是可化简的，因为在一个查询中的关系间的连接一般都是链式的。
　　简言之，化简是相对安全的操作，并且比较容易实现。但是一个可化简的查询是否应该化简就需要进一步分析了。我们考虑一个查询Q(X1 ,X2 ,...,Xn )，它没有一元子查询，但可以化简。如果我们不化简它，那就只能对其中某个变元做元组代入了。选择对哪一个变元做元组代入将在2.4中讨论。现在无妨假定对Xi 做元组代入。因为Q是可化简的，所以它以等价于两个查询Q'(X1 ,X2 ,...,Xm )和Q"(Xm ',Xm+1 ,...Xn )。Q"是在Q'之后执行的。在这种情况下Xi 会有三种可能性：
　　(1)Xi =Xm
　　(2)Xi ∈X1 ,X2 ,...,Xm-1
　　(3)Xi ∈Xm+1 ,...,Xn
　　对于(1)的情况来说，Q应该做化简，这是因为Xm '对应的范围关系Rm '中元组数总是要比Xm 对应的Rm 中元组数要少。为使我们明确理解在这种情况下为什么要做化简，我们无妨详细研究、对比一下两种情形。
　　i) 如果不化简，我们经过代入|Rm |个元组后要处理|Rm |个查询Q'(X1 ,...,Xm-1 ,Xm =α)和|Rm |个查询Q"(Xm =α,Xm+1 ,...,Xn )。
　　ii) 如果化简这个查询为 Q'(X1 ,X2 ,...,Xm ) 和 Q"(Xm',Xm+1 ,...,Xn )，那么经代入 |Rm | 个元组后要处理
　　|Rm | 个查询Q'(X1 ,X2 ,...,Xm-1 ,Xm =α)得到的结果为关系Rm '，
　　但还要执行 |Rm '| 个查询 Q"(Xm '=α,Xm+1 ,...,Xn ) 。因此，经化简可以少执行 |Rm |-|Rm '| 个查询 Q"(Xm '=α,Xm+1 ,...,Xn ) 。由于|Rm |>|Rm '|，所以应该做化简。
　　对于(2)的情形，做化简没有害处，因为先做化简或先做元组代入都一样。
　　对于(3)的情形就不好确定了。如果Q被替换为(Q'，Q")，在Q'处理完之前，Xm+1 ,...,Xn 中的任何一个变元都不能做元组代入。在这种情况下是否应该做化简有待进一步研究。
　　一般地说来，化简的好处是使我们可以处理变元少的查询而不用处理变元很多的查询，这样减少了实现时的复杂性。除了做化简本身的开销外，它的唯一缺点是限制了元组代入的次序。这可能会妨碍选择最好的处理查询的策略。
　　*例12.6考虑把例12.4中图12-6的情况化简。
　　通过传递性，可以把图12-6变成图12-7。从这个图上看，这个查询是不可化简的。
　　SNAME　┌─┐　　 CITY　　　┌─┐
　　　　 ←─┤S ├────────┤J │
　　　　　　 └┬┘　　　　　　　　└┬┘
　　　　　　　 │S#　　　　 S#　　　 │J#
　　　　　　　 │　　　　　　　　　　│
　　　　　　 ┌┴┐　 QOH>QU　　 ┌┴┐
　　　　　　 │V ├────────┤Y │
　　　　　　 └─┘　　　　　　　　└─┘
　　　　　　　　　 P#　　　　　　　P#
　　　　　　　　　　　　┌─┐
　　　　　　　　　　　　│P │
　　　　　　　　　　　　└─┘
　　图12-7 通过传递性把图12-6变成了不可化简的形式
　　但是我们也可以把它变成可用两种方法化简的形式，如图12-8所示。这里的V和Y都可以做为公共变元。
　　
　　SNAME　┌─┐　　 CITY　　　 ┌─┐
　　　　 ←─┤S ├────────┤J │
　　　　　　 └─┘　　　　　　　　└┬┘
　　　　　　　　　　　　　　S#　　　 │J#
　　　　　　　　　　　　　　　　　　 │
　　　　　　 ┌─┐　 QOH>QU　　 ┌┴┐
　　　　　　 │V ├────────┤Y │
　　　　　　 └─┘　　 P#,S#　　　 └─┘
　　
　　　　　　　　　　 P#
　　　　　　　　　　　　┌─┐
　　　　　　　　　　　　│P │
　　　　　　　　　　　　└─┘
　　
　　图12-8　通过传递性把图12-6变成可化简的形式
　　
　　除了穷举方法外，目前还没有别的算法可以把一个查询变换为可化简形式。图12-8的查询可化简为三个不可化简的查询，如图12-9所示。
　　
　　　　　　 ┌─┐(S#,P#,QOH)　　　　┌─┐
　　　　　　 │V ├──→　　　　　　 │V'│
　　　　　　 └┬┘　　　　　　　　　 └┬┘
　　　　 ①　　│　　　　　　　　②　 P#│QOH>QU
　　　　　　　 │P#　　　　　　　　　 S#│
　　　　　　 ┌┴┐　　　　　　　　　 ┌┴┐　　　　
　　　　　　 │P │　　　　　　　　　 │Y │
　　　　　　 └─┘　　　　　　　　　 └┬┘
　　　　　　　　　　　　　　　　　　　　↓
　　　　　　　　　　　　　　　　　　　(J#,S#)
　　　　　　　　　　③　　　　　 ┌─┐
　　　　　　　　　　　　　　　　 │Y'│
　　　　　　　　　　　　　S#　　 └┬┘
　　　　 SNAME ┌─┐　　　　　　│　
　　　　　　 ←─┤S │　　　　　　│J#
　　　　　　　　 └─┘　　　　　　│
　　　　　　　　　　　 CITY　　　　
　　　　　　　　　　　　　　　　 ┌┴┐
　　　　　　　　　　　　　　　　 │J │　 图12-9　图12-8的查询化简后的形式
　　这个例子也说明了化简对于元组代入的限制。被代入的第一个变元必须是V或P（无疑这里是P），第二个必须是V'或Y（此处是V'），前两个子查询处理完之前S和J都不能代入。
　　下面提供一个决定是否化简的算法。当然，这种算法比“总是化简”的算法要精细一些，但是不是很实用就不好说了。在2.5中我们要给出INGRES中采用的“总是化简”的算法。
　　定义：Q是X可化简的，如果存在一个化简Q→(Q'，Q")使得X是Q'的某变元。否则称Q为X不可化简的。
　　
　　算法：
　　(1)确定“最好的”下一代入变元，设为Xi 。
　　(2)若Q是Xi 可化简的则化简。
　　(3)否则对Xi 做元组代入。
　　这个算法中存在的问题是计算出代入哪一个变元最好与决定化简有关。如果我们能用一个简单的选择方法选出下次做代入的变元，这个算法会很有用。
　　现在把这种算法用到图12-8上，假定用对应关系元组数最少的变元作为下一个代入变元，这里应该是P（根据例12.3中列出的元组数）。Q是”P可化简”的，所以化简它，其结果如图12-10。处理Q'后，我们又面临如何化简Q"的问题。假定S是4个变元中范围关系的元组数最少的，但由于Q"是S不可化简的。所以根据算法不予化简。
　　
　　　　　　　Q':　　 ┌─┐　P#　　　┌─┐
　　　　　　　　　　 │V ├─────┤P │
　　　　　　　　　　 └┬┘　　　　　└─┘
　　　　　　　　　　　 ↓
　　　　　　　　　　 ┌─┐ QOH>QU ┌─┐
　　　　　　　Q":　　│V'├─────┤Y │
　　　　　　　　　　 └─┘　 P#,S#　└┬┘
　　　　　　　　　　　　　　　　　　　 │J#
　　　　　　　　　　　　　　 S#　　　　│
　　　　　　 SNAME ┌─┐　　CITY ┌┴┐
　　　　　　　　 ←─┤S ├─────┤J │
　　　　　　　　　　 └─┘　　　　　└─┘
　　
　　　　　　　　　　图12-10　图12-8的查询经化简后的结果
　　
　　总之，这种算法并没有比”总是化简”有明显的好处。后者决定化简时不依赖于元组代入变元是哪个，所以实现简单。
　　
　　2.4 元组代入
　　选择元组代入是整个优化过程中最重要的，也是最难的。先考虑n元查询Q(X1 ,X2 ,...,Xn )中对Xi 做元组代入的影响。经代入得到一组n-1元查询Q(X1 ,X2 ,...,Xi =α,...,Xn ),α∈Ri 。若用Qiα 表示Q(Xi =α)，则对Xi 做元组代入可表为：O→Qiα,α∈Ri 。很可能Qiα 对于很多不同的α是相同的。
　　例如，考虑查询Q(S,J)：
　　RETRIEVE (S.SNAME) WHERE (S.CITY=J.CITY)
　　其中S的范围关系是SUPPLIER (SNAME, CITY)。将CITY的值相同但SNAME不同的那些元组代入到S后得到只涉及J的一元查询是完全一样的。因此，在一般情况下，Q中对Xi 做元组代入的结果是　　　　　Qiα , α∈Ri 其中Ri 是Ri 的一个子集。它去掉了代入后会产生冗余的元组。若用C(Q)表示处理Q的最小代价，则
　　
　　C(Q) = min ∑ C(Qiα )　　　　　　　　　　 (12.7)
　　i　α∈Ri
　　乍一看，这个式子似乎是无意义的。但我们可以通过对C(Qiα )取近似值来计算C(Q)。例如，可以假定C(Qiα )=C0 。这种取近似值法使近似值既不依赖于i又不依赖于α。于是(12.7)的右边变成：
　　min ∑ C(Qiα ) ≌ min C0|Ri|=C0 min|Ri |　　　　(12.8)
　　i α∈Ri　　　　　　　i
　　这里的|Ri |表示Ri 的元组个数。由此得到一个选择元组代入变元的规则。
　　规则1　选择需代入元组最少的变元。
　　如果我们在(12.8)中用|Ri |代替|Ri |，这个式子就更简单了。尽管这样很粗糙，但很容易实现，只要求少量的统计信息就可，并且很见成效。
　　上述是基于C(Qiα )既不依赖于i也不依赖于α的前提之下得到的结果。这样的假定是不合理的。可以假定 C(Qiα) 不依赖于α，但不能假定C(Qiα)不依赖于i。Qiα的结构并不依赖于α。但对于不同的i, Qiα 的复杂程度是不同的。在代价中不就出这种差别会影响整个优化策略的有效性。为反映这种差别，我们对(12.8)修改，得到类似于(12.7)的式子：
　　C(Q)≌min|Ri |Ci　　(12.9)
　　i
　　这里的Ci 是对C(Qiα )的估计值。
　　假定所采用的策略是只要有可能就处理一元子查询和只要有可能就化简。因为只当不可化简并且也没有一元子查询时才做元组代入，所以可以假定(12.7)中的Q是不可化简的，而且没有一元子查询，经元组代入后也不会不可化简了。因此，Qiα 可分为Ni 个不可化简的部分：
　　Qiα →qijα , j=1,2,...,Ni
　　其中qijα 是被化简后得到的不可化简部分或是一个一元子查询。无妨假定Ni 和C(qijα )都不依赖于代入到Xi 的α，这样我们可以得到
　　Ni
　　C(Qiα) = ∑C(qijα )　　　　　　　　　(12.10)
　　j=1
　　于是，(12.7)就变成：
　　Ni
　　C(Q) = min[|Ri | ∑C(qijα )]　　　　　　　　　 (12.11)
　　i　　　j=1
　　因为通常qijα 要比Qiα 简单得多，所以通过对C(qijα )估计来计算C(Q)比直接对C(Qiα )估计来计算C(Q)要准确。因而我们得到第二个规则：
　　规则2.选择Xi 使得
　　Ni
　　Ci (Q)=|Ri |∑Cij　　　　　　　(12.12)
　　j=1
　　最小。
　　这里的Cij 是对C(qijα )的估计值。现在的问题是要找出一个好的Cij 。对于一个查询　，一般可以假定它的代价C(q)依赖于q中各变元的范围关系的大小。实际上，如果变元数较少，可以用
　　
　　C(q)=∏|Rj |　　　　　　　　　　　　(12.13)
　　j
　　来估计。当然，可以这样来取Cij 的估计值，不过在一般情况下，集合qijα,j=1,2,...,Ni 中的某些查询必须按某种顺序处理，而不能并行地处理。这是一个很重要的问题。对Ci (Q)求极小值时还不知道某些关系的大小。所以要用规则2并且用(12,13)估计Cij ，就必须对范围关系的大小取估计值。
　　无论用哪一种规则选择元组代入的变元，都需要对范围关系的大小做估计。因此产生一个问题；用哪些关系作为范围关系呢？要处理的查询可能有许多一元子句。如果我们在算法中考虑到确定在哪些关系上执行一元子查询，哪些上不执行，那么共有2n 个选择（n个范围关系）。当然，若某变元被选为元组代入的变元，那么涉及到此变元的一元子查询应该先执行，这样可以缩减范围关系；若没有被选中，那么涉及它的一元子查询就不一定要处理了，处理很可能浪费时间。我们可以采用这样的策略：根据一元子句的类型估计每个Ri '，执行3个可能得到结果关系最小的一元子查询，执行后从中选出结果关系最小的变元作为元组代入的变元。
　　*例12.7　对例12.6中图12-9的最下面的不可化简的子查询做元组代入。
　　这个查询如图12-11(a)所示。
　　　　　　　　　　　　　　┌─┐
　　　　　　　　　　　 S#　　│Y'│
　　　SNAME ┌─┐　　　　 └┬┘
　　　　　←─┤S │　　　　　 │J#
　　　　　　　└─┘　　　　　 │
　　　　　　　　　　 CITY　 ┌┴┐
　　　　　　　　　　　　　　 │J │
　　　　　　　　　　　　　　 └─┘
　　　　　　　　　　 图 12-11 (a) 要处理的查询示意图
　　假定对Y'做元组代入。代入一元组(J#=002，S#=101)。其结果变成如图12-11(b)。
　　
　　　SNAME ┌─┐　CITY　 ┌─┐ J#=102
　　　　←─┤S ├─────┤J ├──┐
　　　　　　　└┬┘　　　　　└─┘　　≡
　　　　　　　│S#=101
　　　　　　　　≡
　　　　　　　　　　　 图 12-11 (b) 对Y'做元组代入的结果
　　又出现了两个一元子句，一个对应“SUPPLIER”的（S#=101），另一个对应“PROJECT”的（J#=002），因此，对于α=(J#=002，S#=101)和Xi =J来说，得到的一组qijα 共三个查询如图12-11(c)所示。
　　
　　　　 ┌─┐S#=101　　　　　　　 ┌─┐J#=102
　　　① │S ├─┐　　　　　　　② │J ├─┐
　　　　 └┬┘　≡　　　　　　　　 └┬┘　≡
　　　　　 ↓(SNAME,CITY)　　　　　 ↓(CITY)
　　　　　　
　　③
　　　　 SNAME ┌─┐　CITY　　 ┌─┐
　　　　　　 ←─┤S'├──────┤J' │
　　　　　　　　 └─┘　　　　　　└─┘
　　
　　　　　　　　　　　 图 12-11 (c) 三个子查询
　　S'的范围关系是SUPPLIER(S#=101)[SNAME,CITY]，J'的范围关系是PROJECT(J#=002)[CITY]。为估计处理③的代价，必须对这两个范围关系的大小做估计。
　　
　　
　　以上我们介绍了当查询是不可化简的时候选择元组代入变元的两个规则。第一个是选择范围关系最小的变元；第二个是考虑代入后分割查询的可能，选出
　　　　　　　　　　　　　Ni
　　　　　　C(Q) = min[|Ri | ∑C(qijα )]　　　　　　　　　 (12.11)
　　　　　　　　　 i　　　j=1
　　最小的变元。但用第二个规则需要在执行运算前估计出结果关系的大小。这样要得到精确的值很难。很多人提出过对结果关系的大小做估计的办法，但这方面的实际经验还不够，还要进一步研究。另外，规则1最好用于涉及3个变元以上的查询。对于2元查询我们还有更好的办法。
　　
　　2.5　二元查询的元组代入
　　多元查询化简后的结果往往是一些二元查询，因此有必要对这种特殊情况做深入的探讨。这里基于元组代入方法来讨论，第三节中我们还要更进一步讨论这一问题。
　　考虑关于关系R的一个布尔函数B(x)。设q(B)表示关系R中满足B（也就是B为真）的元组数，N(B)是找出q(B)个合格元组必须存取的元组数。N(B)与存贮结构有很强的依赖关系，而q(B)却不依赖于存贮结构。一般地说来，我们有
　　q(B)≤N(B)≤|R|　　　　　　　　　(12.14)
　　定义：B是全有索引的（在R的存取结构中），如果N(B)=q(B)；B是无索引的，如果N(B)=|R|；B是部分有索引的，如果q(B) 索引不一定必须是辅助索引，也可以顺序排的主索引或散列结构的索引。
　　*例12.8　假定一个关系SUPPLIER(S#,SNAME,CITY)在S#上有散列的索引，在SNAME上有辅助索引，在CITY上没有索引，考虑下列条件：
　　B1 :S#=10312
　　B2 :CITY='NEW YORK'
　　B3 :SNAME='FORD'
　　B4 :B2 ∧B3
　　这里的B1 和B3 是全有索引的，B2 是无索引的，而B4 是部分有索引的。
　　若用∧表示“与”，用∨表示“或”，则
　　N(B1 ∧B2 )≤min(N(B1 ),N(B2 ))　　 (12.15)
　　max(N(B1 ),N(B2 ))≤N(B1 ∨B2 )≤N(B1 )+N(B2 )　　(12.16)
　　也就是说，如果
　　m　　　　　n
　　B=（∧ Bi ）∧（∧ Cj ）其中Bi 是全有索引的，Cj 是无索引的。
　　i=1　　　　　 j=1
　　则
　　N(B)=min q(Bi )　　　　　　　　　　　　　 (12.17)
　　i≤m
　　
　　现在我们来考虑检索满足限定条件B的元组所付出的代价。我们忽略掉在索引中查找的开销，这种代价相对小些。主要是存取N(B)个元组所付出的代价。因为关系R一般都存放在外存上，以页的方式从外存向内存读入，所以对满足B的那些元组检索的代价为：
　　P(B)=必须存取的N(B)个元组所占的页数
　　假定关系R的H个元组可放于一页中，显然：
　　「(1/H)•N(B)│≤P(B)≤min(N(B),R所占页数)　　　　(12.18)
　　其中「k|表示取大于或等于k的最小整数。如果P(B)= 「(1/H)•N(B)|，我们就说B是完全聚集的（相对于关系R的存贮结构）。我们现在定义一个一般性的聚集因子：
　　「(1/H)•N(B)│
　　λ(B)=───────　　　　　　　　　　　　　　(12.19)
　　P(B)
　　当λ(B)=1时，B就是完全聚集的。
　　可以看出“索引”和“聚集”是条件B和存贮结构间的两种独立的关系。它们都影响到检索N(B)个合格的元组所付出的代价。然而，若要把关系聚集存放，就需要对原来的存贮结构做完全的重新组织。因此，非聚集索引只有当N(B)值较少时或当P≤1时才有用（这是因为页面一般很小，而元组数很大）。
　　*例12.9　有一关系EMP(E#,ENAME,DEPT,SALARY)，它的关系字是E#，在E#上的索引是以ISAM结构存放的。假定100个元组放于一页上共占100页，在外存上另外三个属性也都有索引。考虑下列条件：
　　B1：范围在30000到30216之间的E#
　　B2：ENAME="A.B.Jones,Jr."
　　B3：DEPT=1033
　　B4：范围在21000到24000间的SALARY
　　B5：B3∧B4
　　根据这些条件得到一些统计信息（虽然也是假定的，但这是比较合乎实际的）：
　　　┌──┬───┬──┬───┬──────┐
　　　│条件│ q(B) │N(B)│ P(B) │ 聚集因子　 │
　　　├──┼───┼──┼───┼──────┤
　　　│ B1 │　217 │217 │　　3 │　 1　　　　│
　　　│ B2 │　　1 │　1 │　　1 │　 1　　　　│
　　　│ B3 │　 67 │ 67 │　 41 │　 0.024　　│
　　　│ B4 │　737 │737 │　100 │　 0.01　　 │
　　　│ B5 │　　6 │　6 │　　5 │　 0.2　　　│
　　　└──┴───┴──┴───┴──────┘
　　B4 是全有索引的，但却不起作用，无论如何也要取出100页。SALARY上的索引并没有对B4 有任何帮助，却对B5 有帮助。如果在SALARY上没有索引，那么P(B5 )应该等于P(B3 )（即41），而不是5了。
　　现在我们回到处理二元查询的问题上来。
　　考虑一个查询Q(x,y)，其中x,y对应的范围关系是R1 、R2 。这个查询有两个部分：结果属性表T(x,y)和限定条件B(x,y)。假定我们要做元组代入，应选择哪一个变元呢？如果用一个元组α代入x，我们得到关系R2 的条件B2α ；如果用β入Y，我们得到关于R1 的条件B1β　。我们应该按存取页数来度量哪中方法的代价小，选择代价小的方法代入。也就是用下式计算：
　　C(Q)=min( ∑ P(B2α ,R2 ), ∑ P(B1β ,R1 ) )
　　α∈R1　　　　　　 β∈R2
　　其中R表示R的子集，它去掉了元组代入后可能出现冗余的元组。
　　我们可以看出，就 B2α ,α∈R1　和 B2β ,β∈R2与存贮结构的关系而言，它们是同类的条件。如果B2α 在R2 上对于一个α来说是有索引的，那么它对所有的α都是有索引的；如果B2α 对某α是强聚集的(λ≈1)，那么它对于所有α都是强聚集的，尽管这时λ值可能有些偏差。我们用P(B2 ，R2 )表示P(B2α ,R2 )所有α的平均值，用P(B1，R1)表示P(B1β ，R1 )的平均值，则：
　　C(Q)=min( |R1 |P(B2 ,R2 ),|R2 |P(B1 ,R1 )　(12.20)
　　如果第一项小我们应对X做元组代入，否则对Y代入。
　　*例12.9考虑两个关系
　　SUPPLIER(S#,SNAME,CITY)、 PROJECT(J#,CITY)
　　和一个查询：
　　RANGE OF (X,Y)IS (SUPPLIER,PROJECT)
　　RETRIEVE(X.SNAME)
　　WHERE(X.CITY=Y.CITY)。
　　这里假定：
　　　 ┌────────┬────┬──────┬───┬────┐
　　　 │关系　　　　　　│主结构　│　 索引　　 │元组数│ 页数　 │
　　　 ├────────┼────┼──────┼───┼────┤
　　　 │R1=SUPPLIER　 │按S#散列│SNAME,CITY│ 1000 │　100　 │
　　　 │R2=PROJECT　　│按J#散列│　　 没有　 │ 3000 │　200　 │
　　　 └────────┴────┴──────┴───┴────┘
　　还假定供应者(SUPPLIER)位于50个城市，项目(PROJECT)位于100个城市，即|R2 |=100。
　　B2α : Y.CITY=α.CITY　Y∈PROJECT
　　B1β : X.CITY=β.CITY　X∈SUPPLIER
　　由于CITY在R2 中无索引，所以对于所有α
　　P(B2α ,R2 )=200
　　CITY在R1 中有索引，使
　　1000个元组
　　平均N(B1β) = ──────── =20
　　R1 中50个城市
　　因此，
　　P(B1 ,R1 )≤20
　　设P(B1 ,R1 )=19，方程式(12,20)变成：
　　C(Q)=min{(50)(200),(100)(18)}
　　=min{10,000,1800}
　　显然应该对Y做元组代入。
　　我们也可以通过动态改变关系的存贮结构帮助提高执行查询的效率。因此(12.20)可改为
　　C(Q)=min{|R1 |P(B2 ,R2 )+重新构造R2 的代价,
　　|R2 |P(B1 ,R1 )+重新构造R1 的代价}　　(12.21)
　　这个式子中的函数P是新结构的而不是旧结构的。
　　*例12.10　继续讨论例12.9
　　假定我们在PROJECT的CITY上加一个索引，加索引的代价是对关系扫描一次（取200页）加上对索引表分类的代价之和。假定加索引的代价为220页。如果在R2 中已加入了CITY索引，那么
　　R2 中的3000个元组
　　平均N(B2α) =（─────────）=30
　　R2 中的100个城市
　　P(B2 ，R2 )≤30。
　　设P(B2 ,R2 )=28。(12.21)变成
　　C(Q)=min{50×28+220,18×100}
　　=min{1620,1800}
　　显然应对X做元组代入。
　　从例子中我们看到有时在二元查询中对某一关系重新组织确实有好处。加索引的办法很多，而且很容易，甚至有时可以改变原来的存贮结构以达到强聚集。虽然这么做代价可能较高，但有时也可能会得到好处。我们要注意到，加索引只能使N(B)达到最小，而不能使P(B)达到最小。是否值得动态加索引取决于查询本身的形式。
　　
　　2.6　INGRES系统中分解查询的算法
　　INGRES系统对查询的分解算法由四个子算法构成——化简、子查询排序、元组代入和变元选择。各部分之间的关系如图12-12所示。
　　
　　　　　┌┄┄┄┄┄┄　　(查询)
　　　　　│　　　　　　　　　↓　
　　　　　│　　　　　　　　　　　　　 是 ┌────┐
　　　　　│　　　　　　　　查询是　　─→│一元查询├─→ 返回到调用程序
　　　　　│　　　　　　　　 一元?　　　　│处理程序│
　　　　　│　　　　　　　　　　　　　　　└────┘
　　　　　│　　　　　　　　　↓
　　　　　│　　　　　　┌─────┐
　　　　　│　　　　　　│　化　简　│
　　　　　│　　　　　　└──┬──┘
　　　　　│　　　　　　┌──┴──┐
　　　　　│　　　　　　│子查询排序│
　　　　　│　　　　　　└──┬──┘
　　　　分│　　　　　　　　　↓　　　
　　　　　│　　　　　　　　　　　　　　 无
　　　　解│　　┌─→　　 有子查询　　 ─→ 返回到调用程序
　　　　　│　　│　　　　　　?　　　
　　　　程│　　│　　　　　　　　　　
　　　　　│　　│　　　　　　↓有　　
　　　　序│　　│　　　┌──────┐
　　　　　│　　│　　　│选择子查询Qi │
　　　　　│　　│　　　└──┬───┘
　　　　　│　　│　　　　　　↓
　　　　　│　　│　　　┌──────┐
　　　　　│　　│　　　│从子查询Qi 中│
　　　　　│　　│　　　│选出变元Xj　 │
　　　　　│　　│　　　└──┬───┘
　　　　　│　　│　　　　　　↓
　　　　　│　　│　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　│　　│否　　　 Xj 的范围
　　　　　│　　└─　　　关系中有未代　　┄┄┄┄┐
　　　　　│　　　　　　　入的元组　　　　　　　　┆
　　　　　│　　　　　　　　　　　　　　　　　　　┆
　　　　　│　　　　　　　　　 ↓ 是　　　　　　　┆
　　　　　│　　　　　　 ┌──────┐　　　　 ┆
　　　　　│　　　　　　 │向Qi 中的Xj 代│　　　　 ┆
　　　　　│　　　　　　 │入下一元组　│　　　　 ┆
　　　　　│　　　　　　 └──┬───┘　　　　 ┆ (返回路径)
　　　　　└┄┄┄┄┄┄　　　 ↓　　　　　　　　 ┆
　　　　　　　　　　　　┌┄┄┄┄┄┄┐　　　　　┆
　　　　　　　　　　　　┆ 分解程序　 ┆　　　　　┆
　　　　　　　　　　　　└┄┄┬┄┄┄┘　　　　　┆
　　　　　　　　　　　　　　　└┄┄┄┄┄┄┄┄┄┘
　　　　　　　　　　图 12-12 分解的控制流程图
　　分解算法是递归的，也就是说自身可调用自身。子算法的基本功能如下：
　　(1)化简：把查询分为一些不可化简的部分并把它们排序。
　　(2)子查询排序：利用化简的结果生成一些子查询。每个子查询含有一个不可化简部分和一些一元子句。每个子查询生成后转向元组代入子算法，下一个子查询的生成要等待结果返回才进行。
　　(3)元组代入：管理代入元组值的处理。它调用变元选择部分，选出一个代入变元，向这个变元代入每个元组后，把得到的化简了的查询转向化简算法。在做下一次代入前要等待返回。
　　(4)变元选择：大部分优化工作都在这里。这一部分计算出对每个变元做元组代入的代价。选出代价最小的变元，也可能必须同时预处理一些一元子查询。
　　1.化简算法：
　　　　　　　　　　　　　　　↓Q
　　　　　　　　　　　　　　　　　　　否
　　　　　　　　　┌──→　 变元数>1　 ─┐
　　　　　　　　　│　　　　　　　　　　　│　
　　　　　　　　　│　　　　　 │是　　　 │　
　　　　　　　　　│　　　　　 ↓　　　　 │　
　　　　　　┌──┴─┐否　　　　　　　　│　┌──┐
　　　　　　│分为不相│←　　连通?　　　 └→│输出├→转到子查询
　　　　　　│交的部分│　　　　　　　　　┌→│序列│　　排序
　　　　　　└────┘　　　 │是　　　 │　└──┘
　　　　　　　　　　　　　　　 ↓　　　　 │
　　　　　　　　　　　　┌──────┐　│
　　　　　　　　　　　　│分为不可化简├─┘
　　　　　　　　　　　　│　的部分　　│
　　　　　　　　　　　　└──────┘
　　
　　　　　　　　　　图 12-13 化简算法
　　输入：一个多元查询Q，
　　输出：Q的一些不可化简的部分，它们是按适当的次序排列的。把这个序列转到子查询排序去处理，返回Q的结果关系。其基本的步骤如图12-13。
　　设X=(X1 ,X2 ,...,Xn )表示Q的变元，设T(X)和B(X)分别表示Q的结果属性表和限定条件。我们假定B(X)是合取范式形式的，取
　　B(X) = ∧Ci (X)
　　i
　　其中Ci (X)只含析取式。现在考虑一个二值矩阵，它有P+1行（对应T(X)和P个子句），有n列（对应变元x1 ,x2 ,...,xn ）。矩阵中元素为1表示对应变元出现在对应的子句中（或结果属性表中）；O表示未出现。我们称这个矩阵为关联矩阵。
　　*例12.11　考虑下列关系和查询的关联　　：
　　关系：SUPPLIER(S#,SNAME,CITY)
　　PARTS(P#,PNAME,SIZE)
　　SUPPLY(S#,P#,QUANTITY)
　　查询：RANGE OF(S,P,Y)IS(SUPPLIER,PARTS,SUPPLY)
　　RETRIEVE(S,SNAME)
　　WHERE(S.CITY='NEW YORK')AND (P.PNAME='BOLY')
　　AND (P.SIZE=20) AND (Y.S#=S.S#)
　　AND (Y.P#=P.P#) AND (Y.QUANTITY≥200)
　　这个查询的关联矩阵为：
　　
　　S　 P　 Y
　　T : S.NAME　　　　　　　1　 0　 0
　　C1 :S.CITY='NEW YORK'　1　 0　 0
　　C2 :P.PNAME='BOLT'　　　0　 1　 0
　　C3 :P.SIZE=20　　　　　　0　 1　 0
　　C4 :Y.S#=S.S#　　　　　　1　 0　 1
　　C5 :Y.P#=P.P#　　　　　　0　 1　 1
　　C6 :Y.QOANTITY≥200　　0　 0　 1
　　
　　在图12-12中有两个步骤没有详细画出。
　　其一是我们需要对关联矩阵检查独立查询，如果不连通需要把查询分成一些不相交的部分；
　　其二是需要把连通的 查询分为不可化简的一些部分，然后把它们按一种适当的次序排起来。
　　(1)连通性算法
　　算法如图12-14所示。
　　　　　　　　　　　 ┌────┐
　　　　　　　　　　　 │置 i=0　│
　　　　　　　　　　　 └─┬──┘
　　　　　　　　　　　　　 ↓　　　
　　　　　　　　　　　　　　　　　　是　　　　　　　　是
　　　　　　　　　　　　行数=1？　 ─→　 此行是全　 ─→ 连通
　　　　　　　　　　　　　　　　　　　　　　1 ？
　　　　　　　　　　　　　 │否
　　　　　　　　　　　　　 ↓　　　　　　　　 ↓否
　　　　　　　　　　　　　　　　　　是　　　　│
　　　　　　　　　　　　　i=n？　 ─→────┴───→ 不连通
　　
　　　　　　　　　　　　　 ↓否
　　　　　　　　　　　 ┌────┐
　　　　　　　　　　　 │ i=i+1　 │
　　　　　　　　　　　 └─┬──┘
　　　　　　　　　　　　　 ↓　　　
　　　　　　　　　 ┌────────┐
　　　　　　　　　 │使第i列为1的那些│
　　　　　　　　　 │行形成逻辑或　　│
　　　　　　　　　 └───┬────┘
　　　　　　　　　　　　　 ↓　　　　
　　　　　　　　　 ┌─────────┐
　　　　　　　　　 │用逻辑或替换第ｉ　│
　　　　　　　　　 │列为1 的那些行的　│
　　　　　　　　　 │第一行,删去其余行　│
　　　　　　　　　 └───┬─────┘
　　　　　　　　　　　　　 ↓　　　　
　　　　　　　　　 图12-14　联通性算法
　　如果连通性算法的结果是一个只有一行的矩阵而这一行不全为1，那么对应0的那些变元就是多余的、可以删去。
　　如果最终的矩阵有许多行，则对应每行的变元的集合必不相交。
　　我们记录下最终矩阵的每行所对应的原来的那些行，那么就把此查询的连通部分划分出来了。
　　　　考虑一下例12.11，这里把C4 去掉后，关联矩阵为：
　　　　　　S　 P　 Y
　　　T　　 1　 0　 0
　　　C1　　1　 0　 0
　　　C2　　0　 1　 0
　　　C3　　0　 1　 0
　　　C5　　0　 1　 1
　　　C6　　0　 0　 1
　　对这个矩阵用连通性的算法，我们得到：
　　　　　 S　 P　 Y　　
　　T,C1　　1　 0　 0
　　　C2　　0　 1　 0
　　　C3　　0　 1　 0
　　　C5　　0　 1　 1
　　　C6　　0　 0　 1
　　
　　　　　　　　　 S　 P　 Y　　
　　T,C1　　　　　　1　 0　 0
　　C2 ,C3 ,C5　　　 0　 1　 1
　　C6　　　　　　　0　 0　 1
　　
　　　　　　　　　　　S　 P　 Y　　
　　T0 ,C1　　　　　　　1　 0　 0
　　C2 ,C3 ,C5 ,C6　　　　0　 1　 1
　　由此可见，这个查询不连通，连通部分是（T，C1）和（C2，C3，C5，C6）。
　　(2)分解成不可化简的部分
　　设Q是一连通的多元查询。我们应该注意，如果去掉一个一元变元会导致Q不连通，那么Q就是可化简的。令具有这种性质的一个变元叫做联接变元。我们可以得到：Q是不可化简的　当且仅当　Q没有联接变元。联接变元有一些非常重要的性质，对化简算法极有用，归纳如下：
　　
　　命题10.1 假定X是Q的一个联接变元，去掉它使Q分成K个连通部分，则每部分中的任何联接变元都是Q的联接变元；Q的每个联接变元都是其中一部分的联接变元。进而，无论按哪种次序相继去掉两个联接变元，都把Q化简为同样的一些不相交部分。
　　
　　证明：每个联接变元把以它作为唯一公共变元的一些部分联接起来。设X是Q的一个联接变元，它把Q1 ，Q2 ，...,QK 联接起来。设Y是其中某一部分的联接变元，假定是Q1的联接变元。那么Y联接了Q1 的一些部分Q11 ，Q12 ，...，Q1j ，这些部分中只能有一部分含有X，无妨假定Q11 含有X。因此(Q12 ,...,Q1j )和Q的其余部分只有Y是公共变元，Y是Q的一个联接变元。反过来，设Y是Q的一个联接变元，它联接了Q1 '，Q2 '，...,Qj '。集合 Q1 '，Q2 '，...,Qj ' 中只有一个元素含有X，无妨假定Q1 '含有X。集合 Q1 ，Q2 ，...,QK　中只有一个元素含有Y，设Q1 含有Y。于是 Q1 '，Q2 '，...,Qj ' 和 Q1 ，Q2 ，...,QK　不相交，因为每个Qi ,(i≥2)与Q的其余部分的公共变元只有X，而且 Q2 '，...,Qj ' 中不含X。因此Q2 '，...,Qj '是通过Y联接到Q1 上的一些子集。Y是Q1 的联接变元。很显然Q的某些部分 Q2 ，...,QK　只是通过X联接起来的；而另一些部分Q2 '，...,Qj ' 只靠Y联接起来。Qxy 则是靠X和Y联接起来的。无论先去掉X后去掉Y还是先去Y后去X，其结果都是一些不相交的部分Q2 ,Q3 ,...,Qk ,Q1 ',Q2 ',...,Qj ',QXY ，其中Qi 表示去掉X的Qi ，Qi '表示去掉Y的Qi ',QXY 表示去掉X和Y的QXY 。
　　命题的证明可参考图 12-15
　　Ｑｋ　　　　　　　　　　　　　　　　　　 Ｑｊ’
　　•　　　　　　　　　　　　　　　　　　　　 •
　　•　　　　 Ｘ　　　　Ｑｘｙ　　　　 Ｙ　　　　•
　　•　　　　　　　　　　　　　　　　　　　　 •
　　Ｑ２　　　　　　　　　　　　　　　　　　　Ｑ２’
　　图12-15　联接变元
　　根据命题10.1我们可以通过检验Q的每个变元是否可能是联接变元，找出Q的不可化简部分。每个变元只需要检查一次，而且检查的先后次序无关。因为一变元是联接变元 当且仅当 去掉它会使Q不连通，所以我们可以利用连通性算法做这种检查。下面看一下如何检查。
　　去掉Q的关联矩阵中每行只有一个“1”的那些行（也就是去掉一元子句对应的那些行）。然后，从第一列开始，依次去掉每列查连通性。假定去掉m列时Q分为分别有n1 ,n2 ,...,nk 个变元的K个连通部分，于是这些部分对应于Q中具有n1 +1,n2 +2,...,nk +1的一些部分，它们之间只有Xm 是公共变元。我们继续查第m+1，...,n列时会发现，变元Xm+1 ,...,Xn 中任一个都只在这些部分中的一部分里出现。由此，在第m列之后（也就是第一个联接变元后）的检查是在缩小体积的矩阵上做的。
　　
　　Q的每个不可化简的部分对应于关联矩阵的一行或几行，可以表示为相对应那些行的“逻辑式”。因此Q可以用具有所有变元的一个矩阵来表示，其列数与变元数相同，其行数与不可化简的部分的数目相同。这种矩阵叫做缩减的关联矩阵。矩阵的行按下列次序排列比较方便：
　　1)除结果属性表以外只有一个变元的那些行。
　　
　　2)去掉一元子句后只有一个公共变元的那些部分，而且这些部分都不包含结果属性表。这些行应按联接变元分组。
　　3)不包含结果属性表的其它部分
　　4)包含属性表的部分
　　*例12.12　考虑例12.11的缩减关联矩阵。
　　例12.11的查询按上述排列法得到的矩阵为：
　　S　 P　 Y
　　C1　　1　 0　 0
　　C2　　0　 1　 0
　　C3　　0　 1　 0
　　C6　　0　 0　 1
　　C5　　0　 1　 1
　　T,C4　　1　 0　 1
　　这也就是说，把一元子句对应的行放在最上面，一些链状结构的子句对应的行放在其后，那些不可化简的行和结果属性表放在最下面。
　　
　　2.子查询排序
　　此程序任务很简单：接收化简部分的输出，取出与缩减关联矩阵的第一个多元的行所对应的部分，把这部分与所有有关的一元子句合起来形成一个子查询。删去用过的行，把子查询转到元组代入程序处理。一旦返回子查询的结果，就在剩余的矩阵上重复这一过程。矩阵用完并且得到Q的结果时，把Q的结果返回到调用程序。
　　*例12.13对例12.11用上述算法。
　　用了这个算法处理后，生成出的子查询如下：
　　Q1 :C2 ，C3 ，C6 ，C5
　　Q2 :C1 ，C4 ，T.
　　如果把它们用QUEL写出来就是：
　　Q1 :RANGE OF (P,Y)IS (PARTS,SUPPLY)
　　RETRIEVE INTO SUPPLY 1(Y.S#)
　　WHERE(P.PNAME='BOLY')
　　AND (P.SIZE=20)
　　AND (Y.QUANTITY≥200)
　　AND (Y.P#=P.P#)
　　Q2 :RANGE OF (S,Y)IS (SUPPLIER,SUPPLY1)
　　RETRIEVE(S,SNAME)
　　WHERE(S.CITY='NEWYORK')
　　AND (Y.S#=S.S#)
　　3.元组代入
　　向元组代入程序输入一个查询Q，Q是一个含有变元X1 ，X2 ，...，Xn 的不可化简的部分和零个或多个涉及这些变元的一元子句构成的，并且输入这n个变元的范围关系R1 ，R2 ，...,Rn 。所得到的结果返回调用程序。
　　元组代入的第一件事是调用变元选择程序，该程序取出Q和那些范围关系，选出一个要做元组代入的变元。为做选择，可能必须处理某些或所有的一元子句来限制筛选范围关系。一般地说来，从变元选择程序返回 Q', R1 '，R2 '，...,Rn '和要代入的变元（假定是Xn）。把Rn '中每个元组α代入Xn ，使Q'变成一个n-1元的查询Q'(α)，所涉及的变元是X1 ，X2 ，...,Xn-1 每代入一个α，把Q'(α)转到化简程序（也就是递归调用整个分解程序），返回时带回一个结果。把所有返回的结果积累起来，返回到调用程序。
　　
　　4.变元选择
　　这一部分是优化的核心。输入是一个不可化简的多元查询和一些有关的一元子句。这一部分的任务是选出一个做元组代入的变元。
　　所采用的策略是：
　　1)预处理每个子查询。理由是处理一元子查询的代价相对较小，但对于准备选择变元却很有帮助。
　　2)找出当前范围关系的元组数最小的变元作为下一步元组代入的变元。
　　这种变元选择的策略实现较容易。INGRES系统采用了这套方法使得处理多元查询很见成效。
　　

原文转自：http://www.ltesting.net