基于改進免疫遺傳算法的索引數(shù)據(jù)庫查詢優(yōu)化方法

徐千淞 陳怡 陳云選 張劉玲

【摘要】? ? 查詢優(yōu)化是提高索引數(shù)據(jù)庫性能的關鍵技術，針對索引數(shù)據(jù)庫查詢優(yōu)化效率低的難題，提出了一種改進免疫遺傳算法的數(shù)據(jù)庫查詢優(yōu)化算法。首先借助免疫算法提高遺傳算法的整體性能，解決遺傳過程中會出現(xiàn)退化和求解過程中對特征信息利用不夠的現(xiàn)象。然后考慮群體中具有相似特性的個體容易聚集的現(xiàn)象，將遺傳算法中的交叉操作變?yōu)樽赃m應交叉概率操作。結果表明，本文提出的算法是解決數(shù)據(jù)庫查詢優(yōu)化的有效途徑，能夠獲得理想的數(shù)據(jù)庫查詢結果，具有實際意義。

【關鍵詞】? ? 索引數(shù)據(jù)庫? ? 查詢優(yōu)化? ? 免疫遺傳算法

一、引言

在許多基于數(shù)據(jù)庫的應用中，數(shù)據(jù)庫的查詢響應時間己經(jīng)成為影響整個數(shù)據(jù)庫系統(tǒng)性能的關鍵性限制因素。研究數(shù)據(jù)庫系統(tǒng)的學者們普遍認為數(shù)據(jù)庫查詢效率的目標是：以最快的時間響應用戶的查詢并且在此基礎上控制最少的網(wǎng)絡通信費用。在多連結查詢中，一個查詢隨著連結的關系數(shù)的增加該查詢的執(zhí)行計劃的個數(shù)呈現(xiàn)指數(shù)級的增長，導致查詢優(yōu)化的計算非常復雜。

在之前學者們的研究中，為了優(yōu)化查詢效率，已經(jīng)提出了模擬退火算法、遺傳算法、SSD-1算法等的思想。其中遺傳算法因其效果顯著而被廣泛應用于數(shù)據(jù)庫查詢優(yōu)化中。Kristin Bemmett等人定義了交叉和變異算子并提出一種基于遺傳算法的數(shù)據(jù)庫查詢優(yōu)化的方法[1]。接著SangkyuPho等人又提出了一種新的編碼方法，方法定義了基于遺傳算法查詢優(yōu)化的執(zhí)行步驟和代價函數(shù)的計算方法[2]。國內對基于遺傳算法在數(shù)據(jù)庫查詢優(yōu)化的研究相對較晚。周瑩等人提出了基于多蟻群遺傳算法的數(shù)據(jù)庫查詢優(yōu)化研究[3]，林基明、班文嬌等提出了基于并行遺傳-最大最小蟻群算法的數(shù)據(jù)庫查詢優(yōu)化[4]。都使用遺傳算法對數(shù)據(jù)庫查詢進行了一定的優(yōu)化。雖然在前面國內外己經(jīng)有過關于遺傳算法在數(shù)據(jù)庫查詢優(yōu)化中的大量研究，但是從實際應用的角度來看，他們的方法還是有一定的缺陷，像算法時間復雜度比較大、交叉算子和變異算子的選取有待進一步改進等。

因此，針對上述方法計算復雜度較高，查詢時間過長的缺點，本文提出一種改進的遺傳算法。結合免疫理論和遺傳算法的優(yōu)點來產生一種新的算法，它不僅具有遺傳算法搜索的特性，而且還具有自適應的性質，可以解決免疫算法的目標函數(shù)最優(yōu)解問題。因此，通過在數(shù)據(jù)庫查詢優(yōu)化中使用該算法，可以顯著提高索引數(shù)據(jù)庫查詢的效率。

二、索引數(shù)據(jù)庫查詢

通常采用二叉連結樹來表示索引數(shù)據(jù)庫的多連結表查詢。查詢樹中的左節(jié)點表示連接操作，右節(jié)點表示兩個操作之間的關系，如圖1所示。

樹中定義了操作的執(zhí)行順序，索引數(shù)據(jù)庫查詢的策略空間大小是由算法所遵循的等價轉換規(guī)則集和查詢執(zhí)行引擎所支持的物理操作集所共同決定的。一般情況下策略空間都比較大，因此，查詢優(yōu)化算法通常避免在整個策略空間搜索，盡可能在最佳的查詢執(zhí)行計劃的一個策略空間的子集中搜索[5]。對于一個復雜查詢，等價的運算樹的數(shù)量可能會很大。查詢優(yōu)化程序一般要限制所考慮的搜索空間。我們考慮濃密樹型結構，因其在體現(xiàn)并行化時用途更為明顯。選擇了搜索空間后，需要選擇一個高效的搜索算法了，原則是要使算法的執(zhí)行時間和找到的查詢執(zhí)行計劃的執(zhí)行計劃的和最小。

三、改進遺傳算法的數(shù)據(jù)庫查詢優(yōu)化問題求解

