嵌入式移动实时数据库中一种基于代价模型的查询优化技术.doc

《嵌入式移动实时数据库中一种基于代价模型的查询优化技术.doc》由会员分享，可在线阅读，更多相关《嵌入式移动实时数据库中一种基于代价模型的查询优化技术.doc（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、摘 要随着当前最先进的无线通信和移动计算机技术的发展，移动环境下查询处理中的表连接涉及到不同站点之间的操作，这些站点包括固定服务器和移动计算机。由于节省电源的需要以及移动计算环境下一些不对称的特征表现，常规的为分布式数据库设计的查询处理方案不能直接应用于移动计算环境下。分布式环境下常用到的查询优化算法主要是基于连接/半连接的优化算法，以及由此而提出的SDD-1算法等等。这些算法在分布式数据库中得以广泛运用。移动数据库技术是一种可以支持移动计算环境的分布式数据库技术，在分布式数据库中使用的这些算法到了移动环境下有必要对其进行一定的改进，包括其代价估算模型，才能适应新的要求。移动环境下具有很多不对

2、称的特征。根据这些特征，可以针对连接和查询处理(主要是多关系连接查询操作)分别设计相应的方案。直观的看来，在移动环境中使用半连接操作能有效减少数据传输量和电源消耗量。对不同连接方式进行实验可以看到这些特征对于查询代价的影响。从模拟实验得出的结果可以看到，通过充分考虑移动环境网络拓扑结构和其它特征，提出的相关算法在减少移动终端电源消耗和数据传输量两个方面都是非常有效的，并且通过对其进行适当扩展，这些策略能得以应用进而设计出一个适用于移动计算环境下的有效查询处理过程。关键词：移动计算，查询处理，表连接，多元连接查询46AbstractWith the cutting edge technology

3、 advance in wireless and mobile computers, the query processing in a mobile environment involves join processing among different sites which include static servers and mobile computers. Because of the need for energy saving and also the presence of asymmetric features in a mobile computing environme

4、nt, the conventional query processing for a distributed database cannot be directly applied to a mobile computing system. the regular optimization algorithms of distributed query, such as the optimization algorithm based on join,the optimization algorithm based on semi join,SDD-1 algorithm, have bee

5、n greatly researched and widly used in DDBMS. Mobile DBMS is one kind of DDBMS which supports mobile computing. However, the regular optimization algorithms used in DDBMS must be developed so as to apple to the Mobile DBMS. without doing any changes, these algorithms wont be fitted for the mobile co

6、mputing environment.There are many asymmetric features in a mobile environment. Then, in light of these features, query processing methods for both join and query processing can be devised. Intuitively, employing semijoin operations in a mobile computing environment is able to further reduce both th

7、e amount of data transmission and energy consumption. According to those asymmetric features of a mobile computing system, two different join methods have been examined. For query processing, which refers to the processing of multijoin queries, two query processing schemes are devised. It is shown b

8、y the simulation results that, by exploiting the asymmetric features, these characteristic functions are very powerful in reducing both the amounts of energy consumption and data transmission incurred and can lead to the design of an efficient and effective query processing procedure for a mobile co

9、mputing environment.Key words: mobile computing, query processing, join method, multijoin queries.目 录摘 要IAbstractII1引言1.1课题背景(1)1.2国内外研究状况(1)1.3本文的组织(7)2分布式数据库的查询优化方法与技术2.1基于半连接操作的优化算法(9)2.2多关系半连接查询优化算法(13)2.3SDD-1算法(19)2.4本章小结(20)3嵌入式/移动实时环境下的查询优化处理3.1适用于移动数据库系统的客户/服务器结构(22)3.2嵌入式/移动实时数据库查询优化处过程(25

10、)3.3嵌入式/移动实时环境下的查询代价分析(27)3.4代价估算公式(28)3.5本章小结(30)4 嵌入式/移动实时环境下的数据库查询优化算法4.1 查询处理方法和优化策略(31)4.2 算法仿真实验与性能分析(33)4.3本章小结(39)5结束语5.1总结(40)5.2未来展望(40)致 谢(42)参考文献(43)1 引言1.1 课题背景互联网正不断延伸、渗透，推动我们进入一个移动信息社会，任何可以获得并传播信息的地方都可以成为人们的工作场所。信息系统正逐渐走出传统的机房与桌面，使用户能够随时随地获取为做出正确决策所需要的信息，并使企业事务一发生便可获得反馈信息。这就是移动计算模式，也就

