楊燕艷

（蘇州托普信息職業(yè)技術(shù)學(xué)院，江蘇 蘇州 215311）

對(duì)分布式數(shù)據(jù)庫(kù)查詢算法的改進(jìn)與應(yīng)用研究

楊燕艷

（蘇州托普信息職業(yè)技術(shù)學(xué)院，江蘇 蘇州 215311）

針對(duì)分布式數(shù)據(jù)庫(kù)數(shù)據(jù)查詢難的情況，文章對(duì)分布式數(shù)據(jù)庫(kù)查詢算法原理及優(yōu)化問題展開了分析，然后提出了基于貪婪算法的改進(jìn)查詢算法，并對(duì)算法進(jìn)行了應(yīng)用測(cè)試。從應(yīng)用效果來(lái)看，采用改進(jìn)算法能夠降低數(shù)據(jù)庫(kù)查詢代價(jià)，并保證查詢合格率，因此能夠滿足系統(tǒng)的運(yùn)行需求。

分布式數(shù)據(jù)庫(kù)；查詢算法；貪婪算法

隨著信息技術(shù)的發(fā)展，大數(shù)據(jù)時(shí)代已經(jīng)全面到來(lái)，對(duì)數(shù)據(jù)管理提出了更高的要求。采用分布式數(shù)據(jù)庫(kù)，能利用其強(qiáng)大的數(shù)據(jù)管理功能滿足數(shù)據(jù)存儲(chǔ)和管理的需求。但就目前來(lái)看，分布式數(shù)據(jù)庫(kù)也將受到分布性和冗余性的影響，以至于難以快速實(shí)現(xiàn)數(shù)據(jù)查詢操作。而對(duì)分布式數(shù)據(jù)庫(kù)查詢算法進(jìn)行改進(jìn)，能進(jìn)一步提高數(shù)據(jù)庫(kù)查詢效率，并降低數(shù)據(jù)庫(kù)的傳輸代價(jià)，進(jìn)而使分布式數(shù)據(jù)庫(kù)得到更好的應(yīng)用。

1 分布式數(shù)據(jù)庫(kù)查詢算法原理及優(yōu)化問題

在分布式數(shù)據(jù)庫(kù)查詢方面，得到廣泛應(yīng)用的傳統(tǒng)算法為半連接算法。從算法原理上來(lái)看，就是利用半連接操作減少操作連接關(guān)系數(shù)量，以加強(qiáng)網(wǎng)絡(luò)數(shù)據(jù)傳輸量控制，進(jìn)而實(shí)現(xiàn)查詢優(yōu)化[1]。半連接算法由連接和投影構(gòu)成，需要完成關(guān)系代數(shù)運(yùn)算，先假設(shè)節(jié)點(diǎn)A和B上分別擁有兩個(gè)隨意待連接關(guān)系R和S，然后根據(jù)屬性條件R.A=S.B進(jìn)行半連接操作，可以得到如下公式：

式中，∞指的是連接操作，∝指的是為半連接操作，投影操作用π表示。對(duì)算法的連接過(guò)程進(jìn)行研究時(shí)，可以簡(jiǎn)化傳輸代價(jià)公式，得到T=c0+c1x(c0)。其中，c0指的是兩站點(diǎn)經(jīng)過(guò)初始化得到的一次傳輸代價(jià)，c1代表是傳輸率，x指的是數(shù)據(jù)傳輸量。按照簡(jiǎn)化公式實(shí)現(xiàn)半連接，即R∞A=RS，首先還要先對(duì)節(jié)點(diǎn)B上的關(guān)系S在屬性B上的投影值進(jìn)行計(jì)算，得到πB(S)。在此基礎(chǔ)上，需將計(jì)算結(jié)果由節(jié)點(diǎn)B傳至A，得到傳輸代價(jià)c0+c1×size(B)×val(B[S])。在該表達(dá)式中，size(B)即為屬性B的長(zhǎng)度，val(B[S])為該屬性在S中的數(shù)量。A節(jié)點(diǎn)完成投影值接收后，會(huì)進(jìn)行半連接的計(jì)算，得到R’=R∝S，執(zhí)行R∞πB(S)操作。將得到的結(jié)果從A傳遞至B，將得到傳輸代價(jià)c0+c1×size(R)×card(R’)。在該表達(dá)式中，size(R)即為R的長(zhǎng)度，card(R’)為其元組數(shù)。B在完成結(jié)果接收后，會(huì)執(zhí)行R’∞A=BS操作，得到如表1所示的結(jié)果集。

