当前位置：文档之家 › 数据库第四章关系系统及其查询优化(精)

数据库第四章关系系统及其查询优化(精)

  • 格式：doc
  • 大小：50.50 KB
  • 文档页数：3

下载文档原格式

  / 3

合集下载

关系数据库查询优化.ppt

关系数据库查询优化.ppt
查询优化实例（8）
• （2）计算Q2的查询时间 • ●计算自然连接：计算自然连接时读取S与SC表
的方式与Q1一致，总读取块数为2100块，花费时 间为10 5秒，但其连接结果块数大为减少，总计 104个，所花时间为104/10/20s=50s。仅为Q1的 千分之一。 • ●作选择操作：做选择操作的时间为50s。 • ●做投影操作：与Q1类似，其时间可忽略不计 • 这样，Q2的全部查询时间≈ 105+50+50= 205s
查询优化实例（5）
• 其中读S表100块，读SC表20次，每次100 块 。 由 于 每 块 花 费 时 间 1/20 秒 ， 此 时 总 共 花费时间105秒。
• 连接后的元组数为103×104=107，设每块 （约）能装10个元组，则写入中间文件要 花106/20=5×104s。
第4章 关系数据查询优化： 4.1 查询处理与优化
第4章 关系数据查询优化： 4.1 查询处理与优化
查询优化实例（10）
• 从这3个计算时间可以看出，3种等价的查 询表达式具有完全不同的处理时间，它们 分别是10 5s、205s和10s，其差距之大令 人瞠目。
第4章 关系数据查询优化： 4.2 查询优化技术 4.2查询优化技术 4.2.1手动优化与自动优化
存放SC元组。 • ● 读/写一块磁盘的时间为1/20秒，即1秒读写20个磁盘
块。 • ● 为了简化起见，所有内存操作所花的时间忽略不计。
第4章 关系数据查询优化： 4.1 查询处理与优化
查询化实例（4）
• （1）计算Q1的查询时间 • ① 首先做笛卡尔乘积 • 将S与SC的每个元组相连接，其方法为先读入S中的50个
元组（5*10）至s表中的内存缓冲区，然后不断地将SC的 元组按100位一块读入后与S的元组相连接，直至读完所 有SC元组（共计100次）。这种操作内连接满100位后就 写中间文件一次。反复进行这样的操作，直至做完笛卡尔 乘积，此时读取的总块数为 • = 100+20×100=2100块

数据库第4章 关系系统及其优化课后题答案

数据库第4章 关系系统及其优化课后题答案

第4章关系系统及其优化1.试述查询优化在关系数据库系统中的重要性和可能性。

答：查询优化在关系数据库系统中有着非常重要的地位。

关系数据库系统和非过程化的SQL语言能够取得巨大的成功，关键是得益于查询优化技术的发展。

关系查询优化是影响RDBMS性能的关键因素。

优化对关系系统来说既是挑战又是机遇。

所谓挑战是指关系系统为了达到用户可接受的性能必须进行查询优化。

由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性。

这就为关系系统在性能上接近甚至超过非关系系统提供了机遇。

2.对学生-课程数据库有如下的查询：查询信息系学生选修的所有课程名称:SELECT Cname FROM St,Course,SCWHERE St.Sno=SC.Sno AND o=o AND St.Sdept=’IS’试画出用关系代数表示的语法树，并用关系代数表达式优化算法对原始的语法树进行优化处理，画出优化后的标准语法树。

