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

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

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