對分布式數據庫查詢算法的改進與應用研究

楊燕艷

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

對分布式數據庫查詢算法的改進與應用研究

楊燕艷

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

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

分布式數據庫；查詢算法；貪婪算法

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

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

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

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

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

表1 R’∞A=BS結果集

2 分布式數據庫查詢算法的改進分析

2.1 數據庫通信建模

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

圖1 建模查詢

2.2 算法的改進思路

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

2.3 改進算法的提出

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

圖2 A和B的合并結果

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

表2 不同查詢順序的查詢代價

3 分布式數據庫改進查詢算法的應用分析

3.1 數據庫系統(tǒng)分析

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

3.2 改進算法的應用

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

3.3 算法的應用效果

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

表3 不同查詢順序的實驗結果

續(xù)表3

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

表4 原有算法與改進算法的查詢合格率比較

4 結語

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

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

[2]劉曉丹.基于Oracle分布式數據庫的查詢算法改進研究[J].自動化與儀器儀表，2015（11）：164-165.

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

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

[5]楊浩，林喜軍，曲海鵬.分布式網絡下改進的Top-k查詢算法[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— ），女，江蘇南通人，講師，學士；研究方向：數據庫研究。