第2章 关系数据库 2.1 关系模型 2.2 关系代数 2.3 查询优化.

Presentation on theme: "第2章 关系数据库 2.1 关系模型 2.2 关系代数 2.3 查询优化."— Presentation transcript:

1 第2章 关系数据库 关系模型 关系代数 查询优化

2 2.1 关系模型 1.关系模型的特点及组成 特点： 结构简单，表达力强 语言的一体化 非过程化的操作 坚实的数学基础 操作效率较低 组成：
2.1 关系模型 1.关系模型的特点及组成 特点： 结构简单，表达力强 语言的一体化 非过程化的操作 坚实的数学基础 操作效率较低 组成： 关系数据结构 关系数据操作 关系完整性约束 关系DB系统 是支持关系模型的DB系统

3 2.1 关系模型 2、关系数据结构 a 0 b 0 c 0 a 1 b 1 c 1 D1XD2： 1)域:
关系模型 D1XD2： 2、关系数据结构 1)域: 是一组具有相同数据类型的值的集合。 2)笛卡尔积 给定一组域 D1，…，Dn (可有相同的域)。其笛卡尔积为： DlXD2X…XDn={(d1，d2，…，dn)| di∈Di，i=1,2…,n} D1 D2 a 0 b 0 c 0 a 1 b 1 c 1 姓名 性别 c 0 a 1 b 1 例：姓名集D1={a,b,c} 性别集D2={0,1}

4 2.1 关系模型 3)关系 笛卡尔积的有限子集 称作对应域上的关系。 关系：是元组的集合。 R(D1，D2， …，Dn) R是n元(目)关系
2.1 关系模型 候选键 主键 3)关系 笛卡尔积的有限子集 称作对应域上的关系。 关系：是元组的集合。 R(D1，D2， …，Dn) R是n元(目)关系 4)术语： 候选键 主键、主属性 非主属性 外键（外来关键字） 外键提供了一种表示两个关系联系的方法。 S(Sno，Cardno，Sname，Sage…) SC(Sno，Cno，Grade) 非主属性 两个主属性 9801 01 95 02 80 9802 88 03 92 9803 Sno Cno Grade ……

5 2.1 关系模型 5)关系的性质： (1)每列的值为同一类型。 (2)每列具有不同的属性名 (3)任意两元组不能完全相同。
2.1 关系模型 5)关系的性质： (1)每列的值为同一类型。 (2)每列具有不同的属性名 (3)任意两元组不能完全相同。 (4)行的次序可以互换。 (5)列的次序可以互换。 (6)分量值是原子的。 分量值 属性名 学号 姓名 年龄 元组 关系的类型 ： 基本关系 查询表 视图表 职工 工资 基本 奖金 .. … ; 网虫? +5? 不允许

6 2.1 关系模型 6）关系模式与关系数据库 关系模式：是关系结构的描述和定义，即二维表的表结构定义。 关系实质上是一张二维表。
2.1 关系模型 6）关系模式与关系数据库 关系模式：是关系结构的描述和定义，即二维表的表结构定义。 关系实质上是一张二维表。 因此，关系模式必须指出表的结构，即它由哪些属性构成，这些属性来自哪些域，以及属性与域之间的对应关系。 关系模式简记为关系的属性名表: R(U) =R(A1 ，A2，A3，….An) 例:学生（学号,姓名,总成绩） 关系数据库: 对应关系模型的一个应用领域的全部关系的集合。 联系？

7 2.1 关系模型 3. 关系模型的数据操作 关系模型中常用的关系数据操作有四种：
2.1 关系模型 3. 关系模型的数据操作 关系模型中常用的关系数据操作有四种： (1)数据查询。基本操作有：关系属性的指定；关系元组的选择；两个关系的合并。 (2)数据插入。在关系内插入一些新元组。 (3)数据删除。在关系内删除一些元组。 (4)数据修改。修改关系元组的内容。可分解为：先删除要改的元组，再插入新元组。 关系数据操作是一种集合式操作。复杂的关系数据操作可通过基本的关系数据运算获得。此外，还需要有关系的操作规则及具体的关系数据语言来实现这些操作。 关系数据语言可分为研究用的抽象语言和可使用的实现语言。关系数据语言大体分成三类，如表2-3。