從算法結(jié)果來(lái)看，最終所有結(jié)果在一個(gè)結(jié)點(diǎn)上得到了集中，以至于無(wú)法對(duì)算法具體應(yīng)用情況進(jìn)行考慮。受這一因素的影響，請(qǐng)求節(jié)點(diǎn)可能與結(jié)果集存放節(jié)點(diǎn)并不相同。如果存在大量結(jié)果集，發(fā)送查詢請(qǐng)求就會(huì)因一些節(jié)點(diǎn)需完成大量數(shù)據(jù)傳輸而出現(xiàn)擁堵問題，而另一些節(jié)點(diǎn)則會(huì)被閑置，進(jìn)而導(dǎo)致負(fù)載不均衡。而分布式數(shù)據(jù)庫(kù)具有數(shù)據(jù)量大和數(shù)據(jù)屬性多的特點(diǎn)，采用傳統(tǒng)半連接算法將無(wú)法完成傳輸代價(jià)的有效縮減，從而導(dǎo)致系統(tǒng)在數(shù)據(jù)傳輸?shù)倪^(guò)程中產(chǎn)生較多數(shù)據(jù)冗余和較大的通信代價(jià)。針對(duì)這一情況，還要對(duì)分布式數(shù)據(jù)庫(kù)查詢算法進(jìn)行改進(jìn)優(yōu)化，以便達(dá)到更好的算法應(yīng)用效果。

表1 R’∞A=BS結(jié)果集

2 分布式數(shù)據(jù)庫(kù)查詢算法的改進(jìn)分析

2.1 數(shù)據(jù)庫(kù)通信建模

在分布式數(shù)據(jù)庫(kù)查詢的過(guò)程中，查詢操作執(zhí)行所消耗的代價(jià)由數(shù)據(jù)處理代價(jià)、通信代價(jià)和存儲(chǔ)器訪問代價(jià)構(gòu)成。由于分布式數(shù)據(jù)庫(kù)的網(wǎng)絡(luò)節(jié)點(diǎn)較多，所以相較于其他代價(jià)，分布式數(shù)據(jù)庫(kù)的通信代價(jià)更高，因此主要還要完成通信建模分析[2]。為簡(jiǎn)化問題的分析，可以對(duì)剩余兩種代價(jià)進(jìn)行忽略。假設(shè)在分布式數(shù)據(jù)庫(kù)中，存在有A，B，C，D 4個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，各自擁有10，5，20，15的數(shù)據(jù)量，彼此間拓?fù)潢P(guān)系和通信距離如圖1所示。在數(shù)據(jù)傳輸?shù)倪^(guò)程中，延遲和費(fèi)用都會(huì)對(duì)通信產(chǎn)生影響。而在對(duì)通信整個(gè)傳輸開銷進(jìn)行衡量時(shí)，利用費(fèi)用得到開銷最小，傳輸數(shù)據(jù)量也最小，因此費(fèi)用將起到至關(guān)重要的作用。結(jié)合這些特點(diǎn)，可以得到CCOM(x)=c0+c1×x的模型，其中c0為數(shù)據(jù)傳輸一次需要的固定費(fèi)用，即啟動(dòng)代價(jià)，c1指的是單位傳輸數(shù)據(jù)費(fèi)，可稱之為單位傳輸代價(jià)，x依然為數(shù)據(jù)傳輸量。

圖1 建模查詢

2.2 算法的改進(jìn)思路

