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

PAGE44摘要随着当前最先进的无线通信和移动计算机技术的发展，移动环境下查询处理中的表连接涉及到不同站点之间的操作，这些站点包括固定服务器和移动计算机。由于节省电源的需要以及移动计算环境下一些不对称的特征表现，常规的为分布式数据库设计的查询处理方案不能直接应用于移动计算环境下。分布式环境下常用到的查询优化算法主要是基于连接/半连接的优化算法，以及由此而提出的SDD-1算法等等。这些算法在分布式数据库中得以广泛运用。移动数据库技术是一种可以支持移动计算环境的分布式数据库技术，在分布式数据库中使用的这些算法到了移动环境下有必要对其进行一定的改进，包括其代价估算模型，才能适应新的要求。移动环境下具有很多不对称的特征。根据这些特征，可以针对连接和查询处理(主要是多关系连接查询操作)分别设计相应的方案。直观的看来，在移动环境中使用半连接操作能有效减少数据传输量和电源消耗量。对不同连接方式进行实验可以看到这些特征对于查询代价的影响。从模拟实验得出的结果可以看到，通过充分考虑移动环境网络拓扑结构和其它特征，提出的相关算法在减少移动终端电源消耗和数据传输量两个方面都是非常有效的，并且通过对其进行适当扩展，这些策略能得以应用进而设计出一个适用于移动计算环境下的有效查询处理过程。关键词：移动计算，查询处理，表连接，多元连接查询AbstractWiththecuttingedgetechnologyadvanceinwirelessandmobilecomputers,thequeryprocessinginamobileenvironmentinvolvesjoinprocessingamongdifferentsiteswhichincludestaticserversandmobilecomputers.Becauseoftheneedforenergysavingandalsothepresenceofasymmetricfeaturesinamobilecomputingenvironment,theconventionalqueryprocessingforadistributeddatabasecannotbedirectlyappliedtoamobilecomputingsystem.theregularoptimizationalgorithmsofdistributedquery,suchastheoptimizationalgorithmbasedonjoin,theoptimizationalgorithmbasedonsemijoin,SDD-1algorithm,havebeengreatlyresearchedandwidlyusedinDDBMS.MobileDBMSisonekindofDDBMSwhichsupportsmobilecomputing.However,theregularoptimizationalgorithmsusedinDDBMSmustbedevelopedsoastoappletotheMobileDBMS.withoutdoinganychanges,thesealgorithmswon’tbefittedforthemobilecomputingenvironment.Therearemanyasymmetricfeaturesinamobileenvironment.Then,inlightofthesefeatures,queryprocessingmethodsforbothjoinandqueryprocessingcanbedevised.Intuitively,employingsemijoinoperationsinamobilecomputingenvironmentisabletofurtherreduceboththeamountofdatatransmissionandenergyconsumption.Accordingtothoseasymmetricfeaturesofamobilecomputingsystem,twodifferentjoinmethodshavebeenexamined.Forqueryprocessing,whichreferstotheprocessingofmultijoinqueries,twoqueryprocessingschemesaredevised.Itisshownbythesimulationresultsthat,byexploitingtheasymmetricfeatures,thesecharacteristicfunctionsareverypowerfulinreducingboththeamountsofenergyconsumptionanddatatransmissionincurredandcanleadtothedesignofanefficientandeffectivequeryprocessingprocedureforamobilecomputingenvironment.Keywords:mobilecomputing,queryprocessing,joinmethod,multijoinqueries.目录TOC\o"1-2"\u摘要 IAbstract II1 引言1.1 课题背景 (1)1.2 国内外研究状况 (1)1.3 本文的组织 (7)2 分布式数据库的查询优化方法与技术2.1 基于半连接操作的优化算法 (9)2.2 多关系半连接查询优化算法 (13)2.3 SDD-1算法 (19)2.4 本章小结 (20)3 嵌入式/移动实时环境下的查询优化处理3.1 适用于移动数据库系统的客户/服务器结构 (22)3.2 嵌入式/移动实时数据库查询优化处过程 (25)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)引言课题背景互联网正不断延伸、渗透，推动我们进入一个移动信息社会，任何可以获得并传播信息的地方都可以成为人们的工作场所。信息系统正逐渐走出传统的机房与桌面，使用户能够随时随地获取为做出正确决策所需要的信息，并使企业事务一发生便可获得反馈信息。这就是移动计算模式，也就是所谓的“ComputingAnywhere”。在移动计算模式[1]中，由移动终端(如笔记本、手机、PDA等)构成的计算结点可以在自由移动的过程中保持网络连接，使得人们在任何时候、任何地点、访问任何数据的需求成为可能。但是原来基于有线网络和固定主机的分布式数据库不再适应这种应用环境，于是一种更加灵活、复杂的数据库技术便应运而生，并迅速成为一个新的研究热点，这就是移动数据库。所谓移动数据库技术是指支持移动计算环境的分布式数据库技术，它涉及数据库，分布式计算以及移动通讯等多个学科领域，已成为分布式数据库一个新的研究方向。由于移动数据库系统的终端设备通常不是传统的台式计算机，而是诸如掌上电脑，PDA，车载设备，移动电话等嵌入式设备，因此，它又被称为嵌入式移动数据库系统。在移动数据库的设计中，需要考虑诸多传统计算环境下不需要考虑的问题，如对断接操作的支持，对跨区长事务的支持，对位置相关查询的支持，对查询优化的特殊考虑以及对提高有限资源的利用率和对系统效率的考虑等等。为了有效地解决上述问题，诸如复制与缓存技术，移动事务处理，数据广播技术，移动查询处理与查询优化，位置相关的数据处理及查询技术，移动信息发布技术，移动Agent等技术在移动数据库中具有特别的意义。它们都是实现和完善移动数据库的关键性技术，还有待于人们的进一步探索。国内外研究状况移动计算环境以及移动设备的特点，对移动计算的应用软件提出新了的要求。因此嵌入式移动数据库管理系统与传统数据库管理系统相比，也存在特殊的要求，主要表现为以下几方面：1)易于定制。在嵌入式/移动环境下，软硬件资源有限，因此嵌入式系统中从硬件、操作系统到数据库，都强调与具体的移动计算应用的捆绑和集成。所以可定制是该环境下的软件的最大特点。因此EMDBMS的开发应该以组件化的思想想为指导，便于系统根据用户的实际需求进行定制。2)内核尽可能小。这主要是由于移动终端存储容量、计算能力等都有限。3)便于用户使用。移动用户的计算机水平普遍不高，系统应向用户屏蔽掉数据库系统的技术细节，并且提供自动配置功能，即系统能根据用户当前的软、硬件状态自动地配置系统参数。4)便于移植。移动设备的硬件资源多种多样，所使用的操作系统也不尽相同，因此移动DBMS应能方便地在各个平台间移植。5)支持断接操作。在移动计算环境中，断接不应该被视为故障，而应作为一种特殊情况来处理。即使在断接情况下，用户也能进行各种操作，并且在用户重新入网时，系统负责进行同步，以保持数据的一致性。这些操作对用户应该都是透明的。国内外相关产品及技术目前，国内外很多公司都在嵌入式移动环境领域做了很多工作，一些大型的数据库公司纷纷推出自己相应的数据库产品，如Sybase的iAnywhere，Informix的Cloudscape，Oracle的think9i[2-4]。在国内，中国人民大学推出了人大小金灵。由于这些产品在研究开发时的重点不同，因此这些产品各有特点，但在某些方面又有不足之处。Oracle公司，Informix公司的移动数据库产品都是基于客户/Agent/服务器这样一个三层的无连接结构，它们主要解决移动客户机与数据库之间因为无线网络的低带宽、高延迟、易中断而带来的网络连接问题。通过扩展传统的客户/服务器结构来提高无线网络的使用效率。而Sybase公司则将其一直处于领先地位的复制技术的产品进行延伸，推出了基于会话的SybaseSqlAnywhere和基于消息的SQLRemote两种复制方式。但它没有涉及客户机的移动性、数据广播方式、应用程序的不同一致性要求等方面。嵌入式/移动实时数据库查询处理相关技术查询处理是关系型数据库系统的一个重要问题，而描述性的数据查询语言引起的低效率问题在嵌入式环境下更为严重。所以，能否在嵌入式系统中建立一个成功的关系DBMS，采用什么样的查询处理及优化技术是十分关键的。在嵌入式和移动环境下，由于移动设备和无线网络的特殊性，查询优化又有了新的含义。嵌入式移动环境下查询优化和处理技术是指在传统分布式数据库查询优化和处理技术的基础上利用多种方法，消除带宽多样性、断接等因素产生的影响，使查询引擎能够根据当前可用网络条件采取恰当的优化策略。同时，针对移动设备有限的电源能力，需要合理地组织本地数据库管理、远程数据库访问等消耗电能较多的操作，达到节能目的，延长关键数据的可用时间。综合国内外相关研究文献，大致可以将涉及到嵌入式/移动实时数据库的查询处理分为以下几种：1)语义缓存这是研究得比较多的一个方向，具体适用的范围也是移动终端，这种策略更多的考虑的是移动主机相对较弱的存储和计算能力。因此其思路也就是更细化移动客户端缓存的粒度，由此而发展出移动子集，查询修剪等相关技术。缓存技术并不是新的技术，它已经在很多传统的领域得到广泛的运用。它利用了数据的空间局部性，其性能取决于数据库的物理组织，不合适的物理组织可能造成较高的网络通讯和空间开销。在传统的页缓存技术中，由于没有保持缓存数据的语义信息，客户机主要依靠网络连接服务器来判断局部缓存数据是否与查询结果相匹配，这种方法在出现断接时是不可行的。这种理论更偏向从物理优化角度进行研究，因此语义缓存的实现应该有自定义的底层存储管理系统，它能使得缓存的数据带有时间和空间的特征。2)传统分布式数据库系统查询优化算法的扩展和改进传统分布式数据库系统中研究的较多的就是尽量减少网络开销的半连接操作优化算法。但是，嵌入式/移动实时数据库系统的网络拓扑结构与传统分布式数据库系统有很大的区别，网络中结点的类型和功能也有很大的不同。首先，嵌入式/移动实时数据库系统中的移动终端自带一个本地DBMS，具有一定的自治功能。很多最新的信息或者表都最先存在移动终端，这也就使得参与连接运算所涉及的站点有可能包括移动终端。移动终端参与运算带来的电源消耗，网络传输等，将很大程度的影响整个查询操作的性能。而在传统的分布式数据库系统中，由于固定主机的计算能力和存储能力一般都远大于移动终端，半连接操作仅仅考虑固定主机之间的网络传输等消耗，这也使得分布式环境下的优化算法不能直接应用到嵌入式/移动实时数据库所在的移动网络环境下。3)多重查询优化处理策略多重查询处理优化(MultipleQueryProcessing,MQP)就是对一组查询语句，求出它们的公共子表达式(CommonSubexpression，CSE)，在查询过程中，公共子表达式仅被执行一次，得到一个中间结果，所有包含该公共子表达式的查询都使用这一中间结果，这样就使得查询代价大为降低。这种策略主要是从移动网络数据广播的方面进行考虑。移动计算环境的一个非常重要的特点是要在有限的网络带宽上进行数据的分发。数据分发的方式有多种：基于推动的策略、基于拉动的策略、推拉结合的策略。在基于推动的策略中，数据被组织成多盘进行广播调度，移动客户象访问一个远程磁盘一样从广播中获取自己所需要的数据。在基于拉动的策略中，移动客户通过上行链路向中央服务器发出请求，中央服务器响应并处理移动客户的请求，然后将结果数据集通过下行链路发送给移动客户。如果通过上行链路发出的请求很多，中央服务器通过下行链路发送的结果数据集的数量就会非常多，占据大量的带宽资源，致使无线网络负荷过重，移动查询响应时间迅速增长。因此，若能批量处理某一时间段内移动客户的请求，对查询集中的公共子表达式仅执行一次，生成物化视图，然后对该物化视图采用广播的方式发送到移动客户端，相同的数据仅广播一次，这样将不仅降低了查询代价，也减少了带宽使用。传统移动计算环境体系结构移动计算技术所研究的一个重要问题是要建立一个高效、合理、可行的计算环境体系结构，满足不同应用系统的数据处理请求。这一节介绍几种典型的体系模型，并分析其体系特征。1)Imielinski通用模型图1-1描述了移动计算环境的通用模型[5]。这个模型将无线局域WLAN(WirelessLAN)引入整个拓扑结构。其中MU可以是哑终端或移动主机；MSS提供无线接口与MO通信，而移动用户可以通过MSS存取自己的用户profile、日志、权限控制和其他私有数据。移动客户本身也管理若干文件，这需要硬件支持，将RAM扩展为VMFS。而FH是更为安全、可靠的固定网络中的静止节点。通过这个模型可以界定MCE中的许多新问题，重点要解决WLAN内部以及各WLAN之间的各种数据管理问题。通用模型建立的是一个基于小区(Cell)概念的通用个人通信网PCN(PersonalCommunic-ationNetwork)该体系中的用户在其主定位服务器HLS(HomeLocationServer)中注册一个永久用户地址，当用户在不同小区之间移动时，所发出的请求能够透明地跨区间以不同频段来移交(Takeover)或转接(Handoff)处理。作为一个参考模型，该模型描述了早期移动计算环境的基本结构，MSS作为小区无线通信的中转器，提供的无线通信带宽一般远低于固定网络并且稳定性较差。但随着无线通信能力的不断增强以及信息服务方式的变化，这种结构已经不完全合适了。2)Bayou系统结构Bayou系统是XeroxPARC开发的复制存储系统，支持MCE中的协同工作[6]。该系统提供允许MC主动读写共享数据的存取机制，如存取预约日历、书目数据库、会议通知、设计文档和消息布告栏等。系统对特定应用的更新冲突处理机制，可以检测和解决发生的更新冲突并将更新传播，实现最终一致性。图1-2是Bayou的系统模型[7]。19.2KbpsMU19.2KbpsMU2MbpsMU固定网络（Mbps到Gbps）FHMSSFHMSSMSSMSSFHFH无线局域网单元无线广播单元注：MUmobileunit：移动设备MSSMobileSupportStation：支持移动计算的固定站点，具有无线通信接口FH固定主机，没有无线通信接口图1-1移动计算体系结构通用模型应用应用BayouAPI服务器入口存储系统服务器状态存储系统服务器状态存储系统服务器状态图1-2Bayou系统模型Bayou系统由若干对等的服务器形成服务器系统，各个服务器保留数据集的完全副本，应用通过BayouAPI与服务器进行交互。Bayou系统中的应用是一个客户，由BCL(BayouClientLibrary)实现API、装入应用代码、选择执行读写的副本等。BayouAPI作为一个客户进入服务器的入口(Stub)支持客户机/服务器间的RPC协议，允许对服务器上的数据进行读写。系统中的客户机和服务器可以分离也可以运行在相同的主机上，无论哪种方法，Bayou都采用RAWA(Read-any/Write-any)的弱一致存取策略。Bayou系统提供支持特定应用的基于数据依赖的冲突解决方案和使用基于时标的系统全局复制管理。它更接近于一个可定制系统，需要相当多的用户或系统管理员的干预。但对于实际的应用，如MRS(MeetingRoomScheduler),BCM(BayouCalendarManager)和BXMH(BayouEXMH)等，可以根据具体的应用特征，选择可行的处理机制。它通过更丰富的API提供给用户对副本和一致性管理的手段，象BXMH对邮件的一致性约束不是非常严格。3)Coda/Odyssey系统结构Coda[8]作为一种分布式文件系统，提供了处理服务器和网络失败的两种方法：服务器复制和非连接操作，服务器复制即在多个服务器上存储文件的副本，而非连接操作可以临时缓存站点的内容，在网络非连接状态作为复制的站点。Coda中复制的单元是卷，即若干存储在服务器上的文件集合，卷构成了共享文件系统的子树。支持非连接操作的关键在于三个状态之间的变换：数据预取、模拟和整合。文件数据在预取状态被提前取回到客户本地；模拟状态发生在网络非连接期间，客户访问缓存在本地的文件数据：非连接期结束后，进入整合状态，被修改的文件和目录被传播到服务器，系统处理文件数据的同步和更新冲突检测。Coda系统将上述各种复杂处理对上层应用屏蔽，由于在一些场合并不合适，因此发展产生了Odyssey系统[9]，可以支持移动信息访问应用。其中应用决定如何根据使用场合进行合适的调整，即采用的自适应策略是与应用相关的。本文的组织本文对于嵌入式移动数据库技术进行了初步的研究，对嵌入式移动实时环境下查询优化技术及其代价模型进行了研究和比较。研究了传统分布式数据库与移动数据库的不同，进而提出了一种改进的适合移动环境下的查询优化算法。第二章主要介绍了传统的分布式数据库所使用的查询优化技术，包括基于半连接操作的多关系半连接查询优化算法以及由此衍生的一些其它算法。第三章指出了嵌入式/移动实时环境下查询优化的特点，对其做了一些合理的假设以便于对具体问题的探讨和研究。这一章同时提出了一个适用于嵌入式/移动实时数据库的查询优化处理策略。在章节的末尾主要对于嵌入式/移动实时数据库查询优化的代价模型进行了分析并给出了一个相应的代价估算公式。第四章设计并实现了一个可以对于涉及多个站点的多元连接进行优化的原型系统，该原型系统使用了上一章中提到的代价模型及估算公式，借鉴了最小生成树的思想和传统分布式数据库多元连接查询优化算法。实验表明，经过该算法处理后，查询的响应时间在没有明显增加总代价的情况下有较大缩短。分布式数据库的查询优化方法与技术绝大多数分布式数据库系统都是关系型的，由于关系查询的语义级别较高，为查询优化提供了可能。在分布式数据库系统中有三类查询：局部查询、远程查询和全局查询。局部查询和远程查询都只涉及单个结点上的数据(本地或者远程的)，对于这两个类型，查询优化采用的技术就是集中式数据库的查询优化技术。全局查询涉及多个站点的数据，因此查询处理和优化要复杂得多，下面要讨论的重点就是对于连接(Join)常用的一些算法[10]，因为它是查询中最费事的操作。基于半连接操作的优化算法数据在网络中传输时，以整个关系传输，然后进行连接，显然是一种冗余的方法。在一个关系传输到另一场地后，并非每个数据都参与连接操作或都有用。因此，不参与连接的数据或无用的数据不必在网络中来回传输。基于半连接的优化策略的基本原理就是采用半连接(semijoin，什么是半连接技术下面将介绍)操作，在网络中尽量只传输参与连接的数据。在分布式数据库中连接查询的主要手段是半连接技术，各种不同算法的差异主要是在连接顺序上，即在保证结果一致的情况下，以什么样的顺序将这些表连接起来最优。优化的对象一般是数据传输量的总和[11]。分布式数据库的连接查询算法应该在把握好连接查询原则的情况下，根据具体情况灵活设计。考虑分布式查询Q=A1A2，情况一：A1的数据(或者绝大部分)和A2的数据(或者绝大部分)都出现在连接查询中。其等价描述是：Q、A1、A2的记录数相等(或相近)。这种情况是非常常见的。例如，在电信公司的用户数据系统中，要查询两个地区的各种业务用户数量。查询结果如表2-1：地区1、地区2的数据分别存储在各自的节点中。显然，该查询是上述两个地区用户情况在业务类别相等条件下连接的结果。而且经过连接后，各个节点查询到的数据都保留在最后的查询结果中，没有出现某个子查询的数据传送到上层节点后对最后结果没有贡献的情况。这样的连接查询完全可以采用合并查询的算法。与合并查询的唯一不同是最后得到子查询的结果通过连接的方式组合成为最后结果，而不是合并。表2-1两个地区的用户数据地区业务地区1地区2固定电话544,233667,234小灵通156,433185,233宽带48,77768,344………………情况二：A1的数据(或者绝大部分)都出现在连接查询结果中，而A2的数据又很多对查询的结果毫无贡献。其等价描述是：Q的记录数和A1相等(或相近)，且小于A2的记录数。下面的例子可以说明为什么会出现这样的情况：假设某公司需要查询该公司的供应部门采购情况，下面是相关数据的定义和存储情况：采购部门的采购单结构如下：NO：采购单编号，10个字节AMOUNT：采购金额，5个字节GOODNO：采购货物代码，5个字节TMIE：采购时间，4个字节假设需要查询的采购单记录数量是10。假设公司的货物代码表是由设备维护部门维护的，与采购单不在一个节点上，货物代码表的结构如下：GOODNO：货物代码，5个字节GOODNAME：货物名称，15个字节假设有10000种货物，这样货物代码表的总数量是20*10000=200000字节。查询的结果是两个表进行表连接(采购货物代码二货物代码)，查询结果是30*10=300字节。如果采用合并查询的算法，则传输的数据量是200000十20*10=200200字节，是实际查询结果的几百倍。出现这样情况的原因，主要是因为货物代码表的绝大部分内容，都没有对查询结果做出贡献，因为我们只需要10种货物的名称，没有必要将所有10000种货物的代码表都传送过来。一种改进的查询算法如下：设供应部所在节点为“节点1”，对它的原子查询请求是A1；设备管理部门所在的节点为“节点2”，对它的原子查询请求是A2。第一步，GQP将全局查询要求分解为两个子查询A1和A2，将A1发送到节点1；第二步，节点工做查询A1，然后将A1结果送回GQP。此步骤的传输量是200字节；第三步，GQP将A1的结果和A2发送到节点2。此步骤的传输量为200个字节；第四步，节点2先做查询A2，再做Q=A1A2，然后将最后结果Q送往GQP。上述算法的数据总传输量是：200+200+300=700字节。这个算法可以作为情况二的可行算法，其目标是减少数据传输量。情况三：A1和A2中均有很多数据不出现在查询结果Q中。等价描述是：A1和A2的记录数都大于Q的记录数。半连接的概念首先是在分布式数据系统分布式查询设计中提出的，它的定义如下：设R和S是两个关系，属性A，B，AR，BS，则RABS(R的属性A和S的属性B的半连接)定义[14]为：RABS={x|xR且yS使得x[A]=y[B]}。半连接定义的另一种理解方法是RS=R(RS)，即R和S进行表连接后在R上的投影。值得注意的是，与连接操作不同，半连接操作不满足交换律，即RSSR。半连接处理的依据是：RS=RaS，其中a表示R与S连接的属性列。通过半连接处理优化连接操作的依据是：RS＝S(RS)。当RS只是R的一小部分时，可以大大减少数据的传输量。其执行过程如图2-1所示。半连接程序其传输代价用公式T=C0+C1X粗略估算。其中，X是数据传输量，这里可以以bit(位)为单位计算；C0为两结点之间初始化一次传输所花费的开销，它由通信系统决定，近似为一个常数，单位为s(秒)；C1为单位数据传输的代价，单位为(秒/bit)。其操作过程如下：站点1(关系R)站点2(关系S)②①a(S)③Ra(S)④⑤(Ra(S))S图2-1基于半连接的执行示例第①步：在站点2计算关系S在属性a上的投影：a(S)。第②步：把a(S)的结果从站点2传到站点1，其传输代价为：C0+C1*size(a)*val(a[S])其中size(a)表示属性a的长度，val(a[S])表示关系S中属性a的个数。第③步：在站点1计算半连接，设其结果为R'，则R'=RS。实际上，这个操作是执行Ra(S)。第④步：把R'从站点1传到站点2，其传输代价为：C0+Cl*size(R)*card(R')其中size(R)是R中元组的长度，card(R')是R'的元组数。第⑤步：在站点2执行连接操作R'S。显然，步骤①、③、⑤无需传输费用，所以执行这样一个半连接程序，总的传输代价为：T'=C0+C1*Size(a)*val(a[S])+C0+C1*Size(R)*card(R')=2*C0+C1(Size(a)*val(a[S])+Size(R)*card(R'))半连接运算不具有对称性，即没有交换性。因此另一个等价的半连接程序(SR)S可能具有不同的传输代价。通过对它们代价进行比较，就可以确定R和S的最优半连接程序。如果不采用半连接程序法，而直接采用连接法，则需要把其中一个关系从一个站点传到另一个站点。例如在站点2执行连接操作，相应传输代价为：T=C0+Cl*size(R)*card(R)其中size(R)和card(R)分别为关系R中元组的长度和元组的个数。在一般情况下，card(R)>>card(R')是成立的，即T'<<T成立，因此半接程序法的传输代价较小，采用半连接程序执行连接操作是合适的。现在重新考虑Q=A1A2(A1和A2都是原子查询)，情况三，A1、A2中均有很多数据不在现在查询结果Q中。此时，应该尽量避免A1和A2中多余数据〔即在Q中并不出现的数据)在网络之间传输。接下来就是基于半连接的算法：第一步，应该考虑一下最终的结果Q中包含A1和A2的数据哪一个更多一些。如果是A1多一些，那么下面的算法将按照A2A1，的方向进行；反之将按照A1A2的方向进行。这里不妨假设结果Q中A1第二步，节点1(A1所在节点)将A1需要与A2进行连接的属性列通过GQP发送到节点2(A2所在节点)；第三步，在节点2将A2与节点1发送过来的数据进行连接操作，所得结果即为A2A1；第四步，将节点2的连接结果(A2A1)通过GQP再次发送到节点1；第五步，在节点1将A1与节点2通过GQP发送过来的数据(A2A1)做连接操作，连接后的结果是A1(A2A1)＝A1A2。第六步，将最终的查询结果发送给GQP。可以看出，半连接的处理方法虽然可以节省一些数据传输量，但是算法的复杂度也相应提高，同时节点之间的相互调度也增加了一些延迟时间。在实际应用中还需要仔细在节省的数据传输量，算法复杂度和延迟时间之间进行衡量。多关系半连接查询优化算法普通多关系半连接查询方法是按照关系间的连接顺序执行半连接，优点是处理简单，不足之处是没有考虑到如何优化子查询的半连接顺序来进一步减少网络通信的代价[12]。本文的基于多关系半连接查询优化算法是针对普通多关系半连接查询方法的不足之处而提出的，即通过代价估算和半连接，在如何进一步减少子查询的网络代价问题上进行了改进。本文将执行所有子查询所产生的中间结果的数据量作为网络代价的决定性因素，本文约定多关系半连接查询优化算法的优化效益，是指多关系半连接查询优化算法与普通多关系半连接查询方法进行比较所得的相对效益。本文定义确定多关系半连接查询优化算法优化效益的函数为式2-1[13]。设＝(执行普通多关系半连接查询方法的网络代价一执行多关系半连接查询优化算法的网络代价)/执行普通多关系半连接查询方法的网络代价。(式2-1)数据库分布如图2-2所示，站点0、1、2、3、4分别表示不同的计算机，站点1、2、3、4的数据库中分别存放着不同的表。站点0存放全局数据库信息，例如全局表信息、全局表与局部表的对应信息(如局部表所属的局部数据库访问信息如Provider、UserID、Password、DataSource等)，其中全局表信息包括全局表表名、全局表各字段信息，全局表信息只是全局表的表结构，不存放实际数据，实际数据存放在局部数据库的局部表中。站点1、2、3、4分别存放局部数据库信息，其中局部表信息包括局部表名称、局部表字段信息，还包括实际数据。例子中各个全局表和局部表的主要字段有ID标志符和Name名称两个属性，为了方便计算通信代价，例子中假定两个属性具有相同的长度。例子中，站点0向本站点的全局数据库发出全局查询请求，全局查询语句经过查询分解，转换为对站点1、2、3、4的局部查询语句，从而全局查询转换为对站点1、2、3、4中的局部数据库的分布式查询。分布式查询过程中的中间数据传输到站点0，在站点0进行缓存，最后在站点0对中间数据进行拼装，作为最终查询结果返回给用户。下面讨论分布式查询在优化前及优化后的半连接执行顺序、通信代价及优化效益。查询例子：以链式连接ProductsOrderDetaiIsOrdersCustomers作为基本连接。站点0站点0OrdersOrderDetailsEmplyeesProductsShippersCustomers站点1站点2站点3站点4OrdersProductsShippersCustomersOrderDetailsEmplyees全局数据库中的全局表局部数据库中的局部表图2-2数据库分布图全局查询语句为：SelectProductName,OrderDetaiIName,OrderName,CustomerNameFromProducts,OrderDetails,Orders,CustomersWhereProducts.ProductID=OrderDetails.ProductIDAndOrderDetails.OrderlD=Orders.OrderlDAndOrders.CustomerID=Customers.CustomerID前文己描述过站点0中的全局数据库除了存放全局表信息外，还存放着全局表与局部表的对应信息，这里对应信息除了上述已描述过的局部表所属的局部数据库访问信息外，还存放着每个局部表的统计量参数信息。设：局部表Orders的统计量T为830，表示局部表Orders中的总的记录数为830；局部表Orders的统计量V(OrderlD)为830，表示局部表Orders中在OrderlD属性上值不同的记录数为830；局部表Orders的统计量V(CustomerlD)为90，表示局部表Orders中在CustomerID属性上值不同的记录数为90。例子中，各个关系、连接属性及其统计量参数如表2-2所示。链式连接的全局查询语句经过初步查询分解为以下三个查询语句：SelectProductName,OrderDetailNameFromProducts,OrderDetailsWhereProducts.ProductID=OrderDetails.ProductID及SelectOrderDetaiIName,OrderNameFromOrderDetails,OrdersWhereOrderDetails.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及SelectOrderName,CustomerNameFromOrders,CustomersWhereOrders.CustomerID=Customers.CustomerID图2-3为链式连接优化前的半连接图，图2-4为链式连接经过多关系半连接查询优化算法优化后的半连接图。ProductsProductsOrderDetailsOrdersCustomers站点3站点2站点1站点4图2-3链式连接优化前的半连接图ProductsProductsOrderDetailsOrdersCustomers站点3站点2站点1站点4图2-4链式连接优化后的半连接图优化前链式连接优化前半连接执行顺序为：OrderDetailsProductsOrderDetailsOrdersOrdersCustomers链式连接优化前通信代价分为以下几个部分：1)半连接OrderDetailsProducts的通信代价首先将站点3中Products表的属性ProductID及属性ProductName的数据传输到站点0，通信代价为：80+80=160；然后站点0将属性ProductlD的数据传输到站点2进行连接，通信代价为：80。通信总代价为：160+80=240。2)半连接OrderDetailsOrders的通信代价首先将站点1中Orders表的属性OrderlD及属性OrderName的数据传输到站点0，通信代价为：830+830=1660；然后站点0将属性OrderlD的数据传输到站点2进行连接，通信代价为：830。通信总代价为：1660+830=2490。3)半连接OrdersCustomers的通信代价首先将站点4中Customers表的属性CustomerID及属性CustomerName的数据传输到站点0，通信代价为：90+90=180；然后站点0将属性CustomerID的数据传输到站点1进行连接，通信代价为：90。通信总代价为：180+90=270。4)站点2中表OrderDetails的属性OrderDetaillD及属性OrderDetaiIName的数据传输到站点0的通信代价通信总代价为：80+80=160。链式连接优化前通信总代价为：240+2490+270+160=3140。优化后链式连接优化后半连接执行顺序为：OrderDetailsProductsOrdersOrderDetailsCustomersOrders链式连接优化后通信代价分为以下几个部分：1)半连接OrderDetailsProducts的通信代价首先将站点3中表Products的属性ProductID及属性ProductName的数据传输到站点0，通信代价为：80+80=160；然后站点0将属性ProductID的数据传输到站点2进行连接，通信代价为：80。通信总代价为：160+80=240。2)半连接OrdersOrderDetails的通信代价首先将站点2中表OrderDetails的属性OrderDetailID及属性OrderDetailName的数据传输到站点0，通信代价为：80+80=160；然后站点0将属性OrderDetailID的数据传输到站点1进行连接，通信代价为：80。通信总代价为：160+80=240。3)半连接CustomersOrders的通信代价首先将站点1中表Orders的属性OrderID及属性OrderName的数据传输到站点0，通信代价为：80+80=160；然后站点0将属性OrderID的数据传输到站点4进行连接，通信代价为：80。通信总代价为160+80=240。4)站点4中表Customers的属性CustomerID及属性CustomerName的数据传输到站点0的通信代价通信总代价为：80+80=160。链式连接优化后通信总代价为：240+240+240+160=840。链式连接优化效益=(执行普通多关系半连接查询方法的网络代价一执行多关系半连接查询优化算法的网络代价)/执行普通多关系半连接查询方法的网络代价=(3140-840)/3140=0.73。如果直接将站点1、2、3、4中局部数据库的数据送到站点0，其通信代价为：(80+80)+(2850+2850)+(830+830)+(90+90)=7700。链式连接优化效益=(7700-840)/7700=0.89。则其优化效益更为明显。通过上述链式连接的例子可以看出基于多关系半连接的查询优化算法明显地减少了中间结果数据量，有效地降低了网络通信总代价。与普通的多关系半连接算法比较，基于多关系半连接的查询优化算法的优化效益更高。SDD-1算法用半连接查询取代连接查询的方法，可以减少数据在网络中的传输量。但是事先不可能知道哪个关系表的元组被更多的包含在连接结果中，所以如何确定传输哪一个关系表的属性列是摆在我们面前的问题，而SDD-1算法很好的解决了这个问题[13]。由美国计算机公司1978年研制的SDD-1是分布式数据库管理系统的第一个样机，该系统采用的分布式查询方法是多关系半连接算法。在介绍SDD-1算法前，首先介绍选择因子及半连接的收益分析有关概念。定义1设R和S是两个关系，R和S半连接选择因子记为[15]SF(RS)=card(a(S))/card(S)(式2-2)其中card(a(S))是关系S在关系R和S的公共属性a上投影所包含的不同元组的个数，card(S)是关系S的元组个数。定义2半连接代价公式记为：cost(RS)=size(a(S))=card(a(S))*length(a)(式2-3)其中length(a)是属性a定义的长度(字节数)；半连接效益公式记为：benefit(RS)=(1-SF(RS))*size(R)(式2-4)其中size(R)表示关系R的大小(字节数)；有益半连接：benefit(RS)-cost(RS)>0的半连接；最有益半连接：多个半连接中，benefit(RS)-cost(RS)结果最大的半连接。SDD-1查询优化算法大致思想是通过反复的获得有益半连接运算，减少每个站点上用于连接运算的数据，然后将所有站点的数据汇集到数据量最大的站点做最后装配。处理过程主要包括三个步骤：(1)初始化：从全部关系中的半连接中生成有益的半连接集合；(2)选择有益的半连接：从有益的半连接集合中找出最有益的半连接，将其添加到执行策略中，并相应地修改被影响关系的统计值(选择因子，关系的大小等)；(3)选择组装场地：重复第一步，直到所有有益的半连接加入到执行策略中。关系经上面步骤缩减后，选择存储数据量最大的站点为组装场地。本章小结移动DBMS的计算环境是传统分布式DBMS的扩展，它可以看作客户与固定服务器结点动态连接的分布式系统。本章主要介绍了传统分布式数据库中连接操作使用的减少通信开销的优化策略以及由此而产生的多关系连接查询优化算法，这些算法为接下来的探讨和改进提供了一些参考和根据。嵌入式/移动实时环境下的查询优化处理未来的移动计算机都将配备以无线网络为主的移动联网设备，以支持移动用户访问网络中的数据，这是一种更加灵活、复杂的分布式计算环境，人们称之为移动计算(MobileComputing)。移动计算系统是由固定结点和移动结点构成的分布计算系统，它将使用户在移动的同时通过移动通信网络保持与固定结点或其它移动结点的连接。与固定网络的传统分布计算环境相比，移动计算环境具有以下特征：(1)频繁断接性；(2)网络条件多样性；(3)网络通信的非对称性。其中，非对称性指的是服务器到移动计算机的下行链路与移动计算机到服务器的上行链路相比，它们之间的通信带宽与代价相差很大。近年来，数据处理技术所依赖的计算环境发生了重大变化，移动计算机的使用成为计算机界发展的一个必然趋势。计算机从大型机向个人电脑的发展使得个人能有更多的机会和方法获取信息和进行计算，而移动计算机则加快了这一发展进程。各个应用领域都开始对移动设备使用，移动计算技术、移动数据处理和移动信息服务等进行深入的研究并逐渐进入实用化。在早期的研究中移动计算[16,17]主要集中在研究移动主机协议、降低电源消耗、上下文感知的计算以及弱连接通信中的数据共享。这时主要分析移动计算和传统分布计算之间的差别以及如何从分布计算向移动计算过渡[18]。移动设备的一个共同特征是：体积相对较小，处理能力较弱，移动用户本地的处理效率和准确性较低。如果将它作为一个大型服务系统的应用终端或智能终端，可以充分利用各种网络资源和大型服务器的处理能力。而使用性能较高的便携式计算机的MC可以通过复制技术维护一个数据缓存与副本，在发生断接时，MC可以在副本的基础上继续工作。恢复连接后，MC与主本以及其他副本进行同步，达到数据一致。随着移动通信技术的快速发展，智能化终端产品将不断涌现，移动计算硬件平台的价格正在不断下降，移动电子商务应用解决方案正在不断完善，企业、个人用户对移动计算的需求将会稳步增长，一个无缝覆盖的数字化的地球将随着移动计算的发展一步一步向我们走近。随时随地上网，随时随地发布消息，随时随地获得信息，这就是离我们并不遥远的移动计算能够带给我们的便利，移动计算技术将大大改变我们的工作和生活环境。目前，移动计算己经成为第三代互联网的标志性技术之一。适用于移动数据库系统的客户/服务器结构和传统的分布计算模型相比，代理的移动性和自治性带来了许多的优点，采用移动代理技术可以得到许多的好处[19-22]。节约网络带宽：移动代理直接在数据端执行处理，和客户端没有中间数据结果的传递，只返回最后的结果。因而在要处理的数据量特别大、网络带宽不足的情况下，移动代理可以有效地节约网络带宽。提供实时的远程交互：在一些远程控制系统中，如外太空探测器的控制、网络的时延使得远程实时控制变得不太可能，发送代理程序实行远端的本地控制可解决该问题。支持离线计算：用户派遣出代理程序后，可以断开网络连接，而代理将在网络上自主运行。代理完成任务后，当它发现用户设备重新连上网络时，就返回计算结果。Client/Agent/Server模型移动数据库系统可以看作是传统分布式数据库系统的扩展。移动数据库体系结构中的固定网络其实就是传统的分布式数据库系统，在此基础上增加一些移动基站或仅在一些结点上增加无线接口就构成了移动数据库系统。移动Agent是一个独立的计算机程序，它可以自主地在异构的网络上，按照一定的规程迁移，寻找合适的计算资源、信息资源或软件资源，利用这些资源同处一台主机或网络的优势，处理或使用这些资源，代表用户完成特定的任务。它要完成的任务是由启动它的应用程序决定的，可能从在线购物到实时设备控制进而到分布式科学计算。应用程序启动MobileAgent并把它送入网络中[23,24]，按照预定的或者由它们自己根据动态搜集的信息所决定的路线迁移，完成任务就返回到主站点向用户报告结果。一般基于移动Agent的移动数据库体系结构如图3-1如示。服务器(SVR)：服务器一般为固定结点，每个服务器维护一个本地数据库，在服务器保留有所有请求的历史记录。MCMC固定网络（Mbps到Gbps）SVR/DAMSS/MADSVR/DAMSS/MADSVR/DAMSS/MADSVR/DASVR/DALDBLDBLDBLDBLDBMCMCMC:MobileClient(移动客户机)MSS:MobileSupportStation(支持移动计算的固定站点)MAD:MobileAgentDock(移动Agent码头)SVR:Server(固定主机管理本地数据库)DA:DatabaseAgent(数据库Agent)LDB:LocalDatabase(本地数据库)图3-1基于Agent的移动数据库体系结构数据库Agent(DA)：位于服务器上的静止Agent，负责处理客户机对数据库的访问请求，直接对数据库进行操作，通过与移动Agent通讯来接收和返回结点信息到客户机。移动支持结点(MSS)：位于固定高速网络中，用于支持无线网络单元，它既能通过无线链路与移动客户机通信，也可通过固定网络与服务器通信。移动Agent码头(MAD)：位于MSS上的移动Agent管理系统。它根据客户机的请求创建移动Agent，并将移动Agent送到正确地址，它还接收从服务器端返回的移动Agent，将其结果传递给相应客户机。服务器(SVR)：服务器一般为固定结点，每个服务器维护一个本地数据库，在服务器保留有所有请求的历史记录。数据库Agent(DA)：位于服务器上的静止Agent，负责处理客户机对数据库的访问请求，直接对数据库进行操作，通过与移动Agent通讯来接收和返回结点信息到客户机。移动支持结点(MSS)：位于固定高速网络中，用于支持无线网络单元，它既能通过无线链路与移动客户机通信，也可通过固定网络与服务器通信。移动Agent码头(MAD)：位于MSS上的移动Agent管理系统。它根据客户机的请求创建移动Agent，并将移动Agent送到正确地址，它还接收从服务器端返回的移动Agent，将其结果传递给相应客户机。移动客户机(MC)：具有移动性且与网络频繁断接的计算设备。这种模型的优点在于：断接时，Agent仍然可以与Server交互执行任务；Agent可以利用固定网络的高带宽；可以由Agent执行优化操作；可以有选择地传送结果。但是这种模型也存在缺点：一旦出现断接操作，客户机就不能继续工作。而且Agent只能优化从固定网络到移动客户机的数据传输，反之则不能，即从移动客户机到固定网络的数据传输无法优化。为了解决这些问题可以采用下面将介绍的Client/Intercept/Server模型。Client/Intercept/Server模型这种模型将Agent划分为两个部分：服务器端Agent(Server-sideAgent)和客户端Agent(Client-sideAgent)。顾名思义Server-sideAgent驻留在固定网络的服务器端；而Client-sideAgent则驻留在客户端。后者解释客户机的请求并与前者一起执行优化处理以减少在无线链路上的数据传输，改善数据的可用性并保证移动客户机的操作不间断性。从客户机的角度来看，Client-sideAgent的作用相当于一个驻留在本地客户机上的局部服务器代理。同样，Server-sideAgent就如同在服务器端的本地客户机代理。Server-sideAgent驻留在固定网络中，并不一定要和相应的服务器驻留在同一台机器上，因此这组Agent可以看成是“虚”插入在客户机和服务器之间的数据通路上。该模型对于客户机和服务器都是透明的。它们可以为多个应用程序所使用。两个Agent的共同协作来优化无线链路的使用从而使不同的应用获益，特别是可以更为有效地进行特定应用的优化。该模型可以灵活的处理断接操作。在Client-sideAgent上可以进行局部数据缓存。该缓存可以在一定程度上满足在断接情况下客户的数据需求。缓存的命中丢失可以由Agent进行排队处理，一旦再次连接成功就可以解决命中丢失问题[25-27]。同样在断接状态，服务器端对客户机的要求也可以在Server-sideAgent处进行缓存等待处理直到再次成功连接。对于弱连接的处理方法类似。该模型较适用于具有足够的计算能力和较强辅存能力的“胖”客户。其缺点是每个应用都要求在服务器端和客户机端开发相应的程序。但是无需为每个应用实例都开发一对Agent。相反，由于Agent对所执行的功能和优化是共性的，它只要为每个不同应用类型，如文件系统，数据库系统，WEB应用，分别开发一对Agent即可。对于两个Agent的角色的划分可以获得类似于Client/Agent/Server模型中Agent角色划分的分类结果。显然，Server-sideAgent可以作为客户机的全权代理或与特定服务相关。嵌入式/移动实时数据库查询优化处过程移动计算环境的特性使得面向固定计算环境的客户/服务器查询模型变得不再适用。对查询模型的改进从两个方向进行：基于缓存和复制技术的模型具有独特的优点，可以有效的支持断接的查询，但此模型应用上具有其局限性；基于Agent的查询模型有着不可替代的作用，能较好地支持用户的移动性，可以支持脱机查询，断接查询。在系统的初步设计中，作一些必要、合理的假设，可以简化系统的设计，使系统在设计中不会过多的纠缠于一些琐碎的细节，而迷失了主要的方向。同时，合理的假设也使系统结构清晰明了，利于系统的定制和维护。在本文的设计中，综合考虑了嵌入式/移动环境下的特点以及3.1节中提到的体系结构，作了以下几点假设：1)准分布式体系结构[28]。理论上，移动数据库管理系统是传统分布式数据库管理系统的移动形式，即有数据复本的服务器也可以是移动的。但是一开始就从一个全可移动的分布式数据库系统的要求来考虑问题，会给查询处理等问题增加不少难题。因此这里假设移动端只能从位置固定的中心数据库中获取数据，即中心服务器的位置是不变的。这个假设是合理的。以后只需在现有的体系上进行扩展，由一个或多个在固定网络上的同步服务器负责和移动着的数据库服务器进行通信，维护它们的位置信息、事务信息、复本信息就可以解决数据库服务器的移动问题。而这些都可以做到对移动用户是透明的。2)移动用户的配置采用目前流行的配置[29-31]：无磁盘等持久存储设备，只提供RAM和ROM存储；操作系统一般固化在ROM中；由一般操作系统提供基本的网络功能，可以通过TCP/IP和其他主机通信。操作系统包括WindowsCE和Linux的各种改进版本。这些设备都可以缓存一定的数据库数据，从而可以利用缓存技术通过在客户机上缓存部分数据，达到减少访问数据库服务器的目的，从而提高了性能。但是，传统的缓存技术要求客户机保持与服务器的连接，这样才能维护缓存的一致性[32,33]。因此，对于经常需要断接操作的移动客户机来说，传统的缓存技术也是不能适用的。3)移动用户的操作在一段时间内具有较强的可预见性。目前情况下，很多的移动设备都是为某种特殊的应用定制的，如用于飞机停机时的检测，税务部门的税收记录等等。因此用户在一定时间内的操作是可预见的，有规律可寻的，这些规律可用于查询优化，同时用户所需要的大部分的数据也就可以预先设定。另外，通过积累用户操作的历史数据，应用数据挖掘等方法，也可以找到一些规律。4)中心服务器有足够的空间及计算能力，能支持大量的用户同时访问。并保存大量用户的信息，如：用户订阅的数据集，喜好信息，操作的历史记录等等。这个假设也是合理的，因为中心服务器可以是大型计算机，也可以是一个分布式的服务器群，它们互相协作，作为一个整体对移动方提供服务。以上文中的假设为基础，本文根据Client/Intercept/Server模型分别设计了两个Agent：服务器端Agent和客户端Agent。客户端集成了一个后台嵌入式数据库管理系统SQLite，用户提出查询请求后先由客户端Agent判断能否在本地得以获得结果，若能将由本地DBMS(SQLite)进行查询处理，否则就提交该查询请求至服务器端Agent，服务器端Agent会维持一个服务队列，对于队列中的每一个请求将建立一个单独的处理线程负责查询的实现和结果的返回。首先，客户端Agent检查该查询是否能部分或全部在移动子集的一个语义片段中得到满足。若完全满足，则用该片段中可用数据直接处理并返回；如果查询只能被部分满足，将对该查询进行查询修剪。所谓查询修剪，是指当一个查询只能部分地被一个语义片段S响应时，可将该查询分成两部分：一部分是能从S中得到答案的，另一部分是不能从S中得到结果的。由于移动子集中可能存在多个语义片段，对后者要继续重复上述工作，直至遍历移动子集中所有分片。仍然不能满足的查询部分要传递给服务器端Agent进行处理。提交到服务器端Agent的查询优化部分主要针对多元连接，因为这类操作可能会涉及多个结点上的片段，是最费事的操作。其次，对于提交到服务器端Agent的查询优化部分，服务器将对于每个请求启动一个后台服务例程。这个例程将读取服务器主机中同步更新的全局关系表、全局站点表、相关系数表等数据，运用一定的算法对查询进行分析，给出一个全局较优的查询步骤。嵌入式/移动实时环境下的查询代价分析传统的分布式数据库中查询优化处理使用的代价模型并没有反映太多与移动计算环境有关的特点，因此，很显然，以前的很多关于分布式查询处理的研究没有充分考虑移动环境下不对称的特点，而这些特点在设计相关查询处理策略的时候相当重要。鉴于此，在本文中考虑了移动计算环境三个重要的不对称特征，设计出有效的针对查询中的多元连接操作优化策略。在进行代价分析的时候，还要从下面三个方面进行考虑：1)考虑移动主机和固定服务器不同的计算能力，将两者做为参与连接操作时候不同的站点类型进行区别对待，而传统分布式系统下只考虑固定服务器之间的连接操作，没有考虑不同站点之间计算能力的区别。2)建立网络开销模型的同时，细化并区别移动站点收/发数据不同的传输代价系数，同时将电源消耗率加入开销代价考虑之中。3)移动终端处于活动状态和空闲状态时候电源消耗的不同。移动终端有可能设计成这种模式[33,34]：尽量把处理工作迁移到服务器端来使得自己保持在更多的空闲状态。表3-1显示了移动计算环境中代价模型使用的一些参数，这些系数可以由于移动计算机的具体规格参数估算出来[34-37]。代价估算公式一般而言，一个查询语句经过处理后其结果传到查询点的总代价为：总代价＝CPU代价+I/O代价+传输代价。在这里，主要考虑移动计算环境拓扑结构中不对称的表3-1移动计算系统代价模型参数说明表参数符号说明SM服务器/移动计算机计算能力比E发送/接收数据能量消耗比移动计算机空闲系数Erc移动计算机数据接收能量消耗系数Esd移动计算机数据发送能量消耗系数Ts服务器端查询处理时间函数dt查询处理数据传输总量Ec查询处理能量消耗总量特点，同时为了简化问题，提出一种新的代价估算公式为：cost()=本地处理电源消耗代价+网络传输代价。其中移动主机本地处理电源消耗代价计算公式如下：①Ec(C)=Esd(|R2|)+*Ts(|R1R2|)+Erc(|R1R2|)(式3-1)②Ec(C)＝Erc(|R1|)+(1/)*SM*Ts(|R1R2|)(式3-2)公式①和②的区别在于：对于连接R1R2（假定R1在服务器主机S上，R2在移动计算机M上)，①中S将表R1传送到M进行处理，而②中M将表R2传送到S进行处理。网络传输代价计算公式如下：Cnet()=C0+C1+C2*t*f(D)(式3-3)其中C0和C1分别表示两个主机启动一次所需的代价，由于它们的值相对来说很小，一般可以忽略不计，另外为了问题讨论的方便，该表达式可以简化为Cnet()=C2*t*f(D)：C2表示单位容量的数据在网络中传输所需要的代价，它的值随着主机所在的网络的不同而不同。表3-2表示了在不同网络条件下的C2的值，C2为每一单位的数据量在不同的网络条件下传输所消耗的网络资源的代价，其值是文献[38]通过试验得到的数据；t为单个元组的大小；f(D)表示估算一个查询语句结果的元组的个数。表3-2不同网络条件下的C2的值C2的值网络条件1固定节点之间的本地传输代价10固定节点和本地节点之间的本地传输代价10移动节点之间的本地传输代价30固定节点之间的远程传输代价45固定节点和本地节点之间的远程传输代价45移动节点之间的远程传输代价1)自然连接中间结果大小的近似计算公式|RiRj|=|Ri|*|Rj|/Card-D(dom(Ak))(式3-4)|Ri|和|Rj|分别表示Ri，Rj的大小，Ri与Rj通过公共域Ak连接，域dom(Ak)是属性Ak所有可能取的值的集合。2)中间结果传输网络代价公式Cost(Ri→Rj)=Cnet()=C+C2*t*f(D)(式3-5)其中X是Ri往Rj传输的数据量，C是启动一次两地传输的固定费用，一般可以忽略C，C2是网络范围内的单元传输费用。本章小结本章主要对于嵌入式，移动，实时三种环境综合一起后对于数据库查询优化的一些影响和改变进行了探讨和假设，并给出了一种查询分解的可能方式：将查询分解为本地执行和交给服务器端执行两种情况，这样可以有利于问题的深入研究。另外，本章主要对于嵌入式移动实时数据库的查询优化进行了分析，在充分考虑了嵌入式移动实时数据库与传统分布式数据库系统异同点的基础上，主要针对最费事的连接操作给出了已有研究中提到过的相应的代价估算公式，这一章内容主要为下一章提出的优化算法做准备。4嵌入式/移动实时环境下的数据库查询优化算法4.1查询处理方法和优化策略本文第二章介绍的多关系半连接算法主要是利用半连接运算代替连接运算，并确定了数据传输的方向，减少了数据传输量。但是这些算法也存在这一些问题：1)对于算法中的选择因子，不可能事先知道。选择因子的确定依赖于DDBS的其他算法。2)算法要多次进行辅助运算(如对选择因子、传输代价的修改以及用半连接的结果替代本地数据)。针对这些情况本文设计出一种算法简单，运行效率较高的并行处理算法，并且该算法指定局部数据库中经过半连接优化操作后数据量最大的站点作为查询的中间结果的最后装配的站点[39]。4.1.1多元连接查询优化算法思想在给出本文提出的多元连接查询优化算法前，先简单描述一下最小生成树算法的思想。给定一个多元自然连接查询Q，设Q涉及的关系为{R1,R2,R3,...,Rn}。用连接图表示这n个关系以及关系之间可能的连接，图的顶点表示关系，边表示关系之间的连接。通过上一章的代价估计模型，预先估计连接的代价作为边上的权值。对于n个关系的连接图可以建立许多不同的生成树，每一棵生成树都可以是一种连接方式。最小生成树算法的目标就是尽量得到一个全局上的最佳连接次序，使查询Q的总代价最小[40-42]。一个好的移动计算环境下的多元连接查询算法，应该是通信费用低，并行性高。提高算法的并行性，对整个算法的效率有很大的影响。尤其对于多元连接查询，查询所涉及的关系往往分布在不同的场地，采用尽可能多的并行连接尤为重要。本文接下来提出的改进最小生成树算法能得到一个尽可能多的并行连接操作，同时使总代价尽可能小。4.1.2改进最小生成树算法1)算法描述第一步：最小生成树的初始状态T0为只有n个顶点而无边的非连通图，即T0＝{V,{¢}}图中每个顶点自成一个连通分量。第二步：在E中选择代价最小的边，若该边依附的两顶点至少有一个已在T0中的连通分量上，则将此边并入E’（E’初始值为¢），而选择下一条代价最小的边，否则加入T0中。第三步：重复第二步直到E＝¢，则此时T0即为已找到的尽可能多的并行处理，输出T0。第四步：从E’中选择代价最小的边，若该边依附的顶点落在T0不同的连通分量上，则此边加入T0中，否则舍此边而选择下一条代价最小的边。第五步：重复第四步直到T0中所有顶点都在同一连通分量为止。2)算法实现主要算法伪代码如下：算法4-1：generatePath输入：表信息结点链表头pTableNodeHead，连接信息链表头pLinkPairHead输出：优化后的连接处理路径//只对链式连接进行优化和考虑intgeneratePath(tableNode*pTableNodeHead,intNum,linkPair**pLinkPairHead){ 打开结果输出文件； 计算连接总数totalPair； while(notUsed>0){//初始化各条件进行新的一次并行处理 置每个pTableNodeHead节点的IS_USED信息为FALSE； for(k=totalPair,pLinkHead=*pLinkPairHead;k;k--,pLinkHead=pLinkHead->pNext)用算法4-2重新计算每个未处理的连接的最小代价； while(1){ 置minCost为最大值； FIND_ONE=FALSE；遍历未处理连接，找到代价最小的一个并置FIND_ONE=TRUE； if(FIND_ONE){ 总的未处理连接数notUsed自减1；//层次锁锁住此次处理的连接相关的两个表以及其分别所处连接路径二叉树上所有的表； } else 此次遍历没有找到一个处理连接，跳出该层并行处理流程； } } }算法4-2：joinCost输入：表信息结点链表头pTableNodeHead，连接信息链表头pLinkPairHead输出：每个连接的最小代价(保存在pLinkPairHead相关链表结点中)for(k=totalPair,pLinkHead=*pLinkPairHead;k;k--,pLinkHead=pLinkHead->pNext){ if(pLinkHead->Used==TRUE)continue；找到参与连接的两个表目前所在site位置siteID1和siteID2； C_net1=db_cost_transport[siteID1-1][siteID2-1]; C_net2=db_cost_transport[siteID2-1][siteID1-1];计算出该两表最优传输代价，并将相应传输路径信息记录在连接信息链表中；} 4.2算法仿真实验与性能分析4.2.1系统