（计算机软件与理论专业论文）嵌入式移动实时数据库管理系统查询优化方法研究.pdf

i 华 中 科 技 大 学 硕 士 学 位 论 文 摘 要 嵌入式设备的大量普及，移动通信技术的快速发展，实时系统在日常生产生活中 的广泛应用，导致了需要嵌入式设备管理的实时移动数据日益增多。在此背景下， 结合了嵌入式系统、移动计算、实时系统及传统数据库特点的嵌入式移动实时数据 库管理系统(emrtdbms)已成为数据库领域的新兴技术，其查询优化器的设计，要 充分考虑到应用环境的变化，根据特点做出相应调整。 数据库管理系统(dbms)的查询优化器以查询的语法树作为输入，经过预处理、 逻辑优化、执行计划选择等步骤，生成最终的执行计划。在此过程中，可以使用启 发式规则和基于代价模型的优化技术，整个过程依赖于数据字典中的统计信息。 spj(select-project-join)查询的逻辑优化主要包括连接顺序选择、 选择下推和投影 下推。其中条件表达式中的逻辑运算 and 和 or 会对选择条件下推造成影响，可以 在预处理中将其变为范式形式。对比条件表达式的合取变换与析取变换得到的优化 后的逻辑查询树，关系表达式的合取变换策略对后续优化有利。 嵌入式flash存储器、 数据广播以及数据实时性导致传统代价模型在ertmdbms 中并不适用。 新代价模型能够考虑到 emrtdbms 的数据来源选择、 flash i/o 代价、 数据广播开销以及数据截止期等影响 emrtdbms 查询代价的因素，一个类似于动 态规划的执行计划选择算法能够在此代价模型的基础上完成逻辑优化和执行计划选 择的过程。 通过仿真实验分析，查询条件的合取变换和类似动态规划的执行计划选择策略 在参与连接的关系数量相对较小时能较好地完成 emrtdbms 的 spj 查询优化工作。 关键词关键词：查询优化，合取范式，代价模型，执行计划选择 ii 华 中 科 技 大 学 硕 士 学 位 论 文 abstract popularization of embedded devices, rapid development of mobile communication technology and wider using of real-time systems in the day-to-day work and life lead to increasing number of real-time mobile data which need to be managed on the embedded device. in this situation, the embedded real-time mobile database management system (emrtdbms), which combines the features of embedded system, mobile computing, real-time system as well as traditional database technology, has become a hot technology in the database fields, also the design of query optimizer for emrtdbms should been given full consideration to the changes of environment and make adjustments accordingly. the query optimizer of the database management system (dbms) uses parse tree of the query as input, and then takes the steps of pre-processing, logic optimization and execution plan choosing, at last generates the final execution plan. during processing, heuristic rules and optimization technology based on cost model which depend on the data statistics in the data dictionary can be used. the logic optimization of the spj(select-project-join) query mainly includes the processing of joining sequence choosing, conditions pulling down and projection pulling down. if there are “and” or “or” operation in the query conditions, it would effect the pulling down of the conditions. in the step of pre-processing, the query conditions can be transformed to normal form. after the comparison between the results of the logic optimization using the query conditions in conjunctive normal form and disjunctive normal, it can be said that the strategy of transforming the query conditions into conjunction form is better for the optimization afterwards. embedded flash storage, data broadcast and the data deadline required by the real-time feature lead to the result that we cant use traditional cost model in the ertmdbms. a new cost model considers all the factors which can affect the cost of the query in emrtdbms, including data source choosing, flash i/o cost, broadcast cost and data deadline, and an algorithm like dynamic programming which base on the new cost model can finish the processing of logic optimization and execution plan choosing. through simulation analysis, the strategies of transforming the query condition into iii 华 中 科 技 大 学 硕 士 学 位 论 文 conjunctive normal form and the algorithm like dynamic programming for choosing the execution plan based on the new cost model can work well when the number of the relations is relative small. key words: query optimization, conjunctive normal form, cost model, execution plan choosing 独创性声明独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学学位论文版权使用授权书位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密，在_年解密后适用本授权书。 不保密 。 （请在以上方框内打“”） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 本论文属于 1 华 中 科 技 大 学 硕 士 学 位 论 文 1 1 绪绪 论论 随着数字信息技术和网络技术的高速发展， 后 pc (post-pc)时代已经来临。 如今， 嵌入式系统己经渗透到人们日常生活的方方面面。从各种 pda、掌上电脑到日常通 信用到的各式手机，再到家用电器中的电视机、洗衣机、电冰箱，乃至作为交通工 具的摩托车、小汽车，嵌入式系统已经在各个方面影响我们的日常生活。与嵌入式 系统一样，无线通信技术也在近些年得到飞速发展，各种技术、标准、协议的层出 不穷，通信带宽不断增大，通信质量逐步提高，各种移动通信概念走进千家万户， 改变着我们每天的生活。 嵌入式系统和无线通信网络技术相结合，就出现了移动办公、移动通信等崭新的 移动服务理念。特别是伴随着硬件的飞速发展，移动处理器运算能力日益增强，单 位存储单元价格迅速下降，移动设备对数据的存储和管理能力已日益强大。而且， 随着人们日常生活节奏加快，以及各种生产活动对质量要求的进一步提高，诸如实 时股票交易系统、实时监控系统、实时工业控制系统等实时应用也步入我们的日常 工作与生活。所有变化都对信息的获取手段、存储方式、处理技术提出了全新的要 求，它意味着作为普通终端的智能手机、掌上电脑、pda 及各种监控设备除了提供 传统功能以外，还必须能够存储和管理越来越多的移动和实时数据。然而，如果针 对单个应用开发数据存储管理系统，不仅开发时间长，开发难度大，而且缺乏统一 的接口，使用和移植都存在较大问题。因此，开发出一个能够在移动设备上使用的 实时移动数据库管理系统，并使用该系统来满足嵌入式移动实时环境的数据存储和 管理要求，就成为了嵌入式系统软件开发的一个重要内容。 随着社会信息化进程的逐步深入，各种应用需求的不断提出，嵌入式移动实时数 据库管理系统必将在电子商务、实时环境监测、移动办公及军事上得到广泛应用。 2 华 中 科 技 大 学 硕 士 学 位 论 文 1.11.1 嵌入式移动实时数据库管理系统嵌入式移动实时数据库管理系统 1.1.1 嵌入式移动实时数据库管理系统嵌入式移动实时数据库管理系统体系结构体系结构 嵌入式移动实时数据库管理系统是指在移动计算环境下，支持实时、移动数据管 理和操纵，应用于工业控制、移动通信、掌上电脑、pda 等嵌入式设备上的数据库 管理系统。近年来，对嵌入式实时移动数据库管理系统的研发越来越引起人们的关 注。因为需要嵌入式终端管理的实时、移动数据的数量在不断增加，数据结构日益 复杂，需要有一个统一、有效数据管理系统来简化应用程序的开发。嵌入式移动实 时数据库管理系统不仅要具备数据存储和操纵等传统数据库管理系统的基本功能， 而且要满足移动计算环境，嵌入式系统的体系结构以及应用的实时性等新特点。 嵌入式实时应用的移动客户端一般是车载设备、pda、智能手机等嵌入式设备， 数据库系统嵌入到这些设备中， 运行于嵌入式操作系统(如 linux、 wince、 vxworks 等)之上。 其体系结构与传统的数据库系统有较大差别， 目前较为常用的嵌入式移动 实时数据库管理系统的结构1,2由imielinski 结构发展而来， 其体系结构如图 1.1所示。 系统由固定网络及移动网络两大部分组成。固定网络由一组移动服务基站 mss （mobile server station） 、 信息服务器is （information server） 、 位置服务器ls （location server） 、以及固定主机 fh（fix host）构成，它们通过 wan 或其它有线网络连接， 数据分布于 is 和 mss 中；移动网络由一系列相交或者不相交的无线广播单元 wbu （wireless broadcast unit）构成，每个 wbu 由一个 mss 支持，并且由一组移动客 户 mc （mobile client） 组成， 每个 mc 为一个嵌入式移动设备， 它可以跨单元移动。 1.1.2 嵌入式移动实时数据库嵌入式移动实时数据库管理管理系统的特点系统的特点 与传统数据库管理系统相比， 嵌入式移动实时数据库管理系统除了具有数据存储 和操纵功能，基于其特定应用背景，还具有如下特点3： 3 华 中 科 技 大 学 硕 士 学 位 论 文 1) 移动性：移动主机不仅可以在不同的地方连通网络，而且在移动的同时也可 以保持网络连接。 2) 频繁断接性：移动主机一般不能保持持续联网的工作方式，而是主动或被动 的间隙性入网、断接。而且，即使处于连接状态，不同时间的网络状况(如带宽、通 信代价、网络延迟等)也是变化的。 3) 网络通信非对称性： 由于物理通信媒介的限制， 一般下行链路(服务器端到移 动客户端)的通信带宽与代价远大于上行链路(移动客户端到服务器端)。 4) 资源有限性：移动主机 cpu 的运算能力、内存容量、存储器的大小及电源 的能力都远不及固定主机。其数据缓存的数量和应用规模受到很大限制。 5) 实时性：在移动主机上运行的事务和管理的数据都有显式时间限制，系统的 正确性不仅依赖于事务的逻辑结果，而且依赖于该逻辑结果产生的时间。 以上就是嵌入式移动实时数据库管理系统不同与传统数据库管理系统的几大特 点，因此，嵌入式移动实时数据库管理系统在设计和实现上都与传统数据库管理系 fix network（wan/intranet/atm etc.） is mss mss ertdbms ertdbms ldb ertdbms ldb mc mc mc mc mc ertdbms repdb ertdbms repdb wireless broadcast unit wired connect wireless connect 图 1.1 嵌入式移动实时数据库的系统模型 is ls mss disconnect fh ldb 4 华 中 科 技 大 学 硕 士 学 位 论 文 统有着较大的区别。 1.1.3 嵌入式移动实时数据库管理系统嵌入式移动实时数据库管理系统现状现状 实时数据库系统受到了数据库和实时系统两个领域研究人员的关注。 实时数据库 在数据特征与事务模型4、事务的优先级分派、调度和并发控制协议与算法5,6,7；数 据恢复、查询处理及其优化等方面已取得了一些成果。 对于嵌入式移动数据库，目前的市场上已经有了一些解决方案。如 sybase 公司 的移动数据库ianywhere， ibm公司的关系型数据库db2的卫星版及漫游版、 informix 公司的 cloudscape 、oracle 9i 数据库的 lite 版本、berkeley db 和 sqlite 等。在国 内市场，有人大“小金灵”和东大阿尔派的 openbase 在嵌入式移动环境下的解决方 案。但是，这些数据库产品往往只能支持嵌入式移动环境，对实时事务的支持往往 不够。目前，还没有能够支持嵌入式、实时、移动环境的数据库管理系统。因此， 急需开发出一种能够应用于上述三种环境的数据库管理系统来满足日益增长的应用 需求，这也正是本课题的研究意义所在。 1.21.2 数据库管理系统查询优化数据库管理系统查询优化的的研究研究进展进展 1.2.1 数据库管理系统查询优化的目的数据库管理系统查询优化的目的 关系数据库系统一个主要功能就是让用户通过关系数据库的标准查询语言 sql8来访问和修改数据。 sql 作为关系数据库查询语言的国际标准， 向用户提供了 一个易于使用的、非过程化的、描述性的语言来存取其中的数据。大多数商用数据 库产品(如 oracle, sql server, sybase, ibm db2 等)都采纳了这一国际标准， 用户借助 于 sql 语句，可以完成对数据的复杂操作。 查询是数据库系统中最基本、常用的一种操作，因此，查询是否具备较高的执行 效率和较短的响应时间，已成为数据库管理系统的设计者和用户所共同关注的问题。 由于同一个关系存在着不同的存取方法，两个关系连接存在着不同算法，多个关系 连接存在着不同顺序， 因此， 对于一个给定的查询通常会存在很多等价的执行计划， 5 华 中 科 技 大 学 硕 士 学 位 论 文 这些执行计划的输出结果相同，但是执行的时间效率、空间开销往往差别很大。因 此，为了提高数据库系统的性能，进入数据库管理系统的查询必须首先进行优化处 理。从各种数据库管理系统的产品在市场上多年的表现来看，成功的大型商用数据 库管理系统往往具备高效的查询优化器。 1.2.2 数据库数据库管理管理系统系统的的查询处理查询处理流程流程 数据库管理系统中对于用户查询的处理是通过查询处理器来完成的。如图 1.2 所 示为一般的查询处理器的结构，它主要分为两个部分： 查询请求 查询 分析器 查询预处 理器 查询 优化器 语法树 查询编译器 执行引擎 执行器 执行计划 预处理后 的语法树 图 1.2 数据库管理系统查询处理器过程 1) 查询编译器：它将查询翻译成数据库管理系统的内部可计算的形式，称为执 行计划，查询编译器主要包括三个部分： (1) 查询分析器：它由文本形式的查询出发，建立一棵查询的语法树结构。 (2) 查询预处理器：它对查询进行语义检查(例如，查询中所提到的关系是否都 确实存在)，并进行某些树结构转换，例如对查询的选择条件进行预处理， 实现 view 功能，对嵌套查询进行重写等功能，其输出为处理后的语法树。 (3) 查询优化器：它将处理后的语法树转换称为对于实际数据有效的操作序列， 也就是执行计划。查询优化器包括了逻辑优化和物理优化两个部分，在优化 过程中会充分利用数据字典中的信息来进行最优计划的选择。 2) 执行引擎： 它负责执行查询计划中的每个步骤。 执行引擎与 dbms 中大多数 的其他成分都有交互。 例如， 为了对数据进行操作， 必须将数据从外存读入缓冲区； 为了决定不同事务操作的执行顺序，需要和数据库管理系统的事务管理器及并发控 6 华 中 科 技 大 学 硕 士 学 位 论 文 制部分进行交互；为了避免访问被加了锁的数据，需要和并发控制部分进行交互； 为了确保对于数据库的所有修改都正确地记了日志，需要和日志管理器进行交互。 当执行计划中的所有的操作都被执行引擎处理完毕之后，才能够得到查询结果。 查询优化器的主要功能是将语法树转换为效率较高的执行计划。 不同的系统对查 询优化器的具体实现不同，但一般来说，大多数查询优化器的结构如图 1.3 所示： 逻辑优化 优化后的逻 辑查询计划 操作代 价估计 数据 字典 物理优化 语法树 执行计划 启发式规则 (改善查询的代数定律) 中间结果 大小估计 物理计划 的枚举 启发式规则 逻辑查询计划 图 1.3 数据库管理系统查询优化器的结构 由图 1.3 可以看出，查询优化器在进行处理时一般分为三个步骤： 1) 语法树到逻辑树的变换。 2) 逻辑优化。根据启发式规则（关系代数的 12 条代数定律）对逻辑查询树进 行变换，或者根据代价模型（例如中间结果的大小）从众多等价的逻辑查询计划中 选择能够生成更加有效执行计划的方案。 3) 执行计划生成。主要使用执行计划枚举的方法，对于逻辑计划中的每一个操 作，根据数据的存取路径、扫描方式、连接算法等信息对操作的可能执行方案进行 枚举，最后由每个节点的执行计划形成一个组合，称为执行计划。通常这样的执行 计划会有很多个，需要对每个执行计划进行代价估算，从中选择代价最小的一个。 在此过程中，可以使用一些启发式规则减小计划枚举的空间。 1.2.3 国内外研究现状国内外研究现状 查询优化的研究始于上个世纪 70 年代，目前研究领域已涉及查询优化器的各个 7 华 中 科 技 大 学 硕 士 学 位 论 文 方面。总的来说，查询优化器的功能是为执行引擎提供输入，该输入能够使数据库 查询的吞吐量和平均响应时间达到最优。因此，查询优化的过程就是搜索最优执行 计划的过程，为达到这个目标，优化器必须满足以下三个要求9，而且，众多研究也 主要围绕这些问题来展开： 1) 一个包含了最小执行计划的搜索空间。 2) 一个准确的代价估计模型。 3) 一个高效的枚举算法。 ibm 公司的 system-r 项目10极大地推进了关系数据库查询优化的研究，该系统 中提出了关系数据库数据访问方法选择的技术11，目前该技术已被广泛的应用于商 用优化器。在 system-r 系统中，spj 查询的搜索空间被限制为由线性连接顺序组成 的操作树，又称为“左深树” ，连接算法可以选择嵌套循环或是排序连接，对于关系 的扫描，能够使用索引（聚簇的或是非聚簇的）或是顺序扫描。对于代价估计， system-r 的代价包括了每步操作的输出数据大小，输出数据是否排序及操作的开销 估计三项。 ，system-r 在枚举算法方面使用了两项重要的技术：一是动态规划算法， 二是记录结果中的“兴趣顺序” 。 在 system-r 系统中，对于两个执行计划代价比较，只有在表示相同的表达式并 且“兴趣顺序”相同时才会进行。在随后的研究中， “兴趣顺序”被泛化为“物理属 性”12，广泛地应用于现代优化器中。 优化器的搜索空间不仅依赖于关系代数等价变换规则的数量， 还决定于执行器所 实现的操作算法的种类。同时，关系的连接顺序，是否推迟笛卡尔积运算也是影响 搜索空间的重要因素。一般的优化器都采用“左深树”的线性顺序和推迟笛卡尔积 的策略。文献13则在一个扩展的系统中提出了基于查询来选择是否采用“丛生树” 策略。对于外连接，其运算不满足交换率。而然，可以采用“连接先于外连接”的 规则对含外连接的顺序进行重新排列，文献14给出了基于代价的外连接变换算法。 对于查询中含有 group-by 子句的情况，一般是将 group-by 放在所有的连接之后完 成。但是如果能够将 group-by 运算先于连接完成，则能大大减少参加连接的元组的 数量，文献15,16,17,18提出了“上拉”group-by 的等价变换规则，对于这一问题的 8 华 中 科 技 大 学 硕 士 学 位 论 文 进一步研究，文献19给出了一个综述。 对于复杂查询合并的问题， 当查询中存在视图时， 如果视图定义为简单 spj 查询， 那么将视图替换为查询后即可对连接顺序进行调整。但是当视图的定义比 spj 查询 要复杂时，则不能如此。文献20提出了当视图中存在 select distinct 关键字时如何 “上拉”distinct 的办法，文献18则提出了当视图中存在 group-by 时的处理办法。 对于复杂查询中含嵌套子查询的情况，较难处理的是含有相关子查询的嵌套查询， 文献21给出了将相关嵌套子查询扁平化的方法。文献22首次提出了使用代数学的 视角解嵌套的思想，文献24提出了在保证查询语义不变的情况下将聚集“上拉”的 技术。文献23则提出了一种将嵌套子查询转换为“table-expression”或是视图的方 法，该方法在文献24中得到了进一步的强化。 “半连接”的优化技术也在嵌套子查 询的合并中得到了广泛应用，文献25中提出了利用“半连接”技术来优化含有视图 或是嵌套子查询的技术。 对于代价估计的研究，主要解决两个问题：一是怎样获取数据库中存储数据的统 计信息；二是如何根据物理操作的输入数据，估算结果的大小和执行时间。针对基 本数据的统计信息获取，文献26提出了数据直方图的概念，由于数据库中的数据列 之间往往存在相关性，文献27,28又进一步提出了二维直方图的概念。当数据库系 统中管理的数据量十分庞大时，直接计算统计信息会导致较大的开销，文献29提出 了利用部分样本数据估算统计信息的办法， 文献30则提出了维护递增数据统计信息 的方法。对于导出数据的估计（例如选择操作结果的元组数量） ，文献31也给出了 相应的估算策略。对于操作代价估算的问题，文献32提出，除了利用传统的参数进 行估计以外，缓冲区的利用率对代价的精确计算也有着重要的意义。 对于一个给定的查询，搜索算法能在搜索空间中找到一个代价较小的执行计划。 由于多连接查询优化在本质上就是组合优化的问题，因此搜索算法可以借鉴最优化 理论来完成。目前，常用的算法有以下三大类：穷尽搜索算法、启发式算法、随机 搜索算法。应用于 system-r 系统的动态规划就是典型的穷尽搜索，文献33对其进 行了进一步的扩展和改进。穷尽式搜索的缺点是搜索空间大，效率比较低。因此， 提出了基于启发式的搜索算法33，启发式搜索减少了搜索空间，算法能够在恒定时 9 华 中 科 技 大 学 硕 士 学 位 论 文 间内完成，却不能保证得到最优执行计划。最常见的随机算法有模拟退火算法 (sa)34、迭代改进(ii)35、遗传算法(ga)36以及两阶段优化算法(2po)。 在优化器的结构扩展方面，提出了两个比较意义的模型，分别是 starburst37和 volcano/cascades38,39。针对分布式数据库的查询优化，hasan40发现不同节点之 间的网络通信的代价也是影响查询的主要开销之一,文献41通过 xprs 试验系统提 出了分布式数据库的两阶段优化策略。 在移动数据库的查询优化方面，文献42提出了基于公共子表达式的多重查询优 化技术。在内存数据库的查询优化方面，文献43提出了基于 sb*树的内存数据库逻 辑优化策略。针对嵌入式实时数据库系统的特点，文献44提出了一种新的连接顺序 优化算法 (greedy iterative improvement, gii)。该算法结合了贪婪算法和迭代改进算 法的优点，能满足系统的实时要求，可以控制查询优化时间，比传统的查询优化策 略能更好地适应不同事务类型的需要。 总之，在数据库管理系统的查询优化领域，已经取得了丰硕的成果，以上列举的 思想、方法、技术仅仅是沧海一粟。然而，随着数据库管理系统在新环境中的使用 （例如在嵌入式、实时、移动环境中） ，查询优化也面临新的问题，因此，根据应用 环境对现有的查询优化技术进行调整也就成为了新的数据库管理系统研发的重要任 务。 1.31.3 本文本文内容与内容与组织结构组织结构 本论文的组织结构安排如下： 第一章介绍嵌入式移动实时数据库的理论和应用背景， 并描述了查询优化器的结 构及其研究现状。 第二章对查询优化的主要理论和技术进行了总结。 主要内容包括关系代数的等价 变换规则、统计信息以及获取技术、中间结果大小的估计、物理操作符的 i/o 预估、 基于代价模型的执行计划选择及相关的启发式规则。 第三章以一个 spj 查询为例， 介绍了嵌入式移动实时数据库管理系统逻辑优化的 过程，主要介绍了查询条件合取变换的过程。 10 华 中 科 技 大 学 硕 士 学 位 论 文 第四章分别从嵌入式、 实时和移动三个方面分析了新的应用环境对嵌入式移动实 时数据库管理系统数据特征的影响。根据影响嵌入式实时移动数据库代价的诸多因 素，给出了一个适用于嵌入式移动实时数据库管理系统查询优化的代价模型及相应 的查询计划选择算法。 第五章根据上两章提出的算法，设计了两个仿真实验，对算法的正确性和性能进 行了验证和分析，得出了该优化器的设计方案能够完成嵌入式移动实时数据库管理 系统的查询优化任务的结论。 第六章对全文工作进行总结，并指出以后研究工作的方向。 11 华 中 科 技 大 学 硕 士 学 位 论 文 2 2 查询优化的基本方法查询优化的基本方法 整个优化过程一方面在关系代数级别发生， 即优化器要找到一个与给出的关系代 数表达式等价，但更为有效的逻辑计划。另一方面在物理层面发生，即为逻辑计划 生成一个有效的执行计划。在查询表达式的变换过程中，需要依赖于关系代数的等 价规则和操作结果大小估计。在由逻辑计划向执行计划的转换过程中，则需要对逻 辑计划中不同物理操作的代价进行精确估计。不管是逻辑计划还是执行计划的选择， 都可以使用基于代价模型或是启发式规则的方法。 2.12.1 改进查询计划的代数定律改进查询计划的代数定律 如果两个关系代数表达式的执行在数据库实例中产生相同的元组集， 则我们称其 为等价的45。等价规则，又称代数定律，能够指出两种不同形式表达式的等价性。 优化器利用这些代数定律将表达式转换成逻辑上等价的其他形式。以下就是关系代 数表达式的一些常用等价规则。、1、2表示谓词，l1、l2、l3等表示属性列表， 而 e、e1、e2等表示关系代数表达式。关系名 r 是关系代数表达式的特例。 1) 合取的选择运算可分解为单个选择运算的序列： 1212 ( )( )ee 2) 选择运算满足交换律： 1221 ( )( )ee 3) 一系列投影运算中只有最后一个运算是必需的，其余的可省略： 121 ( )( ) n llll ee 4) 选择操作可与笛卡尔积及 连接相结合： 121 ()eee 2 e 1 1 (e 2 21 )ee 12 2 e 5) 连接运算满足交换律： (2-1) (2-2) (2-3) (2-4) (2-5) 12 华 中 科 技 大 学 硕 士 学 位 论 文 1 e 22 ee 1 e 6) 连接运算满足结合率： 1 (e 2) e 31 ee 2 (e 3) e 1 (e 1 2) e 23 31 ee 13 2 (e 2 3) e 对于(2-8)式，2只涉及 e2及 e3的属性。当 条件为空时，连接即退化为笛 卡尔积，因此，笛卡尔积也是满足结合律的。 7) 选择运算在以下两个条件下对 连接运算具有分配律： (1) 选择条件 0的所有属性只涉及参与连接运算的表达式之一（如 e1）时： 0 1 (e 0 21 )()ee 2 e (2) 选择条件 1只涉及 e1属性，选择条件 2只涉及 e2的属性时： 12 1 (e 1 21 )()ee 2 2 ()e 8) 投影运算在下面的条件下对 连接运算具有分配率： (1) l1、l2分别代表 e1、e2的属性，条件 只涉及 l1l2中的属性： 12 1 ( ll e 1 21 )() l ee 2 2 () l e (2) l1、l2分别代表 e1、e2的属性； l3是 e1中出现在连接条件 中但不在 l1l2中的属性； l4是 e2中出现在连接条件 中但不在 l1l2中的属 性： 12 1 ( ll e 13 21 )() ll ee 24 2 () ll e 9) 集合的并与交满足交换律，但集合的差运算不满足交换律： e1e2 =e2e1 e1e2 =e2e1 10) 集合的并与交满足结合律： (e1e2)e3=e1(e2e3) (e1e2)e3=e1(e2e3) (2-6) (2-7) (2-10) (2-12) (2-13) (2-14) (2-15) (2-16) (2-8) (2-9) (2-11) 13 华 中 科 技 大 学 硕 士 学 位 论 文 11) 选择运算对并、交、差运算具有分配律： p (e1e2)= p (e1)p (e2) p (e1e2)= p (e1)p (e2) p (e1e2)= p (e1)e2 p (e1-e2)= p (e1)- p (e2) p (e1-e2)= p (e1)- e2 12) 投影运算对并运算具有分配律： l(e1e2)= l(e1)l(e2) 以上列出的这 12 条代数定律只是关系代数等价规则的一部分，还有其他涉及到 扩展关系代数运算符的等价规则一般在更复杂的查询优化中用到。 2.22.2 操作代价估计操作代价估计 不管是逻辑计划的选择，还是执行计划的生成，都必须依赖于操作代价估计。操 作代价的准确估计往往要基于一些参数， 这些参数要么由精确计算得到， 要么由 “统 计量收集”过程来估计。有了这些参数，不仅能估计操作结果的大小，而且能对各 操作的不同实现算法进行代价评估。 2.2.1 统计量获取统计量获取 为了对操作代价进行顺利估计，在数据库管理系统的数据字典中，一般应该保存 以下这些统计信息： 1) t(r)为关系 r 的元组数。 2) b(r)为关系 r 中元组的磁盘块数。 3) l(r)为关系 r 中每个元组的字节数。 4) f(r)为关系 r 的块因子，即一个磁盘块能容纳的关系 r 中的元组的个数。 5) v(r，a)为关系 r 的属性 a 上所具有的不同值的数目。 6) min(r，a)为关系 r 中属性 a 的最小值。 7) max(r，a)为关系 r 中属性 a 的最大值。 以上是与关系 r 相关的统计信息，同理，对于索引，也应该有相同的统计信息， (2-17) (2-18) (2-19) (2-20) 14 华 中 科 技 大 学 硕 士 学 位 论 文 如索引的高度、索引中叶节点的页数、索引关键字的取值的计数、索引所占的磁盘 块数等，就不一一列举了。这些信息对于代价来说非常重要，但是还相对简单，为 了提高代价估计的精确度，现实中的优化器往往还要维护更深入的统计信息，例如 直方图。 在直方图中，每个属性的取值被分成若干区间，对于每个区间，直方图将属性落 在该区间中的元组的个数与该直方图相关联。直方图维护的统计信息较为详尽，占 据的空间也少，数据库管理系统中使用的主要是等宽和等深直方图。 统计量的获取，对于元组数量较小的关系，可以通过元组遍历的方式来进行，如 果元组规模非常庞大，遍历方式会带来巨大的开销，此时一般采用部分采样的方式 进行估算。 对于统计信息的维护问题，如果要维护精确的统计信息，则数据库每次修改时必 须同时刷新统计信息的值，这样会带来较大的系统开销。一般数据库系统会在负载 比较轻的情况下或是由管理员手动来刷新统计信息。 2.2.2 操作操作结果结果大小估计大小估计 中间结果的大小是影响逻辑计划代价的重要因素，因此，估计逻辑计划中每个操 作结果大小就显得十分重要。而且，一个中间结果的大小并不依赖于计算该中间结 果采用的方式（如多关系连接的结果大小不依赖于连接计算的顺序） ，这个结论保证 了中间结果大小估计的一致性。以下就是一些适合于大多数情况的估计准则。 1) 投影大小的估计 投影为每个输入元组产生一个结果元组，输出结果的元组长度发生变化。对于关 系代数运算而言，投影运算会消除重复元组。因此，结果中元组的数目会比原来关 系中的元组数目略小一点。形如a(r)的投影的计算结果的大小估计为 v(r，a)。 2) 选择大小的估计 选择运算一般减少元组数目，而且运算结果的大小估计依赖于选择谓词，以下分 单个等值谓词、单个比较谓词和谓词联合进行分析。 (1) 单个等值谓词：对于a=a(r)这样的等值谓词，假设取值均匀分布，则计算结 15 华 中 科 技 大 学 硕 士 学 位 论 文 果的估计为 t(r)/v(r，a)。如果在属性 a 上有一个直方图，则可以首先定 位值 a 所在的区间，然后用该区间的频度计数代替 t(r)，用该区间中出现的 不同的 a 的值来代替 v(r，a)。 (2) 单个比较谓词：一般而言，对于a 60 and score 3 sdept = cs score 60 score nodetype = con then return /当节点为空或是单个选择条件式，算法返回 endif if plogicroot-nodetype = or then if plogicroot-pleft-nodetype = and / or 节点左孩子为 and 节点的情况 then rightcopy*(plogicroot-pright) /拷贝节点的右子树到 rightcopy plogicroot-nodetype and /设置节点类型为 and pnodeadd-pleft plogicroot-pleft-pright pnodeadd-pright plogicroot-pright pnodeadd-op or plogicroot-pright pnodeadd /将新增节点nodeadd设为节点右子树 plogicroot-pleft-op or /将节点左子树类型改为 or plogicroot-pleft-pright rightcopy /令节点右子树为 rightcopy flag 1 /标记此轮处理中进行过变换 endif if plogicroot-pright-nodetype = and / or 节点右孩子为 and 节点的情况 then leftcopy *(plogicroot-pleft) /拷贝节点的左子树到 leftcopy plogicroot-nodetype and /设置节点类型为 and pnodeadd-pleft plogicroot-pleft pnodeadd-pright plogicroot-pright-left pnodeadd-op or plogicroot-pleft pnodeadd /将新增节点 nodeadd 设为节点左子树 plogicroot-pright-op or /将节点右子树的类型改为 or plogicroot-pright-pleft rightcopy /令节点右子树为 rightcopy flag 1 /标记此轮处理中进行过变换 endif conjunctive-normal-form(plogicroot - pleft) /递归处理根节点的左子树 conjunctive-normal-form(plogicroot - pright) /递归处理根节点的左子树 endif end conjunctive-normal-form /*新增一个节点 nodeadd，令节 点的左子树为节点左子树的右子 树，右子树为节点的右子树*/ /*新增一个节点 nodeadd，令节 点的左子树为节点的左子树，右 子树为节点右子树的左子树*/ 27 华 中 科 技 大 学 硕 士 学 位 论 文 算法 3-2：生成条件表达式的合取范式(generatecnf) 输入：条件表达式的根节点(plogicroot) 返回值：条件表达式的合取形式(plogicroot) 算法描述如图 3.7 所示： 图 3.7 算法 generatecnf 的过程 以上就是条件表达式合取范式的求解过程。如果变换为析取范式，则树中所有 or 节点移动到顶端，然后，每一个以 or 为根的子树中，只含有以 and 连接的单 个条件，其求取算法在思路上不发生变化，只要将合取范式求取算法中所用规则的 and 和 or 对换即可，即： a (b c) = (a b) (a c)。 3.2.3 查询表达式变换后的结果查询表达式变换后的结果 如果采用合取变换，则图 3.1 中的条件表达式树在进行变化后，成为图 3.8 所示 的形式。条件表达式中所有的 and 节点都上移到树的顶端，所有以 or 为根的子树 中不再有 and 节点，可将其作为一个复合条件，成为 and 所连接的条件表达式集 合的一个元素。 如果将原始表达式变为析取范式的形式，则图 3.1 中的条件表达式树在进行变化 后，成为图 3.9 所示的形式。从图中可以清楚的看到，条件表达式中所有的 or 节点 都已上移到树的顶端， 而每个最下层的 or 节点都成为以 and连接的条件子树的根。 这样， 就可以将每一个以 and 为根的子树中的条件下推到与扫描或是投影运算相结 合，所有的以 and 为根的子树的运算结果由顶层 or 运算进行集合的并运算。 (3-2) procedure generatecnf