半联接计划的全局查询优化策略研究

何爱华 戚晓明

（1.蚌埠学院，蚌埠 233030；2.中国矿业大学，徐州 221116）

半联接计划的全局查询优化策略研究

何爱华1戚晓明2

（1.蚌埠学院，蚌埠 233030；2.中国矿业大学，徐州 221116）

在分布式数据库系统中数据的分布导致查询处理复杂化，它需要考虑网络流量、响应时间、算法复杂度等多种因素。在网络环境中，减少数据的传输量能够极大的提高查询效率，探讨基于半联接计划减少数据传输量的全局查询优化策略。

分布式数据库；半联接；关系代数；查询优化

1 分布式数据库的查询策略

分布式数据库是一个单独的逻辑数据库，该数据库在物理上延伸到由数据通信网络连接在不同位置的计算机上。用户根据全局模式信息用全局查询语言同时为多个站点进行查询。为了查询存储在多个站点的信息，必须将查询分解为一系列SQL语句，每一条语句都由特定的数据库管理系统来处理。当接受到一条SQL语句后，该站点的查询优化器就会产生一个查询执行计划，执行语句，将结果返回到这个应用。一个全局查询一般要处理以下几个问题：

（1）将全局查询分解成为多个全局子查询，每一个子查询对应相关的局部数据库中的数据，分解后的子查询仍用全局查询语言表示。

（2）将每一个全局子查询转换成相应的局部数据库的本地查询语言并传送到相应的局部数据库中执行。

（3）将局部数据库返回的操作结果进行合并，组合成最终的全局查询结果。

涉及不同站点的全局联接的查询代价非常昂贵，因为必须在局部数据库间传送信息来决定结果中的元组。寻找一种高效的联接方法是查询优化的关键。

2 基于半联接查询优化策略

2.1 半联接的关系代数运算

在关系代数中，联接操作是笛卡尔积和选择操作的组合。自然联接是一种等值联接，它要求两个关系中进行比较的分量必须是相同的属性组，并且要在结果中把重复的属性去掉，记为R∞S，具体计算步骤如下：

（1）计算 R 和 S的笛卡尔积：R×S。

（2）挑选笛卡尔积中R和S公共属性相等的元组。

（3）在步骤2的基础上，去掉S的公共属性列。

关系R和S的半联接操作记为R∝S，定义为R和S的自然联接在关系R的属性集上的投影，即：

式中∏R中的R表示关系R的属性集。

也可以用以下方法计算半联接：先求出S在R和S的公共属性集上的投影，再求R和这个投影的自然联接，即：

关系R和S自然联接和半联接计算结果见表1。

2.2 基于半联接查询优化的算法

基于半联接查询优化算法的基本原理就是采用半联接操作，尽量只传输参与联接的数据。例如，A地的一个应用要联接B地和C地的两个表，并把结果传回A地。采用半联接的方法是将B地相关表中那些将会实际参与联接的元组从B地传到C地，然后在C地对这些元组和C地的相关表做联接。更一般的情况下，两个关系T1和T2的半联接（基于某个联接条件）被定义为T1和T2的联接在T1的列上的投影，其关系代数表达式为：

表1 关系R和S自然联接和半联接计算结果

换言之，半联接是由T1中参与与T2联接的元组组成，其关系表达式为：

T1∞join-conditionT2 （4）

可以先计算半联接，然后再和T2联接，其关系表达式为：

式（4）和式（5）是等价的，为简明起见，假设要做的联接是自然联接来证明式（6）：

在式（5）中，虽然用两个联接代替了一个联接，实际上却提高了联接的经济性。为计算T1和T2的半联接，可以先在联接条件中的属性上对T2做投影，然后将结果与T1用相同的条件进行联接，即：

式（7）的第一步中潜在地减少了通信代价，因为T2的投影要比T2小很多，这样就可以避免在通信链路上传送大量数据。当然，这种操作也必须为额外的对半联接结果和T2的联接付出代价，如果在通信上节省的代价超过了额外联接的代价，则半联接操作就是成功的。

2.3 半联接在数据库表中的应用

下面以B地的表S(Id,Specialty)和C地的表C(StuId，Course)来详细说明半联接操作。假设A地的应用要计算Id和StuId的等值联接。以上表的属性分别为 Id 和 StuId（9 个字节）、Specialty（3 个字节）、Course（6个字节）。设表S大约有1 500个元组；大约有500个学生至少选修一门课程，且平均每个学生选修4门课程，则表C中大约2 000个元组。联接的结果中大约有2 000个元组，每个元组的长度为18个字节。将A地的应用按半联接操作来完成可以分三步完成。

（1）在C地计算表C在StuId上的投影并传送到B地，即传输 F=∏StuId(C)的值，它的大小为 9×500=4 500字节。F中包含目前至少选修一门课程的学生的Id。

（2）在B地根据联接条件对表S和F做联接并把结果传送到C地，即传输R=∏Id,Specialty(S∞F),它的大小为12×500=6 000个字节。R中包含了对应与表S中所有至少选修了一门课程的学生的信息。

（3）在C地根据联接条件对表C和R做联接，然后把联接结果返回到A地。它的大小为18×2 000=36 000字节。

以上操作总共传送了46 500字节，三个步骤的计算对应以下关系代数表达式：

2.4 几种联接查询策略的比较

（1）若将表S和C均送到A地做联接，需要传送 12×1 500+15×2 000=48 000 字节。

（2）若把表S传送到C地并计算联接，然后把结果传送到A地，需要传送 12×1 500+18×2 000=54 000字节。

（3）若把表T传送到B地并计算联接，然后把结果传送到A地，需要传送 12×2 000+18×2 000=66 000字节。

在半联接操作中总共传送了46 500字节，比较上述三种方法，就通信代价而言，半联接的方法经济性较好。

3 结 语

通信代价是衡量分布式数据库查询代价的主要指标，半联接方法的全局查询策略传输代价较小，它能有效的提高分布式数据库的查询效率，采用半联接方法是可行的。对复杂的联接查询而言，可能存在多种半联接方法，计算多种半联接方法的代价，可以从中找到一种最佳方法，从而选择最优方案。

[1]张学琴.基于高校教材管理系统的分布式查询优化技术[J].信息技术,2009（12）：114-116.

[2]陈晓明.分布式数据库分片关系变换查询优化[J].电子设计工程，2011(8)：44-46.

[3]Jeffrey A,Hoffer,Mary B,et al.Modern Database Management Seventh Edition[M].北京：电子工业出版社,2006.

[4]Philip M,Lewis,Arthur Bernstein,et al.Database And Transaction Processing[M].北京：机械工业出版社,2005.

[5]Michael V,Mannino.Database Design,Application Development,and Administration[M].北京：电子工业出版社,2005.

Research on the Strategies of Overall Query Optimization Based on the Semijoin

HE Aihua1QI Xiaoming2
(1.Bengbu College，Bengbu 233030；2.China University of Mining and Technology，Xuzhou 221116)

The data distribution in Database systems of a distributed data processing results in the complexity of the query processing.It needs to consider the network flows,response duration,algorithms complexity factors,etc.In the network environment,reducing the amount of data transmission can greatly improve query efficiency.One of the query optimizer methods is to reduce the amount of data transmission by effective join methods.

distributed database；semijoin；relations algebra；query optimizer

TP301

A

1673-1980（2012）01-0126-02

2011-10-08

安徽省教育厅项目(2010SQRL113)；高校优秀青年人才基金项目

何爱华(1975-)，女，安徽太湖人，硕士，安徽省蚌埠学院计算机科学与技术系讲师，研究方向为计算机技术。