2.3 分布式数据库查询优化的准则和代价估算
2.3.1 查询优化的准则
分布式查询优化的准则是花费最小的总代价，在最短的响应时间内获得所需要的数据。所谓响应时间，是从接收查询到完成查询所需的时间。它既与通信时间有关，也与局部处理时间有关，而通信费用与所传输的数据量和通信次数成正比[7]。
2.3.2 查询代价分析
通信费用与分布式数据库系统所基于的通信网络的类型有关，对不同的通信类型有不同的查询处理优化算法[8]。
（1）在远程通信网络中：一般在远程通信网络中，各站点之间的数据传输速度比单机情况下内存与磁盘间的数据传输速度要慢许多倍。因此，在这种分布式查询环境中，查询的局部处理时间与通信所需时间相比，可以忽略不计，减少通信费用成为分布式查询优化的主要目标。而通信费用与所传输的数据量成正比。因此，在基于远程通信网的分布式数据库系统的查询处理中，常常以减少传输的次数和数据量作为优化的重要目标。
（2）在高速局域网中：传输时间比局部处理时间要短得多。在这种情况下，往往以响应时间作为优化目标。所谓响应时间，是从接收查询到完成查询所需的时间。它既与通信时间有关，也与局部处理时间有关，但局部处理时间是关键，所以减少局部处理的时间是问题的主要方面。在某些情况下，查询处理同时以减少通信费用与响应时间
作为优化目标。这时，算法往往需要在这两者之间作出权衡。
（3）查询代价的估算方法：
设一个查询执行的预期代价为QC，则：
在集中式中：QC=I/0代价+CPU代价
在分布式中：QC=I/0代价+CPU代价+通信代价
通信代价可用如下公式作粗略估算：
TC(X)=C0+C1*X
其中：X为数据的传输量，通常以bit为单位计算;
CO为两站点间通信初始化一次所花费的时间，它由通信系统确定，近似一个常数，以秒为单位;
C1为传输率(传输速度的倒数)，即单位数据传输的时间，单位是bit/s。
在上述公式中，C0和C1相比，如果C0较大时，说明建立通信网络的开销大，此时，往往以减少传输次数为目标。反之，就以减少数据传输量为目标。
3 基于关系代数等价变换的优化算法
3.1 基于关系代数等价变换优化算法的基本原理
把查询问题转变为关系代数表达式，分析得到查询树，进行从全局到片段的变换得到基于片段上的查询树，然后利用关系代数等价变换规则的优化算法，尽可能先执行选择和投影操作。这样，一方面可以减少后续操作的操作量，另一方面可以减少操作次数。
3.2 关系代数等价变换规则的优化算法
利用关系代数等价变换规则，把查询树中连接和合并操作尽可能上提，即向树根方向移动。选择和投影操作尽可能下移，即向树叶方向移动。这就是说，尽可能先执行选择和投影操作，后执行连接和合并操作。经过选择和投影操作不但可以减少其后续操作的操作量，而且还可以减少操作次数，这是因为：
（1）如果是水平分片，把分片的限定语句与选择条件进行比较，判别它们之间是否存在矛盾，去掉存在矛盾的片段，如果只剩下一个水平分片的片段，就可以去掉一个“并”操作，达到优化查询的目的。
（2）如果是垂直分片，把片段中的属性集与投影操作涉及的属性集进行比较，去掉无关的所有片段。如果只剩下一个垂直分片的片段，就可以去掉一个"连接"操作，以达到优化查询的目的。
3.3 上述查询优化的实现步骤和方法
根据上述的分布式数据库查询优化算法，可以列出以下具体步骤：
（1）将一个查询问题转换成关系代数表达式。
（2）从关系代数表达式到查询树的变换：对一个关系代数表达式进行语法分析，可以得到一棵语法树，即查询树。
树的叶子：是已知关系或被分成的片段；
树的结点：是关系操作符；
树的根：是查询的最终结果；
将关系代数表达式转换为查询树的方法是：查询树的根节点是最终的查询结果，叶节点是查询涉及的所有关系或片段，中间节点是按代数表达式中的操作顺序组成的一组关系操作符。尽可能先执行选择和投影操作，后执行连接和合并操作，即把选择和投影操作向树叶移动，而连接和合并操作向树根移动[9]。
3.4 关系代数等价变换规则
设 和 是关系代数表达式，F是连接运算的条件，则有：
（1）连接、笛卡尔积交换律
（2）连接、笛卡尔积结合律
， ， 是关系代数表达式，则有：
（3）投影串接律
∏L1(∏L2(…(∏Ln(E)))…)≡∏L1(E),其中E是等价关系代数表达式,Li是投影属性集合,而且L1 L2 … Ln.
（4）选择串接律
σc1and…andcn(E)≡σc2(σc2(…(σCn(E)))…),其中E是等价关系代数表达式,ci为选择条件。
（5）选择投影交换律
(a)∏L(σc(E))≡σc(∏L(E)),其中E是等价关系代数表达式,Li是投影属性集合,c只涉及L中的属性.如果还涉及L以外的属性B1,…,Bm,则
∏L(σc(E))≡∏L(σc(∏L,B1,…,Bm(E)))
（6）选择、连接和笛卡儿积交换律
如果F中涉及的属性都是 中的属性，则
（7）选择与并的交换律
设 ， ， 有相同的属性名，则
（8）选择与差运算的分配律
若 ， 有相同的属性名，则
（9）选择对自然连接的分配律
F只涉及其公共属性
（10）投影与笛卡尔积的分配律
设 和 是两个关系表达式， ，…， 是 的属性， ，…， 是 的属性
（11）投影与并的分配律
若 ， 有相同的属性名，则
3.5 等价关系代数优化规则
对于一个查询语句来说，当给出的查询非常简单和短小的时候，一些优化器事实上生成每一个可能的查询运算方案，并且测算每个方案的代价。当查询非常复杂的时候，需要大量的时间来生成每个可能的方案和测算代价，结果可能是枚举出即将被抛弃的方案。因此，对于通用查询优化器而言，好的解决办法是定义一般的优化规则，从而避免优化器枚举出一些差的方案。针对特定的查询树(RAT)，适用以下规则[10]：
规则1：下推选择和投影，以减少元组数和关系大小；
规则2：把某些选择运算和笛卡儿积相结合，即将选择运算附加在连接运算上；
规则3：同时执行同一关系上的多个选择和投影以避免重复扫描同一关系；
规则4：把投影操作和邻接运算结合起来执行；
从全局查询到片段查询的变换：在具有分片透明性的系统中，这个变换的典型方法是：把基于全局关系的查询树中的全局关系名，用其重构该全局关系的各片段名替换，变换成相应在片段上的查询树。
转贴于 酷文网-论文下载中心 http://www.coolwen.net
共7页: 上一页 [1] [2] 3 [4] [5] [6] [7] 下一页
网摘收藏:
当前位置:
载入中...
-> 在百度中搜索：
-> 在Google中搜索：