11、是所谓的“Computing Anywhere”。在移动计算模式1中，由移动终端(如笔记本、手机、PDA等)构成的计算结点可以在自由移动的过程中保持网络连接，使得人们在任何时候、任何地点、访问任何数据的需求成为可能。但是原来基于有线网络和固定主机的分布式数据库不再适应这种应用环境，于是一种更加灵活、复杂的数据库技术便应运而生，并迅速成为一个新的研究热点，这就是移动数据库。所谓移动数据库技术是指支持移动计算环境的分布式数据库技术，它涉及数据库，分布式计算以及移动通讯等多个学科领域，已成为分布式数据库一个新的研究方向。由于移动数据库系统的终端设备通常不是传统的台式计算机，而是诸如掌上电脑，PDA，

12、车载设备，移动电话等嵌入式设备，因此，它又被称为嵌入式移动数据库系统。在移动数据库的设计中，需要考虑诸多传统计算环境下不需要考虑的问题，如对断接操作的支持，对跨区长事务的支持，对位置相关查询的支持，对查询优化的特殊考虑以及对提高有限资源的利用率和对系统效率的考虑等等。为了有效地解决上述问题，诸如复制与缓存技术，移动事务处理，数据广播技术，移动查询处理与查询优化，位置相关的数据处理及查询技术，移动信息发布技术，移动Agent等技术在移动数据库中具有特别的意义。它们都是实现和完善移动数据库的关键性技术，还有待于人们的进一步探索。1.2 国内外研究状况移动计算环境以及移动设备的特点，对移动计算的应用

13、软件提出新了的要求。因此嵌入式移动数据库管理系统与传统数据库管理系统相比，也存在特殊的要求，主要表现为以下几方面：1) 易于定制。在嵌入式/移动环境下，软硬件资源有限，因此嵌入式系统中从硬件、操作系统到数据库，都强调与具体的移动计算应用的捆绑和集成。所以可定制是该环境下的软件的最大特点。因此EMDBMS的开发应该以组件化的思想想为指导，便于系统根据用户的实际需求进行定制。2) 内核尽可能小。这主要是由于移动终端存储容量、计算能力等都有限。3) 便于用户使用。移动用户的计算机水平普遍不高，系统应向用户屏蔽掉数据库系统的技术细节，并且提供自动配置功能，即系统能根据用户当前的软、 硬件状态自动地配置

14、系统参数。4) 便于移植。移动设备的硬件资源多种多样，所使用的操作系统也不尽相同，因此移动DBMS应能方便地在各个平台间移植。5) 支持断接操作。在移动计算环境中，断接不应该被视为故障，而应作为一种特殊情况来处理。即使在断接情况下，用户也能进行各种操作，并且在用户重新入网时，系统负责进行同步，以保持数据的一致性。这些操作对用户应该都是透明的。1.2.1 国内外相关产品及技术目前，国内外很多公司都在嵌入式移动环境领域做了很多工作，一些大型的数据库公司纷纷推出自己相应的数据库产品，如Sybase的iAnywhere，Informix的Cloudscape，Oracle的think9i2-4。在国内