8 2.1 关系模型 4. 关系的完整性 1）实体完整性 三类完整性约束： 实体完整性 由关系系统自动支持 参照完整性 用户定义的完整性
2.1 关系模型 4. 关系的完整性 三类完整性约束： 实体完整性 参照完整性 用户定义的完整性 由关系系统自动支持 1）实体完整性 实体完整性规则 : 若属性A是基本关系R的主码属性，则属性A不能取空值。 是应用领域需要遵循的约束条件 说明： (1)该规则是对基本关系的约束和限定。 (2)实体有唯一性标识—主键。 (3)主键上的属性不能取空值。

9 2.1 关系模型 2）参照完整性 引用关系： 关系中的某属性的值需要参照另一关系的属性来取值。 例1：学生(学号，姓名，性别，专业号，年龄)
2.1 关系模型 2）参照完整性 引用关系： 关系中的某属性的值需要参照另一关系的属性来取值。 例1：学生(学号，姓名，性别，专业号，年龄) 专业(专业号，专业名) 引用 例2: 学生(学号，姓名，性别，专业号，年龄，合作者号) 引用

10 2.1 关系模型 例：学生(学号，姓名，性别，专业号，年龄) 设：基本关系R、S(可为同一关系)。 若F是R的一个(组)属性，但不是R的键。
2.1 关系模型 设：基本关系R、S(可为同一关系)。 若F是R的一个(组)属性，但不是R的键。 如果F与S的主键K相对应，则称F是R的外键。 说明：S的主键K和R的外键F必须定义在同一个(组)域上 R为参照关系，S为目标关系。 外键 参照关系 例：学生(学号，姓名，性别，专业号，年龄) 专业(专业号，专业名) 引用 目标关系

11 2.1 关系模型 参照完整性规则 若属性(组) F是R的外键它与S的主键K相对应， 则对于R中每个元组在F上的值必为下列之一：
2.1 关系模型 参照完整性规则 若属性(组) F是R的外键它与S的主键K相对应， 则对于R中每个元组在F上的值必为下列之一： (1)取空值(F的每个属性值均为空)； (2)等于S中某个元组的主键值。 例：学生(学号，专业号，姓名，….) 关系中每个元组的专业号取值： (1)空值(未知值)； (2)非空值。 定义了外键与主键之间的引用规则。 指外键不能引用不存在的主键值。 3）用户定义的完整性 反映具体应用所涉及的数据应满足的语义要求、约束条件。 例：学生关系中的年龄在15~45之间，选修关系中的成绩在0~100之间。

12 2.2 关系代数 关系数据语言分类： 1)关系代数 2)关系演算 元组关系演算 域关系演算 3)具有双重特点的语言(SQL) 共同特点是:
2.2 关系代数 关系数据语言分类： 1)关系代数 2)关系演算 元组关系演算 域关系演算 3)具有双重特点的语言(SQL) 共同特点是: 具完备的表达能力 是非过程化的集合操作语言 功能强 可嵌入、又可独立使用

