[發(fā)明專利]一種基于進化算法的數(shù)據(jù)庫多連接查詢優(yōu)化方法

在審

• 申請?zhí)枺?/td>: 201710700285.3
• 申請日: 2017-08-16
• 公開（公告）號: CN107463702A
• 公開（公告）日: 2017-12-12
• 發(fā)明（設(shè)計）人: 孫治;秦小林;張力戈;王文彬;王會勇
• 申請（專利權(quán)）人: 中科院成都信息技術(shù)股份有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 成都九鼎天元知識產(chǎn)權(quán)代理有限公司51214
• 代理人: 鄧世燕

技術(shù)領(lǐng)域

本發(fā)明屬于計算機信息技術(shù)應(yīng)用領(lǐng)域，具體涉及分布式數(shù)據(jù)庫的連接執(zhí)行策略的優(yōu)化，可用于優(yōu)化分布式數(shù)據(jù)庫的連接執(zhí)行策略，減少大規(guī)模多連接查詢的執(zhí)行時間。

背景技術(shù)

隨著傳統(tǒng)的數(shù)據(jù)庫技術(shù)日趨成熟、計算機網(wǎng)絡(luò)技術(shù)的飛速發(fā)展和應(yīng)用范圍的擴大，以分布式為主要特征的數(shù)據(jù)庫系統(tǒng)的研究與開發(fā)受到人們的高度關(guān)注。而多關(guān)系連接查詢作為分布式數(shù)據(jù)庫中的重要操作，是查詢優(yōu)化中需要突破的一個難點。分布式查詢處理具有能夠通過通信網(wǎng)絡(luò)存取遠程站點的數(shù)據(jù),以及在不同站點間傳輸請求和數(shù)據(jù)的能力。分布式查詢優(yōu)化的準則是使通信費用最低和響應(yīng)時間最短,即以最小的總代價,在最短的響應(yīng)時間內(nèi)獲得需要的數(shù)據(jù)。為了執(zhí)行全局查詢和確定一個好的查詢策略，首先需進行查詢分解，然后再確定操作執(zhí)行的次序，最后確定操作的執(zhí)行方法，其中關(guān)鍵是確定操作執(zhí)行的次序，即主要是確定連接操作的順序。

SDD-1算法是一種在傳統(tǒng)分布式關(guān)系型數(shù)據(jù)庫中廣泛應(yīng)用的查詢方法。在查詢涉及到的關(guān)系數(shù)較少時,該算法在查詢計劃的生成時間和查詢的通信費用方面都有著其它算法無法比擬的優(yōu)越性。但是由于SDD-1算法本身的局限性,在求解最優(yōu)查詢計劃時,它容易陷入局部最優(yōu)解。而涉及到的關(guān)系數(shù)目增多時,其生成查詢計劃的時間會迅速上升,甚至有可能超出系統(tǒng)的承受能力。遺傳算法和蟻群算法都是啟發(fā)式尋優(yōu)方法，常被應(yīng)用到解決各種優(yōu)化問題。在搜索最優(yōu)解的過程中，遺傳算法的前期搜索速度快且可潛在并行，具有較強的全局搜索能力。而蟻群算法后期搜索速度快且充分使用了信息的正反饋，具有較強的局部搜索能力。

因此，針對以上問題，有必要提出一種新的基于進化計算的優(yōu)化方法，解決SDD-1算法在生成查詢計劃時容易陷入局部最優(yōu)解的缺陷,顯著降低查詢計劃的生成時間，提高連接查詢的查詢效率。該方法將并行遺傳算法和多蟻群算法進行了融合。在普通蟻群基礎(chǔ)上引入多蟻群概念，降低算法陷入局部最優(yōu)的概率，提高算法尋優(yōu)的能力利用并行遺傳算法來突破多蟻群算法前期搜索的盲目，并結(jié)合多蟻群算法的優(yōu)秀尋優(yōu)能力，最終達到提高查詢效率的目的。

發(fā)明內(nèi)容

為了克服現(xiàn)有技術(shù)的上述缺點，本發(fā)明提供了一種基于進化算法的數(shù)據(jù)庫多連接查詢優(yōu)化方法，通過并行遺傳算法的全局搜索能力和多蟻群算法的局部搜索能力，對SDD-1算法容易陷入局部最優(yōu)解的問題進行了優(yōu)化，輸出了規(guī)約最優(yōu)的查詢執(zhí)行策略，最終達到提高查詢效率的目的。

本發(fā)明解決其技術(shù)問題所采用的技術(shù)方案是：一種基于進化算法的數(shù)據(jù)庫多連接查詢優(yōu)化方法，包括如下步驟：

步驟一、對原始數(shù)據(jù)進行預(yù)處理，構(gòu)建出查詢圖G；

步驟二、獲取有益雙向半連接集合BS；

步驟三、構(gòu)建并行遺傳算法的初始種群；

步驟四、執(zhí)行并行遺傳算法，得到規(guī)約最優(yōu)查詢路徑；

步驟五、構(gòu)建多個蟻群的初始種群；

步驟六、執(zhí)行多蟻群算法；

步驟七、輸出最終的查詢執(zhí)行策略。

與現(xiàn)有技術(shù)相比，本發(fā)明的積極效果是：

本發(fā)明首先將數(shù)據(jù)預(yù)處理和雙向半連接兩種技術(shù)引入到SDD-1算法中，采用投影等一元操作精簡數(shù)據(jù)，同時還對各節(jié)點的數(shù)據(jù)進行了歸并排序，而雙向半連接技術(shù)可以對行和列的數(shù)據(jù)同時進行縮減。然后計算出全部有益雙向半連接加入到集合BS中，采用并行遺傳算法求解SDD-1算法的連接查詢策略，構(gòu)造了適用于該問題的群體初始化方法、適應(yīng)度函數(shù)和相關(guān)遺傳算子，得到了求解該問題的規(guī)約最優(yōu)查詢路徑。最后用該查詢路徑對蟻群算法的信息素矩陣進行初始化，利用多蟻群優(yōu)化方法再次求出最優(yōu)查詢路徑，解決了并行遺傳算法局部搜索能力弱的問題。

本發(fā)明充分考慮了數(shù)據(jù)連接查詢時需進行的數(shù)據(jù)傳輸和歸并排序操作的特性，采用雙半連接技術(shù)和數(shù)據(jù)歸并排序預(yù)處理技術(shù)，進而加快查詢處理速度。傳統(tǒng)的SDD-1算法采用爬山法尋找最優(yōu)查詢執(zhí)行策略，存在兩點不足：容易陷入局部最優(yōu)和查詢計劃生成時間隨著關(guān)系數(shù)目成指數(shù)增長。針對上述不足，本發(fā)明將并行遺傳算法和多蟻群算法進行了融合。并行遺傳算法具有較好的全局搜索能力，并行執(zhí)行可以大大縮短搜索時間。多蟻群算法可以降低算法陷入局部最優(yōu)的概率，提高算法尋優(yōu)的能力利用并行遺傳算法來突破多蟻群算法前期搜索的盲目，并結(jié)合多蟻群算法的優(yōu)秀尋優(yōu)能力，最終達到提高查詢效率的目的。該多連接查詢優(yōu)化方法在實際應(yīng)用中可以制定出更優(yōu)的查詢執(zhí)行策略，從而減少多表連接時的查詢響應(yīng)時間。

附圖說明

本發(fā)明將通過例子并參照附圖的方式說明，其中：

圖1為本發(fā)明方法的流程圖。

具體實施方式