15、，中国人民大学推出了人大小金灵。由于这些产品在研究开发时的重点不同，因此这些产品各有特点，但在某些方面又有不足之处。Oracle公司，Informix公司的移动数据库产品都是基于客户/Agent/服务器这样一个三层的无连接结构，它们主要解决移动客户机与数据库之间因为无线网络的低带宽、高延迟、易中断而带来的网络连接问题。通过扩展传统的客户/服务器结构来提高无线网络的使用效率。而Sybase公司则将其一直处于领先地位的复制技术的产品进行延伸，推出了基于会话的Sybase Sql Anywhere和基于消息的SQL Remote两种复制方式。但它没有涉及客户机的移动性、数据广播方式、应用程序的不同一

16、致性要求等方面。1.2.2 嵌入式/移动实时数据库查询处理相关技术查询处理是关系型数据库系统的一个重要问题，而描述性的数据查询语言引起的低效率问题在嵌入式环境下更为严重。所以，能否在嵌入式系统中建立一个成功的关系DBMS，采用什么样的查询处理及优化技术是十分关键的。在嵌入式和移动环境下，由于移动设备和无线网络的特殊性，查询优化又有了新的含义。嵌入式移动环境下查询优化和处理技术是指在传统分布式数据库查询优化和处理技术的基础上利用多种方法，消除带宽多样性、断接等因素产生的影响，使查询引擎能够根据当前可用网络条件采取恰当的优化策略。同时，针对移动设备有限的电源能力，需要合理地组织本地数据库管理、远程

17、数据库访问等消耗电能较多的操作，达到节能目的，延长关键数据的可用时间。综合国内外相关研究文献，大致可以将涉及到嵌入式/移动实时数据库的查询处理分为以下几种：1)语义缓存这是研究得比较多的一个方向，具体适用的范围也是移动终端，这种策略更多的考虑的是移动主机相对较弱的存储和计算能力。因此其思路也就是更细化移动客户端缓存的粒度，由此而发展出移动子集，查询修剪等相关技术。缓存技术并不是新的技术，它已经在很多传统的领域得到广泛的运用。它利用了数据的空间局部性，其性能取决于数据库的物理组织，不合适的物理组织可能造成较高的网络通讯和空间开销。在传统的页缓存技术中，由于没有保持缓存数据的语义信息，客户机主要依

18、靠网络连接服务器来判断局部缓存数据是否与查询结果相匹配，这种方法在出现断接时是不可行的。这种理论更偏向从物理优化角度进行研究，因此语义缓存的实现应该有自定义的底层存储管理系统，它能使得缓存的数据带有时间和空间的特征。2)传统分布式数据库系统查询优化算法的扩展和改进传统分布式数据库系统中研究的较多的就是尽量减少网络开销的半连接操作优化算法。但是，嵌入式/移动实时数据库系统的网络拓扑结构与传统分布式数据库系统有很大的区别，网络中结点的类型和功能也有很大的不同。首先，嵌入式/移动实时数据库系统中的移动终端自带一个本地DBMS，具有一定的自治功能。很多最新的信息或者表都最先存在移动终端，这也就使得参与

19、连接运算所涉及的站点有可能包括移动终端。移动终端参与运算带来的电源消耗，网络传输等，将很大程度的影响整个查询操作的性能。而在传统的分布式数据库系统中，由于固定主机的计算能力和存储能力一般都远大于移动终端，半连接操作仅仅考虑固定主机之间的网络传输等消耗，这也使得分布式环境下的优化算法不能直接应用到嵌入式/移动实时数据库所在的移动网络环境下。3)多重查询优化处理策略多重查询处理优化(Multiple Query Processing, MQP)就是对一组查询语句，求出它们的公共子表达式(Common Subexpression，CSE)，在查询过程中，公共子表达式仅被执行一次，得到一个中间结果，所