13 2.2 关系代数 关系代数是一种抽象的查询语言。它以关系为运算对象，通过对关系进行“组合”或“分割”，得到所需的数据集合—关系。 分类：集合运算（并、交、差；广义笛卡尔积） 关系运算及其扩充 一、 集合运算 设：t 为元组变量；R、S为同类(相同元、相应属性同域）关系；下列运算结果为同类关系： 1.并运算: RUS ={t |（t∈R）∨（t ∈ S）} 2.差运算: R—S={t |（t∈R）∧（t  S）} 3.交运算: R∩S={t |（t∈R）∧（t ∈ S）} R∩S= R－(R－S)

14 2.2 关系代数 集合运算示例 R 2 A 1 3 a 3 c b 2 d c 2 d e 5 f g 6 f R 1 A 2 3
2.2 关系代数 集合运算示例 R 2 A 1 3 a c b 2 d c d e f g f R 1 A 2 3 b d b b c d d b R 1 ∪ 2 A 3 b d b b c d d b a c e f g f R 1 ∩ 2 A 3 b d c d R 1 - 2 A 3 b b d b

15 R×S={tr ts|（tr∈R）∧（ts ∈ S）}
2.2 关系代数 4.广义笛卡尔积: 设:R、S为不同类关系，则结果为不同类关系： R×S={tr ts|（tr∈R）∧（ts ∈ S）} m元关系 R × S R . A 1 2 3 S b d d b d b b b d b b b c d d c d b d b d d b b 连接为 m+n元关系 n元关系 R A 1 2 3 b d b b c d d b S A 2 3 2 d 3 b

16 2.2 关系代数 记号：设t为R的元组变量 设：R（A1，A2，…An)=R(U) t[Ai] (Ai为属性) t[A] (A为属性集)
2.2 关系代数 记号：设t为R的元组变量 设：R（A1，A2，…An)=R(U) t[Ai] (Ai为属性) t[A] (A为属性集) 例：t [学号 ]--R中学号上的值 t [学号，姓名] 学号 姓名 年龄 t

17 σF(R)={t |(t∈R) ∧F( t )=true}
2.2 关系代数 R A 1 2 3 a f b 2 d c d e f g f 二、关系运算 1. 选择 (σ) ： 是关系行上的选择，产生同类关系。 σF(R)={t |(t∈R) ∧F( t )=true} 含义：由R中满足F条件的元组组成。 其中：F由属性名（值）、比较符、逻辑运算符组成。 例： σSage≥19(Student) 例： σA2>5 ∨A3 ≠“f”(R) √ √ √ √ σ A2>5 ∨ A3 ≠ “f” (R) A 1 2 3 b d c d e f g f

18 2.2 关系代数 (R) ∏ R A 1 2 3 a 3 f b 2 d c 2 d e 6 f g 6 f 3, 2 A
2.2 关系代数 R A 1 2 3 a f b 2 d c d e f g f 3, 2 ∏ A (R) 2. 投影运算(∏)： 是关系列的选择,产生不同类关系 ∏A(R)={t[A] |(t∈R) } 含义： R中取属性名表A中指定 的列，消除重复元组。 A 3 2 f 3 d 2 f 6 9801 1 95 2 90 9802 88 3 92 9803 Sno Cno Grade 80 …… SC表 例： ∏ Sno，Cno(SC) 用关系代数表示查询： 例：查选2号课程的学生记录。 例: 成绩在90分以上的学生号。 解： σCno=‘2’(SC) 解: ΠSno(σGrade≥90(SC))

19 R ⋈ S={tr ts|(tr∈R)∧(ts ∈ S) ∧ tr[A] θ ts[B]}
2.2 关系代数 3. 连接运算：连接也称为θ连接。它从两个关系的笛卡尔积中选取属性间满足一定条件的元组。 R ⋈ S={tr ts|(tr∈R)∧(ts ∈ S) ∧ tr[A] θ ts[B]} AθB ① ② 比较运算符 = σ R. A θ S. B(R×S) 含义：从R × S中选取R关系在A属性组上的值与S关系在B属性组上值满足θ关系的元组。 大于连接：θ为“>”的连接。 等值连接：θ为“=”的连接。 R ⋈ S= σR. A = S. B(R×S) A=B 例：

20 2.2 关系代数 R⋈S=Π属性名表 (σR.Bi=S.Bi (R×S)) 例: 3. 连接运算：
2.2 关系代数 3. 连接运算： 自然联接：设R、S有同名属性 Bi ( i=1,2….k) R⋈S=Π属性名表 (σR.Bi=S.Bi (R×S)) ②选同名属性值也相同的行 ①笛卡尔积 ③选择列并去掉重复属性 例:

21 2.2 关系代数 ΠA(σF (R)) 目标 A 条件 F 来源 R 例：查选修002号课程的学生姓名与年龄。
2.2 关系代数 ΠA(σF (R)) 学生-课程数据库表见教材: S(sno，sname，sex，age，dept) C(cno，cname， credit ， pcno) SC(sno，cno，grade) 目标 A 条件 F 来源 R 例：查选修002号课程的学生姓名与年龄。 ∏sname,age(S ⋈ σcno=‘002’ (SC)) 例: 查询至少选修了一门其直接先行课为005号课程的学生名。 ∏sname(σpcno=‘005’ (C ⋈ SC ⋈ S))

