数据库原理_精品-第4章关系系统及查询优化课案.ppt

* 数据库系统 * 四、关系代数表达式的优化 1、语法树 用来表示关系代数表达式的一棵树，其内结点表示一种运算，叶结点表示一个关系。例： SELECT S.SN FROM S, SC WHERE S.S# = SC.S# AND SC.C# = ‘C2’; 可转化为如下关系运算： Project (SN) (Restrict (SC.C#=‘C2’) (Join (S.S#=SC.S#) (S，SC) ) ) Project (SN) Restrict（SC.C#=‘C2’） Join（S.S#=SC.S#） S SC 语法树 * 数据库系统 * 为简化优化算法，可将关系代数运算限制在“并、差、笛卡尔积、投影、选择”五种基本运算上。 Project (SN) Restrict（SC.C#=‘C2’） Join（S.S#=SC.S#） S SC 规范化为 ?SN ?SC.C#=‘C2’ ?S.S#=SC.S# ? S SC * 数据库系统 * 2、关系代数表达式的优化算法 输入：一棵关系代数表达式的语法树 输出：计算该表达式的程序 利用选择的串接定律，把形如 ? （E）的式子变换为 F1?F2???Fn ? （? （?（? （E）?）） F1 F2 Fn 对每一个选择，利用“选择的串接定律、选择和投影的交换律、选择对笛卡尔积的分配律、选择对并的分配律、选择对差的分配律”尽可能把它移到树的叶端 （1）分解选择 （2）选择下移 * 数据库系统 * 对每一个投影，利用“投影的串接定律、选择和投影的交换律、投影对笛卡尔积的分配律、投影对并的分配律”尽可能把它移到树的叶端 （3）投影下移 利用“投影的串接定律、选择的串接定律、选择和投影的交换律”把选择和投影合并成单个选择、单个投影、或选择后跟投影等三种情况，使多个选择和 / 或投影能同时执行、或在一次扫描中完成 （4）选择、投影合并 * 数据库系统 * 把上面得到的语法树分组： 每个二元运算和它的 一元直接祖先 为一组。若它的后代直到叶子全是一元运算，则也将它们并入该组。 按照每组的求值应在其后代组求值之后进行的顺序为每组生成一个程序，以产生整个表达式的求值程序。 （5）按点分组（每组只有一个二元运算） （6）生成程序 不超过别的 二元运算结点 但对于笛卡尔积，若后面（父结点）是不能与它结合为等值连接的选择运算时，其一直到叶子的一元运算结点需单独算一组。 * 数据库系统 * 例子：考虑由以下关系组成的图书馆数据库 BOOKS（TITLE，AUTHOR，PNAME，LC-NO） BORROWERS（NAME，ADDR，CITY，CARD-NO） LOANS（CARD-NO，LC-NO，DATE） 借书证号 图书编号 查询：找出2000年01月01日前借出书籍的书名和借书人姓名。 借出日期 用SQL 语言可如下表达： SELECT TITLE，NAME FROM BOOKS，BORROWERS，LOANS WHERE BOOKS.LC-NO=LOANS.LC-NO AND BORROWERS.CARD-NO=LOANS.CARD-NO AND DATE {2000-01-01}; * 数据库系统 * SELECT TITLE，NAME FROM BOOKS，BORROWERS，LOANS WHERE BOOKS.LC-NO=LOANS.LC-NO AND BORROWERS.CARD-NO=LOANS.CARD-NO AND DATE {2000-01-01}; 把上述SQL语句转化为关系代数表达式： 转化为投影 转化为连接 转化为选择 ? （ TITLE，NAME DATE{2000-01-01} ? （ BOOKS （ BORROWERS LOANS））） * 数据库系统 * 若把连接用笛卡尔积来实现，上式变为： DATE{2000-01-01} ? （ （ BOOKS ?（ BORROWERS ? LOANS））））） ? BOOKS.LC-NO=LOANS.LC-NO AND BORROWERS.CARD-NO=LOANS.CA