20、有包含该公共子表达式的查询都使用这一中间结果，这样就使得查询代价大为降低。这种策略主要是从移动网络数据广播的方面进行考虑。移动计算环境的一个非常重要的特点是要在有限的网络带宽上进行数据的分发。数据分发的方式有多种：基于推动的策略、基于拉动的策略、推拉结合的策略。在基于推动的策略中，数据被组织成多盘进行广播调度，移动客户象访问一个远程磁盘一样从广播中获取自己所需要的数据。在基于拉动的策略中，移动客户通过上行链路向中央服务器发出请求，中央服务器响应并处理移动客户的请求，然后将结果数据集通过下行链路发送给移动客户。如果通过上行链路发出的请求很多，中央服务器通过下行链路发送的结果数据集的数量就会非常多

21、，占据大量的带宽资源，致使无线网络负荷过重，移动查询响应时间迅速增长。因此，若能批量处理某一时间段内移动客户的请求，对查询集中的公共子表达式仅执行一次，生成物化视图，然后对该物化视图采用广播的方式发送到移动客户端，相同的数据仅广播一次，这样将不仅降低了查询代价，也减少了带宽使用。1.2.3 传统移动计算环境体系结构移动计算技术所研究的一个重要问题是要建立一个高效、合理、可行的计算环境体系结构，满足不同应用系统的数据处理请求。这一节介绍几种典型的体系模型，并分析其体系特征。1) Imielinski通用模型图1-1描述了移动计算环境的通用模型5。这个模型将无线局域WLAN(Wireless LA

22、N)引入整个拓扑结构。其中MU可以是哑终端或移动主机；MSS提供无线接口与MO通信，而移动用户可以通过MSS存取自己的用户profile、日志、权限控制和其他私有数据。移动客户本身也管理若干文件，这需要硬件支持，将RAM扩展为VMFS。而FH是更为安全、可靠的固定网络中的静止节点。通过这个模型可以界定MCE中的许多新问题，重点要解决WLAN内部以及各WLAN之间的各种数据管理问题。通用模型建立的是一个基于小区(Cell)概念的通用个人通信网PCN(Personal Communic- ation Network)该体系中的用户在其主定位服务器HLS(Home Location Server)中

23、注册一个永久用户地址，当用户在不同小区之间移动时，所发出的请求能够透明地跨区间以不同频段来移交(Take over)或转接(Hand off)处理。作为一个参考模型，该模型描述了早期移动计算环境的基本结构，MSS作为小区无线通信的中转器，提供的无线通信带宽一般远低于固定网络并且稳定性较差。但随着无线通信能力的不断增强以及信息服务方式的变化，这种结构已经不完全合适了。2) Bayou系统结构Bayou系统是Xerox PARC开发的复制存储系统，支持MCE中的协同工作6。该系统提供允许MC主动读写共享数据的存取机制，如存取预约日历、书目数据库、会议通知、设计文档和消息布告栏等。系统对特定应用的更

24、新冲突处理机制，可以检测和解决发生的更新冲突并将更新传播，实现最终一致性。图1-2是Bayou的系统模型7。 19.2Kbps MU2Mbps MU固定网络（Mbps到Gbps）FHMSSFHMSSMSSMSSFHFH无线局域网单元无线广播单元 注： MU mobile unit：移动设备 MSS Mobile Support Station：支持移动计算的固定站点，具有无线通信接口 FH 固定主机，没有无线通信接口图1-1 移动计算体系结构通用模型应用Bayou API服务器入口存储系统服务器状态存储系统服务器状态存储系统服务器状态图1-2 Bayou系统模型Bayou系统由若干对等的服务器

25、形成服务器系统，各个服务器保留数据集的完全副本，应用通过Bayou API与服务器进行交互。Bayou系统中的应用是一个客户，由BCL(Bayou Client Library)实现API、装入应用代码、选择执行读写的副本等。Bayou API作为一个客户进入服务器的入口(Stub)支持客户机/服务器间的RPC协议，允许对服务器上的数据进行读写。系统中的客户机和服务器可以分离也可以运行在相同的主机上，无论哪种方法，Bayou都采用RAWA(Read-any/Write-any)的弱一致存取策略。Bayou系统提供支持特定应用的基于数据依赖的冲突解决方案和使用基于时标的系统全局复制管理。它更接近