針對(duì)分布式數(shù)據(jù)庫(kù)的查詢問題，可以引入貪婪算法實(shí)現(xiàn)對(duì)傳統(tǒng)半連接算法的改進(jìn)。所謂的貪婪算法，又被稱之為貪心算法，就是在問題求解的過(guò)程中，先進(jìn)行當(dāng)前最好選擇，從而得到局部最優(yōu)解。而通過(guò)選擇一系列局部最優(yōu)解，就可以通過(guò)貪婪選擇得到問題的整體最優(yōu)解。所以采用貪婪算法，需要以迭代方式進(jìn)行選擇，每次選擇都要將問題簡(jiǎn)化為規(guī)模小的子問題，然后通過(guò)求解子問題的最優(yōu)解確定問題最優(yōu)子結(jié)構(gòu)[3]。采用該算法實(shí)現(xiàn)分布式數(shù)據(jù)庫(kù)查詢連接算法改進(jìn)，可以根據(jù)要求完成相應(yīng)度量法則的選取，從而實(shí)現(xiàn)對(duì)分級(jí)事件處理方法的優(yōu)化，按照順利實(shí)現(xiàn)多輸入。如果輸入無(wú)法與部分最優(yōu)解融合得到可行解，則可以將該輸入舍去，所以能夠完成最優(yōu)的依次分級(jí)處理。在連接查詢數(shù)據(jù)庫(kù)的過(guò)程中，采用該算法可以利用中間查詢反饋結(jié)果值進(jìn)行消耗通信代價(jià)的虛擬表示，然后在不同數(shù)據(jù)節(jié)點(diǎn)連接查詢時(shí)完成消耗代價(jià)最小的中間結(jié)果查找，并通過(guò)合并結(jié)果降低系統(tǒng)查詢代價(jià)。采用貪婪算法實(shí)現(xiàn)原有數(shù)據(jù)查詢算法改進(jìn)，其實(shí)是先利用靜態(tài)優(yōu)化方法完成結(jié)果執(zhí)行，以免系統(tǒng)通信開銷過(guò)大[4]。在此基礎(chǔ)上，則可以通過(guò)計(jì)算數(shù)據(jù)統(tǒng)計(jì)結(jié)果與實(shí)際偏差完成動(dòng)態(tài)規(guī)劃方案的調(diào)用，即利用啟發(fā)式規(guī)則完成各種查詢方案的篩選，然后根據(jù)消耗代價(jià)完成最優(yōu)方案的選擇。

2.3 改進(jìn)算法的提出

按照上述思路，可以得到改進(jìn)的查詢算法。首先，在連接相鄰數(shù)據(jù)服務(wù)器節(jié)點(diǎn)時(shí)，可先進(jìn)行連接消耗代價(jià)最小的連接運(yùn)算查找，即逐次完成相鄰節(jié)點(diǎn)連接查詢代價(jià)計(jì)算。按照C節(jié)點(diǎn)∞相鄰節(jié)點(diǎn)=關(guān)系節(jié)點(diǎn)數(shù)據(jù)量×相鄰關(guān)系節(jié)點(diǎn)數(shù)據(jù)量×通信距離的計(jì)算公式，則能得到CA∞B=10×5×0.2=10，CB∞C=5×20×0.5=50，CC∞D(zhuǎn)=20×5×0.4=120，CD∞A=15×10×0.6=90。通過(guò)計(jì)算，可以發(fā)現(xiàn)A和B兩個(gè)節(jié)點(diǎn)連接消耗的通信代價(jià)最小。對(duì)這兩個(gè)節(jié)點(diǎn)進(jìn)行合并，則能得到如圖2所示的結(jié)果。

圖2 A和B的合并結(jié)果

完成A B合并之后，可以按照上述步驟進(jìn)行再次計(jì)算，以得到最小的查詢代價(jià)。具體來(lái)講，就是得到CAB∞C=10×20×0.5=100，CD∞AB=15×10×0.6=90，CC∞D(zhuǎn)=20×5×0.4=120。由計(jì)算結(jié)果可知，需要對(duì)AB和D進(jìn)行合并。最后，對(duì)ABD和C進(jìn)行合并，則能得到CABD∞C=90×20×0.5=900。最后，在對(duì)整個(gè)分布式系統(tǒng)進(jìn)行查詢時(shí)，需要消耗的通信代價(jià)應(yīng)該為CA∞B+CD∞AB+CABD∞C=1 000。由此，可以得到(((A∞B)∞D(zhuǎn))∞C)的查詢順序，從而實(shí)現(xiàn)對(duì)查詢的優(yōu)化處理。采用不同查詢順序所消耗的查詢代價(jià)如表2所示。通過(guò)對(duì)比可以發(fā)現(xiàn)，采取不同的查詢順序，最后一步都將消耗1 000的通信代價(jià)，但是中間消耗的查詢代價(jià)并不相同。而采用得到的最優(yōu)查詢順序，消耗的代價(jià)總共為1 100，比其他查詢順序都小。

表2 不同查詢順序的查詢代價(jià)

3 分布式數(shù)據(jù)庫(kù)改進(jìn)查詢算法的應(yīng)用分析

3.1 數(shù)據(jù)庫(kù)系統(tǒng)分析