答：关系代数表达式如下：πcname(бSt.sdept=’IS’(бst.sno=sc.Sno(бo=o(ST×SC×COURSE))) 用关系代数表示的语法树如下左图：用关系代数表达式优化算法对原关系代数表达式进行优化，优化后的关系代数表达式如下：πcname(бo=o((бSt.sno=sc.sno(πsno(бSt.sdept=’IS’(ST))×πsno,cno(SC))) ×πcno,cname(Course))优化处理后的标准语法树如上右图。

3.简述查询优化的一般准则。

答:1)选择运算应尽可能先做。

2）在执行连接前对关系适当地预处理。

3）把投影运算和选择运算同时进行。

4）把投影同其前或其后的双目运算结合起来。

5）把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算。

6）找出公共子表达式。

4.试述查询优化的一般步骤。

数据库原理关系系统及其查询优化

数据库原理关系系统及其查询优化

授课：XXX
15
对于Q2
读Student和SC不变，仍为105秒； 中间结果10,000个元组，读写共两次： S2= (10,000/10)*2/20=100s 总时间S1+S2，约205秒，降低了3个数量级！
2021/3/10
授课：XXX
16
对于Q3
先对SC进行选择，读100块，时间5s，满足 条件的元组50个，直接放在1个内存块中；
合成一个连接运算；
5. 把投影和其前或后的双目运算结合； 6. 找出公共子表达式。
2021/3/10
授课：XXX
20
4.2.4 等价变换规则
1. 连接、笛卡儿集交换律
E1×E2 = E2×E1
E1 E2 = E2 E1
E1 E2 = E2 E1
F
F’
2021/3/10
2021/3/10
授课：XXX
18
分析它们，从Q1到Q4,一个比一个效率高， 感性地告诉我们：笛卡儿集运算最好能 和相应的选择一起构成连接运算；选择 能早做就尽量早做；在双目运算前增加 投影，只保留必要的字段。
2021/3/10
授课：XXX
19
4.2.3 优化的一般策略
1.选择尽可能早做； 2.在连接前尽可能地预处理； 3.投影和选择同时进行； 4. 选择和它前面要进行的笛卡儿集运算结
接着读Student表，与内存块中的SC元组连接， 读Student表1遍时间为5s；
连接结果输出，不占I/O时间；
总时间10秒，再降低了1个数量级！
2021/3/10
授课：XXX
17
对于Q4
类似于Q3，但不需要读取SC和Student元组 全部属性，只读Student的Sno和Sname，SC 的Sno，读写块数进一步减少，从而I/O时间 还可减少

关系系统及其查询优化推选PPT资料

关系系统及其查询优化推选PPT资料
语言能够得到广泛的应用，关键得益于查询优 化技术的发展。 5. 优化的步骤
（１）将查询转换为内部表示－－语法树； （２）根据等价变换规则把语法树优化； （３）选择底层的操作算法； （４）生成查询的执行方案。
第四章 关系系统及其查询优化
4.2 查询优化
6. 查询优化的一般准则
（１）选择运算尽可能先做； （２）执行连接前进行排序或索引； （３）投影运算和选择运算同时进行； （４）投影与前后的双目运算结合； （５）选择与笛卡尔积结合为连接； （６）提取公共子表达式。
（８）选择与笛卡尔积的交换律
σF(E1×E2 ) ≡σF(E1 ) ×E2 σF(E1×E2 ) ≡E1×σF( E2 ) σF(E1×E2 ) ≡σF1(E1 ) ×σF2( E2 ) σF(E1×E2 ) ≡ σF2( σF1(E1 ) ×E2 )
第四章 关系系统及其查询优化
4.2 查询优化
7. 关系代数的等价变换规则
第四章 关系系统及其查询优化
4.2 查询优化
1. 实例
用SQL语言查询选修了2号课程的学生姓名：
FROM Student，SC WHERE Student.Sno=SC.Sno AND o=‘2’ 假定：数据库有1000个学生记录、10000个选课记录、选修2号课程的选 课记录有50个。
（５）选择与投影的交换律
σF(ΠA1,A2,…,An (E)) ≡ΠA1,A2,…,An(σF(E))
（６）选择与并的交换律
σF(E1∪E2 ) ≡ σF(E1 )∪σF(E2 )
第四章 关系系统及其查询优化
4.2 查询优化
7. 关系代数的等价变换规则
（７）选择与差的交换律
σF(E1－E2 ) ≡σF(E1 )－σF(E2 )

4关系系统及其查询优化全解

4关系系统及其查询优化全解

关系系统及其查询优化
do {输出R(i),s(p)到T} p=p+1; }
/*输出S(J)与r中除r(I)外的其他元组所组成的连接元组*/ K-I+1 while (K<=N) and (r(K)[a]=s(J)[b]) do {输出R(K),s(J)到T} KK+1; } II+1, J1+1; }
可以将2者组合成连接操作 对每个叶节点加必要的投影操作，以消除对查询无
用的属性。
关系系统及其查询优化
规则优化:结合存储路径的分析,讨论各种基本 操作执行的策略及选择原则.
选择操作的实现与优化:与选择条件\存取路径 选取元组占整个关系的比例有关系
最原始的实现方法是---顺序扫描(不需要特殊的存 取路径),适用于小的关系
关系系统及其查询优化
第三种情况:
先对SC表做选择运算：读SC表5秒。 读取S表：时间也是5秒 连接结果做投影： 总时间为：5+5=10秒
Q1 sname ( s.sname o'2' ( S SC))
Q2 Sname ( o'2'(sSC))
Q3 sname ( S o'2'( SC))
p. pname 'bolt '
P
s.city'najing ' sp.quan10000
S
Sp
关系系统及其查询优化
用投影操作取消对查询 Sname
无用的属性
sp.snum
sname ,snum
snum , pnum
pnum p. pname 'bolt '
关系系统及其查询优化