26、于一个可定制系统，需要相当多的用户或系统管理员的干预。但对于实际的应用，如MRS(Meeting Room Scheduler),BCM(Bayou Calendar Manager)和BXMH(Bayou EXMH)等，可以根据具体的应用特征，选择可行的处理机制。它通过更丰富的API提供给用户对副本和一致性管理的手段，象BXMH对邮件的一致性约束不是非常严格。3) Coda/Odyssey系统结构Coda8作为一种分布式文件系统，提供了处理服务器和网络失败的两种方法：服务器复制和非连接操作，服务器复制即在多个服务器上存储文件的副本，而非连接操作可以临时缓存站点的内容，在网络非连接状态作为复制

27、的站点。Coda中复制的单元是卷，即若干存储在服务器上的文件集合，卷构成了共享文件系统的子树。支持非连接操作的关键在于三个状态之间的变换：数据预取、模拟和整合。文件数据在预取状态被提前取回到客户本地；模拟状态发生在网络非连接期间，客户访问缓存在本地的文件数据：非连接期结束后，进入整合状态，被修改的文件和目录被传播到服务器，系统处理文件数据的同步和更新冲突检测。Coda系统将上述各种复杂处理对上层应用屏蔽，由于在一些场合并不合适，因此发展产生了Odyssey系统9，可以支持移动信息访问应用。其中应用决定如何根据使用场合进行合适的调整，即采用的自适应策略是与应用相关的。1.3 本文的组织本文对于嵌

28、入式移动数据库技术进行了初步的研究，对嵌入式移动实时环境下查询优化技术及其代价模型进行了研究和比较。研究了传统分布式数据库与移动数据库的不同，进而提出了一种改进的适合移动环境下的查询优化算法。第二章主要介绍了传统的分布式数据库所使用的查询优化技术，包括基于半连接操作的多关系半连接查询优化算法以及由此衍生的一些其它算法。第三章指出了嵌入式/移动实时环境下查询优化的特点，对其做了一些合理的假设以便于对具体问题的探讨和研究。这一章同时提出了一个适用于嵌入式/移动实时数据库的查询优化处理策略。在章节的末尾主要对于嵌入式/移动实时数据库查询优化的代价模型进行了分析并给出了一个相应的代价估算公式。第四章设

29、计并实现了一个可以对于涉及多个站点的多元连接进行优化的原型系统，该原型系统使用了上一章中提到的代价模型及估算公式，借鉴了最小生成树的思想和传统分布式数据库多元连接查询优化算法。实验表明，经过该算法处理后，查询的响应时间在没有明显增加总代价的情况下有较大缩短。2 分布式数据库的查询优化方法与技术绝大多数分布式数据库系统都是关系型的，由于关系查询的语义级别较高，为查询优化提供了可能。在分布式数据库系统中有三类查询：局部查询、远程查询和全局查询。局部查询和远程查询都只涉及单个结点上的数据(本地或者远程的)，对于这两个类型，查询优化采用的技术就是集中式数据库的查询优化技术。全局查询涉及多个站点的数据，

30、因此查询处理和优化要复杂得多，下面要讨论的重点就是对于连接(Join)常用的一些算法10，因为它是查询中最费事的操作。2.1 基于半连接操作的优化算法数据在网络中传输时，以整个关系传输，然后进行连接，显然是一种冗余的方法。在一个关系传输到另一场地后，并非每个数据都参与连接操作或都有用。因此，不参与连接的数据或无用的数据不必在网络中来回传输。基于半连接的优化策略的基本原理就是采用半连接(semi join，什么是半连接技术下面将介绍)操作，在网络中尽量只传输参与连接的数据。在分布式数据库中连接查询的主要手段是半连接技术，各种不同算法的差异主要是在连接顺序上，即在保证结果一致的情况下，以什么样的顺

