精华内容
下载资源
问答
  • 关系代数表达式优化步骤 本篇主要讲解怎么画查询语法树并对其优化,因为我在学关系代数的语法树的时候,在网上找不到比较详细的教法或者技巧,最后通过答案反推原理,所以想写一篇技巧来描述一下这类题的解题方法。 ...

    关系代数表达式优化步骤

    本篇主要讲解怎么画查询语法树并对其优化,因为我在学关系代数的语法树的时候,在网上找不到比较详细的教法或者技巧,最后通过答案反推原理,所以想写一篇技巧来描述一下这类题的解题方法。

    先上书内讲解

    1、构造查询树

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

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

    2、利用等价转换规则反复地对查询表达式进行尝试性转换,将原始的语法树转換成“优化”的形式(方式的等价变换规则查书)

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

    题目举例

    对学生-课程数据库,查询信息系学生选修了的所有课程名称。

    ​ SELECT Cname FROM Student,Course,SC WHERE Student.Sno=SC.Sno AND SC.Cno=Course.Cno AND Student.Sdept=’IS’;

    ​ 试画出查询树图、关系代数语法树图、优化后的查询树。

    具体的技巧就是 先选择,后投影,按照查询语句的顺序 先写Project(Cname),也就是最终查询结果,然后按照条件语句where从后面往前写,遇到两个表相关联的字段时,可以看看是否这个表后面还有查询,如果没有,则表作为叶端,有的话,就继续连接(join)条件,直到所有的查询条件都连接完毕,剩下的叶端就是表了。
    例如下图的查询树,到join(SC.Cno=Course.Cno)的时候,条件的Course从后往前都没有下一个查询条件了,也就是说这是最后一个关于Course的查询条件,那表名就出来了。
    进行优化语法树的时候,要全部都转为选择σ和投影∏来表示,σ一般表示除了父节点以外的结点,∏ 表示父节点。遇到两个表相关联的情况,下面要用X表示,比查询多这一步而已,读者看图应该能看懂。下一步就是变成优化后的语法树,做法也很简单,就是把那些单表的查询语句移到下面来,移到等值运算后面作为新的查询条件,然后再出结果的表。

    1.构造查询树
    查询语句转关系代数表达式为:∏Cname(σStudent.Sdept=’IS’(Student ⋈ Course ⋈ SC))

    在这里插入图片描述

    2.利用等价代换原则进行优化

    在这里插入图片描述

    在这里插入图片描述

    展开全文
  • 数据库关系代数表达式学习

    万次阅读 多人点赞 2018-01-14 17:15:15
    感谢原作者 ...很有必要学习一下,有些是用代数表达式很方便的东西,用SQL写出来还是挺麻烦的,并不是想象当中那么直接。   一、关系代数的9种操作:    关系代数中包括了:

    关系代数是关系数据库系统查询语言的理论基础。很有必要学习一下,有些是用代数表达式很方便的东西,用SQL写出来还是挺麻烦的,并不是想象当中那么直接。
     
    一、关系代数的9种操作:
     
        关系代数中包括了:并、交、差、乘、选择、投影、联接、除、自然联接等操作。
     
    五个基本操作:
        并(∪)、差(-)、笛卡尔积(×)、投影(π)、选择(σ)
     
    四个组合操作:
        交(∩)、联接(等值联接)、自然联接(RcrossS)、除法(÷) 
    注2:等值连接表示先做笛卡尔积(×)之后,对相应列进行选择或等值关联后的结果(仅筛选行、不筛选列)
    注2:自然连接表示两个关系中若有相同名称的属性,则自动作为关联条件,且仅列出一列
     
     
    二、关系代数表达式:
     
        由关系代数运算经有限次复合而成的式子称为关系代数表达式。这种表达式的运算结果仍然是一个关系。可以用关系代数表达式表示对数据库的查询和更新操作。
     
     
    三、举例说明:
     
        设教学数据库中有3个关系:

        学生关系S(SNO,SNAME,AGE,SEX)
        学习关系SC(SNO,CNO,GRADE)
        课程关系C(CNO,CNAME,TEACHER)
     
     
    (1) 检索学习课程号为C2的学生学号与成绩
    ------------------------------------
    SELECT SNO,GRADE
      FROM SC
    WHERE CNO='C2'
    ------------------------------------
    π SNO,GRADE(σCNO='C2'(SC))
    ************************************
     
     
    (2) 检索学习课程号为C2的学生学号与姓名
    ------------------------------------
    SELECT SC.SNO,S.SNAME
      FROM SC,S
    WHERE SC.SNO=S.SNO
       AND SC.CNO='C2'
    ------------------------------------
    π SNO,SNAME(σCNO='C2'(ScrossSC))
    此查询涉及S和SC,先进行自然连接,然后再执行选择投影操作。
    ----
    π SNO,SNAME(S)crossπSNO(σCNO='C2'(SC)))
    自然连接的右分量为"学了C2课的学生学号的集合"。
    此表达式比前一个表达式优化,执行起来要省时间、省空间。
    ************************************
     
     
    (3) 检索选修课程名为MATHS的学生学号与姓名 
    ------------------------------------
    SELECT SC.SNO,S.SNAME
      FROM SC,S,C
    WHERE SC.SNO=S.SNO
       AND SC.CNO=C.CNO
       AND C.CNAME='MATHS'
    ------------------------------------
    π SNO,SANME(σCNAME='MATHS'(ScrossSCcrossC))
    ************************************
     
     
    (4) 检索选修课程号为C2或C4的学生学号
    ------------------------------------
    SELECT SNO
      FROM SC
    WHERE CNO='C2'
        OR CNO='C4'
    ------------------------------------
    π SNO(σ CNO='C2'∨CNO='C4'(SC))
    ************************************
     
     
    (5) 检索至少选修课程号为C2或C4的学生学号
    ------------------------------------
    SELECT SA.SNO
      FROM SC AS SA,SC AS SB
    WHERE SA.SNO=SB.SNO
       AND SA.CNO='C2'
       AND SB.CNO='C4'
    ------------------------------------
    π 1(σ1=4∧2='C2'∧5='C4'(SC×SC))
    ************************************
     
     
    (6) 检索不学C2课的学生姓名与年龄
    ------------------------------------
    SELECT SNAME,AGE
      FROM S
    MINUS
    SELECT S.SNAME,S.AGE
      FROM SC,S
    WHERE SC.SNO=S.SNO
       AND SC.CNO='C2'
    (Oracle)
    ------------------------------------
    π SNAME,AGE(S)-πSNAME,AGE(σCNO='C2'(ScrossSC))
    ************************************
     
     
    (7) 检索学习全部课程的学生姓名
    ------------------------------------
    这个定义用SQL表示比较麻烦,略过
    ------------------------------------
    π SNO,CNO(SC)÷πCNO(C)
    先用除法取出选取所有课程的SNO集(除法可以理解为一个Filter)
    π SNAME(S cross (πSNO,CNO(SC)÷πCNO(C)))
    再关联S表取出SNAME
    ************************************
     
     
    (8) 检索所学课程包含S3所学课程的学生学号
    ------------------------------------
    这个定义用SQL表示比较麻烦,略过
    ------------------------------------
    π SNO,CNO(SC)÷ πCNO(σSNO='S3'(SC))
    同样运用了除法的特性
    ************************************
     
     
    (9) 将新课程元组('C10','PHYSICS','YU')插入到关系C中
    ------------------------------------
    INSERT INTO C VALUES('C10','PHYSICS','YU')
    ------------------------------------
    (C('C10','PHYSICS','YU'))
    记住该符号的用法
    ************************************
     
     
    (10) 将学号S4选修课程号为C4的成绩改为85分
    ------------------------------------
    UPDATE SC SET GRADE=85
    WHERE SNO='S4'
       AND CNO='C4'
    ------------------------------------
    (SC('S4','C4',?)('S4','C4',85))
    先用''实现DELETE功能,再用'∪'实现INSERT功能
    注意使用?来表示检索时忽略该字段值
    ************************************
     
     
    四、关系代数表达式的优化:
     
        目的:为了系统在执行时既省时间又能提高效率。
        基本策略:先做选择,运用投影去除多余属性等等。
        优化算法:语法树(尽量提前做选择操作;在每个操作后,应做个投影操作,去掉不用的属性值)
     
        例如:
     
        π SNO,SNAME(σGRADE>60(ScrossSC)) 进行优化后转换为:
        π SNO,SNAME(πSNO,SNAME(S)crossπSNO(σGRADE>60(SC)))
        --即提前做选择操作;在每个操作后,应做个投影操作,去掉不用的属性值
     
     
        又如:
     
        S(S#,SNAME,AGE,SEX)
        SC(S#,C#,GRADE)
        C(C#,CNAME,TEACHER)
     
        π CNAME,TEACHER(σSEX='女'(ScrossSCcrossC)) 进行优化后转换为:
        πCNAME,TEACHER(CcrossπC#(πS#,C#(SC)crossπS#(σSEX='女'(S))))
     
        优化前和优化后的语法树如下所示:
     
        syntax_tree
    展开全文
  • Algorithm:关系代数表达式优化算法 Input:一个关系代数表达式的语法树 Output:计算该表达式的程序 Method: (S1)依据定理L4,把形如σF1∩F2∩…∩Fn(E))σ_{F_1∩F_2 ∩ … ∩ F_n} (E))σF1​∩F2​∩…∩...

    Algorithm:关系代数表达式的优化算法
    Input:一个关系代数表达式的语法树
    Output:计算该表达式的程序
    思路:

    1. 选择运算应尽可能先做
    2. 把投影运算和选择运算同时进行:这两者都是一元操作,一个元组能不能成为结果只取决于其本身
    3. 把投影同其前或后的双目运算结合起来
    4. 把某些选择同在它前面要执行的笛卡儿积结合起来称为一个连接运算
    5. 找出公共子表达式

    Method:

    • (S1)依据定理L4,把形如 σ F 1 ∩ F 2 ∩ … ∩ F n ( E ) ) σ_{F_1∩F_2 ∩ … ∩ F_n} (E)) σF1F2Fn(E))的选择表达式变成串接形式 σ F 1 ( σ F 2 ( … ( σ F N ( E ) ) ) ) σ_{F_1}(σ_{F_2}(…(σ_{F_N} (E)))) σF1(σF2((σFN(E)))).

    • (S2)对每个选择,依据定理L4至L9,尽可能把它移至树的底部。

    • S3)对每个投影,依据定理L3,L7,L10和L5,尽可能把它移至树的底部。

    • (S4)依据定理L4至L5把串接的选择和投影组合为单个选择、单个投影,或者一选择后跟一个投影。

    • (S5)对修改后的语法树,将其内结点按以下方式分组: 每个二元运算结点(积、并、差、连接等)和其所有一元运算直接祖先结点放在一组;对于其后代结点,若后代结点是一串一元运算且以树叶为终点,则将这些一元运算结点放在该组中;若该二元运算结点是笛卡儿积,且其后代结点不能和它组合成等连接,则不能将后代结点归入该组。

    • (S6)产生一个程序:它以每组结点为一步,但后代组先执行。

    例如:
    查出1978年1月1日前被借出的所有书的书名
    XLOANS是面向用户的一个视图
    在这里插入图片描述

    SELECT Title FROM XLOANS WHERE Date<=1/1/78
    

    转换为关系代数表达式:
    Π T I T L E ( σ D A T E < = “ 1 / 1 / 78 ” ( Π_{TITLE}(σ_{DATE<=“1/1/78”}( ΠTITLE(σDATE<=1/1/78(XLOANS ) ) )) ))
    再将视图XLOANS替换为视图的定义,得到下图右面的语法树
    在这里插入图片描述

    接下来我们就要对这颗语法树来进行优化

    首先依据定理L4,把形如 σ F 1 ∩ F 2 ∩ … ∩ F n ( E ) ) σ_{F_1∩F_2 ∩ … ∩ F_n} (E)) σF1F2Fn(E))的选择表达式变成串接形式
    σ F 1 ( σ F 2 ( … ( σ F N ( E ) ) ) ) σ_{F_1}(σ_{F_2}(…(σ_{F_N} (E)))) σF1(σF2((σFN(E)))).
    对于语法树中的选择条件:
    在这里插入图片描述
    即可将语法树中的 σ F σ_{F} σF拆开变成串接形式,即为 σ F 2 ∩ F 3 = σ F 2 ( σ F 3 ) σ_{F_2∩F_3}=σ_{F_2}(σ_{F_3}) σF2F3=σF2(σF3)

    然后第二步:对每个选择,依据定理L4至L9,尽可能把选择移至树的底部(尽可能地早做选择和投影)。
    σ F 1 σ_{F_1} σF1通过交换移动到底部
    σ F 2 σ_{F_2} σF2 通过交换移动到底部
    σ F 3 σ_{F_3} σF3移动不了
    因为 Π S Π_S ΠS经过 Π t i t l e Π_{title} Πtitle投影已经没有意义了,所以 Π t i t l e ( Π s ) = Π t i t l e Π_{title}(Π_{s})=Π_{title} Πtitle(Πs)=Πtitle

    在这里插入图片描述
    第三步是继续对投影运算进行移动,对每个投影,依据定理L3,L7,L10和L5,尽可能把它移至树的底部,如果一个投影是对某表达式所有属性进行的,则去掉之。
    首先, Π t i t l e Π_{title} Πtitle移动不下去(因为首先 Π t i t l e Π_{title} Πtitle就不包含 F 3 F_3 F3涉及的属性),就将其转换,使其包含 F 3 F_3 F3涉及的属性,然后再向下移动

    然后
    在这里插入图片描述
    类似处理BORROWERS和LOANS的投影
    在这里插入图片描述
    然后对修改后的语法树,将其内结点按以下方式分组: 每个二元运算结点(积、并、差、连接等)和其所有一元运算直接祖先结点放在一组;对于其后代结点,若后代结点是一串一元运算且以树叶为终点,则将这些一元运算结点放在该组中;若该二元运算结点是笛卡儿积,且其后代结点不能和它组合成等连接,则不能将后代结点归入该组。
    在这里插入图片描述

    展开全文
  • 关系代数表达式优化

    千次阅读 2013-09-01 22:16:36
    理解起来有点费劲,例如不知道关系的连接在哪里进行,连接的中间结果放在哪里,计算后的结果怎么处理,这时如果纠结在这个上面则额外增加了很多的复杂度,最终导致不能正确理解优化过程。 如果只把计算机原理的知识...


    查询的处理的代价通常取决于磁盘访问,磁盘访问比内存访问速度慢很多。




    在这里由于计算机原理的知识的欠缺,理解起来有点费劲,例如不知道关系的连接在哪里进行,连接的中间结果放在哪里,计算后的结果怎么处理,这时如果纠结在这个上面则额外增加了很多的复杂度,最终导致不能正确理解优化过程。

    如果只把计算机原理的知识放到一边,只抓一点:计算需要在内存中进行,所有的块都要放到内存中,才进行计算,这样理解起来就好很多。(抓住关键)



    展开全文
  • 数据库关系代数表达式

    千次阅读 2017-08-23 15:59:47
    一、关系代数的9种操作: 关系代数中包括了:并、交、差、乘、选择、投影、联接、除、自然联接等操作。 五个基本操作: 并(∪)、差(-)、笛卡尔积(×)、投影(σ)、选择(π) 四个组合操作: 交(∩)、...
  • 详细分析关系代数表达式等价变换前后的查询代价。针对DBMS查询优化器如何生成成本最小的查询计划...提出基于关系代数运算等价变换规则的SQL查询优化策略。该策略提供了查询优化器生成成本最小的查询计划的设计依据。
  • 利用改进查询计划的代数定律,分析基于关系代数树的关系代数式查询优化方法、研究关系代数表达式与SQL查询的等价变换准则、分析关系代数表达式等价变换前后的查询代价;通过实验、实例以及代价估计验证了利用关系...
  • 代数优化策略

    千次阅读 2020-03-01 21:39:02
    尽早执行选择操作 目的:减少中间关系 投影和选择操作同时进行 目的:避免重复扫描关系 投影和前后的双目运算结合 目的:减少扫描关系的遍数 选择和前面要执行的笛卡尔积结合成为一个连接运算...找出公共子表达式 ...
  • 关系代数和SQL练习(二)

    千次阅读 2017-01-04 13:11:49
    数据库关系代数表达式学习 关系代数是关系数据库系统查询语言的理论基础 一、关系代数的9种操作:  关系代数中包括了:并、交、差、乘、选择、投影、联接、除、自然联接等操作。 五个基本操作:  并(∪)、...
  • 数据库之关系代数

    2015-10-15 11:45:48
     感谢原作者的整理 ...很有必要学习一下,有些是用代数表达式很方便的东西,用SQL写出来还是挺麻烦的,并不是想象当中那么直接。   一、关系代数的9种操作:    关系代数中包括了:并
  • 面向中文专利信息的关系数据库检索优化策略研究及应用目 录1 引言... 32 中文专利信息检索优化概述... 42.1 中文信息检索的概念... 42.2 中文信息检索的现状... 42.3 中文专利信息检索概述... 52.3.1 中文专利...
  • 索引使用策略优化 示例数据库 最左前缀原理与相关优化 索引选择性与前缀索引 InnoDB的主键选择与插入优化 后记 参考文献 数据结构及算法基础 索引的本质 MySQL官方对索引的定义...
  • 数据库关系代数

    2017-11-21 16:46:00
    关系代数关系数据库系统查询语言的理论基础一、关系代数的9种操作:关系代数中包括了:并、交、差、乘、选择、投影、联接、除、自然联接等操作。五个基本操作:并(∪)、差(-)、笛卡尔积(×)、投影(σ)、选择(π)四...
  • 「 数据库原理 」查询优化(关系代数表达式优化) 转载自 http://www.ptbird.cn/optimization-of-relational-algebraic-expression.html 关系代数表达式是进行数据库查询前的理论部分,在简单的查询中一般不会想到...
  • 第9章 关系查询处理和查询优化 9.1 关系数据库系统的查询处理 1、RDBMS的查询处理分为四个阶段: 【1】查询分析。 对查询语句进行扫描、词法分析和语法分析,识别SQL关键字、属性名和关系名等语言符号,进行语法...
  • 数据库笔记-关系代数

    2021-06-17 12:15:18
    关系代数运算 关系代数的五个基本操作 并(∪):两个关系需有相同的关系模式,并的对象是元组,由两个关系所有元组构成。 RUS≡{t| t∈R ∨t∈S} 差(-):同样,两个关系有相同的模式,R和S的差是由属于R但不属于S...
  • 9.1 关系数据库系统的查询处理 查询处理步骤 查询分析→查询检查→查询优化→查询执行 实现查询操作的算法示例 选择操作 连接操作(费时)嵌套循环方法、排序-合并方法、索引...代数优化策略:通过对关系代数表达
  • 代数优化是指关系代数表达式优化,物理优化指的是通过存取路径和底层操作算法的选择进行的优化。 9.1 关系数据库系统的查询处理 9.1.1 查询处理步骤 1. 查询分析 首先对查询语句进行扫描、词法分析和语法分析。从...
  • 第2部分 关系模型与关系代数 复习习题与讲解资料 【主讲教师:钱哨】 一.考试大纲考点要求 1 掌握关系关系性质、候选键、外部键、主属性、非主属性、关系模型完整性、关系模式、关系数据库等基本概念。 2 ...
  • 一、关系代数的9种操作: 关系代数中包括了:并、交、差、乘、选择、投影、联接、除、自然联接等操作。 五个基本操作: 并(∪)、差(-)、笛卡尔积(×)、投影(σ)、选择(π) 四个组合操作: 交...
  • n代数优化:指关系代数表达式优化 n物理优化:指存取路径和底层操作算法的选择   v关系数据库管理系统查询处理阶段 : 1. 查询分析 2. 查询检查 3. 查询优化 4. 查询执行    v选择操作典型实现方法...
  • 查询处理的过程 ...就是对关系代数表达式进行优化,找出最优的效率最高的关系代数表达式 第四步 根据这个关系代数表达式制定好执行计划(执行计划是指执行一个查询的计算机原语,也就是说它是标注了如何...
  • 由于关系表达式的语义级别很高,使关系系统可以从关系表达式中分析查询语义,提供了执行查询优化的可能性 查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率,而且在于系统可以比用户程序的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,606
精华内容 1,842
关键字:

关系代数表达式的优化策略