22 2.2 关系代数 R S 4. 除（Division） 关系代数定义了除运算。但实际应用中，当关系R真包含了关系S时，R÷S才有意义。
2.2 关系代数 R S 4. 除（Division） 关系代数定义了除运算。但实际应用中，当关系R真包含了关系S时，R÷S才有意义。 R能被S除尽的充分必要条件是： R中的属性包含S中的所有属性；R中有一些属性不出现在S中。 设R为r元、S为s元关系(r>s>0)，当关系R真包含了关系S时，R÷S可用下式计算： R÷S =Π1,2,…r-s(R)-Π1,2,…r-s((Π1,2,…r-s(R)×S)-R) 【例2.8】设R(S#,P#)、W1(P#)、W2(P#)、W3(P#)。 则R÷W1可表示为： ΠS#(R)-ΠS#((ΠS#(R)×W1)-R) 同理可列出另外两式。

23 2.2 关系代数 除法示例(例2.8): 例R÷Wi的运算结果可理解为：
2.2 关系代数 R S# P# S1 P1 S1 P2 S1 P3 S1 P4 S1 P5 S1 P6 S2 P1 S2 P2 S3 P2 S4 P2 S4 P4 S4 P5 除法示例(例2.8): W1 P# P1 W3 P# P1 P2 P3 P4 P5 P6 R ÷ W2 R ÷ W1 R ÷ W3 S# S1 S2 S# S1 S4 W2 P# P2 P4 S# S1 例R÷Wi的运算结果可理解为： R中包含Wi属性值的那些元组在R与Wi的属性名之差（即S#）上的投影。

24 2.2 关系代数 例：查所选课程包含学生210101所选全部课程的学生号和姓名。
2.2 关系代数 设学生-课程数据库(S、SC、C) 例：查所选课程包含学生210101所选全部课程的学生号和姓名。 ① ② 目标A1、A2 ∏ sno,sname( S) ⋈ (∏ sno，cno(SC) ÷ ∏ cno (σsno= (SC))) 例：查询选修了全部课程的学生学号与姓名。 (∏ sno，cno(SC) ÷ ∏ cno ( (C))) ∏ sno,sname( S) ⋈

25 2.2 关系代数 关系代数五种基本运算： 投影,选择,并,差,笛卡尔积 5种基本运算的作用： 1)关系的属性指定
2.2 关系代数 关系代数五种基本运算： 投影,选择,并,差,笛卡尔积 5种基本运算的作用： 1)关系的属性指定 ∏ A1 , A2 , …, An (R) 2)关系的元组选择 σF (R) 3)两个关系的归并 R1×R2 4)关系中元组的插入 R1∪R2 5)关系中元组的删除 R1－R2

26 2.2 关系代数 5. 扩充的关系运算： (2) 赋值: R <- S (3) 外连接 : R和S自然连接时，保留原该舍弃的元组，
2.2 关系代数 5. 扩充的关系运算： (1) 广义投影 : ΠE1, E2 …En(R) (2) 赋值: R <- S (3) 外连接 : R和S自然连接时，保留原该舍弃的元组， 同时在这些元组新增加的属性上填空值（NULL） (4) 半连接：R和S的自然连接只在关系R(或关系S)的 属性集上的投影。 R和S的半连接记为R ⋉ S 见教材例: (5) 聚集: G 聚集函数名(属性) (关系表达式)

27 5. 扩充的关系运算 Z Y X W a b c null b b f null c a d null null b c d
（6）外部并:由R和S中的所有属性(无重复)组成, 其元组由属于R或属于S的元组组成, 并在增加的属性填上空值。 说明：R、S可不同类 Z Y X W a b c null b b f null c a d null null b c d null a d b null e f g R与S的外部并 Y X W a b c b b f c a d (a) Z b c d a d b e f g (b) R S