数据库系统中的关系代数与查询优化

数据库系统中的关系代数与查询优化

数据库系统中的关系代数与查询优化数据库系统是在计算机领域中广泛应用的一种数据管理系统。

在数据库系统中，关系代数是一种基本的操作语言，用于描述和操作关系型数据。

而查询优化则是通过优化查询语句的执行计划，提高查询性能和效率的过程。

本文将从关系代数和查询优化两个方面进行论述。

一、关系代数关系代数是数据库系统中描述和操作关系型数据的一种形式化语言。

它由一组基本操作组成，包括选择、投影、并、差、笛卡尔积和连接等。

下面将依次介绍这些基本操作：1. 选择操作：选择操作是从关系中选取满足指定条件的元组。

它通过使用谓词逻辑对关系进行过滤，只保留满足条件的数据。

2. 投影操作：投影操作是从关系中选取指定的属性列，生成一个新的关系。

它用于减少关系的大小和复杂度，以提高查询性能。

3. 并操作：并操作是将两个关系的元组合并成一个新的关系。

它常用于将满足不同条件的结果集进行合并。

4. 差操作：差操作是找出一个关系中的元组，在另一个关系中不存在的元组。

它用于比较两个关系之间的差异。

5. 笛卡尔积操作：笛卡尔积操作是将两个关系的每个元组组合起来，生成一个新的关系。

它在连表查询等场景中经常使用。

6. 连接操作：连接操作是将两个关系中满足指定条件的元组进行合并，生成一个新的关系。

它常用于关系之间的关联查询。

以上这些操作可以组合使用，形成复杂的查询语句，完成更多的逻辑需求。

关系代数提供了一种简洁而强大的方式来描述和操作数据库中的数据。

二、查询优化查询优化是数据库系统中的重要环节，它通过改变查询语句的执行计划，以提高查询性能和效率。

查询优化的目标是选择一个最佳的执行计划，使得查询能够在最短的时间内返回结果。

在查询优化过程中，首先需要对查询语句进行语法分析和语义分析，确定查询的逻辑意义。

然后，数据库系统会根据查询的复杂度、数据分布情况和数据库统计信息等因素，生成多个可能的执行计划。

接下来，数据库系统会进行执行计划的评估和选择。

这一过程使用了代价模型，通过估算每个执行计划的代价，选择具有最低代价的执行计划作为最终的执行方案。

数据库 4关系系统及其查询优化

数据库 4关系系统及其查询优化

4.6关系代数表达式的优化算法
我们可以应用前面讨论的变换法则来优化关系表达式。 使优化后的表达式能遵循4.2.3中的一般原则。例如把 选择和投影尽可能地早做(即把它们移到表达式语法树 的下部)。以下给出查询关系表达式的优化算法。 算法：关系表达式的优化。 输入：一个关系表达式的语法树。 输出：计算该表达式的程序。 方法： 1. 利用规则(4)把形如F1∧F2...∧Fn(E)变换为 F1(F2(...(Fn(E))...)) 2. 对每一个选择，利用规则(4)～（8）尽可能把它移到 树的叶端。
一个例子
例如STUDENTSC这样的自然连接，用索引连接方法的 步骤是： 1) 在SC上建立Sno的索引 2) 对STUDENT中每一个元组,由Sno值通过SC的索引 查找相应的SC元组 3) 把这些SC元组和STUDENT元组连接起来 这样Student表和SC表均只要扫描一遍。处理时间只是 两个关系大小的线性函数。
几点解释 · 为什么关系系统除了要支持关系数据结构外，还必 须支持选择、投影、连接运算呢？因为不支持这三种 关系运算的系统，用户使用仍不方便，不能提高用户 的生产率，而提高用户生产率正是关系系统主要目标 之一。 为什么要求这三种运算不能依赖于物理存取路径呢？ 因为依赖物理存取路径来实现关系运算就降低或丧失 了数据的物理独立性。不依赖物理存取路径来实现关 系运算就要求关系系统自动地选择路径。为此，系统 要进行查询优化以获得较好的性能。这正是关系系统 实施的关键技术。 要求关系系统支持这三种最主要的运算而不是关系代 数的全部运算功能，是因为它们是最有用的运算功能， 能解决绝大部分的实际回题。
（6）找出公共子表达式。 如果重复出现的子表达式的查询结果不是很大的 关系，并且从外存中读入这个关系比计算该子表达式 的时间少得多，则先计算一次公共子表达式并把结果 写入中间文件是合算的。 当查询的是视图时，定义视图的表达式就是公共子 表达式的情况。

