第11章 关系代数操作的实现算法有效地处理用高级查询语.ppt

第11章关系代数操作的实现算法有效地处理用高级查询语言编写的用户查询是数据库管理系统的主要任务 对关系数据库系统而言 需要从两个方面讨论查询处理 第一方面是各种关系代数操作的算法及其复杂性分析 第二方面是产生逻辑优化的关系代数表达式或其它形式的查询计划 本章讨论第一个方面的工作 下一章讨论第二个方面的工作 第一节查询的处理过程第二节选择操作的实现算法第三节笛卡儿乘积的实现算法第五节投影操作的实现算法第六节集合的并交差实现算法 K 第一节查询的处理过程查询是由高级查询语言 如SQL 表示的对数据库的一系列操作 下边是查询处理的基本流程 扫描与语法分析 查询优化 查询代码生成 查询执行 查询 查询的内部表示 查询的执行计划 查询计划的执行代码 查询结果 1 语法检查 2 语义有效性检查 3 完整性安全性检查 4 产生查询的内部表示 树 图 确定优化的执行策略 产生优化的执行计划 组合DBMS提供的各种操作算法 产生计划的执行代码 控制执行查询计划 产生查询结果 K1 层次和网状数据库的查询语言是面向过程的语言 查询优化由用户程序负责 关系数据库的查询语言是非过程性的语言 查询优化应该由DBMS负责 但因最优化需要大量信息和相当耗时 故仅产生效率较高的执行计划 以下假设 每个关系储存在一个文件中 每个文件仅储存一个关系 下边的参数是本章经常使用的 TR关系R的元组数BR磁盘块数IR每个元组的字节数M主存缓冲区的块数b每个磁盘块字节数 K11 在分析关系代数各种操作的算法时 我们用对磁盘的存取块数来度量一个算法的复杂性 第二节选择操作的实现算法选择操作是在关系R中抽取满足条件C的元组 其SQL表示形式为 K2 select fromRwhereC1andC2orC3 式中第一子式 select 的含义是返回指定的属性 第二子式 from 指出参加选择操作的关系 第三子式 where 指出选择操作的条件 选择条件可以是简单条件 也可以是复合条件 即把一组简单条件用逻辑运算符and or not连接而成的条件 如果逻辑运算符仅是and 则复合条件称为合取条件 一般的DBMS都提供多种选择算法 不同的算法适用于不同的使用环境 有些算法要求参加运算的关系具有指定的存储结构或存取方法 下边介绍选择操作的实现算法 接下页 具有简单条件 条件中仅包含关系的一个属性 的选择算法1 线性搜索 按原始顺序扫描关系 取出满足条件的元组 2 二分搜索 要求关系已排序 并且选择条件是排序域上的等值比较 N元组的关系 其搜索时间复杂性是O log2N 3 主索引或HASH搜索 要求选择条件是主索引属性或HASH属性上的等值比较 4 用主索引查找多个元组 若条件是主属性上的非等值比较 则用等值比较可找出所有满足非等值比较条件的元组 5 使用聚集索引按等值比较条件寻找多个元组 6 使用B 树索引搜索 具有合取条件 一组简单条件用and连接而成 的选择算法7 合取选择算法 先按一个简单条件用前述方法选择 然后检查是否满足其它条件 8 复合索引算法 若合取条件都是等值比较 可考虑使用有关属性上的复合索引 9 指针交集算法 若合取条件是等值比较 可用各索引域的辅助索引得到元组指针集合 然后取这些集合的交集 K21 第三节笛卡儿乘积的实现算法设 关系R和S的元组字节数分别是IR和IS 元组数目分别是TR和TS 则笛卡儿乘积R S的元组的字节数是IR IS 元组数目是TRTS 空间字节数是TRTS IR IS 占用磁盘块数是BR S TRTS IR IS b 其中b是磁盘块的容量 因此 笛卡儿乘积是一个非常耗时的操作 以下介绍笛卡儿乘积的四种实现算法 在选择算法时 要分析各种算法在访问磁盘时的复杂性和对内存缓冲区的要求 1简单算法2主存算法3半主存算法4大关系算法 K3 1笛卡儿乘积的简单算法这种算法仅要求主存提供能容纳两个磁盘块数据的缓冲区 关系R和S各读一块到主存缓冲区 参加笛卡儿乘积运算 通过嵌套循环完成R S 算法定义为 R S K31 输出R S 对结果关系result初始化 forR每块RBdo读RB入主存 forS每块SBdo读SB入主存 在主存完成RB和SB的元组笛卡儿乘积 产生元组存入result endfor endfor 返回result 由于每读R一块 均扫描S一遍 故整个过程中 R读了一遍 而S读了BR遍 从而磁盘存取量为BR BRBS BR S 其中 BR S TRTS IR IS b是输出结果的写盘块数 动画 2笛卡儿乘积的主存算法这种算法假设内存缓冲区有足够的容量 能一次性地把关系R和S都读入主存 完成笛卡儿乘积运算 整个过程 两个关系各读了一遍 这种算法的磁盘存取量为BR BS BR S 其中BR S TRTS IR IS b是写盘块数 算法的形式定义为 R S R S K32 结果关系result初始化 把R和S读入主存 for主存中R的每个元组rdofor主存中S的每个元组sdo产生元组 rs 存入result endfor endfor 返回result 动画 3笛卡儿乘积的半主存算法这种算法假定内存缓冲区比较大 把关系S一次性读入主存 而R则每次仅读一块到主存参加笛卡儿乘积运算 跟主存算法相同 整个过程 两个关系各读了一遍 磁盘的存取量为BR BS BR S 其中BR S TRTS IR IS b是写盘块数 算法的形式定义为 R S R S K33 result初始化 把S读入主存SB forR每块RBdo读RB入主存 在主存完成RB和SB的元组笛卡儿乘积 产生元组存入result endfor 返回result 该算法要求主存缓冲区能容纳BS 1个磁盘块 从磁盘存取量式子看到 R和S是对称的 若把关系R和S的地位对调 磁盘存取量并没有变化 但对主存缓冲区的要求却有所不同 动画 4笛卡儿乘积的大关系算法设主存缓冲区的容量是M 即能容纳M个磁盘块的数据 如果22的资源优势 采用比简单算法效率更高的算法 大关系算法分配给R和S的主存空间分别是1和M 1 算法如下 R S R S K34 把S分为BS M 1 个子集Si 每子集有M 1块 对结果关系result初始化 fori 1toBS M 1 do把Si读入主存 forj 1toBRdo把R的第j块读入主存 在主存完成R S 产生的元组存入result endfor endfor 由于S读了一遍 R读了BS M 1 遍 故磁盘存取量为BRBS M 1 BS BR S 其中BR S TRTS IR IS b是写盘块数 动画 由于两个关系的连接操作实际上是笛卡儿乘积后再按 条件选择元组 故连接操作的实现算法可在笛卡儿乘积算法基础上略加修改而成 由于选择操作和两个元组的接驳均在主存进行 故算法的修改并不改变读盘的复杂性 但结果输出量却有不同程度的减少 例如 基于笛卡儿乘积大关系算法的连接操作 读盘的块数仍是BRBS M 1 BS 但连接结果的写盘块数却是B BR S 是等值比较符的连接操作称为等值连接 两个关系同名属性的等值连接称为自然连接 通过修改关系某些属性名 可以把等值连接转化为自然连接 本节仅考虑自然连接 一 连接操作结果的估计二 连接操作实现算法 第四节连接操作的实现算法考虑关系R S关于条件C的连接操作R cS 我们用 作为连接操作符 关系R S连接操作的SQL表示式如右图所示 其中 是关系R的属性a和关系S的属性b之间的算术比较符 selectR S fromR SwhereR a S b K4 本页分析所用符号 关系RS属性ABBC值域DAEDBDC元素数IAJIBIC元组数TRTS C A B R S 一 连接操作结果的估计与笛卡儿乘积有确定的输出量不同 连接 这里是指自然连接 操作的输出量取决于选择条件 以下是输出量的估计方法 设关系R的属性是A和B 关系S的属性是B和C 连接结果R S的属性是A B和C 在下边的分析中 使用了右表中的符号 K41 设 a b c DA DB DC 连接结果R S的元组数目为size R S size R S Pabc R S size R S Pab RPb EPbc S IAIBIC TR IAJ J IB TS IBIC TRTS IB连接结果R S块数U的估计为U TRTS IB IR IS b其中b是每个磁盘块的字节数 E DB 二 连接操作实现算法下边介绍四种常用的连接操作算法 在讨论中 用t A1 A2 AK 表示元组t在属性A1 A2 AK的值 1 循环嵌套算法2 SORT MERGE连接算法3 HASH连接算法4 索引连接算法后三种算法都要求对操作关系作某些附加的处理 SORT MERGE连接算法需对操作关系按连接域作排序预处理 HASH连接算法需预先建立操作关系关于连接域的HASH存储结构 索引连接算法需要预先建立操作关系关于连接域的聚集索引结构 K42 1 R A BS的循环嵌套算法类似于笛卡儿乘积的简单算法 该算法扫描操作关系R和S的元组 形成二重循环 所不同的是需要判别连接条件 只有满足连接条件的元组才能输出 设A B分别是R S的属性子集 R A BS的算法是 K42a 对result初始化 forr Rdofors Sdoifr A s B then rs 写入resultendifendforendfor算法存取量的估计是BR BRBS U 其中BR和BS分别是关系R和S的磁盘块数 U是连接结果result的数据块数 为降低存取开销 取较小的关系R作为外循环 R S R S R每读一块S扫描一轮 K42b R S的SORT MERGE连接算法1 设关系R和S已按连接域排序 并且连接域至少对一个关系来说是键属性 按照排序顺序扫描这两个关系的元组 检验连接条件 把符合条件的元组进行连接 这个算法的存取块数是BR BS U 其中U是连接结果的磁盘块数 2 一般情况下 先对各关系按连接域排序 然后用上述算法连接 这就是SORT MERGE连接算法 排序操作可以由多路合并算法实现 在主存缓冲区容量为M块的情况下 对关系R排序的磁盘存取量是 BRlogMBR 对关系S排序的磁盘存取量是 BSlogMBS 所以SORT MERGE连接算法的磁盘存取块数是 BRlogMBR BSlogMBS BR BS U 桶号地址0 1 N 1 桶号地址0 1 N 1 BR N块BR N块BR N块 关系R原始结构共BR块 关系S原始结构共BS块 关系S的H存储结构HS BS N块BS N块BS N块 关系R的H存储结构HR 形成HASH结构 K42c 3 R S的HASH连接算法1 按连接属性对R和S建立HASH文件HR和HS2 对桶号循环 用桶指针引导HR和HS连接 以桶数N的简单HASH结构为例 算法是 fori 0toN 1do连接HR和HS的第i桶Endfor 设元组分布均匀 各桶连接采用循环嵌套 算法 则第i桶连接的存取块数是cost BR N BS N BR N BR N BS N 每读R一块 S第i桶的各磁盘块循环一遍 形成HASH结构的访问块数估计是O BR BS 4 R A BS的索引连接算法 连接条件R A S B 设S已对连接域B建立聚集索引文件IS 对R逐块逐元组循环 按连接域值查IS指针 得S记录 再连成大元组 写入结果关系 设S在连接域值域上均匀分布 算法的存取块数为BR TRBS I U 其中 成绩块针900 880 864 822 758 788 758 成绩证号姓名900 880 864 864 822 822 822 788 788 稀疏索引非键值索引数据文件按索引域排序 聚集索引IS 关系S 主存 缓冲区 按分数搜索 I为S连接域值域的大小 即索引项数 对R的一个元组 扫描S的块数估计值为BS I K42d 关系R K5 算法 forR中每元组doR A1 AK 写入TMPendfor if A1 AK 含键thenbeginT TMP retu endelse 去重复 仅取重复组的首项 begin排序TMP i 1 j 2 whilei ndo写TMP i 到T whileTMP j TMP i doj j 1 endwhile i j j j 1 endwhileend 输入 具有n个元组的关系R输出 R的投影T A1 A2 AK R 第五节投影操作 AR的实现算法若投影域含键 仅需对R存取一次 否则结果可能有重复元组 下边是删除重复的排序算法 学号成绩001700028000380004800059200692007960089800998 成绩708080809292969898 除去重复 已排序 123456789IjIjjjIjjIjIj T 投映结果 记录号 TMP 算例执行的示意图 成绩 7080929698 第六节集合的并 交 差的实现算法集合的并 交 差运算要求参加操作的关系具有相同的属性结构 并且属性的顺序也须相同 为避免出现重复扫描 可以使用排序的附加操作 也可以使用HASH结构的方法 下边叙述利用预排序的算法 首先在相同的键属性上排序操作关系 然后扫描两个关系完成操作 1 并操作R S 对称运算 2 交操作R S 对称运算 3 差操作R S 不对称运算 K6 1 并操作R S这种操作具有对称性 即R S S R 假设关系R和S分别有n和m个元组 R的序号为i S的序号为j 算法如下 用Ri k 表示R第i元组的键值 K61 算法简例 设R与S都仅有一个属性 是键 排序后分别是 R 1 4 5 6 n 4 S 2 4 m 2 执行过程是 i j 1 比较1和2 输出1 i改为2 比较4和2 输出2 j改为2 比较4和4 输出4 i j 3 循环停止 输出R剩余元组5 6 算法停止 操作结果 1 2 4 5 6 关于键k对两关系的元组作升序排列 i 1 j 1 whilei nandj mdo比较Ri k 与Sj k 较小一方称为小方 若不等 输出小方元组 小方序号加1 若相等 输出元组R