《语法树学习笔记——数据库实现原理》由会员分享，可在线阅读，更多相关《语法树学习笔记——数据库实现原理（6页珍藏版）》请在金锄头文库上搜索。
1、语法树学习笔记语法树学习笔记数据库实现原理数据库实现原理5.2 写 sql 语句-画语法树-逻辑查询计划-简单优化（选择、投影）5.2.1 写 sql 语句 这部分不是在这儿学的，简单说说吧，高手略过，挑毛病也可： 举例：查询生于 1960 年的影星的名字： SELECT name FROM MovieStar WHERE birthdate LIKE %1960; Select 是查询语句开头的关键字，永远不变，记住即可（别写错单词就行） 后面跟着的是一个或多个属性名（在数据库中叫字段名） ，此处是影星数据库表 的一个字段“name”,存储的是影星的名字。注意：如果这里有多个属性名，请 用逗
2、号“,”分隔开 From 也是关键字，后面跟着的是数据库表名，就是关系名(R)，也可以有多个， 用逗号分隔 Where 查询是条件部分，后面跟着的是查询条件表达式，由属性名、值、运算 或比较符号等组成。 这个例子的查询条件是：生日（birthdate）属性值为以 1960 结尾的那些 记录， “%”是通配符（通配所有长度的字符串， “_”只通配长度为 1 的字符串） ， 注意：用通配符时一定要用 Like 关键字哦。如果字段是日期类型的，快看 SQL 的书吧，要对准格式的！ 5.2.2 画语法树 先看语法树中要用到的语法：语法类,和(或Pattern)比较特殊， 因为它们不是通过语法 规则定
3、义的，而是通过它们所代表的原子的规则来定义的。 Attr的子女必须是符合数据库模式中属性名的字符串 Rel的子女必须是符合数据库模式中关系名的字符串 Value(或Pattern)必须是符合SQL语法的字符串或数值 看个例子吧： 假设一个数据库中存储着学生和系院两个表如下：我们想要查询到所有具有四年级学生的系院的名称： Select DeptName from Department,Student where Student.Major= Department.Code And Student.Year=4 就是让 Student 和 Department 两个表通过“专业”Major 进行等
4、值连接 (join),并限定只返回 Student 中有四年级的那些记录语法树如下：这里只要注意语法名称和画法即可。 注意：1、在 FromList 中的属性名用 Rel 表示，不要用 Attr，2、如果FromList 中有两个以上的关系（表）名，则请在第二个以后的的上层加 入一个！ 3、条件中如果有多个条件，请将每个条件用多级分层， 直到最后细化到,对应的具体属性名称或值为止。 5.2.3 逻辑查询计划树 从语法分析树到逻辑查询计划树，看一个简单的情况的图例：转换成关系代数的方法： 直接将所有“简单的”select-from-where结构转换成关系代数，具体地： 如果有一个属于“SFW”
5、成份的query，并且该成份中的没有 子查询，则我们可以用一个关系代数表达式来替换整个成份select列表、 from列表以及条件，其中代数表达式自底向上由以下内容组成： 中提及的全部关系的积是以下操作符的参数： 选择C，其中C就是要被替换成份中的“condition”表达式的参数，同时选择又是下面操作符的参数 投影L，其中 L 是”SelList”中的属性列表。看下面的图例琢磨琢磨：如果涉及到嵌套查询，那么有关如何从条件中去除子查询的部分大家就到 网上查找吧，如果知道了原理也不难，这里就不研究了，汗 5.2.4 启发式优化 启发式优化的原则： 尽可能地将选择条件下推，尽早执行选择，使得过滤后
6、的中间结果尽可能地 小； 用连接（join）替换笛卡尔积 尽可能下推投影，在适当的位置增加投影操作 利用 pipeline，减少查询计划的执行时间 看图例吧：呵呵，上图不需要优化，按照启发式优化的原则，已经是最优了。这个需要优化: 1、用 join 替换了笛卡尔积和选择的组合，注意替换的细节，选择的条件成为 了 join 的条件， 2、 下推了投影，因为下面 from 列表中的 Department 是可以提前进行投影的 （可以减少结果集） ，不过注意要将 code 一起投影下来，因为在上层进行 join 时是需要 code 这个属性的，否则将 join 不出任何结果，这个很重要，一定要 记住！再看一个例子：注意：这个例子比上图多了一个下推了选择，下推选择时要注意，因为只有 Student 有 Year(学年)的属性，所以，只能下推到 Student 那里，而且因为 Department 中没有 Year 属性，所以 Join 时不需要这个条件！ 也就是因为以上两个原因才可以进行优化，最后显示了优化前和优化后的结果， 虽然优化后表达式复杂了，但是效率肯定是大大提高了！嵌套查询比较麻烦，但是如果弄懂了上面的原理，也是可以迎刃而解滴！By lzq2000 2011-11-3
