第六章-全局查询到段查询的变换.doc

第六章 全局查询到段查询的变换一般说来，把对全局关系的查询（称为全局查询）变换为段的查询（称为段的查询），有几种不同的方法，采用某些规则就可把一个全局查询表达式重新写成一种等价的段查询表达式。6.1 查询的算符树及其等价变换例： S(学号,姓名,年令,性别,系号，奖学金,班长学号，民族)C(课号,课名,学时,任课教师)SC(学号, 课号,成绩) D(系号，系名，系主任)查询：学生刘建所学课号及成绩SELECT 课号，成绩FROM S，SCWHERE S. 学号 = SC. 学号 AND S. 姓名 = 刘建 ； 以上是用SQL完成的查询（语义），在内部实现上，同一个语义可有多种不同方式。对上面的查询，系统可用下面三种方式来实现：T1 = PJ课号,成绩(SLS.学号= SC.学号S.姓名=刘建（S CP SC）T2 = PJ课号,成绩(SL姓名=刘建（S NJN SC）T3 = PJ课号,成绩（SL姓名=刘建S） NJN SC）分析上式，T1、T2、T3是等价的，但T3优于T2，T2优于T1。 怎样才能写出优化的表达式呢? 这就要相应有些准则。引入查询的算符树的概念,并利用准则，通过对算符树进行等价变换达到优化目的。6.1.1 查询的算符树 Q1：查询对北部地区的各个部门供货的供应商号。图6.1是查询Q1的算符树的一个例子， 其中树叶是全局关系，而每个节点表示了一个一元或二元的操作。在本例中，先执行结合操作，再执行选择和投影操作。 图6.1 查询Q1的一种算符树我们可以把关系代数表达式的算符树看作是表达式本身的语法分析树，语法规则（产生式）。R 标识符R （R）R UNOP RR R BINOP R UNOP SLFPJA BINOP CPUN DFJNFNJNINSJFNSJ上述的R可以是算符树的叶节点，运算符是枝节点，可通过对算符树进行等价变换达到优化目的。6.1.2 关系代数的等价变换令U和B分别表示一元代数运算符和二元代数运算符，我们有：l 一元运算的交换律（commutativity）： U1U2R U2U1Rl 二元运算的操作数的交换律 R B S S B Rl 二元运算的结合律（associativity）： R B（S BT） （R B S）B Tl 一远运算的幂等（idempotence）： UR U1U2Rl 一元运算相对于二元运算的分配律（distributivity）： U(R B S） U(R）B U(S）l 一元运算的因子分解（factorization），（这种变换正好与分配律相反）： U(R）B U(S） U (R B S）下面讨论对于上述各条的具体可行的情况。（见表6.1-表6.5）表6.1 一元运算的交换律 SLF2 PJA2 SLF1（*（R） Y Y *（SLF1（R）PJ A1（*（R） SNG1 SNG2 *（PJA1（R） SNG1：Attr（F2） A1 ；SNG2：A1 A2表6.2 二元运算的结合律及操作数的交换律 UN DF CP JNF SJF R*S Y N Y Y N S*R （R*S)*T Y N Y SNG1 N R*(S*T)SNG1：for（R JNF1 S）JNF2T R JNF1（S JNF2 T）：Attr（F2） Attr（S）U Attr（T）：？ 表6.3 一元运算的幂等 PJA（R） PJA1PJA2（R） SNG：A A1，A A2 SLF（R） SLF1SLF2（R） SNG：F=F1 F26.4、6.5见教材。在非分布式数据库中，为了优化查询的执行，给出了一些相关的等价变换的一般准则： 准则1 使用选择和投影的幂等来为每个操作数关系产生相应的选择和投影。准则2 把树中的选择和投影运算尽可能的向下推移。图6.2 查询Q1的修改后的算符树（见教材80页） 图6.2 就是经过运用准则1和准则2变换之后的算符树。6.2 把全局查询变换成段查询 6.2.1 段查询的规范表达式段查询的规范表达式：已知在全局模式上的一个代数表达式，只要对其中出现的每个全局关系名代入由段重构全局关系的代数表达式，就得到了规范表达式。采用同样的方法可以把全局模式上的算符树映射成分段模式上的算符树。( a) 查询Q1的规范形式（用段重构代替全局关系名）（P83）( b) 把算符树中的选择和投影向下推移（准则2）图6. 3 查询Q1算符树的进一步变换（P83）6.2.2 限定关系代数学限定关系：是一种带有限定语的关系，限定语确定了限定关系中所有元组的共同内涵特性，并表示为：R：qR ，这个整体为限定关系。其中，R是一个关系，称为此限定关系的实体，qR是一谓语，称为此限定关系的限定语。这里不要求对关系的元组求出关系的限定语的值，但若可求值，则其值必为真。水平分段是限定关系的典型例子，限定语相应于分段谓语。例如：对于SUPPLIER1，可写成限定形式：SUPPLIER1：CITY=“SF “ 对于DEPT1，可写成限定形式：DEPT1：DEPTNUM10这意味着SUPPLIER1中每一元组对于限定语CITY=“SF “均为真值。DEPT1 中每一元组对于限定语DEPTNUM10均为真值。CITY=“SF“是SUPPLIER1中所有元组的共同内涵特性。同理，DEPTNUM PJDEPTNUM，NAME DEPT1：DEPTNUM 10 例2： PJAREA，MGRNUMDEPT1：DEPTNUM 10 = PJAREA，MGRNUM DEPT1：DEPTNUM 10 规则3： R：qR CP S：qS R CP S：qR AND qS 注意：这里是把两个限定语应用到R CP S 的不相交属性上。 证：令 t1 R，则t1具有内涵特性qR ， t2 S，则t2具有内涵特性qS ，并由乘法定义知，元组 R CP S且它必具有内涵特性qR AND qS 。例： S（学号，系，性别） S1 = SL系=“计算机“（S） S1：系 = “计算机“ C（课程，专业，学分） C1 = SL专业=“软件与理论“（S） C1：专业 = “软件与理论“ S1：系 = “计算机“ CP C1：专业 = “软件与理论“ S1 CP C1：系 = “计算机 “ AND 专业 = “软件与理论“ 注意：两限定语不相交的属性。规则4： R：qR DF S：qS R DF S：qR （R DF S ） R 但（R DF S ） S 有R DF S：qR 注意事项： R IN S = R DF（ R DF S ）= S DF（S DF R） 即交集运算具有可交换性，即 R IN S = S IN R 如果应用扩充代数学的定义，将会出现R：qR IN S：qS R：qR DF （R：qR DF S：qS） R：qR DF R DF S：qR R DF（R DF S）：qR R IN S：qR （1）而 S：qS IN R：qR S：qS DF S：qS DF R：qR S：qS DF S DF R：qS SDF （S DF R）：qS S IN R：qS （2）事实上，我们想得到的结果是： R IN S ：qR AND qS 证： 设t R IN S ,则t R且 t S t具有特性 qR且具有特性qS 。规则5： R：qR UN S：qS R UN S：qR OR qS 这是显然的。以上是把关系代数的五种基本运算推广到限定关系的运算中，下面是关系代数复合运算的推广。规则6： R：qR JNF S：qS R JNF S：qR AND qS AND F 证：R：qR JNF S：qS SLF（R：qR CP S：qS） SLF（R CP S：qR AND qS） SLF（R CP S）：（qR AND qS） AND F R JNF S ：qR AND qS AND F规则7： R：qR SJF S：qS R SJF S：qR AND qS AND F 证：R：qR SJF S：qS PJATTR（R）（R：qR JNF S：qS） PJATTR（R）R JNF S：qR AND qS AND F （由规则6） PJATTR（R）（R JNF S）：qR AND qS AND F （由规则2） R SJF S：qR AND qS AND F （由半结合定义）运用规则1, 就可把图6.3 ( b)的最右分支剪掉，因DEPT3中没有北部地区。关系代数表达式可以进行很多种有条件和无条件的等价变换，限定关系代数表达式也可进行同样的变换。例：SLCITY = “LA“SUPPLIER1：CITY=”SF“ SLCITY = “LA“SUPPLIER1：CITY=”SF” AND CITY = ”LA” （限定语为永假）通过识别空关系的过程可大大简化查询树，运用规则1,可把图6.3 ( b)最右分支剪掉，因DEPT3中没有北部地区。针对限定关系的代数运算，可考虑如下几个优化的新准则：准则3 把选择向下推到树叶处， 然后对它们使用限定关系的代数运算：如果结果的限定语是永假式，则用空关系来代替此选择的结果。准则4 利用限定关系的代数运算来求结合的操作数的限定语之值；如果这个结合的结果的限定语是永假式，则用空关系来代替此子树（包括此结合及它的操作数在内）。6.2.3 水平分段关系的化简例Q3：查阅部门号为1的部门名、地区及经理号。 对全局关系 DEPT 进行操作： SLDEPTNUM=1DEPT 现将这一全局查询变换到段查询（查询的规范化格式） SLDEPTNUM=1 SLDEPTNUM=1 UN DEPT1:DEPTNUM10DEPT1: DEPT2 DEPT3DEPTNUM10 1020 (a) 查询Q3的规范形式 （b）查询Q3的化简 图6.5 水平分段关系的化简再如：运用限定关系的运算规则1和优化准则3,可把图6.3 ( b)最右分支剪掉，因DEPT3可写成限定形式DEPT3：DEPTNUM20，限定语表明DEPT3中的元组都是南部地区（没有北部地区）的部门，AREA=NORTH 意味NOT（DEPTNUM20）。6.2.4水平分段关系之间结合的化简分布结合的例子：Q4：查询至少有一个供应订单的供应商号和名：SNUM，NAME。 Q4 ：PJSNUM，NAME（SUPPLY NJN SUPPLIERE） PJSNUM，NAME NJNDEPTNUM=DEPTNUM UN UNSUPPLY1：SNUM= SUPPLY2：SNUM= SUPPLIER1： SUPPLIER2：SUPPLIER.SNUM AND SUPPLIER.SNUM AND CITY=”SP” CITY=”LA”SUPPLIER.CITY=”SF” SUPPLIER.CITY=”LA”（a） 查询Q4的规范形式准则5：为了分布出现在全局查询中的结合，可以把并运算（代表段的收集）推向结合之上。上述准则可用于简化水平分段关系与水平分段关系之间的结合。UN PJSNUM，NAME PJSNUM，NAME NJN NJNSUPPLY1：SNUM= SUPPLIER1： SUPPLY2：SNUM= SUPPLIER2：CITY=”LA”SUPPLIER1.SNUM AND CITY=”SF” SUPPLIER2.SNUM ANDSUPPLIER1.CITY=”SF” SUPPLIER2.CITY=”SF” （b） 查询Q4的分布式结合（运用准则5，把并运算推向结合之上） 图6.5 水平分段关系之间结合的化简这里已经剪掉了2个限定关系结合对子：SUPPLY1 NJN SUPPLIER2 和 SUPPLY2 NJN SUPPLIER1因为利用准则4，可知限定语为永假。6.2.5采用推论方法（inference）进一步化简 已经看到，在对限定关系进行选择性查询或结合性查询时，利用准则3和准则4对限定语进行是否为永假式的判断是极为有用的，但有些情况确定一个公式是否为永假式并非可直接判断，可以采用更为复杂的内涵信息，并要求使用定理证明程序加以判断。仍以Q1为例：Q1：查询对北部地区分公司供货的供应商号。PJSNUMSLAREA=“NORTH“（SUPPLY JNDEPTNUM=DEPTNUM DEPT） 假设：1. 北部地区仅包含了部门110 。 2. 来自部门110 的订单全部送给“SF“的供应商。 利用上面假设来推导哪些是永假，以便消除相应子表达式。 首先，由第1条有下面蕴涵式： AREA = “NORTH“ NOT（1020） 利用准则3，把选择操作应用到段DEPT1，DEPT2，DEPT3，并求出结果的限定语的值，借助上面的蕴涵式，知其中两个段DEPT2、DEPT3为永假，可消去相应的子表达式，得到图6.6（a）所示的算符树。 PJSNUM JNDEPTNUM=DEPTNUM UN UN PJSNUM,DEPTNUM PJSNUM,DEPTNUM SLAREA=”NORTH”SUPPLY1:SNUM= SUPPLY2:SNUM= DEPT1:SUPPLIER1.SNUM AND SUPPLIER2.SNUM AND 1DEPTNUM10SUPPLIER1.CITY=”SF” SUPPLIER2.CITY=”LA” （a） PJSNUM JNDEPTNUM=DEPTNUM PJSNUM,.DEPTNUM PJDEPTNUMSUPPLY1:SNUM= SLAREA=”NORTH”SUPPLIER1.SNUM AND SUPPLIER1.CITY=”SF” DEPT1：1DEPTNUM10 （b） 图6.6 采用推论方法进行算符树的化简然后，利用准则5将合并运算上移至结合之上，再分配该结合：SUPPLY1与DEPT1结合，SUPPLY2与DEPT1结合，由假设1可知： AREA = “NORTH“ DEPTNUM 10而由假设2可知：DEPTNUM 10 NOT（SNUM=SUPPLIER.SNUM AND SUPPLIER.CITY=”LA”)通过运用准则4，可知SUPPLY2与DEPT1结合将为空。于是得到图6.6（b）所示的算符树。6.2.6垂直分段关系的化简将垂直分段关系的查询表达式变化成规范表达式之后，一般都要用到结合操作（重构全局关系）。希望寻找一个适当的子集就能足以回答问题，这样就可删除其余段，达到简化目的。例：Q5：列出雇员姓名及工资收入。(见P47分段模式) PJNAME，SALEMP PJNAME,SAL JNEMPTNUM=EMPTNUM EMP4：true UN PJNAME,SAL EMP4：true EMP1: EMP2 EMP3 DEPTNUM10 1020（a）查询Q5的规范算符树 （b）化简算符树 图6.8 垂直分段关系的化简EMP被垂直地分成第一个段EMP4（描述雇员的工资管理）和第2个段，而第2个段又进一步水平地分片成EMP1，EMP2，EMP3 。由于EMP4的属性包含了NAME和SAL，所以仅用段EMP4就可回答该查询，并且可以通过剪掉结合的一个分支进而剪掉了结合及其下面的各段合并运算。化简算符树如图6.8（b）所示。由此可见：垂直分段的运算规则可简化大多数查询，即把大多的查询局部于某个段内。6.2.7半结合操作半结合是关系代数的一种导出式运算，它在分布式查询中有着特殊的重要性。有时将结合运算转换成半结合运算可使查询大大简化。给定一“相等结合” R JNA=B S ，这里A和B分别是R和S的属性（或更一般地说，是属性组），其半结合程序如下： S JNA=B（R SJA=B PJB S） 直观分析：设R，S分布在 JNA=B 不同站点上，将S 投影到 B上，可将结果发送给R站 SJA=B 点，再在R的站点上执行此 R PJB 请求点 半结合运算，再把半结合结果 S 送到S站点，最后在S的站点执行结合操作 图6.8 半结合程序的算符树优点是：（1）S投影后数据量大大减少（只传有用的，淘汰无用的） （2）半结合后，R的元组中只有一个子集“存活”（只留有用的，淘汰无用的），而存活元组恰恰要与S结合。例： S(学号,姓名,年令,性别,系号,奖学金,班长学号,民族)C(课号,课名,学时,任课教师)SC(学号, 课号,成绩) D(系号，系名，系主任)设表S、R分别在站点S和站点R上，请同学们分别写出请求： 列出少数民族学生的学号，姓名，性别，课号，成绩 PJ学号，姓名，性别，课号，成绩（SL民族“汉“ （S NJN SC）发生在站点S和站点R上的含有半结合运算的关系代数表达式。6.3分布式分组和聚集函数的求值数据库应用往往需要执行不能用关系代数来表示的数据库访问操作，所以关系数据库的查询语言一般允许使用不能化简成关系代数表达式的查询式子。这些附加特性中最重要的特性是能把元组分组成关系的不相交子集（水平或导出式水平分段），以及能通过对它们求聚集函数的值进而求出对全局关系的聚集函数的值。聚集函数有：SUM（属性），AVG（属性），COUNT（*），MAX（属性），MIN（属性）如求学习课号为C2课的学生总数。 SELECT COUNT（*） FROM SC WHERE 课号 = “C2“；求平均年龄 SELECT AVG（年龄） FROM S ；求最大年龄的学生的姓名、性别 SELECT 姓名，性别，MAX（年龄） FROM S； Q6：查询产品“P1“的平均订货量。 SELECT AVG（QUAN） FROM SUPPLYWHERE PNUM = “P1“ ； Q7：查每一供应商所供应每种零件的总数量。 SELECT SNUM，PNUM，SUM（QUAN）：TOTAL FROM SUPPLY GROUP BY SNUM，PNUM；Q8：接Q7，但仅保留总和值大于300的那些组。 SELECT SNUM，PNUM，SUM（QUAN） FROM SUPPLY GROUP BY SNUM，PNUM HAVING SUM（QUAN） 300 ；聚集函数、分组功能都不能用关系代数来表达，需对关系代数进行扩充。6.3.1 关系代数的扩充用group-by GBG,AFR操作来扩充关系代数。用G表示某一属性集合，由此集合的值来决定R的分组。用AF表示要对每个组求值的聚集函数。GBG,AFR是一个关系，该关系的框架结构是由G的属性和AF的聚集函数组成，元组数目就是R按G值进行分组的数目，AF所决定的属性值就是对相应组求出的聚集函数的值（不分组，则默认为一个组）。G或AF可以不指定。 利用上述操作可以用代数形式来书写Q6、Q7、Q8 。Q6：求产品P1的平均订货量。 GBAVG（QUAN）SLPNUM =P1SUPPLY （G为空，作用于选择后的所有元组）。 Q7：求每一供应商供应每种零件的总量GBSNUM，PNUM，SUM（QUAN）SUPPLY Q8：求由同一厂商供应的每种零件的总量达300以上的供应商号，零件号，总量。 SL SUM（QUAN）300GBSNUM，PNUM，SUM（QUAN） TSUPPLY Q9：求订单量达300以上的供应商号，零件号，订货量。 PJ SNUM，PNUM，QUAN SLQUAN300 SUPPLY请自己写出对于教学模型的相关询问。6.3.2 GROUP BY 操作的特性（1） 分组操作的分布计算首先考察GB相对于合并运算的分配率。GBG，AF（R1 UN R2） （GBG，AFR1） UN （GBG，AF R2）当且仅当：对任意的i ，j （i是被分组的下标， j是待合并运算的段的下标，Gi是第i个分组中原始记录的集合），或者（Gi Rj）或者（Gi U Rj = ）（*）即每个组所涉及的记录必须全部在同一个段里，不能跨段。显然，对全局关系进行分组计算只要满足上述条件，则可先分布式分组计算，然后再合并。更重要的是站点间并行工作（各段在不同站点上）。为此给出如下准则：准则6：为了在一个全局查询中进行分布分组和组内聚合函数的求值，在满足（Gi Rj）或者（Gi U Rj = ）的条件下，应把合并（段收集水平分段的重构）向上推至相应的GROUP BY 操作范围之上。例：Q8：求同一厂商供应的每种零件供应总量达300以上的供应商号，零件号，总量。 SL SUM（QUAN）300GBSNUM，PNUM，SUM（QUAN）SUPPLY SNUM的值相同元组绝不跨段，可用准则6。 SLSUM（QUAN）300 UN GBSNUM,PNUM,SUM(QUAN) SLSUM(QUAN)300 SLSUM(QUAN)300 UN GBSNUM,PNUM,SUM(QUAN) GBSNUM,PNUM,SUM（QUAN）SUPLLY1 SUPPLY2 SUPPLY1： SUPPLY2： （a）Q8的规范形式 （b）Q8的分布形式 图6.9 具有分组及聚集函数的查询但注意，求每一零件的订货总量则不能分布式计算聚合函数，因同一个零件号可在不同段中。表达式：GBPNUM，SNM（QUAN）SUPPLY 只能写成： GBPNUM，SUM（QUAN）（SUPPLY1 UN SUPPLY2） 而不能将GB对合并进行分配计算，即不能写成：R = GBPNUM,SUM(QUAN)(SUPPLY1) UN GBPNUM，SUM（QUAN）（SUPPLY2） 通过这个例子，我们来考虑把一个聚合函数F分解成F1，F2， ，Fm ，使得Fi（i = 1,2，m）仅对段实施操作，然后再对各段操作后的结果进行加工，如上面的MAX（）函数，对各段求MAX（）值后再选一次最大。但若求每一零件的平均订货量则上式不好用，不能按上述方法进行分布计算，能否有其它解决办法？下面考虑聚集函数的分布计算表达形式:对于聚合函数F、关系R，及R的子集R1, R2 , , Rn 可表示为：F(R)=E(F1(R1),F1(Rn),F2(R1) , F2(Rn) ,Fm(R1) , Fm(Rn) 其中：（1）SUM计算 SUM(R)= SUM(SUM(R1), SUM(R2),SUM(Rn) 这里，m=1，F1是SUM，E也是SUM(2) MAX计算 MAX(R) = MAX(MAX(R1), MAX(R2), MAX(Rn)（3）Min计算 MIN(R) = MIN(MIN(R1), MIN(R2), MAX(Rn)(4) COUNT计算 COUNT(R)=SUM(COUNT(R1),COUNT(R2), COUNT(Rn) (5)AVG(R) = SUM(SUM(R1), SUM(R2),SUM(Rn)/ SUM(COUNT(R1),COUNT(R2),COUNT(Rn)这里，m=2，F1是SUM，F2是COUNT ，E是SUM与COUNT等的组合运算。聚集函数的分布式计算在分布式数据库中是一个重要的特性，因为可以把函数F1（R1）， ,F1（Rn）的部分结果传送给一公共站点，然后在这个公共站点处求表达式E的值，而不用象原先那样把所有的数据传递给该站点，并在该站点计算聚集函数。下面是Q6的例子：求产品P1的平均订货量。GBAVG（QUAN）SLPNUM =P1SUPPLY （*，p1为选择的条件）（G为空，作用于选择后的所有元组） GBAVG(QUAN) E:AVG(QUAN)=SUM(S1,S2)/SUM(C1,C2）SLPNUM=P1 S1,C1:GBSUM(QUAN),COUNT S2,C2:GBSUM(QUAN),COUNT UN SLPNUM=P1 SLPNUM=P1 SUPPLY1 SUPPLY2 SUPPLY1 SUPPLY2 （a） 查询Q6的规范形式 （b）查询Q6的分布式形式 图6.10 聚集函数的分布式求值 图6.10（a）表示了此查询的规范形式，在这种情况下，不可能使用准则6，因为不具备分布计算条件，为解决这个查询，可对两个段SUPPLY1和SUPPLY2进行独立的子查询操作：GBSUM（QUAN），COUNT（*）SLPNUM=P1SUPPLY1 （结果存于S1,C1中）。GBSUM（QUAN），COUNT（*）SLPNUM=P1SUPPLY2 （结果存于S2,C2中）。 令S1、C1分别为对SUPPLY1的GB操作的属性：SUM（QUAN）和COUNT 中的值，同理，S2和C2分别为对SUPPLY2的GB操作的属性：SUM（QUAN）和COUNT中的值，因而数量的平均值AVG（QUAN）由式子（S1+S2）/（C1+C2）给出。这样，把S1，S2，C1和C2传送到要产生查询结果的站点上，并在那儿计算AVG（QUAN）的值。如果没有这种变换，则在函数的非分布式求值时就需要在同一站点上从段SUPPLY1和SUPPLY2收集实际的元组，显然网上传输量大，相应的聚集函数求值效率也低。6.4 参数性查询在查询的选择准则公式中包含了在此查询编译时尚不知其值的一些参数，当执行参数查询时，只能由用户提供这些参数的值，在这种情况下，编译时准备好带有参数的限定语，运行时可以使用不同的参数值重复执行，由于参数值的不同，每次执行完后将送回不同的执行结果。6.4.1 参数性查询的化简和代数的扩充例：Q9：查部门号为为任意给定的 $X或 $Y 的部门信息。显然对DEPTNUM上的选择查询是参数性的： Q9：SLDEPTNUM=$X OR DEPTNUM=$YSUPPLY运行时由发出此查询的程序来给参数 $X 和 $Y 赋以实际的值。参数性查询化简可以在编译时完成一部分，另一部分需要在运行时完成。参数性查询的化简涉及了限定关系代数的应用，以便决定子表达式的限定语是否为永假式。上例中，假设在发出此查询时，参数值为：X = 1 和 Y= 13。于是，由于选择公式“DEPTNUM=1 OR DEPTNUM = 13”与它的限定语矛盾，因此有可能在运行时化简DEPT3的直树，我们期望大部分的优化工作在编译时进行，尤其是对经常被激活的参数性查询。 SLDEPTNUM=$X OR DEPTNUM=$YUN DEPT1： DEPT2： DEPT3： DEPTNUM10 10 20 （a） 查询Q9的规范形式 CUT $X10 $X20 OR OR $Y10 $Y20 ($X10 AND $X20 OR $Y10 AND $Y20SLDEPTNUM=$X OR DEPTNUM=$Y SLDEPTNUM=$X OR DEPTNUM=$YSLDEPTNUM=$XOR DEPTNUM=$YDEPT1： DEPT2： DEPT3：DEPTNUM10 10 20 （b） 带有CUT操作的 查询树 图6.12 参数性查询中CUT的使用为了表示在算符树上存在用于运行时化简的测试，用一新的n元算符称作剪枝（CUT）来替代结合算符，该新算符只对其几个操作数执行结合。每个公式在编译时准备好而在运行时求值，若送回的结果为真，则其相应的操作数就包含在此结合操作中，如果计算结果为假值，则相应的操作数就从树中消去。图6.12（b）表示了这个参数性查询的新算符树，在该例中，应用准则2把选择操作推至结合操作的下面，然后用CUT操作取代该结合操作，CUT操作用到的三个公式（对应结合操作的每个操作数）是： F1：$X 10 OR $Y 10 F2：（$X 10 AND $X 20）OR ($Y 10 AND $X 20) F3：$X 20 OR $Y 20F