分布式數(shù)據(jù)庫查詢優(yōu)化研究

分布式數(shù)據(jù)庫查詢優(yōu)化研究

分布式數(shù)據(jù)庫（ddb）是數(shù)據(jù)庫技術(shù)與網(wǎng)絡(luò)技術(shù)相結(jié)合的產(chǎn)物。該數(shù)據(jù)庫領(lǐng)域有一個分支機(jī)構(gòu)。這項研究始于20世紀(jì)70年代中期。這是一個物理上分散邏輯集中的數(shù)據(jù)庫。該系統(tǒng)的數(shù)據(jù)分布存儲在計算機(jī)網(wǎng)絡(luò)不同位置的計算機(jī)上。每個位置都有獨(dú)立處理能力（即獨(dú)立處理），可以完成本地應(yīng)用，每個區(qū)域也參與全局應(yīng)用（至少之一）。整個節(jié)目由網(wǎng)絡(luò)系統(tǒng)執(zhí)行。在一個分布的數(shù)據(jù)庫中，整個模型有幾個全局關(guān)系。根據(jù)每個全局關(guān)系，它們被劃分為多個邏輯段（一對一或多個）。每個邏輯段根據(jù)余項策略將其分配給物理段。如果是空的，則是空的，如果不是空的，則是空的。形成三個數(shù)據(jù)庫：全球數(shù)據(jù)庫sdb、邏輯數(shù)據(jù)庫lb和物理數(shù)據(jù)庫pdb。兩種模式：分段模式fs和分配模式as。如何提高查詢效率是查詢優(yōu)化的問題,目前分布式查詢優(yōu)化器是基于代價模型,它假設(shè)各節(jié)點(diǎn)是同構(gòu)的并且節(jié)點(diǎn)工作負(fù)載是靜態(tài)的,在查詢的執(zhí)行過程中,系統(tǒng)參數(shù)(如CPU、內(nèi)存、網(wǎng)絡(luò)負(fù)載等等)保持不變,即根據(jù)數(shù)據(jù)庫的統(tǒng)計模型作出靜態(tài)估計.分布式查詢的代價因素分為兩種,一種是I/O操作代價和CPU的使用,這也是集中式數(shù)據(jù)庫所具有的代價,另一種則是分布式數(shù)據(jù)庫查詢所特有的,即網(wǎng)絡(luò)上不同計算機(jī)之間數(shù)據(jù)的傳輸代價,或稱通信代價.一般情況下,分布式查詢處理一般可分為4個階段:1)查詢分解.將查詢問題轉(zhuǎn)換成一個定義在全局關(guān)系上的關(guān)系代數(shù)表達(dá)式,進(jìn)行規(guī)范化、分析、刪除冗余并重寫.2)數(shù)據(jù)本地化.將在全局關(guān)系上的關(guān)系代數(shù)式轉(zhuǎn)換到相應(yīng)段上的關(guān)系表達(dá)式,產(chǎn)生查詢樹.3)全局優(yōu)化.利用優(yōu)化算法對查詢樹進(jìn)行全局優(yōu)化.4)局部優(yōu)化.在組裝場地進(jìn)行本地優(yōu)化.相對于集中式數(shù)據(jù)庫來說,分布式查詢優(yōu)化的總代價除了CPU代價和I/O代價之外,還應(yīng)考慮包括數(shù)據(jù)在網(wǎng)絡(luò)上的傳輸代價.即:總代價=CPU代價+I/O代價+通信代價.對于分布式數(shù)據(jù)庫中數(shù)據(jù)傳輸代價應(yīng)區(qū)別不同情況加以考慮.在遠(yuǎn)程通信網(wǎng)或數(shù)據(jù)傳輸率較低的系統(tǒng)中,通信代價可能會比查詢執(zhí)行中的I/O及CPU開銷大得多,因而作為首要的優(yōu)化目標(biāo)來考慮.在局域網(wǎng)且傳輸率高的系統(tǒng)中,通信代價和局部處理的開銷差不多,此時就應(yīng)在優(yōu)化中將它們平等對待.1基于agent的分布式查詢系統(tǒng)Agent最早出現(xiàn)在人工智能研究的領(lǐng)域,但目前在分布式系統(tǒng)、軟件工程及通信等領(lǐng)域同樣得到了廣泛的應(yīng)用,取得了一系列的成果,并被賦予不同的涵義.多Agent(MAS)系統(tǒng)是由多個Agent組成的集合,Agent之間以及Agent與環(huán)境之間,通過通信、協(xié)商與協(xié)作來共同完成單個Agent所不能解決的問題.多Agent系統(tǒng)的研究領(lǐng)域包括許多方面,比如系統(tǒng)的組織結(jié)構(gòu)、Agent間的通信、Agent間的協(xié)商與協(xié)作、Agent系統(tǒng)中的機(jī)器學(xué)習(xí)、Agent系統(tǒng)的動態(tài)特性等.這些方面與多Agent系統(tǒng)的性能直接相關(guān).在基于Agent的分布式查詢系統(tǒng)中,每個節(jié)點(diǎn)都可以包裝成一個智能Agent,各個節(jié)點(diǎn)之間通過協(xié)調(diào)、協(xié)作以及協(xié)商來達(dá)各自的目標(biāo)和平衡工作負(fù)載,有效地完成查詢?nèi)蝿?wù).2基于代理技術(shù)的分布式咨詢系統(tǒng)的設(shè)計2.1ent模型架構(gòu)基于Agent的查詢MAS(QueryBasedonMulti-AgentSystem,QMAS),見圖1所示采用多Agent技術(shù),其中的各Agent既有思考型、反應(yīng)性,也有混合型結(jié)構(gòu).QMAS包括以下Agent組和Agent:1)查詢監(jiān)測組(QueryDetectGroup),成員有:①查詢接收Agent(QueryReceive-Agent);②特征獲取Agent(FeaturesGet-Agent);③知識形成Agent(KnowledgeShape-Agent).2)內(nèi)核組(KernelGroup),成員有:④任務(wù)規(guī)劃Agent(TaskPlan-Agent);⑤任務(wù)管理Agent(TaskManage-Agent).3)知識庫組和規(guī)則集組(KDB&RuleSetGroup),成員有:⑥知識庫Agent(KDB-Agent);⑦規(guī)則集Agent(RuleSet-Agent).4)輸出組(ExportGroup),成員有:⑧優(yōu)化輸出Agent(OptimizationExport-Agent);⑨命名服務(wù)Agent(NameServer-Agent);⑩輔助通信Agent(AssCommu-Agent,如GGA,MASGA).系統(tǒng)內(nèi)核(systemkernel)主要包括處理器與知識庫和行為規(guī)則集,一般由知識系統(tǒng)、問題求解程序、知識描述知識(元知識)、系統(tǒng)狀態(tài)知識組成,反映Agent對內(nèi)部問題和領(lǐng)域問題的處理能力.從知識庫和行為規(guī)則集的構(gòu)成和在系統(tǒng)中實(shí)際所起的效用上來說,圖中Agent結(jié)構(gòu)表現(xiàn)出了一種思考型結(jié)構(gòu)所具有的特征,它具有較復(fù)雜的推理、問題求解功能.2.2多agent通信設(shè)計本QMAS系統(tǒng)由4個不同的GROUP(即查詢監(jiān)測Group、內(nèi)核Group、知識庫和行為規(guī)則集Group、輸出Group)組成,其中每個GROUP在所屬的MAS里是被唯一標(biāo)識的,每個GROUP中包含至少一個Agent,而每個Agent在所屬的MAS內(nèi)也是被唯一標(biāo)識的.本MAS系統(tǒng)采用人工智能領(lǐng)域中經(jīng)典模型——黑板模型結(jié)構(gòu)(blackboardarchitecture,BBA)描述多Agent系統(tǒng)之間的通信方法.本系統(tǒng)需要解決如下3類通信:1)GROUP內(nèi)的單播、多播和廣播通信;2)不同GROUP間的單播、組播、廣播和選播通信;3)單個Agent向MAS的廣播.2.2.1元模型簡介下面給出這些Agent的詳細(xì)說明:黑板模型結(jié)構(gòu)是Agent通信模型的基礎(chǔ),它可以為Agent通信模型提供Agent的并發(fā)控制、Agent的交互、Agent的實(shí)時控制等服務(wù),黑板模型結(jié)構(gòu)中不同知識源改換為Agent,并且加入1個單元(組)門戶Agent(GroupGatewayAgent,GGA),可得到Agent通信單元模型(CU),如圖2所示:同一個組內(nèi)各Agent間發(fā)送消息的通信原語為:Send_Message(Sender,Receiver,Message)1)當(dāng)Agent進(jìn)行單播通信時,通信原語為:Send_Mesaage(AgentA1,AgentA2,Message).2)當(dāng)Agent進(jìn)行多播通信時,通信原語為:Send_Message(AgentA1,Multicast(A),Message),其中,Multicast(A)={A2,A3,…,Ak},Ai(i=1,2,…,k)為該通信單元內(nèi)除了發(fā)送Agent外任意的其他Agent;3)當(dāng)Agent進(jìn)行廣播通信時,通信原語為:Send_Message(AgentAl,Group(default),Message),其中,Group(default)為發(fā)送Agent所在通信單元.可見,同一個組內(nèi)Agent間發(fā)送消息的通信原語實(shí)現(xiàn)了在通信單元(組)內(nèi)部的單播、組播以及廣播通信.由于處于相同通信單元內(nèi)的Agent實(shí)現(xiàn)的功能相似,所以可不必實(shí)現(xiàn)通信單元內(nèi)的選播通信,當(dāng)不同通信單元進(jìn)行通信時,就有必要實(shí)現(xiàn)選播通信.2.2.2mas的agent本系統(tǒng)構(gòu)造了一個樹形拓?fù)涞亩郃gent系統(tǒng)(TreeTopologyMulti-AgentSystem,TTMAS).TTMAS通信模型如圖3所示.可見,整個通信模型呈樹狀拓?fù)浣Y(jié)構(gòu),TTMAS中根節(jié)點(diǎn)是命名服務(wù)Agent(NameServer-Agent).該Agent擁有一個全局性的共享知識交換區(qū),負(fù)責(zé)MAS全局的系統(tǒng)服務(wù),管理MAS的Agent注冊表中所有Agent的信息(包括組標(biāo)識、Agent標(biāo)識、提供的服務(wù)、MAS標(biāo)識等),與Agent命名服務(wù)器水平直接相連的Agent為MAS門戶Agent(MASGatewayAgent,MGA),它為不同MAS間的通信起紐帶作用.系統(tǒng)的不同組中各Agent間發(fā)送消息的通信原語為:Send_Message(Sender,Receiver,Message)1)當(dāng)不同組間Agent進(jìn)行單播通信時,通信原語為:Send_Message(AgentAl,Group(B):AgentAl,Message)2)當(dāng)不同組間Agent進(jìn)行多播通信時,通信原語為:Send_Message(AgentAl,Multicast(B),Message)3)當(dāng)Agent進(jìn)行不同組間的廣播通信時,通信原語為:Send_Message(AgentAl,Group(B),Message)4)當(dāng)Agent進(jìn)行選播通信時,通信原語為Send_Message(AgentAl,Group(B):Any,Message)4網(wǎng)絡(luò)優(yōu)化測試依據(jù)以上分布式數(shù)據(jù)庫的查詢優(yōu)化QMAS模型,我們做了如下的模擬測試,基本硬件、軟件環(huán)境如下:主機(jī):Pentium4/主頻2GHz/內(nèi)存1GB,操作系統(tǒng):RedHatLinux企業(yè)版5,數(shù)據(jù)庫:Oracle10g,4個主機(jī)分布在武漢(LDB1),南京(LDB2),北京(LDB3),廣州(LDB4),假定4個LDB都沒有冗余數(shù)據(jù),測試時間在凌晨5:00(網(wǎng)絡(luò)較寬松)和晚19:30(網(wǎng)絡(luò)較擁擠),武昌-南京706公里,武昌-廣州1069公里,武昌-北京1225公里.結(jié)果如表1所示.依據(jù)表1做出圖4.可以看出,1)對本地查詢,本模型沒有效率;2)在網(wǎng)絡(luò)較擁擠時