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

《第六章-全局查询到段查询的变换》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章全局查询到段查询的变换一般说来，把对全局关系的查询（称为全局查询）变换为段的查询（称为段的查询），有几种不同的方法，采用某些规则就可把一个全局查询表达式重新写成一种等价的段查询表达式。6.1查询的算符树及其等价变换例：S(学号,姓名,年令,性别,系号，奖学金,班长学号，民族)C(课号,课名,学时,任课教师)SC(学号,课号,成绩)D(系号，系名，系主任)查询：学生‘刘建‘所学课号及成绩SELECT课号，成绩FROMS，SCWHERES.学号=SC.学号ANDS.姓名=‘刘建‘；以上是用SQL完成的查询（语义），在内部实现上，同一个语义可有多种不同方式。对上面的查询，系统可

2、用下面三种方式来实现：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的算符树的一个例子，其中树叶是全局关系，而每个节点表示了一个一元或二元的操作。在本例中，先

3、执行结合操作，再执行选择和投影操作。16图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分别表示一元代数运算符和二元代数运算符，我们有：l一元运算的交换律（commutativity）：U1U2RU2U1Rl二元运算的操作数的交换律RBSSBRl二元运算的结合律

4、（associativity）：RB（SBT）（RBS）BTl一远运算的幂等（idempotence）：URU1U2Rl一元运算相对于二元运算的分配律（distributivity）：U(RBS）U(R）BU(S）l一元运算的因子分解（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ºA

5、2表6.2二元运算的结合律及操作数的交换律UNDFCPJNFSJFR*SYNYYNS*R（R*S)*TYNYSNG1NR*(S*T)SNG1：for（RJNF1S）JNF2TRJNF1（SJNF2T）：Attr（F2）Attr（S）UAttr（T）：？？？16表6.3一元运算的幂等PJA（R）PJA1PJA2（R）SNG：AºA1，AA2SLF（R）SLF1SLF2（R）SNG：F=F1ÙF26.4、6.5见教材。在非分布式数据库中，为了优化查询的执行，给出了一些相关的等价变换的一般准则：准则1使用选择和投影的幂等来为每个操作数关系产生相应的选择和投影。准则2把树中的选择和投影

6、运算尽可能的向下推移。图6.2查询Q1的修改后的算符树（见教材80页）图6.2就是经过运用准则1和准则2变换之后的算符树。6.2把全局查询变换成段查询6.2.1段查询的规范表达式段查询的规范表达式：已知在全局模式上的一个代数表达式，只要对其中出现的每个全局关系名代入由段重构全局关系的代数表达式，就得到了规范表达式。采用同样的方法可以把全局模式上的算符树映射成分段模式上的算符树。16(a)查询Q1的规范形式（用段重构代替全局关系名）（P83）(b)把算符树中的选择和投影向下推移（准则2）图6.3查询Q1算符树的进一步变换（P83）6.2.2限定关系代数学限定关系：是一种带有限定语

7、的关系，限定语确定了限定关系中所有元组的共同内涵特性，并表示为：[R：qR]，这个整体为限定关系。其中，R是一个关系，称为此限定关系的实体，qR是一谓语，称为此限定关系的限定语。这里不要求对关系的元组求出关系的限定语的值，但若可求值，则其值必为真。水平分段是限定关系的典型例子，限定语相应于分段谓语。例如：对于SUPPLIER1，可写成限定形式：[SUPPLIER1：CITY=“SF“]对于DEPT1，可写成限定形式：[DEPT1：DEPTNUM<10]这意味着SUPPLIER1中每一元组对于