第4章 关系系统及其查询优化.ppt

1、第4章 关系系统及其查询优化,4.1 关系系统 4.2 关系系统的查询优化 4.3 查询优化的一班策略,4.1 关系系统,一、关系系统的定义 一个系统可定义为关系系统，当且仅当它支持： (1) 关系数据库 (2) 支持选择、投影和(自然)连接运算，对这些运算不必要求定义任何物理存取路径。,二、关系系统的分类 1、表式系统 仅支持关系数据结构，不支持集合级的操作。(表式系统不能算关系系统。) 2、(最小)关系系统 仅支持关系数据结构和三种关系操作。 (许多微机关系系统如FoxPro等就属于这一类。) 3、关系完备的系统 支持关系数据结构和所有的关系代数操作。(目前，DB2，SOL/DS,ORAC

2、LE等许多系统就属于这一类。) 4、全关系系统 这类系统支持关系模型的所有特征。特别是：数据结构中域的概念，实体完整性和参照完整性。(目前，大多数关系系统已不同程度上接近了这个目标。,4.2 关系系统的查询优化 查询优化在关系数据库中有着非常重要的地位。关系查询优化是影响关系数据库管理系统性能的关键因素。关系系统为了达到用户可接受的性能必须进行查询优化。而关系数据语言的级别很高，使关系系统可以从关系表达式中分析查询予以，提供了执行查询优化的可能性。 查询优化的总目标：选择有效的策略，求得给定的关系表达式的值。,一、一个实例 eg:求选修了课程C2的学生姓名。用SQL语言表达： SELECT S

3、.SN FROM S,SC WHERE S.S#=SC.S# AND SC.C#=C2; 假定学生课程数据库中有1000个学生记录，10000个选课记录，其中选修C2课程的选课记录为50个。 系统可用多种等价的关系代数表达式来完成这一查询 Q1= SN(S.S#=SC.S#SC.C#=C2（SSC） ) Q2= SN(SC.C#=C2（SSC） ) Q3= SN(SSC.C#=C2（SC） ) 分析以上几种等价的关系代数表达式，可以看到由于查询执行的策略不同，查询时间相差很大。 （一）第一种情况,1、计算广义笛卡儿积 设一个块能装10个S元组或100个SC元组，在内存中存放5块S元组1块SC元

4、组，则读取总块数为： 1000/101000/(105)10000/1002100块 其中读S表100块，读SC表20遍，每遍100块，若每秒读20块，则总计要花105秒。 连接以后的元组数为103104，设每块能装10个元组，则写出这些块要花106/205 104秒。 2、作选择操作 依次读入连接后的元组，按照选择条件选取满足要求的记录，假定内存处理时间忽略。这一步读取中间文件花费的时间需5 104秒(同写中间文件一样)。满足条件的元组假设仅50个，均可放在内存。 3、作投影操作 把第2步的结果在SN上作投影输出，得到最终结果。 执行查询的总时间为25 104105 105秒,（二）第二种情

5、况 1、计算自然连接 读取S和SC表的策略不变，总的读取块数仍为2100块花费105秒，但自然连接的结果比第一种情况大大减少，为104个，因此写出这些元组时间104/10/2050秒。 2、读取中间文件块 ，执行选择运算，花费时间也为50秒。 3、把连接结果投影输出。 第二种情况总的执行时间1055050 205秒。,（三）第三种情况 1、先对SC表作选择运算，只需读一遍SC表，存取100块，花费时间为5秒。因为满足条件的元组仅50个，不必使用中间文件。 2、读取S表，把读入的S元组和内存中的SC元组作连接，也只需读一遍S表共100块，花费时间为5秒。 3、把连接结果投影输出。 第三种情况总的执行时间5510秒。 这个简单的例子才分说明了查询优化的必要性，同时也给出一些查询优化方法的初步概念。如当有选择和连接时，应当先做选择，这样参加连接的元组就可以大大减少。,4.3 查询优化的一般策略 1、选择运算应尽可能先做。 2、在执行连接前对关系适当地预处理。预处理方法主要有两种，对关系排序和在连接属性上建立索引。 3、把投影运算和选择运算同时进行。