文档介绍：应用半连接的分布式数据库查询优化算法
概述
分布式数据库具有分布性和冗余性,导致分布式查询处理比较复杂,因此查询优化是一个非常重要的问题。针对大规模数据分析分布式数据库的数据分片机制,建立改进的数据分片模型,并根据分布式数据库的查询优化目标分析查询优化算法,对半连接查询优化算法进行改进。实例分析表明: 改进的半连接查询算法极大地降低了传输代价, 提高了查询效率
一般的半连接查询方法
半连接是投影和连接组成的一种关系代数运算。假设R1、 R2是2个关系,分别位于站点 S1、S2,而属性 A1、A2 分别在R1和R2上,半连接操作可表示为
连接操作可表示为:
其中:∞表示连接操作,∝表示半连接操作,∏表示投影操作。
直接连接是将站点 S2 中的所有关系 R2 一次传输给站点 S1,而半连接的执行过程如下表所示
改进的半连接查询优化
在一般的半连接查询中,连接代价主要是 2次传输的代价其中的第一次传输,即由站点 S2将∏A2 R2 从 S2 传输到站点 S1,因为只有一个属性,所以相对于大规模数据而言其传输的数据量较少; 第二次传输,即由站点 S1将R1传输到站点 S2,需要传输的数据元组长度为 R1 的长度,记录个数为 R1 的记录数这样,当 R1 长度很长,R1 记录很多时,该次传输的数据量仍然相当大,即带来了较大通信代价由此提出一种改进的半连接查询方法。
首先,介绍改进半连接查询中涉及到的几个概念和理论。
定理1 连接运算的交换律假设有关系 R1 和关系 R2, 那么 R1∞ R2 =R2∞R1,即连接运算满足交换律。
定义1 关系元组比 Rsize假设有关系 R1 和关系 R2,那么 Rsize =size( R1) / size( R2) ,称为关系 R1 和 R2 的关系元组比。
定义2 关系记录比 Rrecord假设有关系 R1 和关系 R2, 那么 Rrecord =record( R1) /record( R2) ,称为关系 R1 和 R2 的关系记录比。
定义3 关系数据比 Rdata
假设有关系 R1 和关系 R2, 那么 Rdata = Rsize* Rrecord, 称为关系 R1 和 R2 的关系数据比由于关系 R1 的记录数和 R1 的记录数一般情况下是成正比的, 所以可认为:
当Rdata > 1 时, 即站点S1 上的数据量大于站点 S2 上的数据量;
当Rdata < 1 时, 即站点S1 上的数据量小于站点 S2 上的数据量;
当满足第 2 种情况时,采用一般的半连接方法是比较合适的, 但当满足第 1 种情况的时候, 显然采用一般半连接的传输代价较大由于连接运算满足交换律, 所以可将传输的内容改为将 R2从站点 S2 传输到站点 S1, 由此降低了传输代价改进的半连接查询算法过程描述见下表
算法性能比较
假设关系 R1 和 R2 的关系结构如下表所示。
根据上表得关系数据比为2,按照改进的半连接查询,计算所需数据如下表所示。