31、序将这些表连接起来最优。优化的对象一般是数据传输量的总和11。分布式数据库的连接查询算法应该在把握好连接查询原则的情况下，根据具体情况灵活设计。考虑分布式查询Q=A1A2，可能出现的三种情况：情况一： A1的数据(或者绝大部分)和A2的数据(或者绝大部分)都出现在连接查询中。其等价描述是：Q、A1、A2的记录数相等(或相近)。这种情况是非常常见的。例如，在电信公司的用户数据系统中，要查询两个地区的各种业务用户数量。查询结果如表2-1：地区1、地区2的数据分别存储在各自的节点中。显然，该查询是上述两个地区用户情况在业务类别相等条件下连接的结果。而且经过连接后，各个节点查询到的数据都保留在最后的查

32、询结果中，没有出现某个子查询的数据传送到上层节点后对最后结果没有贡献的情况。这样的连接查询完全可以采用合并查询的算法。与合并查询的唯一不同是最后得到子查询的结果通过连接的方式组合成为最后结果，而不是合并。表2-1 两个地区的用户数据地区业务地区1地区2固定电话544,233667,234小灵通156,433185,233宽带48,77768,344 情况二： A1的数据(或者绝大部分)都出现在连接查询结果中，而A2的数据又很多对查询的结果毫无贡献。其等价描述是：Q的记录数和A1相等(或相近)，且小于A2的记录数。下面的例子可以说明为什么会出现这样的情况：假设某公司需要查询该公司的供应部门采购情

33、况，下面是相关数据的定义和存储情况：采购部门的采购单结构如下： NO：采购单编号，10个字节AMOUNT：采购金额，5个字节GOODNO：采购货物代码，5个字节TMIE：采购时间，4个字节假设需要查询的采购单记录数量是10。假设公司的货物代码表是由设备维护部门维护的，与采购单不在一个节点上，货物代码表的结构如下：GOODNO：货物代码，5个字节GOODNAME：货物名称，15个字节假设有10000种货物，这样货物代码表的总数量是20*10000=200000字节。查询的结果是两个表进行表连接(采购货物代码二货物代码)，查询结果是30*10=300字节。如果采用合并查询的算法，则传输的数据量是2

34、00000十20*10=200200字节，是实际查询结果的几百倍。出现这样情况的原因，主要是因为货物代码表的绝大部分内容，都没有对查询结果做出贡献，因为我们只需要10种货物的名称，没有必要将所有10000种货物的代码表都传送过来。一种改进的查询算法如下：设供应部所在节点为“节点1”，对它的原子查询请求是A1；设备管理部门所在的节点为“节点2”，对它的原子查询请求是A2。第一步，GQP将全局查询要求分解为两个子查询A1和A2，将A1发送到节点1；第二步，节点工做查询A1，然后将A1结果送回GQP。此步骤的传输量是200字节；第三步，GQP将A1的结果和A2发送到节点2。此步骤的传输量为200个字

35、节；第四步，节点2先做查询A2，再做Q= A1A2，然后将最后结果Q送往GQP。此步骤的传输量是300字节。上述算法的数据总传输量是：200+200+300=700字节。这个算法可以作为情况二的可行算法，其目标是减少数据传输量。情况三：A1和A2中均有很多数据不出现在查询结果Q中。等价描述是：A1和A2的记录数都大于Q的记录数。半连接的概念首先是在分布式数据系统分布式查询设计中提出的，它的定义如下：设R和S是两个关系，属性A，B，AR，BS，则RABS(R的属性A和S的属性B的半连接)定义14为：RABS= x|x R且yS使得xA=yB。半连接定义的另一种理解方法是RS = R(RS)，即R