28 ∏S.姓名( ) 5. 扩充的关系运算 （7）重命名 ①ρx(E):返回表达式E的结果，并把名字x赋给E。
②ρx(A1，A2，……，An)(E): 其含义为返回表达式E的结果，并把名字x赋给E， 同时将各属性更名为A1，A2，……，An。 例: 设R(姓名,课程,成绩),求数学成绩比王红高的学生名 (课程=‘数学’姓名=‘王红’(R)) ∏S.姓名( ⋈ (  课程=‘数学’ S(R)) R.成绩<S.成绩 )

29 2.3 查询优化 1.关系DB的查询优化及其目标 查询优化：从查询的多个执行策略中进行合理选择的过程。
2.3 查询优化 1.关系DB的查询优化及其目标 查询优化：从查询的多个执行策略中进行合理选择的过程。 目标：选择有效的策略，求得关系式的值，以提高其查询效率。 基本途径可以分为两种：用户处理和机器自动处理 查询优化器： 由DBMS自动生成并从中选取较优查询计划的程序。 查询的开销主要包括： 在单机数据库中：总代价 = I/O代价 + CPU代价 在多用户环境下：总代价 = I/O代价 + CPU代价 + 内存代价 在网络环境下： 总代价 = …… + 网络代价 查询的执行开销与多个因素有关： 软件环境、硬件环境、数据量、方法。

30 2.3 查询优化 关系数据库查询过程： DML处理器 关系代数语法树 查询优化器 查询计划 代码生成器 可执行代码 运行处理器
2.3 查询优化 关系数据库查询过程： DML处理器 关系代数语法树 查询优化器 查询计划 代码生成器 可执行代码 运行处理器 … 将查询转为 内部格式 …制定执行策略 …生成执行代码 …执行查询代码 DB (DD) 查询 结果 有关数据的 统计信息

31 例: Student表有l03个学生记录，每人平均选10门课， SC表共有1000*10=l04个选课记录。要求:
为什么要查询优化？ 例: Student表有l03个学生记录，每人平均选10门课， SC表共有1000*10=l04个选课记录。要求: 查学生“王林”选课成绩在85分以上的课程号。 SELECT cno FROM S，SC WHERE S.sno=SC.sno AND sname=‘王林’ AND grade > 85 ； 条件 F1 条件 F2 条件 F3 等价的关系代数表示： ① ∏Cno(σ F1 ∧F2 ∧F3 ( S×SC ) ) ② ∏Cno(σ F2 ∧F3 ( S ⋈ SC ) ) ③ ∏Cno(σF2 (S) ⋈ σF3 (SC) ) 哪种效率高？ 连接时间复杂度为： ① 103×104=O(107) ② 103×10=O(104) ③ 1×10=O(101)

32 对执行基本运算(关系扫描与连接)的次数进行分析：
① ∏Cno(σ F1 ∧F2 ∧F3 ( S×SC ) ) ② ∏Cno(σ F2 ∧F3 ( S ⋈ SC ) ) ③ ∏Cno(σ F2 (S) ⋈ σ F3 (SC) ) ①先在两表上做× ，产生1000*10000=107个连接记录，再在其上进行先σ后∏操作。其基本运算的次数为：3*107。 ②先在两个表上做⋈ ，产生1000*10=104个连接记录，再在其上进行先σ后∏操作。其基本运算的次数为：107+2*104。 ③先分别在两个表上做σ,再做 ⋈ ，产生1*10=10个连接记录，再在其上进行∏ 。其基本运算的次数为： *101。 连接时间复杂度为： ① O(107) ② O(104) ③ O(101)

33 4) 让投影同其前或其后的其它运算同时进行。 例： ∏ sno(S1-S2) 、 S1 ⋈ ∏ sno (S2)
2. 查询优化的一般策略 基本原则：尽量减少查询的中间结果 1) 尽可能先做选择、投影运算。 2) 在执行连接前对关系适当地预处理。 其方法有：a. 索引连接方法 SC表(m个记录) b. 排序合并连接方法 3) 同时进行投影运算和选择运算。 例： ∏ sno(σ grade≥90(SC)) 4) 让投影同其前或其后的其它运算同时进行。 例： ∏ sno(S1-S2) 、 S1 ⋈ ∏ sno (S2) 5) 合并笛卡尔积与其后的选择为连接运算。 例： σR. A > S. C (R×S)= R ⋈ S A>C 6) 找出公共子表达式。 O(n+m) …… … … … … 86002 86001 key 地址 …… Student (n个记录) sno sname …… 86001 王萧虎 86002 李云钢 86005 郭敏星 86006 高 灵 索引文件有序 主文件(随机)

