数据库系统原理及应用 丁忠俊 第二章 关系数据库.ppt

第二章 关系数据库 第一节 关系数据库概述 第二节 关系模型 5.名词对照表 第三节 关系代数 第四节 关系代数式的查询优化 一.关系DB的查询优化概述 关系DB的查询优化分为：代数优化和物理优化。 代数优化：指关系代数表达式的优化。（本节重点） 物理优化：指存取路径的选择和低层操作算法的选择。 1. 关系DB的查询处理过程 查询处理过程：查询分析，查询检查，查询优化，查询执行。 查询分析：对查询语句进行扫描，词法分析和语法分析。判断查询语句是否合法。 查询检查：根据数据字典，检查查询语句的语义，用户的存取权限和完整性的定义。检查通过后，把SQL语句转换成等价的关系代数表达式。 一般用查询树（又称：语法分析树）表示关系代数表达式。 查询优化：选择高效执行的查询处理策略。 查询执行：由代码生成器执行根据查询策略生成的查询计划的代码。 查询优化过程： 查询语句 2.关系代数运算的优化问题 问题：选择怎样的关系代数表达式表示查询，省时，省空间，速度快呢？ 例：有三个等价的关系代数表达式E1，E2，E3： E1= лA（ σB =C∧D=’99’（R×S）)，先做笛卡尔积，后做选择和投影。 E2= лA（ σB =C（R× σ D=’99’（S））)，先做选择，后做笛卡尔积。 E3= л A（ R |×| （σ D=’99’（S）），先做选择，后做联接。 注：E1：先做笛卡尔积，占大量的内存空间。 E2和E3:先对S做选择操作会减少大量的元组，再与R做联接时，内存空间花费小，存取的次数少，花费CUP的时间少。 关系代数式的优化：在保证语义正确的情况下， 如何安排选择，投影和笛卡尔积，联接运算次序。使得写出的关系代数式在计算机上执行时省时，省空间，效率高。 二.关系代数式等价变换规则 关系代数式等价变换：用相同的关系代替两个表达式中相应的关系，所得到的结果关系是一样的。记为：E1≡E2。 等价变换规则： 1.联接与笛卡尔积的交换律 E1×E2≡ E2×E1 （E1和E2表示关系代数表达式） E1 |×| E2 ≡ E2 |×| E1 E1 |×| E2 ≡ E2 |×| E1 (F是条件表达式) 2.联接与笛卡尔积的结合律 (E1×E2)×E3≡ E1×(E2×E3) (E1 |×| E2 ) |×| E3 ≡ E1 |×| (E2 |×|E3) (E1 |×| E2 ) |×| E3≡ E1 |×| (E2 |×|E3) 3.选择与投影的串接 лA1，A2，….., An(лB1,B2,…,Bn(E)) ≡ лA1，A2，….., An(E) (Ai∈ {B1,B2,…,Bn}) σ (σ (E) ) ≡ σ (E) 4.选择与笛卡尔积的交换 若F只涉及到E1中的属性，则： σ（E1×E2） ≡ σ（E1）×E2 若F＝F1∧F2 ，则： σ（E1×E2）≡ σ（E1）× σ（E2） （其中：F1涉及中的属性E1； F2涉及中的属性E2 ） 5.选择与投影的交换 σ （лA1，A2，….., An（E））≡ лA1，A2，….., An（σ（E）） 6.选择与并的交换 σ（E1∪E2）≡ σ（E1）∪ σ（E2） 7.选择与差的交换 σ（E1－E2）≡ σ（E1）－ σ（E2） 8.投影与并的交换 лA1，A2，….., An(E1∪E2)) ≡ лA1，A2，….., An(E1) ∪ лA1，A2，….., An(E2) 9.投影与笛卡尔积的交换 лA1，A2，….., An，B1,B2,…,Bn(E1×E2) ≡ лA1，A2，….., An(E1) × лB1，,B2,…,Bn(E2) (Ai是E1的属性，Bi 是E2的属性） 10.选择与自然联接的交换 σ（E1|×|E2）≡ σ（E1） |×| σ（E2）(F中涉及E1和E2的公共属性) 11.选择与联接的结合 σ（E1×E2）≡ E1 |×| E2 σ（E1 |×| E2）≡ E1 |×| E2 12.涉及到集合的规则 E1∪E2≡ E2∪ E1 E1∩E2≡ E2∩ E