孙中利，戴玉刚，刘战东

（西北民族大学 中国民族信息技术研究院，甘肃 兰州 730300）

在进行分布式数据库查询优化时，人们关注的焦点是如何选择能够得到提高查询效率、缩减传输费用的查询执行策略[1]。查询执行代价优化的目标是使查询执行所用的系统资源尽量的少，从而降低系统开销[2]。但查询优化本质上是NP完全问题，所谓最佳方案是很难找到，查询优化只是寻找相对较优的操作执行步骤而已[3]。

基于半连接查询，已有多种算法被用于处理海量信息查询和复杂查询领域[4]。比较著名的有AHY，PERF，W等3种算法[5]。Tseng和Chen提出基于哈希-半连接的优化算法[6]，这种算法通过用哈希-半连接操作替换部分半连接操作，来得到更有效的查询执行策略。文献[7]中应用了2-way半连接，2-way半连接同时执行了R∝S和S∝R，使得关系R和S同时被缩减，这种方法适用于装配站点为第三站点的情况（除了R、S所在站点）。本文在上述方法的基础上，以传输费用最小为目的，提出一种基于bloom-filters新的半连接查询优化算法。

1 算法理论基础

1.1 半连接及相关定义

分布式数据库环境下，关系R、S、T分别存在于站点1、站点2、站点3上。在介绍基于多关系半连接的查询优化算法前，首先给出以下定义。

定义 1：对于关系 R，S，T，本文定义如下：

N（R）：关系R中元组的个数；

L（R，a）：关系 R中属性 a定义的长度；

中间连接结果的数据信息称作中间计算结果，记作CRT；把真实的连接结果记作RRT；

Πa（R）：关系R中属性a上不同值组成的集合；

Card（SR）：关系S中与关系R连接时传输的数据代价；

定义2：两个关系在单个属性上进行半连接及连接的定义如下：