算法中選擇的概率與群體的適應性有關，群體越多，適應度越強。這使得群體中具有相似特性的個體容易聚集，從而降低算法的收斂速度，并直接影響最優(yōu)解的質量。針對上述問題，本文考慮依靠抗體間的載體距離和適應性抗體的親和力，為了將優(yōu)良的基因個體傳遞給下一代，遺傳算法中的交叉操作變?yōu)樽赃m應交叉概率操作。改進的適應性疫苗提取方法可以從優(yōu)秀的群體中提取疫苗，從而最大化抗體的多樣性并減少先驗依賴性。對于基因突變，其具有疫苗的作用，可以使基因塊重組，提高親和力從而保證算法的局部優(yōu)化能力不變。改進過程如下。

3.1遺傳算子

遺傳算子主要包括三個部分：選擇，交叉和變異。首先設置選擇概率，定義適應度函數(shù)為f（x）。免疫算法中的抗原對應要解決的問題，抗體對應解決方案。在n個抗體的集合中，抗體之間的載體距離為

最后是免疫選擇，從組中選擇出具有高適應性的個體將（通常為50%）。這些被選擇的個體用作下一代初始化的疫苗，以執(zhí)行下一輪免疫遺傳操作，直到算法終止。

四、仿真實驗

4.1環(huán)境配置

為了測試本文改進免疫遺傳算法AIGA（Adaptive Immune Genetic Algorithms， AIGA）的性能，在CPU為Intel Core i7-6700HQ @ 2.60GHz，RAM為8.0GB，操作系統(tǒng)為Windows10的平臺下，采用python編程數(shù)據(jù)庫查詢優(yōu)化算法實現(xiàn)仿真實驗。數(shù)據(jù)庫來自一個大型資源服務搜索系統(tǒng)的數(shù)據(jù)，共有141323記錄，每條記錄包括多個子字段。同時為了使本文算法具有可對比性，選擇的對比算法為：基礎遺傳算法（Genetic Algorithms， GA）、基礎免疫遺傳算法（Immune Genetic Algorithms， IGA）。

4.2結果與分析

最優(yōu)查詢方案的收斂情況和質量，如圖2和圖3所示。對圖2與圖3結果進行分析，可以得到如下結論。

對于10個關系的數(shù)據(jù)查詢問題，當?shù)?87代時，GA算法才找到最優(yōu)數(shù)據(jù)庫查詢方案，對應的執(zhí)時間為110.22s;在相同條件，當?shù)?62代時，IGA算法找到最優(yōu)數(shù)據(jù)庫查詢方案，其執(zhí)行時間為89.25s，相對于GA算法，性能更優(yōu)。對于相同問題，AIGA算法迭代141次后得到比 GA算法和IGA算法更優(yōu)的數(shù)據(jù)庫查詢方案，其執(zhí)行時間為72.29s。相對GA算法，IGA算法提高了求解速度，獲得更優(yōu)的查詢解，同時AIGA算法性能得到進一步提高，克服了對比算法存在的不足，是一種速度快、效率高的數(shù)據(jù)庫查詢優(yōu)化方法。

五、總結

針對當前基于遺傳算法的數(shù)據(jù)庫查詢優(yōu)化算法存在的遺傳過程中出現(xiàn)退化和求解過程中對特征信息利用不夠的現(xiàn)象，且免疫遺傳算法在群體中具有相似特性的個體容易聚集的缺陷，本文提出一種AIGA算法的索引數(shù)據(jù)庫優(yōu)化查詢方案，在免疫遺傳算法的基礎上，將遺傳算法中的交叉操作變?yōu)樽赃m應交叉概率操作，改進遺傳算子，并重新構建免疫疫苗。

實驗結果表明，AIGA算法能夠提高算法的全局搜索能力，較好的克服了GA、IGA算法中存在的缺陷，獲得了更優(yōu)的數(shù)據(jù)查詢方案，在數(shù)據(jù)庫中具有廣泛的應用前景。

參? 考? 文? 獻

[1] Li D， Han L， Ding Y. SQL Query Optimization Methods of Relational Database System[C]// Second International Conference on Computer Engineering & Applications. IEEE Computer Society， 2010.

[2] Kadkhodaei H R， Mahmoudi F. A combination method for join ordering problem in relational databases using genetic algorithm and ant colony[C]// IEEE International Conference on Granular Computing. IEEE， 2012.

[3] 周瑩， 陳軍華. 基于多蟻群遺傳算法的分布式數(shù)據(jù)庫查詢優(yōu)化[J]. 上海師范大學學報（自然科學版）， 2018（1）.

[4] 林基明， 班文嬌， 王俊義， et al. 基于并行遺傳最大最小蟻群算法的分布式數(shù)據(jù)庫查詢優(yōu)化[J]. 計算機應用， 2016， 36（3）：675-680.

[5] Tatar A ， Amorim M D D ， Fdida S ， et al. A survey on predicting the popularity of web content[J]. Journal of Internet Services and Applications， 2014， 5（1）：8-12.