精华内容
下载资源
问答
  • 关系代数优化(语法树优化

    千次阅读 多人点赞 2020-05-07 19:53:40
    数据库 – 关系代数优化 关系代数优化是指通过对关系代数表达式的等价变换操作来提高数据库的查询效率。 关系代数有5大基本操作:包括并( Union,U ),差 (Difference , - ),笛卡尔积( X ),投影( project,∏),...

    数据库 – 关系代数优化(语法树优化)

    关系代数优化是指通过对关系代数表达式的等价变换操作来提高数据库的查询效率。

    关系代数有5大基本操作:包括并( Union,U ),差 (Difference , - ),笛卡尔积( X ),投影( project,∏),选择( select , σ )。
    其他操作:交(Intersection , ∩ ),连接( ⋈ ),除( ÷ );

    代数优化遵循的原则是:先做选择,运用投影去除多余属性等等。
    优化算法:语法树(尽量提前做选择操作;在每个操作后,应做个投影操作,去掉不用的属性值)。

    一,在优化过程中使用到的等价变换规则如下

    1. 连接,笛卡尔积的交换律
    设E1和E2是关系代数表达式,F是连接运算的条件
    在这里插入图片描述

    2. 连接,笛卡尔积的结合
    在这里插入图片描述

    3. 投影的串接定律
    A1…An,B1…Bn为表的属性。
    在这里插入图片描述

    4. 选择的串接定律
    在这里插入图片描述

    5. 选择与投影的交换
    在这里插入图片描述

    6. 选择与笛卡尔积的交换
    在这里插入图片描述
    7.选择与并的交换
    在这里插入图片描述
    8.选择与差的交换
    在这里插入图片描述
    9. 投影与笛卡尔积的交换
    在这里插入图片描述
    10.投影与并的交换
    在这里插入图片描述

    二,关系代数表达式优化步骤

    1、构造查询树
    第一步:把用高级语言定义的查询转换为关系代数表达式
    ★ 以 SELECT子向对应投影操作,以FROM字向对应笛卡尔积以 WHERE子句对应选择操作,生成原始查询树
    ★ SQL语句转化为原始查询树
    第二步:把关系代数表达式转换为查询树。

    注: 查询树是一种表示关系代数表达式的树形结构。在一个查询树中,叶子结点表示关系,内结点表示关系代数操作。查询树以自底向上的方式执行:当一个内结点的操作分量可用时,这个内结点所表示的操作启动执行,执行结束后用结果关系代替这个内结点。

    2、利用等价转换规则反复地对查询表达式进行尝试性转换,将原始的语法树转換成“优化”的形式
    <1> 对每一个选择,利用等价变换规则4~9尽可能把它移到树的叶端。目的是使选择操作尽早执行
    <2> 对每一个投影利用等价变换规则3,9等的一般形式尽可能把它移向树的叶端。目的是使投影操作尽早执行
    <3> 对每个叶节点加必要的投影操作,以消除对查询无用的属性。
    <4> 如果笛卡尔乘积后还须按连接条件进行选择操作,可将两者组合成连接操作
    选择下沉,投影随后

    ---------------------------------------------------------------------------------------------------------------------------
    应用举例
    从数据库中找出选修了课程名为“IS”的学生姓名
    Select Cname
    From Student, Course, SC
    WHERE Student.Sno = SC.Sno AND SC.Cno = Course.Cno AND Student.Sdept =’IS’;

    1.构造查询树
    查询语句转关系代数表达式为:∏Cname(σStudent.Sdept=’IS’(Student ⋈ Course ⋈ SC))
    在这里插入图片描述
    2.利用等价代换原则进行优化
    (1)
    在这里插入图片描述
    (2)
    在这里插入图片描述
    (3)
    在这里插入图片描述
    优化完毕。

    展开全文
  • 查询优化一般算法和语法树,对提高关系运算的理解有很大帮助!
  • 前言:本篇主要讲解怎么画查询语法树并对其优化,因为我在之前学的时候,在网上其实没怎么找到详细地教程,还是自己一点一点扣书扣出来的,所以想写一篇具体来描述一下这类题的方法技巧。 如题,这是东华大学一年的...

    前言:本篇主要讲解怎么画查询语法树并对其优化,因为我在之前学的时候,在网上其实没怎么找到详细地教程,还是自己一点一点扣书扣出来的,所以想写一篇具体来描述一下这类题的方法技巧。

    如题,这是东华大学一年的考研题目:

    我们来解决第二问的前提是先写出它的关系表达式:

    这一步没什么技巧,学过关系代数就很简单,我们主要讲解如何画查询语法树:

    第一步:转化关系表达式:就是将原来的三个表的自然连接转成笛卡尔积形式,在中间再加一个投影和选择即可;L就是指笛卡尔积里的所有属性,选择就是将这三个表连接起来的相同的属性,也比较简单,对照写出来即可;

    第二步:画出原始的优化树,这个画出来很简单,就是把刚刚转化的关系表达式化成这样的形式:

    最重要的第三步!优化!书上写的原则有很多,但其实只要记住该在哪投影,哪选择即可:

    我先把图贴出来:

    首先先看最上边,就是先写一个投影一个选择,投影投的就是咱们最后要的什么,选择就是右子树和左子树最后的连接,我们看右子树是Bike,那上面的选择操作一定就是

    这样我们上面的树就写好了。

    然后我们来到右子树,如果我们的条件是有在Bike里体现的,那一定就是加上Π和,如果我们没有这方面的条件,那就只加一个Π就行,而很明显,在Bike里我们是有条件的,所以就搞成:

    这样即可,就是我要用Bname来筛选出来,但我最后只要Bid就行了;下面的都是这个意思:

     

    这也是同理,我们要清楚的就是,条件是什么,我最后要什么就够了,这就是优化过程;

    要注意一点的是这一点:

    这一步要判断好,这一步输出的可就直接给上边的树了,要确认好上面的树需要什么;

     

    然后就结束啦!其实很简单的,主要是分清条件是什么,每一步只需要什么。

     

     

    展开全文
  • AST抽象语法树

    千次阅读 2018-07-20 23:27:29
    解析(PARSE):将代码字符串解析成抽象语法树。  2.转换(TRANSFORM):对抽象语法树进行转换操作。  3.生成(GENERATE): 根据变换后的抽象语法树再生成代码字符串。 看到上面,我们不仅纳闷了,这不是什么都没做...

    如图所示,AST主要作用有三步:

        1.解析(PARSE):将代码字符串解析成抽象语法树。

        2.转换(TRANSFORM):对抽象语法树进行转换操作。

        3.生成(GENERATE): 根据变换后的抽象语法树再生成代码字符串。

    看到上面,我们不仅纳闷了,这不是什么都没做吗。我们知道javascript程序一般是由一系列的字符组成的,每一个字符都有一些含义,比如我们可以使用匹配的字符([], {}, ()), 或一些其他成对的字符('', "")和代码缩进让程序解析更加简单,但是对计算机并不适用,这些字符在内存中仅仅是个数值,但是计算机并不知道一个程序内部有多少个变量这些高级问题,
    这个时候我们需要寻找一些能让计算机理解的方式,这个时候,抽象语法树诞生了。

    我们通过上面知道,Babel的工作的第一步是 解析操作,将代码字符串解析成抽象语法树,那么抽象语法树就是在解析过程中产生的。其实解析又可以分成两个步骤:
                   1.: 将整个代码字符串分割成 语法单元数组。
                   2.:在分词结果的基础之上分析 语法单元之间的关系。

    那么JS代码中有哪些语法单元呢?大致有下面这些:
                  1. 空白。JS中连续的空格,换行,缩进等这些如果不在字符串里面,就没有任何实际的意义,因此我们可以将连续的空白组合在一起作为一个语法单元。
                  2. 注释。行注释或块注释,对于编写人或维护人注释是有意义的,但是对于计算机来说知道这是个注释就可以了,并不关心注释的含义,因此我们可以将注释理解为一个不可拆分的语法单元。
                  3. 字符串。对计算机而言,字符串的内容会参与计算或显示,因此有可以为一个语法单元。
                  4. 数字。JS中有16,10,8进制以及科学表达式等语法,因此数字也可以理解一个语法单元。
                5. 标识符。没有被引号括起来的连续字符,可包含字母 _, $ 及数字,或 true, false等这些内置常量,或 if,return,function等这些关键字。
                  6. 运算符: +, -, *, /, >, < 等。
                  7,还有一些其他的,比如括号,中括号,大括号,分号,冒号,点等等。

    是不是又有点晕,上图片:

     我们可以发现,程序代码本身可以被映射成为一棵语法树,而通过操纵语法树,我们能够精准的获得程序代码中的某个节点。例如声明语句,赋值语句,而这是用正则表达式所不能准确体现的地方。JavaScript的语法解析器Espsrima提供了一个在线解析的工具,你可以借助于这个工具,将JavaScript代码解析为一个JSON文件表示的树状结构。 

    AST的作用非常多,比如编译器,IDE,压缩优化代码等;再javascript中,虽然我们不会跟AST打交道,却会经常用到它。

     

     

     

     

    展开全文
  • AST 抽象语法树学习

    万次阅读 2017-05-20 21:01:09
    阅读原文Abstract Syntax Tree 抽象语法树简介在使用前端许多工具插件的时候,我们大多知道每个工具库、每个插件能做什么,不过很多同学其实并不清楚背后用到的技术,如webpack、rollup、UglifyJS、Lint等很多的工具...

    阅读原文

    Abstract Syntax Tree 抽象语法树简介

    在使用前端许多工具插件的时候,我们大多知道每个工具库、每个插件能做什么,不过很多同学其实并不清楚背后用到的技术,如webpack、rollup、UglifyJS、Lint等很多的工具和库的核心都是通过Abstract Syntax Tree 抽象语法树这个概念来实现对代码的检查、分析等操作的。通过了解抽象语法树这个概念,你也可以随手编写类似的工具,发现一个新的世界。

    Abstract Syntax Tree 抽象语法树定义

    理论的知识总是有些枯燥乏味,不过客官别急,一步一步来。

    其实这些工具的原理都是通过JavaScript Parser把代码转化为一颗抽象语法树(AST),这颗树定义了代码的结构,通过操纵这颗树,我们可以精准的定位到声明语句、赋值语句、运算语句等等,实现对代码的分析、优化、变更等操作。

    这里写图片描述

    wikipedia定义:

    In computer science, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language.

    翻译为:

    在计算机科学中,抽象语法树(abstract syntax tree或者缩写为AST),或者语法树(syntax tree),是源代码的抽象语法结构的树状表现形式,这里特指编程语言的源代码。

    Javascript的语法是为了给开发者更好的编程而设计的,但是不适合程序的理解。所以需要转化为AST来更适合程序分析,浏览器编译器一般会把源码转化为AST来进行进一步的分析等其他操作。

    以下只介绍Javascript相关的抽象语法树

    比如说有一段代码:

    var a = 3;
    a + 5;

    那么它的抽象语法树就类似:

    img

    JavaScript Parser

    JavaScript Parser,把js源码转化为抽象语法树的解析器。

    浏览器会把js源码通过解析器转为抽象语法树,再进一步转化为字节码或直接生成机器码。

    一般来说每个js引擎都会有自己的抽象语法树格式,Chrome的v8引擎,firefox的SpiderMonkey引擎等等,MDN提供了详细SpiderMonkey AST format的详细说明,算是业界的标准。

    发展到现在可能不同的JavaScript Parser的AST格式会不同,或基于SpiderMonkey AST format,或重新设计自己的AST format,或基于SpiderMonkey AST format优化改进。通过优化抽象语法树,来使程序运行的更快,也是一种提高效率的方法。

    常用的JavaScript Parser有:

    • Esprima
    • UglifyJS2
    • Traceur
    • Acorn
    • Shift

      在Esprima的官网有一个比较各个Parser解析速度的列表 Speed Comparison 。 看下来Acorn是公认的最快的。

    UglifyJS2的作者自己实现了一套js的抽象语法树,用到了继承,和现有的扁平的抽象语法树都有所不同,但作者也提供使用不同的抽象语法树来解析代码。

    AST explorer 可以在线看到不同的parser解析js代码后得到的AST。

    JavaScript AST visualizer 可以在线可视化的看到AST。

    生成并使用抽象语法树

    通过 esprima , 把一个名字为ast的空函数的源码生成一颗AST树:

    var esprima = require('esprima');
        var code = 'function ast(){}';
        var ast = esprima.parse(code);

    生成的抽象语法树长这样:

    {
      "type": "Program",
      "body": [
        {
          "type": "FunctionDeclaration",
          "id": {
            "type": "Identifier",
            "name": "ast",
            "range": [
              9,
              12
            ]
          },
          "params": [],
          "body": {
            "type": "BlockStatement",
            "body": [],
            "range": [
              14,
              16
            ]
          },
          "generator": false,
          "expression": false,
          "range": [
            0,
            16
          ]
        }
      ],
      "sourceType": "module",
      "range": [
        0,
        16
      ]
    }

    通过 estraverse 遍历并且更新抽象语法树,把函数名称改为ast_awsome:

    ...
        var estraverse = require('estraverse');
        estraverse.traverse(ast, {
            enter: function (node) {
                node.name += "_awsome";
            }
        });

    通过 escodegen 将AST重新生成为源码:

    ...
        var escodegen = require("escodegen");
        var regenerated_code = escodegen.parse(ast)

    AST三板斧:

    1. 通过 esprima 把源码转化为AST
    2. 通过 estraverse 遍历并更新AST
    3. 通过 escodegen 将AST重新生成源码

    抽象语法树的用途

    浏览器最先就会把源码解析为抽象语法树,对浏览器而言AST的作用非常重要。

    对开发者而言,AST的作用就是可以精准的定位到代码的任何地方,它就像是是你的手术刀,对代码进行一系列的操作。

    常见的几种用途:

    • 代码语法的检查、代码风格的检查、代码的格式化、代码的高亮、代码错误提示、代码自动补全等等
      • 如JSLint、JSHint对代码错误或风格的检查,发现一些潜在的错误
      • IDE的错误提示、格式化、高亮、自动补全等等
    • 代码混淆压缩
      • UglifyJS2等
    • 优化变更代码,改变代码结构使达到想要的结构
      • 代码打包工具webpack、rollup等等
      • CommonJS、AMD、CMD、UMD等代码规范之间的转化
      • CoffeeScript、TypeScript、JSX等转化为原生Javascript

    总结

    抽象语法树在前端领域中的应用广泛,通过抽象语法树大家可以实现很多功能,发现编写工具提高效率带来的乐趣。

    展开全文
  • JavaScript的语法解析与抽象语法树

    千次阅读 2019-05-16 11:45:26
    抽象语法树(Abstract Syntax Tree)也称为AST语法树,指的是源代码语法所对应的树状结构。也就是说,对于一种具体编程语言下的源代码,通过构建语法树的形式将源代码中的语句映射到树中的每一个节点上。 ...
  • 转JavaScript的语法解析与抽象语法树

    千次阅读 2015-07-10 11:57:24
    JavaScript的语法解析与抽象语法树 Jul 10, 2015 抽象语法树(Abstract Syntax Tree)也称为AST语法树,指的是源代码语法所对应的树状结构。也就是说,对于一种具体编程语言下的源代码,通过构建语法树的形式将源...
  • 将parser分析得到的statement转化为可以优化的AST语法树 对AST语法树做Cost Based优化 根据优化后的AST语法树生成查询计划 本篇文档主要介绍第1点中AST语法树相关的结构。 parser层...
  • java注解处理器——在编译期修改语法树

    千次阅读 多人点赞 2019-01-08 14:23:15
    目录 前言 从需求说起 添加打印日志代码的方案 第一种方案,硬编码 第二种方案,AOP 第三种方案,修改class...语法树的操作: JCTree的介绍 ​​ TreeMaker TreeMaker.Modifiers TreeMaker.ClassDef...
  • 抽象语法树是什么 在计算机科学中,抽象语法树(abstract syntax tree 或者缩写为 AST),或者语法树(syntax tree),是源代码的抽象语法结构的树状表现形式,这里特指编程语言的源代码。树上的每个节点都表示源...
  • 语法树AST、后缀表达式、DAG、三地址代码     抽象语法树的观点认为任何复杂的语句嵌套情况都可以借助于树的形式加以描述。确实,不得不承认应用抽象语法树可以使语句翻译变得相对容易,它很好地描述了语句、...
  • 有数字(0~9构成的正整数)、三种操作运算符...语法树结束后,后面加任何字符都是合法的,比如(+ (* 2 3)(^4)))))))#$是合法的 匆匆忙忙地写了一个,感觉太长了。。。应该有很大的优化空间。 主要思路:用一个va...
  • iOS逆向:【代码混淆】1、基于编译器混淆静态库(StaticLib)2、字符串加密:使用clang-c接口将源代码转换成抽象语法树,并对抽象语法树进行遍历和分析,分析代码中的字符串,并进行加密处理。
  • 二、 Hive语法树的生成

    千次阅读 2016-03-17 09:20:30
    HiveQL是一个非标准的sql...ANTLR(ANother Tool for Language Recognition)是一款功能强大的语言构建工具,提供了词法分析、语法分析等功能。用户编写语言的词法规则和语法规则,然后通过antlr提供的运行时库将语言转
  • Lex和Yacc使用教程(六).语法树打印

    千次阅读 2007-05-25 21:29:00
    语法树打印草木瓜 20070525一、序 没有直观的语法树显示界面,理解前面两篇文章会比较难一些。(语法树的示例见《Lex和Yacc应用教程(四).语法树的应用》) 其实语法树显示程序在Tom Niemann的《A Compact Guide to ...
  • 什么是抽象语法树(AST)

    千次阅读 2019-02-22 09:54:14
    张大胖想起来自己没有考及格的《编译原理》,里边讲到了抽象语法树(AST)不就是所谓结构化的东西吗? 比如表达式 result = 6+7*3 , 用抽象语法树来表示就是: 如果把所有的JavaScript代码都转化成这样一颗...
  • PHP7 的抽象语法树(AST)带来的变化

    千次阅读 2015-12-09 20:50:33
    转载自:http://0x1.im/blog/php/changes-of-php7-because-of-ast.html 本文大部分内容参照 AST 的 RFC 文档而成:... 本文并不会告诉你抽象语法树是什么,这需要你自己去了解,这里只是描述 AST 给 PHP
  • sql 解析,编译,ast 抽象语法树

    万次阅读 2018-03-06 01:35:35
    `),中文是抽象语法树。在不说子查询之类的情况下,这个AST也不会太复杂,毕竟where后面的情况比起编译原理里的程序语言来说情况还是要少得多的。以上述的sql为例,这里解析出来的Where结构是这样的: & sqlparser ....
  • Lex和Yacc使用教程(五).再识语法树

    万次阅读 2007-05-25 21:26:00
    语法树》一文已对语法树有了初步的概念,本文主要目的是巩固语法树的概念,并做进一步的扩展分析。闲说少说,首先给出完整示例,本例在Redhat Linux 9下调试通过,可放心使用。 另外系列文章的标题,有的叫“lex和...
  • 《数据库》查询树优化

    万次阅读 多人点赞 2014-03-08 11:33:42
    查询的启发式优化 典型的启发式规则: 1.选择运算应尽可能先做。在优化策略中这是最重要、最基本的一条 2.把投影运算和选择运算同时进行 如有若干投影和选择运算,并且它们都对同一个关系操作,则可以在扫描此...
  • 原文:JavaScript的工作原理:解析、抽象语法树(AST)+ 提升编译速度5个技巧 作者:前端小智 Fundebug经授权转载,版权归原作者所有。 这是专门探索 JavaScript 及其所构建的组件的系列文章的第 14 篇。 如果你...
  • 构造使用类C语言的脚本引擎(5)作者 :kevin_qing转贴请注明语法检查,常量合并和生成语法树是在reduce规约函数中实现语法树节点定义struct GTreeNode{uint32_t type; uint32_t value;};struct GTreeNode1:public ...
  • 1.1. Sql语法树 ast 如下图锁死1 2. SQL语句解析的思路和过程3 2.1. lexer作为一个工具,完成了对SQL字符串的切割,将语句转化成一个tokens数组。3 2.2. Parser完成了SQL解析的后序部分:使用一个lexer对象...
  • 超级详细的查询树优化!数据库笔记GET!!!

    千次阅读 多人点赞 2020-06-11 11:53:29
    超级详细的查询树优化!数据库笔记GET!!! 主要内容数据库 代数优化 查询树优化 等价变换规则和启发式规则
  • IR中,保留了全部的类型信息,即IR采用了高级形式而非偏底层,这样也是为了将来便于添加更多的静态分析和优化的功能。下面介绍各条IR。    1,赋值语句  mov,type obj src type是引用类型,而非真实...
  • 从嵌套表达式谈抽象语法树(AST)到平台无关中间指令(IR)的翻译过程(线性化) #一些想到的东西: ## 要掌握编译器前端Parser的语法解析是怎么回事,不需要用完整的C语言系的字符串,只要考虑带括号的...
  • 然后,再进行语法分析,生成抽象语法树.下图就是JavaScriptCore世界语法节点的静态类关系:  下面我们看看,语法解析具体过程: JavaScriptCore/parser/parser.cpp: PassRefPtr<ParsedNode> ...
  • 形查询SQL优化一例

    千次阅读 2017-12-04 10:51:49
    形查询sql
  • 本周继续学习AST的SQL语法检测原理的学习,文章的接下来部分准备分为2部分进行学习: 1. SQL注入语法防御规则 2. druid中SQL注入防御模块sql-wall 1. 相关学习资料 ...
  • 数据库题目~查询优化查询

    千次阅读 2020-04-27 21:54:13

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 80,147
精华内容 32,058
关键字:

语法树优化