36、和S进行表连接后在R上的投影。值得注意的是，与连接操作不同，半连接操作不满足交换律，即RSSR。半连接处理的依据是：RS = RaS，其中a表示R与S连接的属性列。通过半连接处理优化连接操作的依据是：RSS(RS)。当RS只是R的一小部分时，可以大大减少数据的传输量。其执行过程如图2-1所示。半连接程序其传输代价用公式T=C0+C1X粗略估算。其中，X是数据传输量，这里可以以bit(位)为单位计算；C0为两结点之间初始化一次传输所花费的开销，它由通信系统决定，近似为一个常数，单位为s(秒)；C1为单位数据传输的代价，单位为(秒/bit)。其操作过程如下：站点1(关系R) 站点2(关系S) a(

37、S)Ra(S) (Ra(S)S图2-1 基于半连接的执行示例第步：在站点2计算关系S在属性a上的投影：a(S)。第步：把a(S)的结果从站点2传到站点1，其传输代价为：C0+ C1*size(a)*val(aS)其中size(a)表示属性a的长度，val(aS)表示关系S中属性a的个数。第步：在站点1计算半连接，设其结果为R，则R=RS。实际上，这个操作是执行Ra(S)。 第步：把R从站点1传到站点2，其传输代价为：C0+Cl*size(R)*card(R)其中size(R)是R中元组的长度，card(R)是R的元组数。第步：在站点2执行连接操作RS。显然， 步骤、无需传输费用，所以执行这样一

38、个半连接程序，总的传输代价为：T= C0+C1*Size(a)*val(aS)+C0+C1*Size(R)*card(R)=2*C0+C1(Size(a)*val(aS)+Size(R)*card(R)半连接运算不具有对称性，即没有交换性。因此另一个等价的半连接程序(SR) S可能具有不同的传输代价。通过对它们代价进行比较，就可以确定R和S的最优半连接程序。如果不采用半连接程序法，而直接采用连接法，则需要把其中一个关系从一个站点传到另一个站点。例如在站点2执行连接操作，相应传输代价为：T=C0+Cl*size(R)*card(R)其中size(R)和card(R)分别为关系R中元组的长度和元组

39、的个数。在一般情况下，card(R)card(R)是成立的，即TT成立，因此半接程序法的传输代价较小，采用半连接程序执行连接操作是合适的。现在重新考虑Q=A1A2(A1和A2都是原子查询)，情况三，A1、A2中均有很多数据不在现在查询结果Q中。此时，应该尽量避免A1和A2中多余数据即在Q中并不出现的数据)在网络之间传输。接下来就是基于半连接的算法：第一步，应该考虑一下最终的结果Q中包含A1和A2的数据哪一个更多一些。如果是A1多一些，那么下面的算法将按照A2A1，的方向进行；反之将按照A1A2的方向进行。这里不妨假设结果Q中A1的数据更多一些；第二步，节点1(A1所在节点)将A1需要与A2进行

40、连接的属性列通过GQP发送到节点2 (A2所在节点)；第三步，在节点2将A2与节点1发送过来的数据进行连接操作，所得结果即为A2 A1；第四步，将节点2的连接结果(A2A1)通过GQP再次发送到节点1；第五步，在节点1将A1与节点2通过GQP发送过来的数据(A2A1)做连接操作，连接后的结果是A1(A2A1)A1A2。第六步，将最终的查询结果发送给GQP。可以看出，半连接的处理方法虽然可以节省一些数据传输量，但是算法的复杂度也相应提高，同时节点之间的相互调度也增加了一些延迟时间。在实际应用中还需要仔细在节省的数据传输量，算法复杂度和延迟时间之间进行衡量。2.2 多关系半连接查询优化算法普通多关

41、系半连接查询方法是按照关系间的连接顺序执行半连接，优点是处理简单，不足之处是没有考虑到如何优化子查询的半连接顺序来进一步减少网络通信的代价12。本文的基于多关系半连接查询优化算法是针对普通多关系半连接查询方法的不足之处而提出的，即通过代价估算和半连接，在如何进一步减少子查询的网络代价问题上进行了改进。本文将执行所有子查询所产生的中间结果的数据量作为网络代价的决定性因素，本文约定多关系半连接查询优化算法的优化效益，是指多关系半连接查询优化算法与普通多关系半连接查询方法进行比较所得的相对效益。本文定义确定多关系半连接查询优化算法优化效益的函数为式2-113。设(执行普通多关系半连接查询方法的网络代

42、价一执行多关系半连接查询优化算法的网络代价)/执行普通多关系半连接查询方法的网络代价。(式 2-1)数据库分布如图2-2所示，站点0、1、2、3、4 分别表示不同的计算机，站点1、2、3、4的数据库中分别存放着不同的表。站点0存放全局数据库信息，例如全局表信息、全局表与局部表的对应信息(如局部表所属的局部数据库访问信息如Provider、 UserID、Password、DataSource等)，其中全局表信息包括全局表表名、全局表各字段信息，全局表信息只是全局表的表结构，不存放实际数据，实际数据存放在局部数据库的局部表中。站点1、2、3、4分别存放局部数据库信息，其中局部表信息包括局部表名称

43、、局部表字段信息，还包括实际数据。例子中各个全局表和局部表的主要字段有ID标志符和Name名称两个属性，为了方便计算通信代价，例子中假定两个属性具有相同的长度。例子中， 站点0向本站点的全局数据库发出全局查询请求，全局查询语句经过查询分解，转换为对站点1、2、3、4的局部查询语句，从而全局查询转换为对站点1、2、3、4中的局部数据库的分布式查询。分布式查询过程中的中间数据传输到站点0，在站点0进行缓存，最后在站点0对中间数据进行拼装，作为最终查询结果返回给用户。下面讨论分布式查询在优化前及优化后的半连接执行顺序、通信代价及优化效益。查询例子：以链式连接ProductsOrderDetaiIsO

44、rdersCustomers作为基本连接。站点0OrdersOrderDetailsEmplyeesProductsShippersCustomers站点1站点2站点3站点4OrdersProductsShippersCustomersOrderDetailsEmplyees全局数据库中的全局表局部数据库中的局部表图2-2 数据库分布图全局查询语句为：Select ProductName,OrderDetaiIName,OrderName,CustomerNameFrom Products,OrderDetails,Orders,CustomersWhere Products.ProductI

45、D= OrderDetails.ProductID AndOrderDetails.OrderlD= Orders.OrderlD AndOrders.CustomerID= Customers.CustomerID前文己描述过站点0中的全局数据库除了存放全局表信息外，还存放着全局表与局部表的对应信息，这里对应信息除了上述已描述过的局部表所属的局部数据库访问信息外，还存放着每个局部表的统计量参数信息。设：局部表Orders的统计量T为830，表示局部表Orders中的总的记录数为830；局部表Orders的统计量V(OrderlD)为830，表示局部表Orders中在OrderlD属性上值不同

46、的记录数为830；局部 表 Orders的统计量V(CustomerlD)为90，表示局部表Orders中在CustomerID属性上值不同的记录数为90。例子中，各个关系、连接属性及其统计量参数如表2-2所示。链式连接的全局查询语句经过初步查询分解为以下三个查询语句：Select ProductName,OrderDetailName From Products,OrderDetailsWhere Products.ProductID= OrderDetails.ProductID及 Select OrderDetaiIName,OrderName From OrderDetails,Ord

47、ersWhere OrderDetails.OrderlD= Orders.OrderID表2-2 例子中的关系及统计量参数关系统计量TOrders830V(OrderID)=830,V(CustomerlD)=90, V(EmployeelD)110，V(ShipperlD)15OrderDetails2850V(OrderID)=830, V(ProductID)=80Employees110V(EmployeelD)110Customers90V(CustomerlD)90Pruducts80V(ProductID)=80Shippers15V(ShipperlD)15及Select OrderName,CustomerName From Orders,CustomersWhere Orders.CustomerID= Customers.CustomerID图