数据库系统概论关系系统及其查询优化(精)

数据库系统概论关系系统及其查询优化(精)
An Introduction to Database System
实际系统的查询优化步骤
3. 选择低层的操作算法
对于语法树中的每一个操作

计算各种执行算法的执行代价 选择代价小的执行算法

4. 生成查询计划(查询执行方案)

查询计划是由一系列内部操作组成的。
An Introduction to Database System

关系完整性

实体完整性、参照完整性、用户自己定义的完整性
An Introduction to Database System
关系系统的定义
一个数据库管理系统可定义为关系系统，当且仅 当它至少支持：
1. 关系数据库（即关系数据结构） 系统中只有表这种结构 2. 支持选择、投影和（自然）连接运算 对这些运算不要求用户定义任何物理存取路径
对关系系统的最低要求
An Introduction to Database System
关系系统的定义
● ●
不支持关系数据结构的系统显然不能称为关系系统 仅支持关系数据结构，但没有选择、投影和连接运算 功能的系统仍不能算作关系系统。

原因：不能提高用户的生产率

支持选择、投影和连接运算，但要求定义物理存取路
例：求选修了课程Ｃ2的学生姓名
SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND o='2';
An Introduction to Database System
查询优化的必要性（续）
假设1：外存：
Student:1000条,SC:10000条, 选修2号课程:50条 假设2：一个内存块装元组:10个Student, 或100个SC, 内存中一次可以存放: 5块Student元组, 1块SC元组和若干块连接结果元组 假设3：读写速度：20块/秒 假设4：连接方法：基于数据块的嵌套循环法

第四章 关系系统及其查询优化精讲

第四章 关系系统及其查询优化精讲
第四章 关系系统及其查询优化
包括两个内容:一是关系系统(关系数据库系统的简称)，
二是关系系统的查询优化。
关系系统和关系模型是两个密切相关而又不同的概念。支持
关系模型的数据库管理系统称为关系系统。
4．1．1 关系系统的定义
一个系统可定义为关系系统，当且仅当它：
(1)支持关系数据库(关系数据结构)。
(2)支持选择、投影和(自然)连接运算，对这些运算不必要 求定义任何物理存取路径。
•数据操作（交互式或程序式） •完整性约束 •授权 •事务处理功能(事务开始、提交、回滚)
准则6 视图更新准则。所有理论上可更新的视图也应该
允许由系统更新。 •有的系统只允许对基本表更新，不支持对视图的更新。
•有的只允许对有限的一类视图如行列子集视图更新。
• 视图更新准则对于系统支持数据逻辑独立性是不可缺少的。
。
2．作选择操作
这一步读取中间文件花费的时间(同写中间文件一样)需5X104s 满足条件的元组假设仅50个，均可放在内存。
3．作投影 把第2步的结果在Sname上作投影输出，得到最终结果。
因此第一种情况下执行查询的总时间:
二、第二种情况
1．计算自然连接
为了执行自然连接，读取Student和SC表的策略不变，总的 读取块数仍为2100块花费105s。但自然连接的结果比第一种情 况大大减少，为104个。 每秒 20块 因此写出这些元组时间为104/10/20=50s
级上用一种方法(即表中的值)显式地表示．
•表名、列名和域名等都用系统内部表(即数据字典表)中的值 表示． •数据字典本身是一个动态的用来描述元数据的关系数据库． •满足信息准则不仅是为了提高用户的生产率
•另一个原因是使得DBA维护数据库的工作更简单、更有效。

关系系统及查询优化

关系系统及查询优化

