嵌入式移動實時數(shù)據(jù)庫中一種基于代價模型的查詢優(yōu)化技術

PAGE44摘要隨著當前最先進的無線通信和移動計算機技術的發(fā)展，移動環(huán)境下查詢處理中的表連接涉及到不同站點之間的操作，這些站點包括固定服務器和移動計算機。由于節(jié)省電源的需要以及移動計算環(huán)境下一些不對稱的特征表現(xiàn)，常規(guī)的為分布式數(shù)據(jù)庫設計的查詢處理方案不能直接應用于移動計算環(huán)境下。分布式環(huán)境下常用到的查詢優(yōu)化算法主要是基于連接/半連接的優(yōu)化算法，以及由此而提出的SDD-1算法等等。這些算法在分布式數(shù)據(jù)庫中得以廣泛運用。移動數(shù)據(jù)庫技術是一種可以支持移動計算環(huán)境的分布式數(shù)據(jù)庫技術，在分布式數(shù)據(jù)庫中使用的這些算法到了移動環(huán)境下有必要對其進行一定的改進，包括其代價估算模型，才能適應新的要求。移動環(huán)境下具有很多不對稱的特征。根據(jù)這些特征，可以針對連接和查詢處理(主要是多關系連接查詢操作)分別設計相應的方案。直觀的看來，在移動環(huán)境中使用半連接操作能有效減少數(shù)據(jù)傳輸量和電源消耗量。對不同連接方式進行實驗可以看到這些特征對于查詢代價的影響。從模擬實驗得出的結果可以看到，通過充分考慮移動環(huán)境網(wǎng)絡拓撲結構和其它特征，提出的相關算法在減少移動終端電源消耗和數(shù)據(jù)傳輸量兩個方面都是非常有效的，并且通過對其進行適當擴展，這些策略能得以應用進而設計出一個適用于移動計算環(huán)境下的有效查詢處理過程。關鍵詞：移動計算，查詢處理，表連接，多元連接查詢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 國內(nèi)外研究狀況 (1)1.3 本文的組織 (7)2 分布式數(shù)據(jù)庫的查詢優(yōu)化方法與技術2.1 基于半連接操作的優(yōu)化算法 (9)2.2 多關系半連接查詢優(yōu)化算法 (13)2.3 SDD-1算法 (19)2.4 本章小結 (20)3 嵌入式/移動實時環(huán)境下的查詢優(yōu)化處理3.1 適用于移動數(shù)據(jù)庫系統(tǒng)的客戶/服務器結構 (22)3.2 嵌入式/移動實時數(shù)據(jù)庫查詢優(yōu)化處過程 (25)3.3 嵌入式/移動實時環(huán)境下的查詢代價分析 (27)3.4 代價估算公式 (28)3.5 本章小結 (30)4嵌入式/移動實時環(huán)境下的數(shù)據(jù)庫查詢優(yōu)化算法4.1查詢處理方法和優(yōu)化策略 (31)4.2算法仿真實驗與性能分析 (33)4.3本章小結 (39)5 結束語5.1 總結 (40)5.2 未來展望 (40)致謝 (42)參考文獻 (43)引言課題背景互聯(lián)網(wǎng)正不斷延伸、滲透，推動我們進入一個移動信息社會，任何可以獲得并傳播信息的地方都可以成為人們的工作場所。信息系統(tǒng)正逐漸走出傳統(tǒng)的機房與桌面，使用戶能夠隨時隨地獲取為做出正確決策所需要的信息，并使企業(yè)事務一發(fā)生便可獲得反饋信息。這就是移動計算模式，也就是所謂的“ComputingAnywhere”。在移動計算模式[1]中，由移動終端(如筆記本、手機、PDA等)構成的計算結點可以在自由移動的過程中保持網(wǎng)絡連接，使得人們在任何時候、任何地點、訪問任何數(shù)據(jù)的需求成為可能。但是原來基于有線網(wǎng)絡和固定主機的分布式數(shù)據(jù)庫不再適應這種應用環(huán)境，于是一種更加靈活、復雜的數(shù)據(jù)庫技術便應運而生，并迅速成為一個新的研究熱點，這就是移動數(shù)據(jù)庫。所謂移動數(shù)據(jù)庫技術是指支持移動計算環(huán)境的分布式數(shù)據(jù)庫技術，它涉及數(shù)據(jù)庫，分布式計算以及移動通訊等多個學科領域，已成為分布式數(shù)據(jù)庫一個新的研究方向。由于移動數(shù)據(jù)庫系統(tǒng)的終端設備通常不是傳統(tǒng)的臺式計算機，而是諸如掌上電腦，PDA，車載設備，移動電話等嵌入式設備，因此，它又被稱為嵌入式移動數(shù)據(jù)庫系統(tǒng)。在移動數(shù)據(jù)庫的設計中，需要考慮諸多傳統(tǒng)計算環(huán)境下不需要考慮的問題，如對斷接操作的支持，對跨區(qū)長事務的支持，對位置相關查詢的支持，對查詢優(yōu)化的特殊考慮以及對提高有限資源的利用率和對系統(tǒng)效率的考慮等等。為了有效地解決上述問題，諸如復制與緩存技術，移動事務處理，數(shù)據(jù)廣播技術，移動查詢處理與查詢優(yōu)化，位置相關的數(shù)據(jù)處理及查詢技術，移動信息發(fā)布技術，移動Agent等技術在移動數(shù)據(jù)庫中具有特別的意義。它們都是實現(xiàn)和完善移動數(shù)據(jù)庫的關鍵性技術，還有待于人們的進一步探索。國內(nèi)外研究狀況移動計算環(huán)境以及移動設備的特點，對移動計算的應用軟件提出新了的要求。因此嵌入式移動數(shù)據(jù)庫管理系統(tǒng)與傳統(tǒng)數(shù)據(jù)庫管理系統(tǒng)相比，也存在特殊的要求，主要表現(xiàn)為以下幾方面：1)易于定制。在嵌入式/移動環(huán)境下，軟硬件資源有限，因此嵌入式系統(tǒng)中從硬件、操作系統(tǒng)到數(shù)據(jù)庫，都強調與具體的移動計算應用的捆綁和集成。所以可定制是該環(huán)境下的軟件的最大特點。因此EMDBMS的開發(fā)應該以組件化的思想想為指導，便于系統(tǒng)根據(jù)用戶的實際需求進行定制。2)內(nèi)核盡可能小。這主要是由于移動終端存儲容量、計算能力等都有限。3)便于用戶使用。移動用戶的計算機水平普遍不高，系統(tǒng)應向用戶屏蔽掉數(shù)據(jù)庫系統(tǒng)的技術細節(jié)，并且提供自動配置功能，即系統(tǒng)能根據(jù)用戶當前的軟、硬件狀態(tài)自動地配置系統(tǒng)參數(shù)。4)便于移植。移動設備的硬件資源多種多樣，所使用的操作系統(tǒng)也不盡相同，因此移動DBMS應能方便地在各個平臺間移植。5)支持斷接操作。在移動計算環(huán)境中，斷接不應該被視為故障，而應作為一種特殊情況來處理。即使在斷接情況下，用戶也能進行各種操作，并且在用戶重新入網(wǎng)時，系統(tǒng)負責進行同步，以保持數(shù)據(jù)的一致性。這些操作對用戶應該都是透明的。國內(nèi)外相關產(chǎn)品及技術目前，國內(nèi)外很多公司都在嵌入式移動環(huán)境領域做了很多工作，一些大型的數(shù)據(jù)庫公司紛紛推出自己相應的數(shù)據(jù)庫產(chǎn)品，如Sybase的iAnywhere，Informix的Cloudscape，Oracle的think9i[2-4]。在國內(nèi)，中國人民大學推出了人大小金靈。由于這些產(chǎn)品在研究開發(fā)時的重點不同，因此這些產(chǎn)品各有特點，但在某些方面又有不足之處。Oracle公司，Informix公司的移動數(shù)據(jù)庫產(chǎn)品都是基于客戶/Agent/服務器這樣一個三層的無連接結構，它們主要解決移動客戶機與數(shù)據(jù)庫之間因為無線網(wǎng)絡的低帶寬、高延遲、易中斷而帶來的網(wǎng)絡連接問題。通過擴展傳統(tǒng)的客戶/服務器結構來提高無線網(wǎng)絡的使用效率。而Sybase公司則將其一直處于領先地位的復制技術的產(chǎn)品進行延伸，推出了基于會話的SybaseSqlAnywhere和基于消息的SQLRemote兩種復制方式。但它沒有涉及客戶機的移動性、數(shù)據(jù)廣播方式、應用程序的不同一致性要求等方面。嵌入式/移動實時數(shù)據(jù)庫查詢處理相關技術查詢處理是關系型數(shù)據(jù)庫系統(tǒng)的一個重要問題，而描述性的數(shù)據(jù)查詢語言引起的低效率問題在嵌入式環(huán)境下更為嚴重。所以，能否在嵌入式系統(tǒng)中建立一個成功的關系DBMS，采用什么樣的查詢處理及優(yōu)化技術是十分關鍵的。在嵌入式和移動環(huán)境下，由于移動設備和無線網(wǎng)絡的特殊性，查詢優(yōu)化又有了新的含義。嵌入式移動環(huán)境下查詢優(yōu)化和處理技術是指在傳統(tǒng)分布式數(shù)據(jù)庫查詢優(yōu)化和處理技術的基礎上利用多種方法，消除帶寬多樣性、斷接等因素產(chǎn)生的影響，使查詢引擎能夠根據(jù)當前可用網(wǎng)絡條件采取恰當?shù)膬?yōu)化策略。同時，針對移動設備有限的電源能力，需要合理地組織本地數(shù)據(jù)庫管理、遠程數(shù)據(jù)庫訪問等消耗電能較多的操作，達到節(jié)能目的，延長關鍵數(shù)據(jù)的可用時間。綜合國內(nèi)外相關研究文獻，大致可以將涉及到嵌入式/移動實時數(shù)據(jù)庫的查詢處理分為以下幾種：1)語義緩存這是研究得比較多的一個方向，具體適用的范圍也是移動終端，這種策略更多的考慮的是移動主機相對較弱的存儲和計算能力。因此其思路也就是更細化移動客戶端緩存的粒度，由此而發(fā)展出移動子集，查詢修剪等相關技術。緩存技術并不是新的技術，它已經(jīng)在很多傳統(tǒng)的領域得到廣泛的運用。它利用了數(shù)據(jù)的空間局部性，其性能取決于數(shù)據(jù)庫的物理組織，不合適的物理組織可能造成較高的網(wǎng)絡通訊和空間開銷。在傳統(tǒng)的頁緩存技術中，由于沒有保持緩存數(shù)據(jù)的語義信息，客戶機主要依靠網(wǎng)絡連接服務器來判斷局部緩存數(shù)據(jù)是否與查詢結果相匹配，這種方法在出現(xiàn)斷接時是不可行的。這種理論更偏向從物理優(yōu)化角度進行研究，因此語義緩存的實現(xiàn)應該有自定義的底層存儲管理系統(tǒng)，它能使得緩存的數(shù)據(jù)帶有時間和空間的特征。2)傳統(tǒng)分布式數(shù)據(jù)庫系統(tǒng)查詢優(yōu)化算法的擴展和改進傳統(tǒng)分布式數(shù)據(jù)庫系統(tǒng)中研究的較多的就是盡量減少網(wǎng)絡開銷的半連接操作優(yōu)化算法。但是，嵌入式/移動實時數(shù)據(jù)庫系統(tǒng)的網(wǎng)絡拓撲結構與傳統(tǒng)分布式數(shù)據(jù)庫系統(tǒng)有很大的區(qū)別，網(wǎng)絡中結點的類型和功能也有很大的不同。首先，嵌入式/移動實時數(shù)據(jù)庫系統(tǒng)中的移動終端自帶一個本地DBMS，具有一定的自治功能。很多最新的信息或者表都最先存在移動終端，這也就使得參與連接運算所涉及的站點有可能包括移動終端。移動終端參與運算帶來的電源消耗，網(wǎng)絡傳輸?shù)龋瑢⒑艽蟪潭鹊挠绊懻麄€查詢操作的性能。而在傳統(tǒng)的分布式數(shù)據(jù)庫系統(tǒng)中，由于固定主機的計算能力和存儲能力一般都遠大于移動終端，半連接操作僅僅考慮固定主機之間的網(wǎng)絡傳輸?shù)认模@也使得分布式環(huán)境下的優(yōu)化算法不能直接應用到嵌入式/移動實時數(shù)據(jù)庫所在的移動網(wǎng)絡環(huán)境下。3)多重查詢優(yōu)化處理策略多重查詢處理優(yōu)化(MultipleQueryProcessing,MQP)就是對一組查詢語句，求出它們的公共子表達式(CommonSubexpression，CSE)，在查詢過程中，公共子表達式僅被執(zhí)行一次，得到一個中間結果，所有包含該公共子表達式的查詢都使用這一中間結果，這樣就使得查詢代價大為降低。這種策略主要是從移動網(wǎng)絡數(shù)據(jù)廣播的方面進行考慮。移動計算環(huán)境的一個非常重要的特點是要在有限的網(wǎng)絡帶寬上進行數(shù)據(jù)的分發(fā)。數(shù)據(jù)分發(fā)的方式有多種：基于推動的策略、基于拉動的策略、推拉結合的策略。在基于推動的策略中，數(shù)據(jù)被組織成多盤進行廣播調度，移動客戶象訪問一個遠程磁盤一樣從廣播中獲取自己所需要的數(shù)據(jù)。在基于拉動的策略中，移動客戶通過上行鏈路向中央服務器發(fā)出請求，中央服務器響應并處理移動客戶的請求，然后將結果數(shù)據(jù)集通過下行鏈路發(fā)送給移動客戶。如果通過上行鏈路發(fā)出的請求很多，中央服務器通過下行鏈路發(fā)送的結果數(shù)據(jù)集的數(shù)量就會非常多，占據(jù)大量的帶寬資源，致使無線網(wǎng)絡負荷過重，移動查詢響應時間迅速增長。因此，若能批量處理某一時間段內(nèi)移動客戶的請求，對查詢集中的公共子表達式僅執(zhí)行一次，生成物化視圖，然后對該物化視圖采用廣播的方式發(fā)送到移動客戶端，相同的數(shù)據(jù)僅廣播一次，這樣將不僅降低了查詢代價，也減少了帶寬使用。傳統(tǒng)移動計算環(huán)境體系結構移動計算技術所研究的一個重要問題是要建立一個高效、合理、可行的計算環(huán)境體系結構，滿足不同應用系統(tǒng)的數(shù)據(jù)處理請求。這一節(jié)介紹幾種典型的體系模型，并分析其體系特征。1)Imielinski通用模型圖1-1描述了移動計算環(huán)境的通用模型[5]。這個模型將無線局域WLAN(WirelessLAN)引入整個拓撲結構。其中MU可以是啞終端或移動主機；MSS提供無線接口與MO通信，而移動用戶可以通過MSS存取自己的用戶profile、日志、權限控制和其他私有數(shù)據(jù)。移動客戶本身也管理若干文件，這需要硬件支持，將RAM擴展為VMFS。而FH是更為安全、可靠的固定網(wǎng)絡中的靜止節(jié)點。通過這個模型可以界定MCE中的許多新問題，重點要解決WLAN內(nèi)部以及各WLAN之間的各種數(shù)據(jù)管理問題。通用模型建立的是一個基于小區(qū)(Cell)概念的通用個人通信網(wǎng)PCN(PersonalCommunic-ationNetwork)該體系中的用戶在其主定位服務器HLS(HomeLocationServer)中注冊一個永久用戶地址，當用戶在不同小區(qū)之間移動時，所發(fā)出的請求能夠透明地跨區(qū)間以不同頻段來移交(Takeover)或轉接(Handoff)處理。作為一個參考模型，該模型描述了早期移動計算環(huán)境的基本結構，MSS作為小區(qū)無線通信的中轉器，提供的無線通信帶寬一般遠低于固定網(wǎng)絡并且穩(wěn)定性較差。但隨著無線通信能力的不斷增強以及信息服務方式的變化，這種結構已經(jīng)不完全合適了。2)Bayou系統(tǒng)結構Bayou系統(tǒng)是XeroxPARC開發(fā)的復制存儲系統(tǒng)，支持MCE中的協(xié)同工作[6]。該系統(tǒng)提供允許MC主動讀寫共享數(shù)據(jù)的存取機制，如存取預約日歷、書目數(shù)據(jù)庫、會議通知、設計文檔和消息布告欄等。系統(tǒng)對特定應用的更新沖突處理機制，可以檢測和解決發(fā)生的更新沖突并將更新傳播，實現(xiàn)最終一致性。圖1-2是Bayou的系統(tǒng)模型[7]。19.2KbpsMU19.2KbpsMU2MbpsMU固定網(wǎng)絡（Mbps到Gbps）FHMSSFHMSSMSSMSSFHFH無線局域網(wǎng)單元無線廣播單元注：MUmobileunit：移動設備MSSMobileSupportStation：支持移動計算的固定站點，具有無線通信接口FH固定主機，沒有無線通信接口圖1-1移動計算體系結構通用模型應用應用BayouAPI服務器入口存儲系統(tǒng)服務器狀態(tài)存儲系統(tǒng)服務器狀態(tài)存儲系統(tǒng)服務器狀態(tài)圖1-2Bayou系統(tǒng)模型Bayou系統(tǒng)由若干對等的服務器形成服務器系統(tǒng)，各個服務器保留數(shù)據(jù)集的完全副本，應用通過BayouAPI與服務器進行交互。Bayou系統(tǒng)中的應用是一個客戶，由BCL(BayouClientLibrary)實現(xiàn)API、裝入應用代碼、選擇執(zhí)行讀寫的副本等。BayouAPI作為一個客戶進入服務器的入口(Stub)支持客戶機/服務器間的RPC協(xié)議，允許對服務器上的數(shù)據(jù)進行讀寫。系統(tǒng)中的客戶機和服務器可以分離也可以運行在相同的主機上，無論哪種方法，Bayou都采用RAWA(Read-any/Write-any)的弱一致存取策略。Bayou系統(tǒng)提供支持特定應用的基于數(shù)據(jù)依賴的沖突解決方案和使用基于時標的系統(tǒng)全局復制管理。它更接近于一個可定制系統(tǒng)，需要相當多的用戶或系統(tǒng)管理員的干預。但對于實際的應用，如MRS(MeetingRoomScheduler),BCM(BayouCalendarManager)和BXMH(BayouEXMH)等，可以根據(jù)具體的應用特征，選擇可行的處理機制。它通過更豐富的API提供給用戶對副本和一致性管理的手段，象BXMH對郵件的一致性約束不是非常嚴格。3)Coda/Odyssey系統(tǒng)結構Coda[8]作為一種分布式文件系統(tǒng)，提供了處理服務器和網(wǎng)絡失敗的兩種方法：服務器復制和非連接操作，服務器復制即在多個服務器上存儲文件的副本，而非連接操作可以臨時緩存站點的內(nèi)容，在網(wǎng)絡非連接狀態(tài)作為復制的站點。Coda中復制的單元是卷，即若干存儲在服務器上的文件集合，卷構成了共享文件系統(tǒng)的子樹。支持非連接操作的關鍵在于三個狀態(tài)之間的變換：數(shù)據(jù)預取、模擬和整合。文件數(shù)據(jù)在預取狀態(tài)被提前取回到客戶本地；模擬狀態(tài)發(fā)生在網(wǎng)絡非連接期間，客戶訪問緩存在本地的文件數(shù)據(jù)：非連接期結束后，進入整合狀態(tài)，被修改的文件和目錄被傳播到服務器，系統(tǒng)處理文件數(shù)據(jù)的同步和更新沖突檢測。Coda系統(tǒng)將上述各種復雜處理對上層應用屏蔽，由于在一些場合并不合適，因此發(fā)展產(chǎn)生了Odyssey系統(tǒng)[9]，可以支持移動信息訪問應用。其中應用決定如何根據(jù)使用場合進行合適的調整，即采用的自適應策略是與應用相關的。本文的組織本文對于嵌入式移動數(shù)據(jù)庫技術進行了初步的研究，對嵌入式移動實時環(huán)境下查詢優(yōu)化技術及其代價模型進行了研究和比較。研究了傳統(tǒng)分布式數(shù)據(jù)庫與移動數(shù)據(jù)庫的不同，進而提出了一種改進的適合移動環(huán)境下的查詢優(yōu)化算法。第二章主要介紹了傳統(tǒng)的分布式數(shù)據(jù)庫所使用的查詢優(yōu)化技術，包括基于半連接操作的多關系半連接查詢優(yōu)化算法以及由此衍生的一些其它算法。第三章指出了嵌入式/移動實時環(huán)境下查詢優(yōu)化的特點，對其做了一些合理的假設以便于對具體問題的探討和研究。這一章同時提出了一個適用于嵌入式/移動實時數(shù)據(jù)庫的查詢優(yōu)化處理策略。在章節(jié)的末尾主要對于嵌入式/移動實時數(shù)據(jù)庫查詢優(yōu)化的代價模型進行了分析并給出了一個相應的代價估算公式。第四章設計并實現(xiàn)了一個可以對于涉及多個站點的多元連接進行優(yōu)化的原型系統(tǒng)，該原型系統(tǒng)使用了上一章中提到的代價模型及估算公式，借鑒了最小生成樹的思想和傳統(tǒng)分布式數(shù)據(jù)庫多元連接查詢優(yōu)化算法。實驗表明，經(jīng)過該算法處理后，查詢的響應時間在沒有明顯增加總代價的情況下有較大縮短。分布式數(shù)據(jù)庫的查詢優(yōu)化方法與技術絕大多數(shù)分布式數(shù)據(jù)庫系統(tǒng)都是關系型的，由于關系查詢的語義級別較高，為查詢優(yōu)化提供了可能。在分布式數(shù)據(jù)庫系統(tǒng)中有三類查詢：局部查詢、遠程查詢和全局查詢。局部查詢和遠程查詢都只涉及單個結點上的數(shù)據(jù)(本地或者遠程的)，對于這兩個類型，查詢優(yōu)化采用的技術就是集中式數(shù)據(jù)庫的查詢優(yōu)化技術。全局查詢涉及多個站點的數(shù)據(jù)，因此查詢處理和優(yōu)化要復雜得多，下面要討論的重點就是對于連接(Join)常用的一些算法[10]，因為它是查詢中最費事的操作。基于半連接操作的優(yōu)化算法數(shù)據(jù)在網(wǎng)絡中傳輸時，以整個關系傳輸，然后進行連接，顯然是一種冗余的方法。在一個關系傳輸?shù)搅硪粓龅睾?，并非每個數(shù)據(jù)都參與連接操作或都有用。因此，不參與連接的數(shù)據(jù)或無用的數(shù)據(jù)不必在網(wǎng)絡中來回傳輸?；诎脒B接的優(yōu)化策略的基本原理就是采用半連接(semijoin，什么是半連接技術下面將介紹)操作，在網(wǎng)絡中盡量只傳輸參與連接的數(shù)據(jù)。在分布式數(shù)據(jù)庫中連接查詢的主要手段是半連接技術，各種不同算法的差異主要是在連接順序上，即在保證結果一致的情況下，以什么樣的順序將這些表連接起來最優(yōu)。優(yōu)化的對象一般是數(shù)據(jù)傳輸量的總和[11]。分布式數(shù)據(jù)庫的連接查詢算法應該在把握好連接查詢原則的情況下，根據(jù)具體情況靈活設計?？紤]分布式查詢Q=A1A2，情況一：A1的數(shù)據(jù)(或者絕大部分)和A2的數(shù)據(jù)(或者絕大部分)都出現(xiàn)在連接查詢中。其等價描述是：Q、A1、A2的記錄數(shù)相等(或相近)。這種情況是非常常見的。例如，在電信公司的用戶數(shù)據(jù)系統(tǒng)中，要查詢兩個地區(qū)的各種業(yè)務用戶數(shù)量。查詢結果如表2-1：地區(qū)1、地區(qū)2的數(shù)據(jù)分別存儲在各自的節(jié)點中。顯然，該查詢是上述兩個地區(qū)用戶情況在業(yè)務類別相等條件下連接的結果。而且經(jīng)過連接后，各個節(jié)點查詢到的數(shù)據(jù)都保留在最后的查詢結果中，沒有出現(xiàn)某個子查詢的數(shù)據(jù)傳送到上層節(jié)點后對最后結果沒有貢獻的情況。這樣的連接查詢完全可以采用合并查詢的算法。與合并查詢的唯一不同是最后得到子查詢的結果通過連接的方式組合成為最后結果，而不是合并。表2-1兩個地區(qū)的用戶數(shù)據(jù)地區(qū)業(yè)務地區(qū)1地區(qū)2固定電話544,233667,234小靈通156,433185,233寬帶48,77768,344………………情況二：A1的數(shù)據(jù)(或者絕大部分)都出現(xiàn)在連接查詢結果中，而A2的數(shù)據(jù)又很多對查詢的結果毫無貢獻。其等價描述是：Q的記錄數(shù)和A1相等(或相近)，且小于A2的記錄數(shù)。下面的例子可以說明為什么會出現(xiàn)這樣的情況：假設某公司需要查詢該公司的供應部門采購情況，下面是相關數(shù)據(jù)的定義和存儲情況：采購部門的采購單結構如下：NO：采購單編號，10個字節(jié)AMOUNT：采購金額，5個字節(jié)GOODNO：采購貨物代碼，5個字節(jié)TMIE：采購時間，4個字節(jié)假設需要查詢的采購單記錄數(shù)量是10。假設公司的貨物代碼表是由設備維護部門維護的，與采購單不在一個節(jié)點上，貨物代碼表的結構如下：GOODNO：貨物代碼，5個字節(jié)GOODNAME：貨物名稱，15個字節(jié)假設有10000種貨物，這樣貨物代碼表的總數(shù)量是20*10000=200000字節(jié)。查詢的結果是兩個表進行表連接(采購貨物代碼二貨物代碼)，查詢結果是30*10=300字節(jié)。如果采用合并查詢的算法，則傳輸?shù)臄?shù)據(jù)量是200000十20*10=200200字節(jié)，是實際查詢結果的幾百倍。出現(xiàn)這樣情況的原因，主要是因為貨物代碼表的絕大部分內(nèi)容，都沒有對查詢結果做出貢獻，因為我們只需要10種貨物的名稱，沒有必要將所有10000種貨物的代碼表都傳送過來。一種改進的查詢算法如下：設供應部所在節(jié)點為“節(jié)點1”，對它的原子查詢請求是A1；設備管理部門所在的節(jié)點為“節(jié)點2”，對它的原子查詢請求是A2。第一步，GQP將全局查詢要求分解為兩個子查詢A1和A2，將A1發(fā)送到節(jié)點1；第二步，節(jié)點工做查詢A1，然后將A1結果送回GQP。此步驟的傳輸量是200字節(jié)；第三步，GQP將A1的結果和A2發(fā)送到節(jié)點2。此步驟的傳輸量為200個字節(jié)；第四步，節(jié)點2先做查詢A2，再做Q=A1A2，然后將最后結果Q送往GQP。上述算法的數(shù)據(jù)總傳輸量是：200+200+300=700字節(jié)。這個算法可以作為情況二的可行算法，其目標是減少數(shù)據(jù)傳輸量。情況三：A1和A2中均有很多數(shù)據(jù)不出現(xiàn)在查詢結果Q中。等價描述是：A1和A2的記錄數(shù)都大于Q的記錄數(shù)。半連接的概念首先是在分布式數(shù)據(jù)系統(tǒng)分布式查詢設計中提出的，它的定義如下：設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。半連接處理的依據(jù)是：RS=RaS，其中a表示R與S連接的屬性列。通過半連接處理優(yōu)化連接操作的依據(jù)是：RS＝S(RS)。當RS只是R的一小部分時，可以大大減少數(shù)據(jù)的傳輸量。其執(zhí)行過程如圖2-1所示。半連接程序其傳輸代價用公式T=C0+C1X粗略估算。其中，X是數(shù)據(jù)傳輸量，這里可以以bit(位)為單位計算；C0為兩結點之間初始化一次傳輸所花費的開銷，它由通信系統(tǒng)決定，近似為一個常數(shù)，單位為s(秒)；C1為單位數(shù)據(jù)傳輸?shù)拇鷥r，單位為(秒/bit)。其操作過程如下：站點1(關系R)站點2(關系S)②①a(S)③Ra(S)④⑤(Ra(S))S圖2-1基于半連接的執(zhí)行示例第①步：在站點2計算關系S在屬性a上的投影：a(S)。第②步：把a(S)的結果從站點2傳到站點1，其傳輸代價為：C0+C1*size(a)*val(a[S])其中size(a)表示屬性a的長度，val(a[S])表示關系S中屬性a的個數(shù)。第③步：在站點1計算半連接，設其結果為R'，則R'=RS。實際上，這個操作是執(zhí)行Ra(S)。第④步：把R'從站點1傳到站點2，其傳輸代價為：C0+Cl*size(R)*card(R')其中size(R)是R中元組的長度，card(R')是R'的元組數(shù)。第⑤步：在站點2執(zhí)行連接操作R'S。顯然，步驟①、③、⑤無需傳輸費用，所以執(zhí)行這樣一個半連接程序，總的傳輸代價為：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的最優(yōu)半連接程序。如果不采用半連接程序法，而直接采用連接法，則需要把其中一個關系從一個站點傳到另一個站點。例如在站點2執(zhí)行連接操作，相應傳輸代價為：T=C0+Cl*size(R)*card(R)其中size(R)和card(R)分別為關系R中元組的長度和元組的個數(shù)。在一般情況下，card(R)>>card(R')是成立的，即T'<<T成立，因此半接程序法的傳輸代價較小，采用半連接程序執(zhí)行連接操作是合適的。現(xiàn)在重新考慮Q=A1A2(A1和A2都是原子查詢)，情況三，A1、A2中均有很多數(shù)據(jù)不在現(xiàn)在查詢結果Q中。此時，應該盡量避免A1和A2中多余數(shù)據(jù)〔即在Q中并不出現(xiàn)的數(shù)據(jù))在網(wǎng)絡之間傳輸。接下來就是基于半連接的算法：第一步，應該考慮一下最終的結果Q中包含A1和A2的數(shù)據(jù)哪一個更多一些。如果是A1多一些，那么下面的算法將按照A2A1，的方向進行；反之將按照A1A2的方向進行。這里不妨假設結果Q中A1第二步，節(jié)點1(A1所在節(jié)點)將A1需要與A2進行連接的屬性列通過GQP發(fā)送到節(jié)點2(A2所在節(jié)點)；第三步，在節(jié)點2將A2與節(jié)點1發(fā)送過來的數(shù)據(jù)進行連接操作，所得結果即為A2A1；第四步，將節(jié)點2的連接結果(A2A1)通過GQP再次發(fā)送到節(jié)點1；第五步，在節(jié)點1將A1與節(jié)點2通過GQP發(fā)送過來的數(shù)據(jù)(A2A1)做連接操作，連接后的結果是A1(A2A1)＝A1A2。第六步，將最終的查詢結果發(fā)送給GQP。可以看出，半連接的處理方法雖然可以節(jié)省一些數(shù)據(jù)傳輸量，但是算法的復雜度也相應提高，同時節(jié)點之間的相互調度也增加了一些延遲時間。在實際應用中還需要仔細在節(jié)省的數(shù)據(jù)傳輸量，算法復雜度和延遲時間之間進行衡量。多關系半連接查詢優(yōu)化算法普通多關系半連接查詢方法是按照關系間的連接順序執(zhí)行半連接，優(yōu)點是處理簡單，不足之處是沒有考慮到如何優(yōu)化子查詢的半連接順序來進一步減少網(wǎng)絡通信的代價[12]。本文的基于多關系半連接查詢優(yōu)化算法是針對普通多關系半連接查詢方法的不足之處而提出的，即通過代價估算和半連接，在如何進一步減少子查詢的網(wǎng)絡代價問題上進行了改進。本文將執(zhí)行所有子查詢所產(chǎn)生的中間結果的數(shù)據(jù)量作為網(wǎng)絡代價的決定性因素，本文約定多關系半連接查詢優(yōu)化算法的優(yōu)化效益，是指多關系半連接查詢優(yōu)化算法與普通多關系半連接查詢方法進行比較所得的相對效益。本文定義確定多關系半連接查詢優(yōu)化算法優(yōu)化效益的函數(shù)為式2-1[13]。設＝(執(zhí)行普通多關系半連接查詢方法的網(wǎng)絡代價一執(zhí)行多關系半連接查詢優(yōu)化算法的網(wǎng)絡代價)/執(zhí)行普通多關系半連接查詢方法的網(wǎng)絡代價。(式2-1)數(shù)據(jù)庫分布如圖2-2所示，站點0、1、2、3、4分別表示不同的計算機，站點1、2、3、4的數(shù)據(jù)庫中分別存放著不同的表。站點0存放全局數(shù)據(jù)庫信息，例如全局表信息、全局表與局部表的對應信息(如局部表所屬的局部數(shù)據(jù)庫訪問信息如Provider、UserID、Password、DataSource等)，其中全局表信息包括全局表表名、全局表各字段信息，全局表信息只是全局表的表結構，不存放實際數(shù)據(jù)，實際數(shù)據(jù)存放在局部數(shù)據(jù)庫的局部表中。站點1、2、3、4分別存放局部數(shù)據(jù)庫信息，其中局部表信息包括局部表名稱、局部表字段信息，還包括實際數(shù)據(jù)。例子中各個全局表和局部表的主要字段有ID標志符和Name名稱兩個屬性，為了方便計算通信代價，例子中假定兩個屬性具有相同的長度。例子中，站點0向本站點的全局數(shù)據(jù)庫發(fā)出全局查詢請求，全局查詢語句經(jīng)過查詢分解，轉換為對站點1、2、3、4的局部查詢語句，從而全局查詢轉換為對站點1、2、3、4中的局部數(shù)據(jù)庫的分布式查詢。分布式查詢過程中的中間數(shù)據(jù)傳輸?shù)秸军c0，在站點0進行緩存，最后在站點0對中間數(shù)據(jù)進行拼裝，作為最終查詢結果返回給用戶。下面討論分布式查詢在優(yōu)化前及優(yōu)化后的半連接執(zhí)行順序、通信代價及優(yōu)化效益。查詢例子：以鏈式連接ProductsOrderDetaiIsOrdersCustomers作為基本連接。站點0站點0OrdersOrderDetailsEmplyeesProductsShippersCustomers站點1站點2站點3站點4OrdersProductsShippersCustomersOrderDetailsEmplyees全局數(shù)據(jù)庫中的全局表局部數(shù)據(jù)庫中的局部表圖2-2數(shù)據(jù)庫分布圖全局查詢語句為：SelectProductName,OrderDetaiIName,OrderName,CustomerNameFromProducts,OrderDetails,Orders,CustomersWhereProducts.ProductID=OrderDetails.ProductIDAndOrderDetails.OrderlD=Orders.OrderlDAndOrders.CustomerID=Customers.CustomerID前文己描述過站點0中的全局數(shù)據(jù)庫除了存放全局表信息外，還存放著全局表與局部表的對應信息，這里對應信息除了上述已描述過的局部表所屬的局部數(shù)據(jù)庫訪問信息外，還存放著每個局部表的統(tǒng)計量參數(shù)信息。設：局部表Orders的統(tǒng)計量T為830，表示局部表Orders中的總的記錄數(shù)為830；局部表Orders的統(tǒng)計量V(OrderlD)為830，表示局部表Orders中在OrderlD屬性上值不同的記錄數(shù)為830；局部表Orders的統(tǒng)計量V(CustomerlD)為90，表示局部表Orders中在CustomerID屬性上值不同的記錄數(shù)為90。例子中，各個關系、連接屬性及其統(tǒng)計量參數(shù)如表2-2所示。鏈式連接的全局查詢語句經(jīng)過初步查詢分解為以下三個查詢語句：SelectProductName,OrderDetailNameFromProducts,OrderDetailsWhereProducts.ProductID=OrderDetails.ProductID及SelectOrderDetaiIName,OrderNameFromOrderDetails,OrdersWhereOrderDetails.OrderlD=Orders.OrderID表2-2例子中的關系及統(tǒng)計量參數(shù)關系統(tǒng)計量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為鏈式連接優(yōu)化前的半連接圖，圖2-4為鏈式連接經(jīng)過多關系半連接查詢優(yōu)化算法優(yōu)化后的半連接圖。ProductsProductsOrderDetailsOrdersCustomers站點3站點2站點1站點4圖2-3鏈式連接優(yōu)化前的半連接圖ProductsProductsOrderDetailsOrdersCustomers站點3站點2站點1站點4圖2-4鏈式連接優(yōu)化后的半連接圖優(yōu)化前鏈式連接優(yōu)化前半連接執(zhí)行順序為：OrderDetailsProductsOrderDetailsOrdersOrdersCustomers鏈式連接優(yōu)化前通信代價分為以下幾個部分：1)半連接OrderDetailsProducts的通信代價首先將站點3中Products表的屬性ProductID及屬性ProductName的數(shù)據(jù)傳輸?shù)秸军c0，通信代價為：80+80=160；然后站點0將屬性ProductlD的數(shù)據(jù)傳輸?shù)秸军c2進行連接，通信代價為：80。通信總代價為：160+80=240。2)半連接OrderDetailsOrders的通信代價首先將站點1中Orders表的屬性OrderlD及屬性OrderName的數(shù)據(jù)傳輸?shù)秸军c0，通信代價為：830+830=1660；然后站點0將屬性OrderlD的數(shù)據(jù)傳輸?shù)秸军c2進行連接，通信代價為：830。通信總代價為：1660+830=2490。3)半連接OrdersCustomers的通信代價首先將站點4中Customers表的屬性CustomerID及屬性CustomerName的數(shù)據(jù)傳輸?shù)秸军c0，通信代價為：90+90=180；然后站點0將屬性CustomerID的數(shù)據(jù)傳輸?shù)秸军c1進行連接，通信代價為：90。通信總代價為：180+90=270。4)站點2中表OrderDetails的屬性OrderDetaillD及屬性OrderDetaiIName的數(shù)據(jù)傳輸?shù)秸军c0的通信代價通信總代價為：80+80=160。鏈式連接優(yōu)化前通信總代價為：240+2490+270+160=3140。優(yōu)化后鏈式連接優(yōu)化后半連接執(zhí)行順序為：OrderDetailsProductsOrdersOrderDetailsCustomersOrders鏈式連接優(yōu)化后通信代價分為以下幾個部分：1)半連接OrderDetailsProducts的通信代價首先將站點3中表Products的屬性ProductID及屬性ProductName的數(shù)據(jù)傳輸?shù)秸军c0，通信代價為：80+80=160；然后站點0將屬性ProductID的數(shù)據(jù)傳輸?shù)秸军c2進行連接，通信代價為：80。通信總代價為：160+80=240。2)半連接OrdersOrderDetails的通信代價首先將站點2中表OrderDetails的屬性OrderDetailID及屬性OrderDetailName的數(shù)據(jù)傳輸?shù)秸军c0，通信代價為：80+80=160；然后站點0將屬性OrderDetailID的數(shù)據(jù)傳輸?shù)秸军c1進行連接，通信代價為：80。通信總代價為：160+80=240。3)半連接CustomersOrders的通信代價首先將站點1中表Orders的屬性OrderID及屬性OrderName的數(shù)據(jù)傳輸?shù)秸军c0，通信代價為：80+80=160；然后站點0將屬性OrderID的數(shù)據(jù)傳輸?shù)秸军c4進行連接，通信代價為：80。通信總代價為160+80=240。4)站點4中表Customers的屬性CustomerID及屬性CustomerName的數(shù)據(jù)傳輸?shù)秸军c0的通信代價通信總代價為：80+80=160。鏈式連接優(yōu)化后通信總代價為：240+240+240+160=840。鏈式連接優(yōu)化效益=(執(zhí)行普通多關系半連接查詢方法的網(wǎng)絡代價一執(zhí)行多關系半連接查詢優(yōu)化算法的網(wǎng)絡代價)/執(zhí)行普通多關系半連接查詢方法的網(wǎng)絡代價=(3140-840)/3140=0.73。如果直接將站點1、2、3、4中局部數(shù)據(jù)庫的數(shù)據(jù)送到站點0，其通信代價為：(80+80)+(2850+2850)+(830+830)+(90+90)=7700。鏈式連接優(yōu)化效益=(7700-840)/7700=0.89。則其優(yōu)化效益更為明顯。通過上述鏈式連接的例子可以看出基于多關系半連接的查詢優(yōu)化算法明顯地減少了中間結果數(shù)據(jù)量，有效地降低了網(wǎng)絡通信總代價。與普通的多關系半連接算法比較，基于多關系半連接的查詢優(yōu)化算法的優(yōu)化效益更高。SDD-1算法用半連接查詢?nèi)〈B接查詢的方法，可以減少數(shù)據(jù)在網(wǎng)絡中的傳輸量。但是事先不可能知道哪個關系表的元組被更多的包含在連接結果中，所以如何確定傳輸哪一個關系表的屬性列是擺在我們面前的問題，而SDD-1算法很好的解決了這個問題[13]。由美國計算機公司1978年研制的SDD-1是分布式數(shù)據(jù)庫管理系統(tǒng)的第一個樣機，該系統(tǒng)采用的分布式查詢方法是多關系半連接算法。在介紹SDD-1算法前，首先介紹選擇因子及半連接的收益分析有關概念。定義1設R和S是兩個關系，R和S半連接選擇因子記為[15]SF(RS)=card(a(S))/card(S)(式2-2)其中card(a(S))是關系S在關系R和S的公共屬性a上投影所包含的不同元組的個數(shù)，card(S)是關系S的元組個數(shù)。定義2半連接代價公式記為：cost(RS)=size(a(S))=card(a(S))*length(a)(式2-3)其中l(wèi)ength(a)是屬性a定義的長度(字節(jié)數(shù))；半連接效益公式記為：benefit(RS)=(1-SF(RS))*size(R)(式2-4)其中size(R)表示關系R的大小(字節(jié)數(shù))；有益半連接：benefit(RS)-cost(RS)>0的半連接；最有益半連接：多個半連接中，benefit(RS)-cost(RS)結果最大的半連接。SDD-1查詢優(yōu)化算法大致思想是通過反復的獲得有益半連接運算，減少每個站點上用于連接運算的數(shù)據(jù)，然后將所有站點的數(shù)據(jù)匯集到數(shù)據(jù)量最大的站點做最后裝配。處理過程主要包括三個步驟：(1)初始化：從全部關系中的半連接中生成有益的半連接集合；(2)選擇有益的半連接：從有益的半連接集合中找出最有益的半連接，將其添加到執(zhí)行策略中，并相應地修改被影響關系的統(tǒng)計值(選擇因子，關系的大小等)；(3)選擇組裝場地：重復第一步，直到所有有益的半連接加入到執(zhí)行策略中。關系經(jīng)上面步驟縮減后，選擇存儲數(shù)據(jù)量最大的站點為組裝場地。本章小結移動DBMS的計算環(huán)境是傳統(tǒng)分布式DBMS的擴展，它可以看作客戶與固定服務器結點動態(tài)連接的分布式系統(tǒng)。本章主要介紹了傳統(tǒng)分布式數(shù)據(jù)庫中連接操作使用的減少通信開銷的優(yōu)化策略以及由此而產(chǎn)生的多關系連接查詢優(yōu)化算法，這些算法為接下來的探討和改進提供了一些參考和根據(jù)。嵌入式/移動實時環(huán)境下的查詢優(yōu)化處理未來的移動計算機都將配備以無線網(wǎng)絡為主的移動聯(lián)網(wǎng)設備，以支持移動用戶訪問網(wǎng)絡中的數(shù)據(jù)，這是一種更加靈活、復雜的分布式計算環(huán)境，人們稱之為移動計算(MobileComputing)。移動計算系統(tǒng)是由固定結點和移動結點構成的分布計算系統(tǒng)，它將使用戶在移動的同時通過移動通信網(wǎng)絡保持與固定結點或其它移動結點的連接。與固定網(wǎng)絡的傳統(tǒng)分布計算環(huán)境相比，移動計算環(huán)境具有以下特征：(1)頻繁斷接性；(2)網(wǎng)絡條件多樣性；(3)網(wǎng)絡通信的非對稱性。其中，非對稱性指的是服務器到移動計算機的下行鏈路與移動計算機到服務器的上行鏈路相比，它們之間的通信帶寬與代價相差很大。近年來，數(shù)據(jù)處理技術所依賴的計算環(huán)境發(fā)生了重大變化，移動計算機的使用成為計算機界發(fā)展的一個必然趨勢。計算機從大型機向個人電腦的發(fā)展使得個人能有更多的機會和方法獲取信息和進行計算，而移動計算機則加快了這一發(fā)展進程。各個應用領域都開始對移動設備使用，移動計算技術、移動數(shù)據(jù)處理和移動信息服務等進行深入的研究并逐漸進入實用化。在早期的研究中移動計算[16,17]主要集中在研究移動主機協(xié)議、降低電源消耗、上下文感知的計算以及弱連接通信中的數(shù)據(jù)共享。這時主要分析移動計算和傳統(tǒng)分布計算之間的差別以及如何從分布計算向移動計算過渡[18]。移動設備的一個共同特征是：體積相對較小，處理能力較弱，移動用戶本地的處理效率和準確性較低。如果將它作為一個大型服務系統(tǒng)的應用終端或智能終端，可以充分利用各種網(wǎng)絡資源和大型服務器的處理能力。而使用性能較高的便攜式計算機的MC可以通過復制技術維護一個數(shù)據(jù)緩存與副本，在發(fā)生斷接時，MC可以在副本的基礎上繼續(xù)工作?；謴瓦B接后，MC與主本以及其他副本進行同步，達到數(shù)據(jù)一致。隨著移動通信技術的快速發(fā)展，智能化終端產(chǎn)品將不斷涌現(xiàn)，移動計算硬件平臺的價格正在不斷下降，移動電子商務應用解決方案正在不斷完善，企業(yè)、個人用戶對移動計算的需求將會穩(wěn)步增長，一個無縫覆蓋的數(shù)字化的地球將隨著移動計算的發(fā)展一步一步向我們走近。隨時隨地上網(wǎng)，隨時隨地發(fā)布消息，隨時隨地獲得信息，這就是離我們并不遙遠的移動計算能夠帶給我們的便利，移動計算技術將大大改變我們的工作和生活環(huán)境。目前，移動計算己經(jīng)成為第三代互聯(lián)網(wǎng)的標志性技術之一。適用于移動數(shù)據(jù)庫系統(tǒng)的客戶/服務器結構和傳統(tǒng)的分布計算模型相比，代理的移動性和自治性帶來了許多的優(yōu)點，采用移動代理技術可以得到許多的好處[19-22]。節(jié)約網(wǎng)絡帶寬：移動代理直接在數(shù)據(jù)端執(zhí)行處理，和客戶端沒有中間數(shù)據(jù)結果的傳遞，只返回最后的結果。因而在要處理的數(shù)據(jù)量特別大、網(wǎng)絡帶寬不足的情況下，移動代理可以有效地節(jié)約網(wǎng)絡帶寬。提供實時的遠程交互：在一些遠程控制系統(tǒng)中，如外太空探測器的控制、網(wǎng)絡的時延使得遠程實時控制變得不太可能，發(fā)送代理程序實行遠端的本地控制可解決該問題。支持離線計算：用戶派遣出代理程序后，可以斷開網(wǎng)絡連接，而代理將在網(wǎng)絡上自主運行。代理完成任務后，當它發(fā)現(xiàn)用戶設備重新連上網(wǎng)絡時，就返回計算結果。Client/Agent/Server模型移動數(shù)據(jù)庫系統(tǒng)可以看作是傳統(tǒng)分布式數(shù)據(jù)庫系統(tǒng)的擴展。移動數(shù)據(jù)庫體系結構中的固定網(wǎng)絡其實就是傳統(tǒng)的分布式數(shù)據(jù)庫系統(tǒng)，在此基礎上增加一些移動基站或僅在一些結點上增加無線接口就構成了移動數(shù)據(jù)庫系統(tǒng)。移動Agent是一個獨立的計算機程序，它可以自主地在異構的網(wǎng)絡上，按照一定的規(guī)程遷移，尋找合適的計算資源、信息資源或軟件資源，利用這些資源同處一臺主機或網(wǎng)絡的優(yōu)勢，處理或使用這些資源，代表用戶完成特定的任務。它要完成的任務是由啟動它的應用程序決定的，可能從在線購物到實時設備控制進而到分布式科學計算。應用程序啟動MobileAgent并把它送入網(wǎng)絡中[23,24]，按照預定的或者由它們自己根據(jù)動態(tài)搜集的信息所決定的路線遷移，完成任務就返回到主站點向用戶報告結果。一般基于移動Agent的移動數(shù)據(jù)庫體系結構如圖3-1如示。服務器(SVR)：服務器一般為固定結點，每個服務器維護一個本地數(shù)據(jù)庫，在服務器保留有所有請求的歷史記錄。MCMC固定網(wǎng)絡（Mbps到Gbps）SVR/DAMSS/MADSVR/DAMSS/MADSVR/DAMSS/MADSVR/DASVR/DALDBLDBLDBLDBLDBMCMCMC:MobileClient(移動客戶機)MSS:MobileSupportStation(支持移動計算的固定站點)MAD:MobileAgentDock(移動Agent碼頭)SVR:Server(固定主機管理本地數(shù)據(jù)庫)DA:DatabaseAgent(數(shù)據(jù)庫Agent)LDB:LocalDatabase(本地數(shù)據(jù)庫)圖3-1基于Agent的移動數(shù)據(jù)庫體系結構數(shù)據(jù)庫Agent(DA)：位于服務器上的靜止Agent，負責處理客戶機對數(shù)據(jù)庫的訪問請求，直接對數(shù)據(jù)庫進行操作，通過與移動Agent通訊來接收和返回結點信息到客戶機。移動支持結點(MSS)：位于固定高速網(wǎng)絡中，用于支持無線網(wǎng)絡單元，它既能通過無線鏈路與移動客戶機通信，也可通過固定網(wǎng)絡與服務器通信。移動Agent碼頭(MAD)：位于MSS上的移動Agent管理系統(tǒng)。它根據(jù)客戶機的請求創(chuàng)建移動Agent，并將移動Agent送到正確地址，它還接收從服務器端返回的移動Agent，將其結果傳遞給相應客戶機。服務器(SVR)：服務器一般為固定結點，每個服務器維護一個本地數(shù)據(jù)庫，在服務器保留有所有請求的歷史記錄。數(shù)據(jù)庫Agent(DA)：位于服務器上的靜止Agent，負責處理客戶機對數(shù)據(jù)庫的訪問請求，直接對數(shù)據(jù)庫進行操作，通過與移動Agent通訊來接收和返回結點信息到客戶機。移動支持結點(MSS)：位于固定高速網(wǎng)絡中，用于支持無線網(wǎng)絡單元，它既能通過無線鏈路與移動客戶機通信，也可通過固定網(wǎng)絡與服務器通信。移動Agent碼頭(MAD)：位于MSS上的移動Agent管理系統(tǒng)。它根據(jù)客戶機的請求創(chuàng)建移動Agent，并將移動Agent送到正確地址，它還接收從服務器端返回的移動Agent，將其結果傳遞給相應客戶機。移動客戶機(MC)：具有移動性且與網(wǎng)絡頻繁斷接的計算設備。這種模型的優(yōu)點在于：斷接時，Agent仍然可以與Server交互執(zhí)行任務；Agent可以利用固定網(wǎng)絡的高帶寬；可以由Agent執(zhí)行優(yōu)化操作；可以有選擇地傳送結果。但是這種模型也存在缺點：一旦出現(xiàn)斷接操作，客戶機就不能繼續(xù)工作。而且Agent只能優(yōu)化從固定網(wǎng)絡到移動客戶機的數(shù)據(jù)傳輸，反之則不能，即從移動客戶機到固定網(wǎng)絡的數(shù)據(jù)傳輸無法優(yōu)化。為了解決這些問題可以采用下面將介紹的Client/Intercept/Server模型。Client/Intercept/Server模型這種模型將Agent劃分為兩個部分：服務器端Agent(Server-sideAgent)和客戶端Agent(Client-sideAgent)。顧名思義Server-sideAgent駐留在固定網(wǎng)絡的服務器端；而Client-sideAgent則駐留在客戶端。后者解釋客戶機的請求并與前者一起執(zhí)行優(yōu)化處理以減少在無線鏈路上的數(shù)據(jù)傳輸，改善數(shù)據(jù)的可用性并保證移動客戶機的操作不間斷性。從客戶機的角度來看，Client-sideAgent的作用相當于一個駐留在本地客戶機上的局部服務器代理。同樣，Server-sideAgent就如同在服務器端的本地客戶機代理。Server-sideAgent駐留在固定網(wǎng)絡中，并不一定要和相應的服務器駐留在同一臺機器上，因此這組Agent可以看成是“虛”插入在客戶機和服務器之間的數(shù)據(jù)通路上。該模型對于客戶機和服務器都是透明的。它們可以為多個應用程序所使用。兩個Agent的共同協(xié)作來優(yōu)化無線鏈路的使用從而使不同的應用獲益，特別是可以更為有效地進行特定應用的優(yōu)化。該模型可以靈活的處理斷接操作。在Client-sideAgent上可以進行局部數(shù)據(jù)緩存。該緩存可以在一定程度上滿足在斷接情況下客戶的數(shù)據(jù)需求。緩存的命中丟失可以由Agent進行排隊處理，一旦再次連接成功就可以解決命中丟失問題[25-27]。同樣在斷接狀態(tài)，服務器端對客戶機的要求也可以在Server-sideAgent處進行緩存等待處理直到再次成功連接。對于弱連接的處理方法類似。該模型較適用于具有足夠的計算能力和較強輔存能力的“胖”客戶。其缺點是每個應用都要求在服務器端和客戶機端開發(fā)相應的程序。但是無需為每個應用實例都開發(fā)一對Agent。相反，由于Agent對所執(zhí)行的功能和優(yōu)化是共性的，它只要為每個不同應用類型，如文件系統(tǒng)，數(shù)據(jù)庫系統(tǒng)，WEB應用，分別開發(fā)一對Agent即可。對于兩個Agent的角色的劃分可以獲得類似于Client/Agent/Server模型中Agent角色劃分的分類結果。顯然，Server-sideAgent可以作為客戶機的全權代理或與特定服務相關。嵌入式/移動實時數(shù)據(jù)庫查詢優(yōu)化處過程移動計算環(huán)境的特性使得面向固定計算環(huán)境的客戶/服務器查詢模型變得不再適用。對查詢模型的改進從兩個方向進行：基于緩存和復制技術的模型具有獨特的優(yōu)點，可以有效的支持斷接的查詢，但此模型應用上具有其局限性；基于Agent的查詢模型有著不可替代的作用，能較好地支持用戶的移動性，可以支持脫機查詢，斷接查詢。在系統(tǒng)的初步設計中，作一些必要、合理的假設，可以簡化系統(tǒng)的設計，使系統(tǒng)在設計中不會過多的糾纏于一些瑣碎的細節(jié)，而迷失了主要的方向。同時，合理的假設也使系統(tǒng)結構清晰明了，利于系統(tǒng)的定制和維護。在本文的設計中，綜合考慮了嵌入式/移動環(huán)境下的特點以及3.1節(jié)中提到的體系結構，作了以下幾點假設：1)準分布式體系結構[28]。理論上，移動數(shù)據(jù)庫管理系統(tǒng)是傳統(tǒng)分布式數(shù)據(jù)庫管理系統(tǒng)的移動形式，即有數(shù)據(jù)復本的服務器也可以是移動的。但是一開始就從一個全可移動的分布式數(shù)據(jù)庫系統(tǒng)的要求來考慮問題，會給查詢處理等問題增加不少難題。因此這里假設移動端只能從位置固定的中心數(shù)據(jù)庫中獲取數(shù)據(jù)，即中心服務器的位置是不變的。這個假設是合理的。以后只需在現(xiàn)有的體系上進行擴展，由一個或多個在固定網(wǎng)絡上的同步服務器負責和移動著的數(shù)據(jù)庫服務器進行通信，維護它們的位置信息、事務信息、復本信息就可以解決數(shù)據(jù)庫服務器的移動問題。而這些都可以做到對移動用戶是透明的。2)移動用戶的配置采用目前流行的配置[29-31]：無磁盤等持久存儲設備，只提供RAM和ROM存儲；操作系統(tǒng)一般固化在ROM中；由一般操作系統(tǒng)提供基本的網(wǎng)絡功能，可以通過TCP/IP和其他主機通信。操作系統(tǒng)包括WindowsCE和Linux的各種改進版本。這些設備都可以緩存一定的數(shù)據(jù)庫數(shù)據(jù)，從而可以利用緩存技術通過在客戶機上緩存部分數(shù)據(jù)，達到減少訪問數(shù)據(jù)庫服務器的目的，從而提高了性能。但是，傳統(tǒng)的緩存技術要求客戶機保持與服務器的連接，這樣才能維護緩存的一致性[32,33]。因此，對于經(jīng)常需要斷接操作的移動客戶機來說，傳統(tǒng)的緩存技術也是不能適用的。3)移動用戶的操作在一段時間內(nèi)具有較強的可預見性。目前情況下，很多的移動設備都是為某種特殊的應用定制的，如用于飛機停機時的檢測，稅務部門的稅收記錄等等。因此用戶在一定時間內(nèi)的操作是可預見的，有規(guī)律可尋的，這些規(guī)律可用于查詢優(yōu)化，同時用戶所需要的大部分的數(shù)據(jù)也就可以預先設定。另外，通過積累用戶操作的歷史數(shù)據(jù)，應用數(shù)據(jù)挖掘等方法，也可以找到一些規(guī)律。4)中心服務器有足夠的空間及計算能力，能支持大量的用戶同時訪問。并保存大量用戶的信息，如：用戶訂閱的數(shù)據(jù)集，喜好信息，操作的歷史記錄等等。這個假設也是合理的，因為中心服務器可以是大型計算機，也可以是一個分布式的服務器群，它們互相協(xié)作，作為一個整體對移動方提供服務。以上文中的假設為基礎，本文根據(jù)Client/Intercept/Server模型分別設計了兩個Agent：服務器端Agent和客戶端Agent?？蛻舳思闪艘粋€后臺嵌入式數(shù)據(jù)庫管理系統(tǒng)SQLite，用戶提出查詢請求后先由客戶端Agent判斷能否在本地得以獲得結果，若能將由本地DBMS(SQLite)進行查詢處理，否則就提交該查詢請求至服務器端Agent，服務器端Agent會維持一個服務隊列，對于隊列中的每一個請求將建立一個單獨的處理線程負責查詢的實現(xiàn)和結果的返回。首先，客戶端Agent檢查該查詢是否能部分或全部在移動子集的一個語義片段中得到滿足。若完全滿足，則用該片段中可用數(shù)據(jù)直接處理并返回；如果查詢只能被部分滿足，將對該查詢進行查詢修剪。所謂查詢修剪，是指當一個查詢只能部分地被一個語義片段S響應時，可將該查詢分成兩部分：一部分是能從S中得到答案的，另一部分是不能從S中得到結果的。由于移動子集中可能存在多個語義片段，對后者要繼續(xù)重復上述工作，直至遍歷移動子集中所有分片。仍然不能滿足的查詢部分要傳遞給服務器端Agent進行處理。提交到服務器端Agent的查詢優(yōu)化部分主要針對多元連接，因為這類操作可能會涉及多個結點上的片段，是最費事的操作。其次，對于提交到服務器端Agent的查詢優(yōu)化部分，服務器將對于每個請求啟動一個后臺服務例程。這個例程將讀取服務器主機中同步更新的全局關系表、全局站點表、相關系數(shù)表等數(shù)據(jù)，運用一定的算法對查詢進行分析，給出一個全局較優(yōu)的查詢步驟。嵌入式/移動實時環(huán)境下的查詢代價分析傳統(tǒng)的分布式數(shù)據(jù)庫中查詢優(yōu)化處理使用的代價模型并沒有反映太多與移動計算環(huán)境有關的特點，因此，很顯然，以前的很多關于分布式查詢處理的研究沒有充分考慮移動環(huán)境下不對稱的特點，而這些特點在設計相關查詢處理策略的時候相當重要。鑒于此，在本文中考慮了移動計算環(huán)境三個重要的不對稱特征，設計出有效的針對查詢中的多元連接操作優(yōu)化策略。在進行代價分析的時候，還要從下面三個方面進行考慮：1)考慮移動主機和固定服務器不同的計算能力，將兩者做為參與連接操作時候不同的站點類型進行區(qū)別對待，而傳統(tǒng)分布式系統(tǒng)下只考慮固定服務器之間的連接操作，沒有考慮不同站點之間計算能力的區(qū)別。2)建立網(wǎng)絡開銷模型的同時，細化并區(qū)別移動站點收/發(fā)數(shù)據(jù)不同的傳輸代價系數(shù)，同時將電源消耗率加入開銷代價考慮之中。3)移動終端處于活動狀態(tài)和空閑狀態(tài)時候電源消耗的不同。移動終端有可能設計成這種模式[33,34]：盡量把處理工作遷移到服務器端來使得自己保持在更多的空閑狀態(tài)。表3-1顯示了移動計算環(huán)境中代價模型使用的一些參數(shù)，這些系數(shù)可以由于移動計算機的具體規(guī)格參數(shù)估算出來[34-37]。代價估算公式一般而言，一個查詢語句經(jīng)過處理后其結果傳到查詢點的總代價為：總代價＝CPU代價+I/O代價+傳輸代價。在這里，主要考慮移動計算環(huán)境拓撲結構中不對稱的表3-1移動計算系統(tǒng)代價模型參數(shù)說明表參數(shù)符號說明SM服務器/移動計算機計算能力比E發(fā)送/接收數(shù)據(jù)能量消耗比移動計算機空閑系數(shù)Erc移動計算機數(shù)據(jù)接收能量消耗系數(shù)Esd移動計算機數(shù)據(jù)發(fā)送能量消耗系數(shù)Ts服務器端查詢處理時間函數(shù)dt查詢處理數(shù)據(jù)傳輸總量Ec查詢處理能量消耗總量特點，同時為了簡化問題，提出一種新的代價估算公式為：cost()=本地處理電源消耗代價+網(wǎng)絡傳輸代價。其中移動主機本地處理電源消耗代價計算公式如下：①Ec(C)=Esd(|R2|)+*Ts(|R1R2|)+Erc(|R1R2|)(式3-1)②Ec(C)＝Erc(|R1|)+(1/)*SM*Ts(|R1R2|)(式3-2)公式①和②的區(qū)別在于：對于連接R1R2（假定R1在服務器主機S上，R2在移動計算機M上)，①中S將表R1傳送到M進行處理，而②中M將表R2傳送到S進行處理。網(wǎng)絡傳輸代價計算公式如下：Cnet()=C0+C1+C2*t*f(D)(式3-3)其中C0和C1分別表示兩個主機啟動一次所需的代價，由于它們的值相對來說很小，一般可以忽略不計，另外為了問題討論的方便，該表達式可以簡化為Cnet()=C2*t*f(D)：C2表示單位容量的數(shù)據(jù)在網(wǎng)絡中傳輸所需要的代價，它的值隨著主機所在的網(wǎng)絡的不同而不同。表3-2表示了在不同網(wǎng)絡條件下的C2的值，C2為每一單位的數(shù)據(jù)量在不同的網(wǎng)絡條件下傳輸所消耗的網(wǎng)絡資源的代價，其值是文獻[38]通過試驗得到的數(shù)據(jù)；t為單個元組的大?。籪(D)表示估算一個查詢語句結果的元組的個數(shù)。表3-2不同網(wǎng)絡條件下的C2的值C2的值網(wǎng)絡條件1固定節(jié)點之間的本地傳輸代價10固定節(jié)點和本地節(jié)點之間的本地傳輸代價10移動節(jié)點之間的本地傳輸代價30固定節(jié)點之間的遠程傳輸代價45固定節(jié)點和本地節(jié)點之間的遠程傳輸代價45移動節(jié)點之間的遠程傳輸代價1)自然連接中間結果大小的近似計算公式|RiRj|=|Ri|*|Rj|/Card-D(dom(Ak))(式3-4)|Ri|和|Rj|分別表示Ri，Rj的大小，Ri與Rj通過公共域Ak連接，域dom(Ak)是屬性Ak所有可能取的值的集合。2)中間結果傳輸網(wǎng)絡代價公式Cost(Ri→Rj)=Cnet()=C+C2*t*f(D)(式3-5)其中X是Ri往Rj傳輸?shù)臄?shù)據(jù)量，C是啟動一次兩地傳輸?shù)墓潭ㄙM用，一般可以忽略C，C2是網(wǎng)絡范圍內(nèi)的單元傳輸費用。本章小結本章主要對于嵌入式，移動，實時三種環(huán)境綜合一起后對于數(shù)據(jù)庫查詢優(yōu)化的一些影響和改變進行了探討和假設，并給出了一種查詢分解的可能方式：將查詢分解為本地執(zhí)行和交給服務器端執(zhí)行兩種情況，這樣可以有利于問題的深入研究。另外，本章主要對于嵌入式移動實時數(shù)據(jù)庫的查詢優(yōu)化進行了分析，在充分考慮了嵌入式移動實時數(shù)據(jù)庫與傳統(tǒng)分布式數(shù)據(jù)庫系統(tǒng)異同點的基礎上，主要針對最費事的連接操作給出了已有研究中提到過的相應的代價估算公式，這一章內(nèi)容主要為下一章提出的優(yōu)化算法做準備。4嵌入式/移動實時環(huán)境下的數(shù)據(jù)庫查詢優(yōu)化算法4.1查詢處理方法和優(yōu)化策略本文第二章介紹的多關系半連接算法主要是利用半連接運算代替連接運算，并確定了數(shù)據(jù)傳輸?shù)姆较颍瑴p少了數(shù)據(jù)傳輸量。但是這些算法也存在這一些問題：1)對于算法中的選擇因子，不可能事先知道。選擇因子的確定依賴于DDBS的其他算法。2)算法要多次進行輔助運算(如對選擇因子、傳輸代價的修改以及用半連接的結果替代本地數(shù)據(jù))。針對這些情況本文設計出一種算法簡單，運行效率較高的并行處理算法，并且該算法指定局部數(shù)據(jù)庫中經(jīng)過半連接優(yōu)化操作后數(shù)據(jù)量最大的站點作為查詢的中間結果的最后裝配的站點[39]。4.1.1多元連接查詢優(yōu)化算法思想在給出本文提出的多元連接查詢優(yōu)化算法前，先簡單描述一下最小生成樹算法的思想。給定一個多元自然連接查詢Q，設Q涉及的關系為{R1,R2,R3,...,Rn}。用連接圖表示這n個關系以及關系之間可能的連接，圖的頂點表示關系，邊表示關系之間的連接。通過上一章的代價估計模型，預先估計連接的代價作為邊上的權值。對于n個關系的連接圖可以建立許多不同的生成樹，每一棵生成樹都可以是一種連接方式。最小生成樹算法的目標就是盡量得到一個全局上的最佳連接次序，使查詢Q的總代價最小[40-42]。一個好的移動計算環(huán)境下的多元連接查詢算法，應該是通信費用低，并行性高。提高算法的并行性，對整個算法的效率有很大的影響。尤其對于多元連接查詢，查詢所涉及的關系往往分布在不同的場地，采用盡可能多的并行連接尤為重要。本文接下來提出的改進最小生成樹算法能得到一個盡可能多的并行連接操作，同時使總代價盡可能小。4.1.2改進最小生成樹算法1)算法描述第一步：最小生成樹的初始狀態(tài)T0為只有n個頂點而無邊的非連通圖，即T0＝{V,{￠}}圖中每個頂點自成一個連通分量。第二步：在E中選擇代價最小的邊，若該邊依附的兩頂點至少有一個已在T0中的連通分量上，則將此邊并入E’（E’初始值為￠），而選擇下一條代價最小的邊，否則加入T0中。第三步：重復第二步直到E＝￠，則此時T0即為已找到的盡可能多的并行處理，輸出T0。第四步：從E’中選擇代價最小的邊，若該邊依附的頂點落在T0不同的連通分量上，則此邊加入T0中，否則舍此邊而選擇下一條代價最小的邊。第五步：重復第四步直到T0中所有頂點都在同一連通分量為止。2)算法實現(xiàn)主要算法偽代碼如下：算法4-1：generatePath輸入：表信息結點鏈表頭pTableNodeHead，連接信息鏈表頭pLinkPairHead輸出：優(yōu)化后的連接處理路徑//只對鏈式連接進行優(yōu)化和考慮intgeneratePath(tableNode*pTableNodeHead,intNum,linkPair**pLinkPairHead){ 打開結果輸出文件； 計算連接總數(shù)totalPair； while(notUsed>0){//初始化各條件進行新的一次并行處理 置每個pTableNodeHead節(jié)點的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){ 總的未處理連接數(shù)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];計算出該兩表最優(yōu)傳輸代價，并將相應傳輸路徑信息記錄在連接信息鏈表中；} 4.2算法仿真實驗與性能分析4.2.1系統(tǒng)