徐千淞 陳怡 陳云選 張劉玲

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

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

一、引言

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

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

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

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

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

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

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

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

3.1遺傳算子

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

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

四、仿真實(shí)驗(yàn)

4.1環(huán)境配置

為了測試本文改進(jì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)化算法實(shí)現(xiàn)仿真實(shí)驗(yàn)。數(shù)據(jù)庫來自一個大型資源服務(wù)搜索系統(tǒng)的數(shù)據(jù)，共有141323記錄，每條記錄包括多個子字段。同時為了使本文算法具有可對比性，選擇的對比算法為：基礎(chǔ)遺傳算法（Genetic Algorithms， GA）、基礎(chǔ)免疫遺傳算法（Immune Genetic Algorithms， IGA）。

4.2結(jié)果與分析

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

對于10個關(guān)系的數(shù)據(jù)查詢問題，當(dāng)?shù)?87代時，GA算法才找到最優(yōu)數(shù)據(jù)庫查詢方案，對應(yīng)的執(zhí)時間為110.22s;在相同條件，當(dāng)?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算法性能得到進(jìn)一步提高，克服了對比算法存在的不足，是一種速度快、效率高的數(shù)據(jù)庫查詢優(yōu)化方法。

五、總結(jié)

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

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

參? 考? 文? 獻(xiàn)

[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]. 上海師范大學(xué)學(xué)報（自然科學(xué)版）， 2018（1）.

[4] 林基明， 班文嬌， 王俊義， et al. 基于并行遺傳最大最小蟻群算法的分布式數(shù)據(jù)庫查詢優(yōu)化[J]. 計(jì)算機(jī)應(yīng)用， 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.