• 选择、投影、连接运算是最有用的运算
二、关系系统的分类
前面定义的关系系统是关系系统的最小要求。 按照E.F.Codd的思想，可以把关系系统分类： 1、表式系统 仅支持表数据结构，不支持集合级的操作，不能算关系系统。 2、最小关系系统 支持关系数据结构和三种关系操作。（FoxBase, FoxPro等） 3、关系完备的系统 支持关系数据结构和所有的关系代数操作（功能上等价）。 4、全关系系统 支持关系模型的所有特征。即不仅是关系上完备的，而且支持数 据结构中域的概念，支持实体完整性和参照完整性。（目前大多 数关系系统已接近或达到了这个目标）
实例_查询优化的实例
• 读取Student和SC表的策略
Student表
第 一 个 五 块 第 二 个 五 块
第1－10个元组 第11－20个元组
内存缓冲区
10个Student元组 100个SC元组
SC表
第1－100个元组 第101－200个元组
第一块 第二块
… …
共 一 万
10个连接后的元组
…
共 一 千 个 学 生 录 记 录 记 课 个 选
优化的一般步骤
（1）把查询转换成某种内部表示 通常是（关系代数）语法树，以4.2.2节中的实例为例。 （2）把语法树转换成标准（优化）形式。
• 语法树最终的优化形式（运用了哪些变换规则？）
πSname σStudent.Sno=SC.Sno πSname,
SC.Sno
πSname
σStudent.Sno=SC.Sno
…
…
中间文件
第n块
Student表第1个五块的元组
SC表第1块的元组 SC表第2块的元组 …… SC表第n块的元组

数据库系统第四章 关系系统及其查询优化

数据库系统第四章 关系系统及其查询优化
定义的解释：



需要支持三种运算：方便用户的操作，这也 是关系系统的目标； 运算不能依赖物理路径：会降低或丧失物理 独立性； 只要求支持三种运算：它们是最有用的功能， 能解决绝大部分实际问题。
4.1.2 关系系统的分类
进行标识的三部分： Fra bibliotek数据结构S：structure 完整性I：integrity 数据操纵M：manipilation
第四章 关系系统及其查询优化
关系系统的定义和分类 关系系统的查询优化 （概念、基本原理和技术）
4.1 关系系统
第二章针对关系模型：

关系数据结构、关系的完整性、三类等价的 关系操作 支持关系模型的数据库管理系统。
关系系统：

问题：


关系模型中的各部分不是一样重要； 如何给出一个关系系统的最小要求以及分类 的定义。
四个步骤：

4.2 查询优化
查询的代价

I/O+CPU+内存 从DD中获取许多统计信息； DB的物理信息改变，能很好的适应； 可以考虑几百种不同的执行计划； 包括了很多复杂的优化技术。
系统优化的好处

4.2 查询优化
几个例子

SQL中：嵌套查询、连接查询、EXISTS的等 价形式 关系代数中：连接、选择、投影的顺序。
4.1.1 关系系统的定义
一个系统可定义为关系系统，当且仅当它：

支持关系数据库（关系数据结构）

用户看到的数据库中只是表这一种数据结构。

支持选择、投影和(自然)连接运算，且不要求 定义任何物理存取路径
不应要求用户建立索引才能支持； 不要求相应运算完全一样，只要有等价的功能就 可以。

第四章 关系数据库系统的查询优化

第四章 关系数据库系统的查询优化

34
（3）优化器可以考虑数百种不同的执 行计划，而程序员一般只能考虑有限 的几种可能性。
35
（4）优化器中包括了很多复杂的优化 技术，这些优化技术往往只有最好的 程序员才能掌握。
36
系统的自动优化相当于使得所有人 都拥有这些优化技术。
关系数据库查询优化的总目标是： 选择有效的策略，求得给定关系表 达式的值。
21
准则6 视图更新准则。
所有理论上可更新的视图也应该允 许由系统更新。 什么叫“一个视图是理论上可更新 的视图”呢？ 它是指对此视图的更新要求，存在 一个与时间无关的算法，该算法可以 无二义性地把更新要求转换为对基本 表的更新序列。
22
准则7 高级的插入、修改和删除操作。 关系系统的操作对象是单一的关 系。以关系为操作对象不仅简化了用 户查询，提高了用户生产率，而且也 为系统提供了很大的余地来进行查询 优化，提高了系统的运行效率。 它允许系统来选择存取路径，以便 得到最有效的运行代码。
17
准则2 保证访问准则。 依靠表名、主码和列名的组合，保证 能以逻辑方式访问关系数据库中的每个数 据项(分量值)。 保证访问准则表明关系系统所采用的 是关联寻址(association addressing)的 访问模式，而不是那种面向机器的寻址方 法。这是关系系统独有的方式。
18
准则3 空值的系统化处理。 全关系型的DBMS应支持空值的概念， 并用系统化的方式处理空值。 以往处理空值的办法常常是对每个允 许取空值的字段定义一种特殊的值来表示 空值。 这不是系统化的好办法。因为这样的 话，用户必须对每个字段或域采用不同的 方法来处理空值。这种方法必然会大大降 低用户生产率。
39
⑷ 生成查询计划。
查询计划也称查询执行方案，是由 一系列内部操作组成的。 这些内部操作按一定的次序构成查 询的一个执行方案。 通常这样的执行方案有多个，需要 对每个执行计划计算代价，从中选择 代价最小的一个。