為驗(yàn)證提出的改進(jìn)算法的應(yīng)用效果，還要以新農(nóng)合分布式數(shù)據(jù)庫(kù)的查詢?yōu)槔?。該?shù)據(jù)庫(kù)為數(shù)據(jù)庫(kù)管理系統(tǒng)（Data Base Management System，DBMS），利用不通網(wǎng)絡(luò)服務(wù)器進(jìn)行數(shù)據(jù)分散，所以各服務(wù)器相當(dāng)于系統(tǒng)數(shù)據(jù)子集，即包含門診數(shù)據(jù)、藥品數(shù)據(jù)等數(shù)據(jù)分別存儲(chǔ)在各省縣的醫(yī)療衛(wèi)生服務(wù)部門服務(wù)器中[5]。在對(duì)該數(shù)據(jù)庫(kù)進(jìn)行查詢時(shí)，需完成多部門節(jié)點(diǎn)數(shù)據(jù)的協(xié)同處理，所以節(jié)點(diǎn)負(fù)荷較大，需要利用優(yōu)化查詢算法減少系統(tǒng)額外通信開銷，進(jìn)而使數(shù)據(jù)庫(kù)系統(tǒng)保持流暢運(yùn)行。而各服務(wù)器都采用了統(tǒng)一操作系統(tǒng)，即Windows 2003 Server，系統(tǒng)中央處理機(jī)（Central Processing Unit，CPU）的內(nèi)存為4 GB，主頻2.4 GHz。在數(shù)據(jù)庫(kù)管理上，均采用SQLServer2005。

3.2 改進(jìn)算法的應(yīng)用

在算法測(cè)試的過(guò)程中，將農(nóng)民參保信息數(shù)據(jù)庫(kù)服務(wù)器設(shè)定為A節(jié)點(diǎn)，其中共包含100 000條元組，由農(nóng)保編號(hào)、出生年月等參保信息構(gòu)成。其次，需要將醫(yī)院信息系統(tǒng)（Hospital Information System，HIS）數(shù)據(jù)庫(kù)服務(wù)器設(shè)定為B節(jié)點(diǎn)，其中包含50 000條元組，由農(nóng)保編號(hào)、出生年月等門診住院信息構(gòu)成。再者，需要將衛(wèi)生部門數(shù)據(jù)庫(kù)服務(wù)器設(shè)定為C節(jié)點(diǎn)，其中包含200 000條元組，由農(nóng)保編號(hào)、出生年月等新農(nóng)合數(shù)據(jù)統(tǒng)計(jì)信息構(gòu)成。最后，需要將負(fù)責(zé)新農(nóng)合報(bào)銷的保險(xiǎn)公司數(shù)據(jù)庫(kù)服務(wù)器設(shè)定為D節(jié)點(diǎn)，其中包含150 000條元組，由農(nóng)保編號(hào)、出生年月等報(bào)銷記錄數(shù)據(jù)構(gòu)成。此外，在應(yīng)用改進(jìn)算法進(jìn)行數(shù)據(jù)庫(kù)查詢優(yōu)化時(shí)，還要弄清楚各節(jié)點(diǎn)間的通信距離。具體來(lái)講，就是要根據(jù)各服務(wù)器間通信傳輸距離完成各節(jié)點(diǎn)通信距離設(shè)定，即A與B節(jié)點(diǎn)距離設(shè)置為20，B與C節(jié)點(diǎn)距離設(shè)置為50，C與D節(jié)點(diǎn)距離設(shè)置為40，A與D節(jié)點(diǎn)距離設(shè)置為60。明確各節(jié)點(diǎn)關(guān)系后，則可以按照提出的改進(jìn)連接算法進(jìn)行數(shù)據(jù)查詢連接。

3.3 算法的應(yīng)用效果

采用不同連接順序的實(shí)驗(yàn)結(jié)果如表3所示。由結(jié)果可知，采用之前得到的最優(yōu)連接方法，能夠有效節(jié)省信息查詢時(shí)間，能夠使系統(tǒng)在最短時(shí)間內(nèi)響應(yīng)用戶的數(shù)據(jù)查詢操作。而消耗的時(shí)間代價(jià)較少，也意味著系統(tǒng)能夠更多地完成數(shù)據(jù)處理任務(wù)，盡量做到即時(shí)結(jié)算報(bào)銷，因此能夠滿足新農(nóng)合數(shù)據(jù)庫(kù)系統(tǒng)對(duì)數(shù)據(jù)查詢的實(shí)時(shí)性要求。

