最新数据库原理与技术课件PPT.ppt

《最新数据库原理与技术课件PPT.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据库原理与技术6.1查询处理概述查询处理是指从数据库中提取数据的一系列活动。主要包括：将用高层数据库语言表示的查询语句翻译为能在文件系统这一物理层次上实现的表达式为优化查询而进行各种转换查询的实际执行输入：SQL语句输出：满足查询条件的数据6.1查询处理概述（2）查询处理的基本步骤：1语法分析与翻译2优化3执行语法分析与翻译关系代数表达式执行计划优化器查询语句执行引擎查询结果有关数据的统计值数据6.2代价估算6.2.1用于估计代价的目录信息6.2.2查询代价的度量6.2.1用于估计代价的目录信息有关关系的统计信息nr：关系r中的元组数目br：含有关系r的元组的块

2、数目sr：关系r中一个元组的大小fr：关系r的块因子，即一个块中能存放的关系r的元组数若假定关系r的元组物理上存于同一文件中，则：br=nr/fr6.2.1用于估计代价的目录信息（2）有关关系的统计信息（续）V(A,r)：关系r中属性A所具有的不同值的数目。V(A,r)等于ПA（r）的大小若A为关系r的码，则V(A,r)=nrSC(A,r)：关系r的属性A的选择基数。表示关系r中满足属性A上的一个等值条件的平均元组数。若A为r的码属性，则SC(A,r)＝1若A为非码属性，并假定V(A,r)个不同的值在元组上均匀分布，则SC(A,r)＝(nr/V(A,r))。说

3、明：V(A,r)与SC(A,r)中的A可以是属性组。6.2.1用于估计代价的目录信息（3）有关索引的统计信息：fi：树形结构(如B＋树)索引i的内部结点的平均扇出。HTi：索引i的层数。对于关系r的属性A上所建的平衡树索引（如B＋树），HTi＝logfi(V(A,r))对于散列索引，HTi＝1LBi：索引i中最低层索引块数目，即索引叶层的块数。对于散列索引，Lbi就是索引中的块数。算法A的代价估计记为EA。6.2.2查询代价的度量查询代价：查询处理对各种资源的使用情况磁盘存取（简化为磁盘块传送数）CPU时间通信开销一个重要的影响因素：主存中缓冲区的大小M＊最

4、好的情形，所有的数据可以读入到缓冲区中＊最坏的情形，缓冲区只能容纳数目不多的数据块——大约每个关系一块。6.3基本运算的实现每一个基本的代数运算都有多种不同的实现算法。•适用于不同的情况等值条件，范围条件数据是聚集的，数据是非聚集的相关属性上有索引，相关属性上没有索引•执行代价不同6.3基本运算的实现（2）6.3.1选择运算6.3.2排序运算6.3.3连接运算6.3.4其他运算6.3.1选择运算全表扫描方法：依次访问表的每一个块，对于每一个元组，测试它是否满足选择条件。代价：E=br缺点：效率低优点：对关系的存储方式没有要求，不需要索引。适用于任何选择条件。6.

5、3.1选择运算（2）索引扫描条件：表在选择条件的属性上建有索引。方法：访问索引，根据索引项的指示去访问数据元组。无序索引：访问满足等值条件的元组有序索引：访问满足范围查找条件的一系列元组。6.3.1选择运算.（3）代价：利用主索引，等值比较：E=HTi+SC(A，r)/fr利用辅助索引，等值比较：E=HTi+SC（A，r）利用主索引，非等值比较：E=HTi+br/2（假设大约一半的元组满足比较条件）利用辅助索引，非等值比较：E=HTi+LBi/2+nr/26.3.1选择运算（4）复杂条件的选择合取：σθ1∧θ2∧…∧θn（r）析取：σθ1∨θ2∨…∨θn（r）

6、方法：利用一个索引进行合取选择。利用组合索引进行合取选择。利用多维索引进行合取选择。通过标识符的交集进行合取选择。通过标识符的并集进行析取选择。6.3.2排序运算排序运算在数据库中的重要意义：SQL查询可能要求有序的查询结果。事先对于作为运算对象的关系进行排序，可以提高某些关系运算（例如连接）的执行效率。内排序：文件较小，整个排序过程都能在内存中进行。外排序：文件较大，排序过程需要使用外存。6.3.2排序运算（2）外部排序-归并算法：（设内存中用于排序的缓冲区页面数为M）第一阶段，建立多个已排序的子表。每次读入M块，进行内排序，将长度为M块的已排序子表（共br/

7、M个）写到外存中。第二阶段，对已排序子表进行归并（可能需进行若干趟）。6.3.2排序运算（3）第二阶段，对已排序子表进行归并。第一趟：将头M-1个已排序子表的各块逐步读入内存，归并并输出。将下M-1个已排序子表的各块逐步读入内存，归并并输出。……已排序子表数目减少到原来的1/（M-1）第二趟：以第一趟的输出作为输入，重复过程。第三趟：以第二趟的输出作为输入，重复归并过程……直至归并为一个已排序文件。6.3.2排序运算（4）第二阶段第一趟：将头M-1个已排序子表的每一个的第一块读入内存的一个缓冲页repeat在所有缓冲页中的第一个元组中挑选排序码值最小的元组；把该

8、元组写到第