关系数据库查询优化

关系数据库查询优化
数据库系统基础教程
第4章 关系数据库查询优化 章
第4章 关系数据查询优化： 4.1 查询处理与优化 章 关系数据查询优化：
4.1 查询处理与优化
查询要求 DML 处理器
关系数据查询过程
查询转换为内部格式
相关数据统计信息
关系代数语法树 查询优化器 制定执行策略
数据库 查询计划 代生成器 生成执行代码
第4章 关系数据查询优化： 4.1 查询处理与优化 章 关系数据查询优化：
查询优化实例（3） 查询优化实例（ ）
• 作如下的统一约定： 作如下的统一约定： • ● 设S有1000个元组，SC有10000个元组，其中修读 有 个元组， 有 个元组， 个元组 个元组 其中修读C5 的元组数为50。 的元组数为 。 • ● 磁盘中每个物理块能存放 个S元组，或100个SC元组。 磁盘中每个物理块能存放10个 元组 元组， 元组。 个 元组 • ● 内存有 个块的缓冲区，其中 块可以存放 元组，1块 内存有6个块的缓冲区 其中5块可以存放 元组， 块 个块的缓冲区， 块可以存放S元组 存放SC元组 元组。 存放 元组。 • ● 读/写一块磁盘的时间为 写一块磁盘的时间为1/20秒，即1秒读写 个磁盘 秒读写20个磁盘 写一块磁盘的时间为 秒 秒读写 块。 • ● 为了简化起见，所有内存操作所花的时间忽略不计。 为了简化起见，所有内存操作所花的时间忽略不计。
第4章 关系数据查询优化： 4.1 查询处理与优化 章 关系数据查询优化：
查询优化实例（7） 查询优化实例（ ）
• ③ 最后做投影操作 • 第二项操作的结果满足条件的元组数为50个，它 第二项操作的结果满足条件的元组数为 个 们可全部存放在内存。对他们在S上做投影操作 上做投影操作， 们可全部存放在内存。对他们在 上做投影操作， 由于是在内存中进行，其时间可忽略不计。 由于是在内存中进行，其时间可忽略不计。这样 Q1的全部查询时间约为 的全部查询时间约为105+2×5×104 ≈ 105s。 × × 。 的全部查询时间约为 注意到一天为86400s，所以这个运算需要超过一 注意到一天为 ， 天的时间来完成。 天的时间来完成。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第四章关系系统及其查询优化
习题
1．试给出各类关系系统的定义：最小关系系统；关系完备上的系统；全关系型的关系系统。

2．试述全关系型系统应满足的十二条准则，以及十二条基本准则的实际意义和理论意义。

3．试述查询优化在关系数据库中的重要性和可能性。

4．对学生-课程数据库有如下的查询：
SELECT Cname
FROM Student，Course，SC
WHERE Student。

Sno=SC。

Sno
AND SC。

Cno=Course。

Cno
AND Student。

Sdept=’IS’；
此查询要求信息系学生选修了的所有课程名称。

试画出用关系代数表示的语法树，并用关系代数表达式优化算法对原始的语法树进行优化处理，画出优化后的标准优化树。

5．试述查询优化的一般准则。

6．试述查询优化的一般步骤。

参考答案
1．答：最小关系系统。

一个系统可定义为最小关系系统，当且仅当它：
（1）支持关系数据库（关系数据结构），从用户观点看，关系数据库由表构成，并且只有表这一种结构
（2）支持选择、投影和（自然）连接运算，对这些运算不必要求定义任何物理存取路径。

