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

1第六章全局查询到段查询的变换一般说来，把对全局关系的查询（称为全局查询）变换为段的查询（称为段的查询），有几种不同的方法，采用某些规则就可把一个全局查询表达式重新写成一种等价的段查询表达式。6.1查询的算符树及其等价变换例：S(学号,姓名,年令,性别,系号，奖学金,班长学号，民族)C(课号,课名,学时,任课教师)SC(学号,课号,成绩)D(系号，系名，系主任)查询：学生‘刘建‘所学课号及成绩SELECT课号，成绩FROMS，SCWHERES.学号=SC.学号ANDS.姓名=‘刘建‘；以上是用SQL完成的查询（语义），在内部实现上，同一个语义可有多种不同方式。对上面的查询，系统可用下面三种方式来实现：T1=PJ课号,成绩(SLS.学号=SC.学号∧S.姓名=‘刘建‘（SCPSC））T2=PJ课号,成绩(SL姓名=‘刘建‘（SNJNSC））T3=PJ课号,成绩（（SL姓名=‘刘建‘S）NJNSC）分析上式，T1、T2、T3是等价的，但T3优于T2，T2优于T1。怎样才能写出优化的表达式呢?这就要相应有些准则。引入查询的算符树的概念,并利用准则，通过对算符树进行等价变换达到优化目的。6.1.1查询的算符树Q1：查询对北部地区的各个部门供货的供应商号。图6.1是查询Q1的算符树的一个例子，其中树叶是全局关系，而每个节点表示了一个一元或二元的操作。在本例中，先执行结合操作，再执行选择和投影操作。PJSNUMSLAREA=“NORTH“JNDEPTNUM=DEPTNUMSUPPLYDEPT2图6.1查询Q1的一种算符树我们可以把关系代数表达式的算符树看作是表达式本身的语法分析树，语法规则（产生式）。R标识符R（R）RUN—OPRRRBIN—OPRUN—OPSLF∣PJABIN—OPCP∣UN∣DF∣JNF∣NJN∣IN∣SJF∣NSJ上述的R可以是算符树的叶节点，运算符是枝节点，可通过对算符树进行等价变换达到优化目的。6.1.2关系代数的等价变换令U和B分别表示一元代数运算符和二元代数运算符，我们有：一元运算的交换律（commutativity）：U1U2RU2U1R二元运算的操作数的交换律RBSSBR二元运算的结合律（associativity）：RB（SBT）（RBS）BT一远运算的幂等（idempotence）：URU1U2R一元运算相对于二元运算的分配律（distributivity）：U(RBS）U(R）BU(S）一元运算的因子分解（factorization），（这种变换正好与分配律相反）：U(R）BU(S）U(RBS）下面讨论对于上述各条的具体可行的情况。（见表6.1----表6.5）表6.1一元运算的交换律SLF2PJA2SLF1（*（R））YY*（SLF1（R））PJA1（*（R））SNG1SNG2*（PJA1（R））SNG1：Attr（F2）A1；SNG2：A1A2表6.2二元运算的结合律及操作数的交换律UNDFCPJNFSJFR*SYNYYNS*R（R*S)*TYNYSNG1NR*(S*T)SNG1：for（RJNF1S）JNF2TRJNF1（SJNF2T）：Attr（F2）Attr（S）UAttr（T）：？？？3表6.3一元运算的幂等PJA（R）PJA1PJA2（R）SNG：AA1，AA2SLF（R）SLF1SLF2（R）SNG：F=F1F26.4、6.5见教材。在非分布式数据库中，为了优化查询的执行，给出了一些相关的等价变换的一般准则：准则1使用选择和投影的幂等来为每个操作数关系产生相应的选择和投影。准则2把树中的选择和投影运算尽可能的向下推移。PJSNUMJNDEPTNUM=DEPTNUMPJSNUM.DEPTNUMPJDEPTNUMSUPPLYSLAREA=“NORTH“DEPT图6.2查询Q1的修改后的算符树（见教材80页）图6.2就是经过运用准则1和准则2变换之后的算符树。6.2把全局查询变换成段查询6.2.1段查询的规范表达式段查询的规范表达式：已知在全局模式上的一个代数表达式，只要对其中出现的每个全局关系名代入由段重构全局关系的代数表达式，就得到了规范表达式。采用同样的方法可以把全局模式上的算符树映射成分段模式上的算符树。PJSNUMJNDEPTNUM=DEPTNUMPJSNUM.DEPTNUMPJDEPTNUMUNSLAREA=“NORTH“UNSUPPLY1SUPPLY2：DEPT1DEPT2DEPT34(a)查询Q1的规范形式（用段重构代替全局关系名）（P83）PJSNUMJNDEPTNUM=DEPTNUMPJSNUM.DEPTNUMPJSNUM.DEPTNUMUNSLAREA=“NORTH“UNSUPPLY1SUPPLY2：DEPT1DEPT2DEPT3PJSNUM.DEPTNUMPJSNUM.DEPTNUMPJSNUM.DEPTNUMSLAREA=“NORTH“SLAREA=“NORTH“(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中所有元组的共同内涵特性。同理，DEPTNUM10是DEPT1中所有元组的共同内涵特性。更值得注意的是导出式水平分段，各段的限定语涉及多个非同类关系中的属性。例如：SUPPLY1，可写成限定形式：[SUPPLY1：SNUM=SUPPLIER.SNUMANDSUPPLER.CITY=“SF“]这里,仅局限于SUPPLY1而言,它的元组对限定语是不能求值的,但每个元组都有限定语所表达的共同内涵特性。限定关系的代数学是关系代数的一种扩充，，其中使用限定关系作为操作数，这种代数除了对关系进行操作以外，还要对限定语进行操作。限定关系代数学也有相应的运算规则，这些规则实际上是关系代数的推广。其运算规则为：规则1：SLF[R：qR][SLFR:FANDqR]证：若元组t∈SLF[R:qR]，则t∈R,且t必使F为真，t也必须使qR为真。∴SLF[R：qR]的限定形式为：[SLFR：FANDqR]5例：SUPPLIER1=SLCITY=“SF“（SUPPLIER）则可知有限定关系：[SUPPLIER1：CITY=“SF“]SLSNUM=20[SUPPLIER1：CITY=“SF“]可写成[SLSNUM=20SUPPLIER1：SNUM=20ANDCITY=“SF“]规则2：PJA[R：qR][PJAR：qR]A可以包含、也可以不包含限定语qR中的属性，但都不会影响PJAR的内涵特性，这可由限定关系的定义及其进一步说明加以解释。例1：PJDEPTNUM，NAME[DEPT1：DEPTNUM≤10]==[PJDEPTNUM，NAMEDEPT1：DEPTNUM≤10]例2：PJAREA，MGRNUM[DEPT1：DEPTNUM≤10]==[PJAREA，MGRNUMDEPT1：DEPTNUM≤10]规则3：[R：qR]CP[S：qS][RCPS：qRANDqS]注意：这里是把两个限定语应用到RCPS的不相交属性上。证：令t1∈R，则t1具有内涵特性qR，t2∈S，则t2具有内涵特性qS，并由乘法定义知，元组t1，t2∈RCPS且它必具有内涵特性qRANDqS。例：S（学号，系，性别）S1=SL系=“计算机“（S）[S1：系=“计算机“]C（课程，专业，学分）C1=SL专业=“软件与理论“（S）[C1：专业=“软件与理论“][S1：系=“计算机“]CP[C1：专业=“软件与理论“][S1CPC1：系=“计算机“AND专业=“软件与理论“]注意：两限定语不相交的属性。规则4：[R：qR]DF[S：qS][RDFS：qR]∵（RDFS）R但（RDFS）S∴有[RDFS：qR]注意事项：RINS=RDF（RDFS）=SDF（SDFR）即交集运算具有可交换性，即RINS=SINR如果应用扩充代数学的定义，将会出现[R：qR]IN[S：qS][R：qR]DF（[R：qR]DF[S：qS]）[R：qR]DF[RDFS：qR][RDF（RDFS）：qR][RINS：qR]（1）而[S：qS]IN[R：qR][S：qS]DF[S：qS]DF[R：qR][S：qS]DF[SDFR：qS][SDF（SDFR）：qS][SINR：qS]（2）事实上，我们想得到的结果是：[RINS：qRANDqS]证：设t∈RINS,则t∈R且t∈S∴t具有特性qR且具有特性qS。规则5：[R：qR]UN[S：qS][RUNS：qRORqS]6这是显然的。以上是把关系代数的五种基本运算推广到限定关系的运算中，下面是关系代数复合运算的推广。规则6：[R：qR]JNF[S：qS][RJNFS：qRANDqSANDF]证：[R：qR]JNF[S：qS]SLF（[R：qR]CP[S：qS]）SLF（[RCPS：qRANDqS]）[SLF（RCPS）：（qRANDqS）ANDF][RJNFS：qRANDqSANDF]规则7：[R：qR]SJF[S：qS][RSJFS：qRANDqSANDF]证：[R：qR]SJF[S：qS]PJATTR（R）（[R：qR]JNF[S：qS]）PJATTR（R）[RJNFS：qRANDqSANDF]（由规则6）[PJATTR（R）（RJNFS）：qRANDqSANDF]（由规则2）[RSJFS：qRANDqSANDF]（由半结合定义）运用规则1,就可把图6.3(b)的最右分支剪掉，因DEPT3中没有北部地区。关系代数表达式可以进行很多种有条件和无条件的等价变换，限定关系代数表达式也可进行同样的变换。例：SLCITY=“LA“[SUPPLIER1：CITY=”SF“][SLCITY=“LA“SUPPLIER1：CITY=”SF”ANDCITY=”LA”]ø（限定语为永假）通过识别空关系的过程可大大简化查询树，运用规则1,可把图6.3(b)最右分支剪掉，因DEPT3中没有北部地区。针对限定关系的代数运算，可考虑如下几个优化的新准则：准则3把选择向下推到树叶处，然后对它们使用限定关系的代数运算：如果结果的限定语是永假式，则用空关系来代替此选择的结果。准则4利用限定关系的代数运算来求结合的操作数的限定语之值；如果这个结合的结果的限定语是永假式，则用空关系来代替此子树（包括此结合及它的操作数在内）。6.2.3水平分段关系的化简例Q3：查阅部门号为1的部门名、地区及经理号。对全局关系DEPT进行操作：SLDEPTNUM=1DEPT现将这一全局查询变换到段查询（查询的规范化格式）SLDEPTNUM=1SLDEPTNUM=1UN[DEPT1:DEPTNUM≤10][DEPT1:[DEPT2[DEPT3DEPTNUM≤10]10DEPTNUM≤20]DEPTNUM20]7(a)查询Q3的规范形式（b）查询Q3的化简图6.5水平分段关系的化简再如：运用限定关系的运算规则1和优化准则3,可把图6.3(b)最右分支剪掉，因DEPT3可写成限定形式[DEPT3：DEPTNUM20]，限定语表明DEPT3中的元组都是南部地区（没有北部地区）的部门，AREA=NORTH意味NOT（DEPTNUM20）。6.2.4水平分段关系