山 东 理 工 大 学 教 案
《数据库系统原理》教案
第  13  次课
教学课型：理论课□ 实验课□ 习题课□  实践课□  技能课□  其它□
主要教学内容（注明：* 重点    # 难点 ）：
第四章 关系系统及其查询优化
一、 关系系统的定义和分类
二、 关系系统的查询优化的目的
三、关系代数等价变换规则（*）
四、优化的一般步骤
五、优化的标准语法树的画法（实际优化的转化步骤）：（*、#）
◆ 根据题目要求写出SQL查询语句
◆ 根据SQL语句写出关系代数表达式
◆ 画出关系代数表达式的语法树
◆ 采用优化准则和关系代数等价变化规则写出优化关系代数表达式
◆ 根据优化关系代数表达式画出标准（优化）形式语法树
教学目的要求：
1、理解关系系统的查询优化的目的
2、掌握关系代数等价变换规则
3、掌握优化的标准语法树的画法
教学方法和教学手段：
教学方法主要是讲授、示教。
教学手段：板书和多媒体相结合。
讨论、思考题、作业：
作业：习题166—167页  4、 5、 6
参考资料：
王珊，陈红：数据库系统原理教程  清华大学出版社，2000
刘方鑫：数据库原理与技术        电子工业出版社，2002
丁宝康：数据库原理              经济科学出版社，2000
第四章 关系系统及其查询优化
学习目标
◆ 掌握关系系统的定义和分类
◆ 理解关系系统中查询优化的必要性及查询优化的策略、方法和步骤
◆ 关系代数的等价变换规则
◆ 查询优化的一般步骤
◆ 根据关系代数表达式能画出原始语法树
◆ 能用优化算法对原始的语法树进行优化处理，画出优化后的标准（优化）形式
本章难重点
◆ 查询优化的必要性
◆ 计算每种关系代数的代价
◆ 把关系代数查询转换成原始语法树
◆ 在原始语法树的基础上进行优化算法，生成优化后的语法树
◆ 考试类别：P166页：题4
本章主要内容：
◆ 关系系统的定义和分类
◆ 关系系统中查询优化的概念
◆ 查询优化的必要性
◆ 查询优化的基本原理和技术
4．1  关系系统
⏹ 能够在一定程度上支持关系模型的数据库管理系统是关系系统。
⏹ 由于关系模型中并非每一部分都是同等重要的，并不苛求一个实际的关系系统必须完全支持关系模型。
⏹ 关系数据结构：域及域上定义的关系
⏹ 关系操作：并、交、差、广义笛卡尔积、选择、投影、连接、除等
⏹ 关系完整性：实体完整性、参照完整性、用户自己定义的完整性
4．1．1  关系系统的定义
一个数据库管理系统可定义为关系系统，当且仅当它至少支持：
⏹ 关系数据库（即关系数据结构），从用户观点看，数据库系统中只有表这一种结构。
⏹ 支持选择、投影和（自然）连接运算，对这些运算不要求用户定义任何物理存取路径
注意：这是对关系系统的最低要求
定义说明如下：
A、如果一个系统仅支持关系数据库而没有选择、投影和连接运算功能，不能称为关系系统。
原因：因为不支持这三种关系运算的系统，使用仍不方便，不能提高的生产率，而提高生产率正是关系系统的主要目标之一。
B、一个系统虽然支持这三种运算，但要求定义物理存取路径，例如要求用户先建立索引才能按索引字段检索记录，也不能称为关系系统。
原因：因为依赖物理存取路径来实现关系运算就降低或丧失了数据的物理独立性。
实际上并不要求关系系统的选择、投影、连接运算和关系代数的相应运算完全一样，而只要求有等价的这三种运算功能。
C、要求关系系统支持这三种最主要的运算而不是关系代数的全部运算功能，是因为选择、投影、连接是关系系统中最有用的运算功能，能解决绝大部分的实际问题。
总之，要求关系系统即要支持关系数据结构，又支持选择、投影和连接是，这是为了使用方便和数据易用。
4．1．2  关系系统的分类
分类依据：支持关系模型的程度。
1、表式系统：仅支持关系(即表)数据结构，不支持关系集合级的操作。例如：倒排表列系统、EXCEL等。
2、(最小)关系系统：仅支持关系数据结构，支持选择、投影、连接关系操作
。例如：FoxBASE，FoxPro等。
3、关系完备的系统：支持关系数据结构、支持所有的关系代数操作，功能与关系代数等价。例如：PB、VFP、VB等。
4、全关系系统：支持关系模型的所有特征。特别是数据结构中域的概念、实体完整性和参照完整性。目前，大型关系系统（例如oracle）已不同程度上接近或达到了这个目标。
图中的圆表示关系数据模型。每个圆分为三部分，分别表示关系模型的三个组成部分：
结构S(Structure)、数据操纵M(Manipulation)、完整性I(Integrity)，图中阴影部分表示各类系统支持模型的程度。
小结如下：
数据结构
数据操作
完整性
表式系统
表
╳
╳
(最小)关系系统
表
选择、投影、连接
╳
关系完备的系统
表
√
╳
全关系系统
表
√
√
4．2  关系数据库系统的查询优化
查询优化的必要性：查询优化是影响RDBMS性能的关键因素。
查询优化的可能性：关系数据语言的级别很高，使DBMS可以从关系表达式中分析查询语义。
4．2．1  关系系统的查询优化
● 关系系统的查询优化是RDBMS实现的关键技术，又是关系系统的优点所在。它减轻了用户选择存取路径的负担。用户只要提出“做什么”，不必指出“怎么做”。
● 由DBMS进行查询优化的好处
⏹ 用户不必考虑如何最好地表达查询以获得较好的效率。
⏹ 系统可以比用户程序的优化做得更好。
(1)优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息
。例如关系中的元组数、关系中每个属性值的分布情况等。优化器可以根据这些信息选择有效的执行计划。
(2)如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往不太可能。
(3)优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。
(4)优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。
● 关系数据库查询优化的总目标：选择有效的策略，求得给定关系表达式的值。
● 实际系统对查询优化的四个步骤：
①将查询转换成某种内部表示，通常是语法树。
②根据一定的等价变换规则把语法树转换成标准(优化)形式。
③选择低层的操作算法。
对于语法树中的每一个操作：
⏹ 计算各种执行算法的执行代价
⏹ 选择代价小的执行算法
④生成查询计划。
● 查询计划也称查询执行方案，是由一系列内部操作组成的。
● 这些内部操作按一定的次序构成查询的一个执行方案。
● 通常这样的执行方案有多个，需要对每个执行计划计算代价，从中选择代价最小的一个。
常用系统模型的代价计算如下：
A、集中式数据库
单用户系统  总代价 = I/O代价 + CPU代价
多用户系统  总代价 = I/O代价 + CPU代价 + 内存代价
B、分布式数据库
总代价=I/O代价+CPU代价+ 内存代价+通信代价
4.2.2 查询优化的必要性
例1：对第3章的表求选修了2号课程的学生姓名。
用SQL语言表达如下：
SELECT  ST.Sname  FROM  ST，SC
WHERE  ST.Sno=SC.Sno AND SC.Cno=’2’
假设1：ST:1000条，SC:10000条，选修2号课程：50条
假设2：一个内存块装元组10个St或100个SC,内存中一次可以存放5块St元组和1块SC元组以及若干块连接结果元组
假设3：读写速度20块oracle数据库怎么查询表/秒
假设4：连接方法是基于数据块的嵌套循环法
⏹ 在内存中尽可能多的装入（如St）的若干块元组，留出一块存放另一个表（SC）的元组，然后把SC中的每个元组和St中的每个元组连接，连接后的元组装满一块后写到中间文件上。
⏹ 再从SC中读入一块和内存中的St元组连接，直到SC表处理完，这时再一次读入若干块St元组，读入一块SC元组 ，重复上述过程，直到把St表处理完。
系统可以用多种等价的关系代数表达式来完成这一查询
查询方式1：Q1=πsname(бst.sno=sc.sno∧sco=’2’(St×Sc))
查询方式2：Q2=πsname(бsco=’2’(St∞Sc))
查询方式3：Q3=πsname(St∞бsco=’2’(Sc))
下面将看到由于查询执行的策略不同，查询时间相差很大。
一、查询方式1：Q1=πsname(бst.sno=sc.sno∧sco=’2’(St×Sc))
1．计算广义笛卡尔积（St×Sc）
读取总块数= 读St表块数 + 读SC表遍数*每遍块数
=1000/10+(1000/(10×5))×(10000/100)=100+20×100=2100
读数据时间：2100/20=105秒
连接后的元组数为1000*10000=107。设每块能装10个元组，共用107/10=106块，写出这些块用106/20=5*104S（秒）
本次连接操作所用总时间是：105S+5*104S
2．作选择操作（бst．sno=sc．sno∧sco=’2’）
依次读入连接后的元组，这一步读取中间文件花费的时间(同写中间文件一样)也是5*104S。选择满足条件的元组假设仅50个，均可放在内存，假定选择操作的内存处理时间忽略。
3．作投影（πsname）
把第2步的结果在Sname上作投影输出，得到最终结果。
◆ 本次查询总时间是：
105S+2*5*104S= 105＋50000＋50000秒= 27.8小时
◆ 其中内存处理（选择和投影）时间均忽略不计。
二、第二种情况：Q2=πsname(бsco=’2’(St∞Sc))
1．计算自然连接(St∞Sc)
为了执行自然连接，读取St和SC表的策略不变，总的读取块数为2100块花费105S。
但自然连接的结果比第一种情况大大减少为104个元组（学号相等元组），因此写出这些元组时间为104／10／20=50S(每块能装10个元组, 每秒读/写20块)，仅为第一种情况的千分之一。
计算自然连接的总时间是105S+50S
2．读取中间文件块花费时间也为50S，再执行选择运算。
（бsco=’2’）
3．把第2步结果投影输出。（πsname）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。