关系上完备的系统：
这类系统支持关系数据结构和所有的关系代数操作（或者功能上与关系代数等价的操作）。

全关系型的关系系统：
这类系统支持关系模型的所有特征。

即不仅是关系上完备的而且支持数据结构中域的概念，支持实体完整和参照完整性。

2．答：关系模型的奠基人E。

F。

Codd具体地给出了全关系型的关系系统应遵循的十二条基本准则。

从实际意义上看，这十二条准则可以作为评价或购买关系型产品的标准。

从理论意义上看，它是对关系数据模型具体而又深入的论述，是从理论和实际紧密结合的高度对关系型DBMSR 评述。

准则0 一个关系型的DBMS必须能完全通过它的关系能力来管理数据库。

准则1信息准则。

关系型DBMS的所有信息都应在逻辑一级上用一种方法即表中的值显式地表示。

准则2保证访问准则。

依靠表名、主码和列名的组合，保证能以逻辑方式访问关系数据库中的每个数据项（分量值）。

准则3空值的系统化处理。

全关系型的DBMS应支持空值的概念，并用系统化的方式处理空值。

准则4基于关系模型的动态的联机数据字典。

数据库的描述在逻辑级应该和普通数据采用同样的方式，使得授权用户可以使用查询一般数据所用的关系语言来查询数据库的描述信息。

准则5统一的数据语言准则。

准则6视图更新准则。

所有理论上可更新的视图也应该允许由系统更新。

准则7高级的插入、修改和删除操作。

准则8数据物理独立性。

无论数据库的数据在存储表示或存取方法上作任何变化，应用程序和终端活动都保持逻辑上的不变性。

准则9数据逻辑独立性。

当对基本关系进行理论上信息不受损的任何改变时，应用程序和终端活动都保持逻辑上的不变性。

准则10数据完整性的独立性。

关系数据的完整性约束条件必须是用数据库语言定义并存储在数据字典中的，而不是在应用程序中加以定义的。

准则11分布独立性。

关系型DBMS 具有分布独立性。

准则12无破坏准则。

如果一个关系系统具有一个低级（指一次处理一个记录）语言，则这个低级语言不能违背或绕过完整性准则。

3．答：重上性：关系系统的查询优化既是RDBMS 实现关键技术又是关系系统的优点所在。

它减轻了用户选择存取路径的负担。

用户只上提出”干什么”，不必指出”怎么干”。

查询优化的优点不仅于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的”优化”做得更好。

可能性：
这是因为：
（1）优化器可以从数据字典中获取许多统计信息，例如关系中的元组数、关系中每个属性值的分布情况、这些属性上是否有索引、是什么索引（B+树索引还是HASH 索引或惟一索引或组合索引）等。

优化器可以根据这些信息选择有效的执行计划，而用户程序则难以获得这些信息。

（2）如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。

在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。

（3）优化器可以考虑数十甚至数百种不同的执行计划，从中选出较优的一个，而程序员一般只能考虑有限的几种可能性。

（4）优化器中包括了很多很复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。

系统的自动优化相当于使得所有人都拥有这些优化技术。

4．答： 结果Join(Student.Sno=Sc.Sno)Join(o)Select(Student.Sdept=’IS’
最初的语法树Project(Cname)Course Student SC
Cname
π.''
Student Sdept IS δ=..Sc Cno Course Cno δ=⨯
..Student Sno Sc Sno
δ=Course
⨯Student SC 关系代数语法树
Cname
π..Sc Cno Course Cno
δ=..Student Sno Sc Sno
δ=Course ⨯
.''
Student Sdept IS δ=⨯
SC Student
优化后的语法树
5．答：下面的优化策略一般能提高查询效率：
（1）选择运算应尽可能先做；
（2）把投影运算和选择运算同时进行；
（3）把投影同其或其后的双目运算结合起来执行；
（4）把某些选择同在它前面执行的笛卡儿积结合起来成为一个连接运算；
（5）找出公共子表达式；
（6）选取合适的连接算法。

6．答：各个关系系统的优化方法不尽相同，大致的步骤可以归纳如下：
（1）把查询转换成某种内部表示，通常用的内部表示是语法树。

（2）把语法树转换成标准（优化）形式。

即利用优化算法，把原始的语法树转换成优化的形式。

（3）选择低层的存取路径。

（4）生成查询计划，选择代价最小的。