嵌入式移動(dòng)實(shí)時(shí)數(shù)據(jù)庫(kù)中一種基于代價(jià)模型的查詢優(yōu)化技術(shù)_第1頁(yè)
嵌入式移動(dòng)實(shí)時(shí)數(shù)據(jù)庫(kù)中一種基于代價(jià)模型的查詢優(yōu)化技術(shù)_第2頁(yè)
嵌入式移動(dòng)實(shí)時(shí)數(shù)據(jù)庫(kù)中一種基于代價(jià)模型的查詢優(yōu)化技術(shù)_第3頁(yè)
嵌入式移動(dòng)實(shí)時(shí)數(shù)據(jù)庫(kù)中一種基于代價(jià)模型的查詢優(yōu)化技術(shù)_第4頁(yè)
嵌入式移動(dòng)實(shí)時(shí)數(shù)據(jù)庫(kù)中一種基于代價(jià)模型的查詢優(yōu)化技術(shù)_第5頁(yè)
已閱讀5頁(yè),還剩58頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論