语法树学习笔记——数据库实现原理

语法树学习笔记数据库实现原理52写SQL语句画语法树逻辑查询计划简单优化（选择、投影）521写SQL语句这部分不是在这儿学的，简单说说吧，高手略过，挑毛病也可举例查询生于1960年的影星的名字SELECTNAMEFROMMOVIESTARWHEREBIRTHDATELIKE1960SELECT是查询语句开头的关键字，永远不变，记住即可（别写错单词就行）后面跟着的是一个或多个属性名（在数据库中叫字段名），此处是影星数据库表的一个字段“NAME”,存储的是影星的名字。注意如果这里有多个属性名，请用逗号“,”分隔开FROM也是关键字，后面跟着的是数据库表名，就是关系名R，也可以有多个，用逗号分隔WHERE查询是条件部分，后面跟着的是查询条件表达式，由属性名、值、运算或比较符号等组成。这个例子的查询条件是生日（BIRTHDATE）属性值为以1960结尾的那些记录，“”是通配符（通配所有长度的字符串，“_”只通配长度为1的字符串），注意用通配符时一定要用LIKE关键字哦。如果字段是日期类型的，快看SQL的书吧，要对准格式的522画语法树先看语法树中要用到的语法语法类,和或PATTERN比较特殊，因为它们不是通过语法规则定义的，而是通过它们所代表的原子的规则来定义的。ATTR的子女必须是符合数据库模式中属性名的字符串REL的子女必须是符合数据库模式中关系名的字符串VALUE或PATTERN必须是符合SQL语法的字符串或数值看个例子吧假设一个数据库中存储着学生和系院两个表如下我们想要查询到所有具有四年级学生的系院的名称SELECTDEPTNAMEFROMDEPARTMENT,STUDENTWHERESTUDENTMAJORDEPARTMENTCODEANDSTUDENTYEAR4就是让STUDENT和DEPARTMENT两个表通过“专业”MAJOR进行等值连接JOIN,并限定只返回STUDENT中有四年级的那些记录语法树如下这里只要注意语法名称和画法即可。注意1、在FROMLIST中的属性名用REL表示，不要用ATTR，2、如果FROMLIST中有两个以上的关系（表）名，则请在第二个以后的的上层加入一个3、条件中如果有多个条件，请将每个条件用多级分层，直到最后细化到,对应的具体属性名称或值为止。523逻辑查询计划树从语法分析树到逻辑查询计划树，看一个简单的情况的图例转换成关系代数的方法直接将所有“简单的”SELECTFROMWHERE结构转换成关系代数，具体地如果有一个属于“SFW”成份的QUERY，并且该成份中的没有子查询，则我们可以用一个关系代数表达式来替换整个成份SELECT列表、FROM列表以及条件，其中代数表达式自底向上由以下内容组成中提及的全部关系的积是以下操作符的参数选择C，其中C就是要被替换成份中的“CONDITION”表达式的参数，同时选择又是下面操作符的参数投影L，其中L是”SELLIST”中的属性列表。看下面的图例琢磨琢磨如果涉及到嵌套查询，那么有关如何从条件中去除子查询的部分大家就到网上查找吧，如果知道了原理也不难，这里就不研究了，汗524启发式优化启发式优化的原则尽可能地将选择条件下推，尽早执行选择，使得过滤后的中间结果尽可能地小；用连接（JOIN）替换笛卡尔积尽可能下推投影，在适当的位置增加投影操作利用PIPELINE，减少查询计划的执行时间看图例吧呵呵，上图不需要优化，按照启发式优化的原则，已经是最优了。这个需要优化1、用JOIN替换了笛卡尔积和选择的组合，注意替换的细节，选择的条件成为了JOIN的条件，2、下推了投影，因为下面FROM列表中的DEPARTMENT是可以提前进行投影的（可以减少结果集），不过注意要将CODE一起投影下来，因为在上层进行JOIN时是需要CODE这个属性的，否则将JOIN不出任何结果，这个很重要，一定要记住再看一个例子注意这个例子比上图多了一个下推了选择，下推选择时要注意，因为只有STUDENT有YEAR学年的属性，所以，只能下推到STUDENT那里，而且因为DEPARTMENT中没有YEAR属性，所以JOIN时不需要这个条件也就是因为以上两个原因才可以进