利用关系代数等价变换规则的优化算法，对片段上的查询树进行优化处理，最后达到优化查询的目的。
下面举一个实例加以说明：
以全局数据模式中的职员表employee(no,name,age,sex,salary,telephone)为例，先对表employee进行垂直分片,使其分为employee_1(no,name,age,sex)和employee_2(no,name,salary,telephone)两个数据模式，再对employee_1(no,name,age,sex)进行水平分片，使其分为employee_11(sex='m')和employee_12(sex='f')两个数据模式，最终形成employee_11(sex='m')、employee_12、em-ployee_2三个局部数据模式。
现在要查询性别为男性且月工资在3000元以上的所有职员的姓名，查询的SQL语句为：
Select name
From employee
Where sex='m'and salary>=3000
其关系代数表达式为： πname(σsex='m'∩salary>=3000(employee))关系代数表达式的查询树如图1所示：
对应片段上的查询树如图2所示：
由图2可以看出employee_12的分片条件与查询选择条件矛盾，故去掉employee_12片段，也就去掉了一个合并操作，同时还去掉了一个对employee_11片段的一个选择操作，从而达到了优化的目的。
优化后的查询树，如图3所示：
图1 关系代数表达式的查询树
Fig1 Relations algebraic expression for the trees
图2 对应的片段上的查询树
Fig2 The corresponding fragment of queries on the tree
图3 优化后的查询树
Fig3 optimized for the trees
若没有进行查询优化处理，根据图1所示，会增加中间查询结果的数据量，例如employee_1表和employee_2表分别有1000条记录，employee_1表中满足salary>=3000的记录有100条，则中间结果的数据记录有100+1000=1100条。
若采取了查询优化处理，据图3所示，则中间查询结果的数据量将大大减少。假设employee_1表和employee_2表分别有1000条记录，employee_1表中满足salary>=3000的记录有100条，则中间结果的数据记录有100+100=200条。由此可见，经过查询优化后，查询效率得到大大提高。
以上是关于基于关系代数等价变换的查询优化处理，其基本原理就是把查询问题转变为关系代数表达式，然后分析得到查询树，进行从全局到片段的变换得到的基于片段的查询树，然后利用关系代数等价变换规则进行查询优化，从而达到优化的目的。分布式查询优化的目的就是为了使包括CPU代价、I/O代价和通信代价的总代价最小，以达到查询优化[11]。
4 关系查询处理和查询优化
4.1 关系数据库系统的查询处理
查询处理的任务是把用户提交给RDBMS的查询语句转换为高效的执行计划。
RDBMS查询处理可以分为4个阶段：查询分析、查询检查、查询优化和查询执行[12]，如图4所示：
（1）查询分析
首先，对查询语句进行扫描、词法分析和语法分析。从查询语句中识别出语言符号，如SQL关键字、属性名和关系等，进行语法检查和语法分析，即判断查询语句是否符合SQL语法规则。
（2）查询检查
根据数据字典对合法的查询语句进行语义检查，即检查语句中的数据库对象，如属性名、关系名、是否存在和是否有效。还要根据数据字典中的用户权限和完整性性约束定义对用户的存取权限进行检查。如果该用户没有相应的访问权限或违反了完整性约束，就拒绝执行该查询。检查通过后便把SQL查询语句转换成等价的关系代数表达式。RDBMS一般都用查询树（query tree），也称为语法分析树（syntax tree），来表示扩展的关系代数表达式。这个过程中要把数据库对象的外部名称转换为内部表示。
（3）查询优化
每个查询都会有许多可供选择的执行策略和操作算法，查询优化（query optimization）就是选择一个高效执行的查询处理策略。查询优化有多种方法。按照优化的层次一般可以分为代数优化和物理优化。代数优化是指关系代数表达式的优化，即按照一定规则，改变代数表达式中操作的次序和组合，使查询执行更高效；物理优化则是指存取路径和底层操作算法的选择。选择的依据可以是基于规则（rule based）的，也可以是基于代价（cost based）的，还可以基于语义（semantic based）的。
实际上，RDBMS中的查询优化器都综合运用了这些优化技术，以获得最好的查询优化效果。
（4）查询执行
依据优化器得到的执行策略生成查询计划，由代码生成器（code generator）生成执行这个查询计划的代码。
4.2 关系数据库系统的查询优化
查询优化在关系数据库系统之中有着重要的地位[13]。关系数据库系统和非过程化的SQL之所以能够取得巨大成功，关键得益于查询优化技术的发展。关系查询优化是影响RDBMS性能的关键因素。
优化对关系系统来说既是机遇又是挑战。所谓挑战是指关系系统为了达到用户可接受的性能必须进行查询优化。由于关系表达式的语义级别很高，使得关系系统可以从关系表达式中分析查询语义，提供了提供查询优化的可能性。这就为关系系统在性能上接近甚至超过非关系系统提供了机遇。
4.2.1 查询优化概述
关系系统的查询优化既是RDBMS实现的关键技术有事关系系统的优点所在。它减轻了用户选择存取路径的负担。用户只要提出“干什么”，不必指出“怎么干”。对比一下非关系系统中的情况：用户使用过程花的语言表达查询要求，执行何种记录级的操作，以及操作的序列是由用户而不是由系统来决定的。因此用户必须了解存取路径，系统要提供用户选择存取路径的手段，查询效率由用户的存取策略决定。如果用户做了不当的选择，系统是无法对此加以改进的。这就要求用户有较高的数据库技术和程序设计水平[14]。
查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序“优化”做得更过好。这是因为[15]：
（1）优化器可以从数据字典中获得许多统计信息，例如每个关系的元组数、关系中每个属性值的分布情况、那些属性上已经能够建立了索引等。优化器可以根据这些信息做出正确的估算，选择较高的执行计划，而用户程序则难以获得这些信息。
（2）如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。
（3）优化器可以考虑数百种法不同的执行计划，而程序员只能考虑有限的几种可能性。
转贴于 酷文网-论文下载中心 http://www.coolwen.net
共7页: 上一页 [1] [2] [3] 4 [5] [6] [7] 下一页
网摘收藏:
当前位置:
载入中...
-> 在百度中搜索：
-> 在Google中搜索：