表3 不同查詢順序的實(shí)驗(yàn)結(jié)果

續(xù)表3

值得注意的是，在驗(yàn)證改進(jìn)算法應(yīng)用效果時(shí)，還要認(rèn)識(shí)到無(wú)論采用哪種算法都會(huì)不可避免地出現(xiàn)結(jié)果不為最優(yōu)的情況。所以，還要對(duì)比原有算法與改進(jìn)算法得到較優(yōu)解的合格率，以確保數(shù)據(jù)查詢結(jié)果的正確性。為此，還要進(jìn)行6組數(shù)據(jù)的查詢，每組數(shù)據(jù)查詢次數(shù)為100次，然后進(jìn)行合格率的統(tǒng)計(jì)。而只要查詢代價(jià)與最優(yōu)代價(jià)差值不超過(guò)設(shè)定范圍，可以認(rèn)為查詢結(jié)果合格。原算法與改進(jìn)算法的查詢合格率比較結(jié)果如表4所示。由結(jié)果可知，相較于原來(lái)的算法，使用改進(jìn)算法能夠獲得更高的數(shù)據(jù)查詢合格率。而隨著數(shù)據(jù)關(guān)系數(shù)量的逐漸增多，無(wú)論是原有算法還是改進(jìn)算法的查詢合格率呈現(xiàn)出下降趨勢(shì)。但相較于原有算法，改進(jìn)算法的查詢合格率一直維持在80%以上。由此可以認(rèn)為，改進(jìn)算法比原來(lái)算法有更高的穩(wěn)定性。

表4 原有算法與改進(jìn)算法的查詢合格率比較

4 結(jié)語(yǔ)

通過(guò)研究可以發(fā)現(xiàn)，在分布式數(shù)據(jù)庫(kù)查詢方面，由于數(shù)據(jù)庫(kù)查詢需要完成大量數(shù)據(jù)傳輸，所以采用傳統(tǒng)半連接算法難以完成通信代價(jià)的縮減，將導(dǎo)致系統(tǒng)無(wú)法及時(shí)響應(yīng)用戶操作。而利用貪婪算法對(duì)原有算法進(jìn)行改進(jìn)，則能通過(guò)查找數(shù)據(jù)查詢的最優(yōu)順序簡(jiǎn)化查詢過(guò)程，從而在降低系統(tǒng)通信代價(jià)的同時(shí)，獲得更高的查詢合格率。因此，該種算法能夠在分布式數(shù)據(jù)庫(kù)查詢中得到較好的應(yīng)用，以滿足數(shù)據(jù)庫(kù)系統(tǒng)的數(shù)據(jù)檢索要求，使系統(tǒng)工作效率得到進(jìn)一步提高。

[1]吳洋，溫佩芝，鄧星，等.一種改進(jìn)的分布式數(shù)據(jù)庫(kù)查詢優(yōu)化遺傳算法[J].桂林電子科技大學(xué)學(xué)報(bào)，2015（3）：217-221.

[2]劉曉丹.基于Oracle分布式數(shù)據(jù)庫(kù)的查詢算法改進(jìn)研究[J].自動(dòng)化與儀器儀表，2015（11）：164-165.

[3]于洪濤，錢磊.一種改進(jìn)的分布式查詢優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用，2013（8）：151-155.

[4]李川.應(yīng)用半連接的分布式數(shù)據(jù)庫(kù)查詢優(yōu)化算法[J].重慶理工大學(xué)學(xué)報(bào)，2013（11）：74-77.

[5]楊浩，林喜軍，曲海鵬.分布式網(wǎng)絡(luò)下改進(jìn)的Top-k查詢算法[J].計(jì)算機(jī)工程，2017（2）：79-84.

Research on the improvement and application of query algorithm in distributed database

Yang Yanyan
(Suzhou Top Institute of Information Technology, Suzhou 215311, China)

In view of the difficult situation of data query in distributed database, this paper analyzes the principle and optimization of distributed database query algorithm, and then proposes an improved query algorithm based on greedy algorithm, and applied the test to the algorithm. From the application effect, the improved algorithm can query the cost of low database and ensure the query pass rate, so it can meet the system operation requirements.

distributed database; query algorithm; greedy algorithm

楊燕艷（1981— ），女，江蘇南通人，講師，學(xué)士；研究方向：數(shù)據(jù)庫(kù)研究。