34 ∏A1,A2…An (∏B1,B2….Bn (E)) ≡ ∏A1,A2…An (E)
2.3 查询优化 3. 关系代数表达式的等价规则 两个关系表达式El和E2是等价的，可记为E1≡E2。 常用的等价变换规则: 3）投影的串接定律 ∏A1,A2…An (∏B1,B2….Bn (E)) ≡ ∏A1,A2…An (E) 若不是子集？ 子集 4）选择的串接定律 σ F1(σ F2 (E)) ≡ σ F1 ∧F2 (E) 5）选择与投影的交换律(两种形式） （1）若F只涉及A1,A2…An 属性： ∏A1，A2…An (σ F (E)) ≡ σ F (∏ A1,A2…An (E)) 变两次投影为一次 多出条件F未涉及属性？

35 ∏A1,A2…An (σ F (E)) σ F (E1 × E2) ≡ σ F1 ( E1) × σ F2 ( E2)
3. 关系代数表达式的等价规则 意义:条件涉及的属性前移—例： ∏A (σR .A = S. B(R×S)) = ∏A (σR .A = S. B(∏A,B (R×S)) = ∏A ( σR .A = S. B (∏A (R)×∏B (S))) (2)若F中还涉及 其他属性B1，…. Bn： ∏A1,A2…An (σ F (E)) ≡ ∏A1，A2…An (σ F (∏A1，A2… An，B1 ，… Bn (E))) F中涉及的其他属性 6）选择与笛卡儿积的交换律 σ F (E1 × E2) ≡ σ F1 ( E1) × σ F2 ( E2) F1只涉及E1中属性 9）投影与笛卡儿积的交换律 ∏A1,A2…An，B1,…Bn (E1 × E2) ≡ ∏A1,A2…An (E1) × ∏B1,B2 … Bn(E2) 减少连接的元组数 是E1中属性 减少连接的数据量

36 例:Πcno(σ F1∧F2 ∧F3 (Student×SC)) //①式
3. 关系代数表达式的等价规则 11.选择对自然连接的分配律:若F中涉及属性都是El中属性,则： (1) σF(El ⋈ E2)≡ σF(El)⋈ E2 若F=F1∧F2,并且F1只涉及E1中、F2只涉及E2中的属性,则: (2) σF(E1 ⋈ E2)≡ σF1(El) ⋈σF2(E2) 12. 选择与连接操作的结合：设A1…,An是E1的属性,B1…,Bm 是E2的属性，F为形如：E1.AiθE2.Bj 所组成的合取式则： σF(El×E2)≡ El⋈ E2 F F1: S.sno=SC.sno 例:Πcno(σ F1∧F2 ∧F3 (Student×SC)) //①式 = Πcno(σ F2∧F3(σF1 (Student×SC ))) //用规则4得到 = Πcno(σ F2∧F3(Student ⋈ SC)) //用规则12得②式 = Πcno(σ F2(Student) ⋈ σ F3(SC)) //再用规则11得③式

37 ΠA 4. 关系代数表达式的优化算法 算法：关系表达式的优化。 五种基本运算表示 × 例: σF 输入：一个关系表达式的语法树。
S R ΠA σF 算法：关系表达式的优化。 输入：一个关系表达式的语法树。 输出：计算该表达式的程序。 五种基本运算表示 （1）用规则4把形如: σF1∧F2... (E) 变为: σF1(σF2...(E)) 再利用规则5～8 把每个选择运算尽量移到树叶。 （2）对每个投影利用规则3、5、9、l0，尽量把它移向树叶。 （3）利用规则3～5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。 (得到优化的基本语法树) （4）使用规则12 使选择运算与笛卡尔积结合成连接运算。 （5）对语法树中的内节点进行分组。 （6）找出查询树中的公共子树。 （7）输出由分组结果得到的优化语法树。 例:

38 ∏sno，sname(σ cname=‘DB’∧sex=‘女’ (SC ⋈ C ⋈ S))
4. 关系代数表达式的优化算法---- 举例 对P76表(S、SC、C)：查选修“DB”课程的女生学号及姓名。 ∏sno，sname(σ cname=‘DB’∧sex=‘女’ (SC ⋈ C ⋈ S)) = ∏sno, sname(σ cname=‘DB’∧sex=‘女’(∏L σ F (SC×C×S)) 其中：L代表无重复的全部属性； F代表： SC. cno=C. cno ∧SC. sno=S. sno ① ② ③ ④ (1)用规则4: 分解 F为①②③④。 对每个选择用规则尽量移到树叶。 (2)对每个投影用规则尽量移向树叶。

39 举例:∏sno, sname(σ cname=‘DB’∧sex=‘女’(∏LσF (SC×C×S))
语法树 ∏sno，sname ∏sno，sname σSC. sno=S. sno σcname=‘DB’∧sex=‘女’ ① ② ∏L × ？ σSC. cno=C. cno S σsex=‘女’ σSC. cno=C. cno ∧ SC. sno=S. sno ③ ④ × S × C SC × C σcname=‘DB’ SC

40 σSC. sno=S. sno σsex=‘女’ σSC. cno=C. cno σcname=‘DB’ × ∏sno，sname
5）选择与投影的交换律 (2)若F涉及属性B1…. Bn： ∏A1,A2…An(σF(E))≡∏A1…An(σF(∏A1… An,B1… Bn (E) )) × σSC. sno=S. sno SC ∏sno，sname σSC. cno=C. cno S σsex=‘女’ C σcname=‘DB’ 9）投影与笛卡儿积的交换律 ∏A1…An,B1,…Bn (E1 × E2) ≡ ∏A1…An (E1) × ∏B1… Bn(E2) F涉及属性及重复投影 先用规则5 再用规则9 ∏SC. sno ∏S.sno ,S.sname 条件F涉及属性 ∏SC. sno ,SC. cno ∏C. cno

41 σsex=‘女’ ⋈ σcname=‘DB’ σSC. sno=S. sno σsex=‘女’ σSC. cno=C. cno
举例 S σsex=‘女’ ∏S. sno，S. sname ∏sno，sname ⋈ SC ∏ SC. sno SC. cno ∏SC. sno σcname=‘DB’ C ∏C. cno 合并操作为⋈ ∏sno，sname (3)合成选择或投影 (4) 用规则12,将σ与×合成连接运算 (5) 对节点分组 (6)找出公共子树 (7)输出优化语法树 σSC. sno=S. sno × ∏S. sno，S. sname ∏SC. sno S σsex=‘女’ 一次扫描完成 σSC. cno=C. cno × σcname=‘DB’ C ∏C. cno SC ∏ SC. sno SC. cno

42 2.3 查询优化 5.查询优化的一般步骤： ①将查询表示成关系代数语法树。 ②根据变换规则将其转换成标准优化形式。 ③选择低层的操作算法。
2.3 查询优化 5.查询优化的一般步骤： ①将查询表示成关系代数语法树。 ②根据变换规则将其转换成标准优化形式。 ③选择低层的操作算法。 对语法树中的每一操作需要根据存取路径、数据的分布、聚簇等信息来选择具体的执行算法。 ④生成、选择查询计划。 用到查询优化的一般策略

43 第2章 关系数据库--- 要点 1、术语： 3、关系数据语言 模式、关系、关系DB 关系代数 元组、属性、域、码等 集合运算：
2、关系模型的组成 关系数据结构 关系操作集合 关系完整性约束 3、关系数据语言 关系代数 集合运算： (并、交、差、广义笛卡尔积) 关系运算： (投影、选择、连接和除运算) 4、关系DB的查询优化 目标、一般策略 优化方法 本章练习： 本章思考题： 1、关系模型的组成？ 2、自然连接与条件连接的区别？