基于改進(jìn)和聲搜索群算法的數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化

高潔

摘 要： 查詢(xún)優(yōu)化是數(shù)據(jù)庫(kù)應(yīng)用的基礎(chǔ)，針對(duì)當(dāng)前數(shù)據(jù)庫(kù)查詢(xún)效率低，難以獲得最優(yōu)查詢(xún)優(yōu)化方案的局限性，提出基于改進(jìn)和聲搜索算法的數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化方法。首先對(duì)當(dāng)前數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化研究現(xiàn)狀進(jìn)行分析，找出當(dāng)前算法存在的一些不足；然后構(gòu)建數(shù)據(jù)查詢(xún)優(yōu)化的數(shù)學(xué)模型，采用和聲搜索算法進(jìn)行求解，并對(duì)標(biāo)準(zhǔn)和聲搜索算法的缺陷進(jìn)行改進(jìn)；最后采用VC++編程實(shí)現(xiàn)數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化性能測(cè)試。結(jié)果表明，該算法可以提高數(shù)據(jù)庫(kù)的查詢(xún)效率，尤其對(duì)大型數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化的優(yōu)勢(shì)更加顯著。

關(guān)鍵詞： 數(shù)據(jù)庫(kù)； 數(shù)學(xué)模型； 查詢(xún)優(yōu)化； 和聲搜索算法

中圖分類(lèi)號(hào)： TN911?34； TP391 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2017）03?0114?03

Database query optimization based on improved harmony search algorithm

GAO Jie1， 2

（1. University of Electronic Science and Technology of China， Chengdu 611731， China；

2. Department of Modern Service， Hebei Women′s Vocational College， Shijiazhuang 050091， China）

Abstract： The database query optimization is the foundation of the database application. Since the database query has low efficiency， and it is difficult to obtain the optimal query scheme， a new database query optimization method based on improved harmony search algorithm is proposed. The research status of the database query optimization is analyzed to find out the shortcomings existing in the current algorithms. The mathematical model of the database query optimization was constructed， and solved with the harmony search algorithm. The defect of the standard harmony search algorithm was improved. The VC++ programming is used to test the performance of the database query optimization. The results show that the algorithm can improve the database query efficiency， and has more significant advantage especially for the large?scale database query optimization.

Keywords： database； mathematical model； query optimization； harmony search algorithm

0 引 言

近些年隨著網(wǎng)絡(luò)技術(shù)、數(shù)據(jù)處理技術(shù)的不斷成熟和融合，出現(xiàn)了許多的數(shù)據(jù)庫(kù)，而且數(shù)據(jù)庫(kù)規(guī)模越來(lái)越龐大[1?2]。查詢(xún)優(yōu)化操作是數(shù)據(jù)庫(kù)應(yīng)用最常用的技術(shù)，查詢(xún)優(yōu)化效率的優(yōu)劣直接決定了數(shù)據(jù)庫(kù)訪(fǎng)問(wèn)結(jié)果的好壞，因此如何設(shè)計(jì)性能優(yōu)異的數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化方法具有十分重要的實(shí)際應(yīng)用價(jià)值[3]。

數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化問(wèn)題引起了國(guó)內(nèi)外研究人員的高度重視，它們采用各種技術(shù)對(duì)其進(jìn)行深入分析，涌現(xiàn)出了大量、有效的數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化算法[3]。最原始的數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化算法基于窮盡策略，即搜索每一種可能的查詢(xún)方案，找到最優(yōu)的數(shù)據(jù)庫(kù)查詢(xún)方案，當(dāng)數(shù)據(jù)庫(kù)規(guī)模比較小時(shí)，其查詢(xún)效率高[4]，然而對(duì)于大型數(shù)據(jù)庫(kù)，由于查詢(xún)條件和約束比較多，該算法的計(jì)算時(shí)間復(fù)雜度急劇上升，查詢(xún)過(guò)程耗時(shí)相當(dāng)長(zhǎng)，有時(shí)甚至無(wú)法找到數(shù)據(jù)庫(kù)的最優(yōu)查詢(xún)方案[5]。為此，有關(guān)研究人員提出了基于動(dòng)態(tài)規(guī)劃的數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化算法，該算法的查詢(xún)效率得到了提高，但其實(shí)質(zhì)上仍然采用窮舉搜索策略，而對(duì)于大型數(shù)據(jù)庫(kù)，查詢(xún)效率低的問(wèn)題仍然存在[6]。近些年，隨著人工智能算法的不斷成熟，有學(xué)者將遺傳算法、粒子群優(yōu)化算法以及蟻群優(yōu)化算法[7?9]引入到數(shù)據(jù)查詢(xún)優(yōu)化問(wèn)題的求解過(guò)程中，它們將最優(yōu)或者次優(yōu)數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化方案作為搜索目標(biāo)，通過(guò)模擬自然界一些生物行為進(jìn)行問(wèn)題求解，找到數(shù)據(jù)庫(kù)查詢(xún)最優(yōu)方案的速度明顯加快，計(jì)算時(shí)間復(fù)雜度下降，成為當(dāng)前數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化問(wèn)題的主要解決算法[10]。相關(guān)研究表明，數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化受到多種條件約束，是一種典型的NP，這些算法的求解過(guò)程易陷入局部最優(yōu)解，有時(shí)不能得到最優(yōu)查詢(xún)方案[11]。

和聲搜索（Harmony Search，HS）算法[12]是一種模擬樂(lè)師調(diào)整音調(diào)的人工智能算法，具有控制參數(shù)少，簡(jiǎn)單易實(shí)現(xiàn)，收斂速度快等優(yōu)點(diǎn)，在很大程度上防止了局部最優(yōu)解的出現(xiàn)。為了獲得更加理想的數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化結(jié)果，提出改進(jìn)和聲搜索算法的數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化算法（Improved Harmony Search，IHS），并采用具體實(shí)驗(yàn)對(duì)其性能進(jìn)行測(cè)試和分析。結(jié)果表明，本文算法可以提高數(shù)據(jù)庫(kù)查詢(xún)效率，特別適合于大規(guī)模數(shù)據(jù)庫(kù)查詢(xún)問(wèn)題的求解。

1 改進(jìn)和聲搜索算法

1.1 HS算法

HS算法是一種受到和聲音樂(lè)啟發(fā)的人工智能算法，模擬樂(lè)師們不斷調(diào)整各種樂(lè)器的音調(diào)產(chǎn)生美妙的和聲對(duì)問(wèn)題實(shí)現(xiàn)求解。設(shè)樂(lè)器[（i=1，2，…，m）]為待求解問(wèn)題的第[i]個(gè)決策變量，和聲為待求解問(wèn)題的第[j]個(gè)解向量，HS工作步驟為：

Step1：設(shè)待求解問(wèn)題為最小優(yōu)化問(wèn)題，[f（X）]為問(wèn)題的目標(biāo)函數(shù)，那么問(wèn)題可以描述為：

[min f（X）s.t. X∈（x1，x2，…，xN）] （1）

式中：[X]為決策變量[xi（i=1，2，…，N）]組成的解向量；[N]為變量的個(gè)數(shù)。

Step2：確定[N]的值，音調(diào)調(diào)節(jié)概率和帶寬PAR和bw；決策變量取值范圍為[[xLi，xUi]；]和聲記憶庫(kù)的規(guī)模為HMS；記憶庫(kù)的概率為HMCR。

Step3： 隨機(jī)生成[HMS]個(gè)和聲[x1，x2，…，xHMS，]并且將它們保存在和聲記憶庫(kù)中，具體為：

[HM=x11x12…x1Nx21x22…x2N????xHMS1xHMS2…xHMSNf（x1）f（x2）?f（xHMS）] （2）

Step4：通過(guò)HM的學(xué)習(xí)、音調(diào)微調(diào)和隨機(jī)選擇音調(diào)產(chǎn)生新的和聲[x′i=（x′1，x′2，…，x′N(xiāo)）]，具體如下：

[x′1]通過(guò)HMCR的概率，其值來(lái)自HM[（x′1～xHMS1）]，根據(jù)1～HMCR的概率隨機(jī)產(chǎn)生，即：

[x′i=x′i∈（x1i，x2i，…，xHMSi）， if rand

若[x′i]來(lái)自[HM，]那么根據(jù)式（4）對(duì)其音調(diào)進(jìn)行微調(diào)。

[x1i=x′i+rand*bw， if rand

式中[rand]為[0，1]的隨機(jī)數(shù)。

Step5： 對(duì)[x′i]進(jìn)行評(píng)估，若其優(yōu)于[HM]的最差解，那么將[x′i]替換為最差解，并保存到[HM]中，即：

[f（xworst）=maxj=1，2，…，HMSf（xj）if f（x）

Step6：如果滿(mǎn)足終止條件就停止運(yùn)行，否則不斷重復(fù)Step3和Step4。

1.2 IHS算法

相關(guān)研究結(jié)果表明，與其他人工智能算法相似，HS算法在后期出現(xiàn)搜索停滯、易出現(xiàn)“早熟”現(xiàn)象[13]，為此本文對(duì)其進(jìn)行改進(jìn)，提出IHS算法，具體思想為：引入?yún)?shù)WSR，其值的大小與迭代次數(shù)[k]之間是一種動(dòng)態(tài)的變化關(guān)系，算法工作初期，其值較大，更新HM的最差和聲，算法工作后期更新HM最優(yōu)和聲，可以有效避免“早熟”現(xiàn)象發(fā)生，加快算法的收斂速度。

為了分析IHS算法的性能，選擇Griewank和Rastrigin函數(shù)進(jìn)行測(cè)試，采用HS算法進(jìn)行對(duì)照實(shí)驗(yàn)，測(cè)試結(jié)果見(jiàn)圖1。對(duì)圖1的測(cè)試結(jié)果進(jìn)行對(duì)比分析可以發(fā)現(xiàn)，IHS算法的搜索速度明顯要快于HS算法，而且解決了HS算法的“早熟”難題，證明了本文對(duì)HS算法改進(jìn)的有效性。

2 GM?QPSO的數(shù)據(jù)查詢(xún)優(yōu)化問(wèn)題求解

2.1 數(shù)學(xué)模型

數(shù)據(jù)庫(kù)查詢(xún)最優(yōu)方案實(shí)際是一個(gè)有[n]個(gè)關(guān)系的連接樹(shù)：[j1， j2，…， ji，]查詢(xún)方案評(píng)估模型為：

[COST=i=1n-icost（ji）] （6）

設(shè)[R]為關(guān)系[R]的元組數(shù)；[C]為[R]和[S]的公共屬性集合，[J=RjoinS，]查詢(xún)代價(jià)[cost（J）]為：

[cost（J）=R×Sci∈CmaxVci，R，Vci，S] （7）

[V（c，R）]為[R]中屬性[c]的取值，具體為：[V（c，J）=V（c，J）， c∈R-SV（c，S）， c∈S-Rmin（V（c，R），V（c，S））， c∈R?S1≤i1，i2，…，im

2.2 IHS算法的數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化問(wèn)題求解

（1） IHS參數(shù)的初始化。

（2） 設(shè)[xi=round（rand（1，N）），i=1，2，…，HMS]隨機(jī)產(chǎn)生[HMS]個(gè)向量，即數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化問(wèn)題的可行解。

（3） 計(jì)算[HM]每個(gè)和聲的適應(yīng)度值，并根據(jù)適應(yīng)度值找到最優(yōu)和最差的和聲[xbest]和[xworst，]適應(yīng)度計(jì)算公式為：

[f（Xi）=1cost（Xi）] （9）

（4） 確定WSR的值，具體如下所示：

[WSR=0.7×1-kTmax+0.3] （10）

式中[k]為當(dāng)前迭代的次數(shù)。

（5） 產(chǎn)生一個(gè)隨機(jī)數(shù)rand，若rand>WSR，那么表示[xworst]被選中，且有[xnew=xworst，]否則有[xnew=xbest。]

（6） 若rand

（7） 計(jì)算[xnew]的適應(yīng)度值[fnew=f（xnew），]若[xworst]被選中，且[fnew>fworst，]那么就有[xworst=xnew，]否則[xbest=xnew]。

（8） 如果達(dá)到最大迭代次數(shù)，最優(yōu)和聲對(duì)應(yīng)的解為數(shù)據(jù)庫(kù)最優(yōu)查詢(xún)方案，否則返回步驟（3），繼續(xù)執(zhí)行。

基于IHS算法的數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化流程見(jiàn)圖2。

3 性能測(cè)試

為了分析IHS算法的數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化問(wèn)題求解的有效性，采用VC++編程實(shí)現(xiàn)仿真實(shí)驗(yàn)，并選擇HS算法、文獻(xiàn)[8]算法進(jìn)行對(duì)比測(cè)試，選擇查詢(xún)代價(jià)和執(zhí)行時(shí)間（單位：s）對(duì)數(shù)據(jù)庫(kù)查詢(xún)最優(yōu)方案進(jìn)行評(píng)價(jià)，所有算法的數(shù)據(jù)庫(kù)查詢(xún)代價(jià)和執(zhí)行時(shí)間如圖3，圖4所示。

對(duì)圖3中各種算法的數(shù)據(jù)查詢(xún)代價(jià)進(jìn)行對(duì)比分析，得到如下結(jié)論：

（1） 當(dāng)連接數(shù)很小時(shí)，IHS算法、HS算法以及文獻(xiàn)[8]算法的數(shù)據(jù)庫(kù)查詢(xún)代價(jià)相差不大，沒(méi)有太大的區(qū)別。

（2） 隨著連接數(shù)不斷增加，IHS算法、HS算法以及文獻(xiàn)[8]算法的數(shù)據(jù)庫(kù)查詢(xún)代價(jià)也隨之增加，在相同條件下，IHS算法的數(shù)據(jù)庫(kù)查詢(xún)代價(jià)要小于HS算法以及文獻(xiàn)[8]算法，這是由于IHS算法加快了數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化問(wèn)題的求解速度，得到了更加理想的數(shù)據(jù)庫(kù)查詢(xún)方案。

從圖4的執(zhí)行時(shí)間可以看出，相對(duì)于HS算法以及文獻(xiàn)[8]算法，IHS算法找到數(shù)據(jù)庫(kù)查詢(xún)最優(yōu)方案的時(shí)間大幅度減少，尤其當(dāng)數(shù)據(jù)庫(kù)連接數(shù)很大時(shí)，IHS算法的執(zhí)行速度更快，優(yōu)勢(shì)更加明顯，可以滿(mǎn)足數(shù)據(jù)庫(kù)查詢(xún)的實(shí)時(shí)性要求，同時(shí)可以應(yīng)用于網(wǎng)絡(luò)數(shù)據(jù)庫(kù)的查詢(xún)，應(yīng)用范圍更加廣泛。

4 結(jié) 語(yǔ)

查詢(xún)效率直接影響大型數(shù)據(jù)庫(kù)的應(yīng)用范圍，為了加快數(shù)據(jù)庫(kù)查詢(xún)的速度，滿(mǎn)足數(shù)據(jù)庫(kù)在線(xiàn)查詢(xún)的實(shí)際要求，提出基于改進(jìn)和聲搜索算法的數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化算法，實(shí)驗(yàn)結(jié)果表明，本文算法可以很快找到數(shù)據(jù)庫(kù)查詢(xún)的最優(yōu)結(jié)果，有效提高了數(shù)據(jù)庫(kù)的查詢(xún)效率，尤其對(duì)于大型數(shù)據(jù)庫(kù)查詢(xún)的優(yōu)越性更加明顯，可以應(yīng)用于實(shí)際的數(shù)據(jù)庫(kù)系統(tǒng)中。

參考文獻(xiàn)

[1] 張敏，馮登國(guó)，徐震.多級(jí)多版本數(shù)據(jù)庫(kù)管理系統(tǒng)全局串行化[J].軟件學(xué)報(bào)，2007，18（2）：346?347.

[2] 張麗平，李松，郝忠孝.球面上的最近鄰查詢(xún)方法研究[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（5）：126?129.

[3] 帥訓(xùn)波，馬書(shū)南，周相廣，等.基于遺傳算法的分布式數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2009，30（8）：1600?1604.

[4] ZHOU Zehai. Using heuristics and genetic algorithms for large scale database query optimization [J]. Journal of information and computing science， 2007， 2（4）： 261?280.

[5] CHEN P H， SHAHANDASHTI S M. Hybrid of genetic algorithm and simulated annealing for multiple project scheduling with multiple resource constraints [J]. Automation in construction， 2009， 18（4）： 434?443.

[6] 郭聰莉，朱莉，李向.基于蟻群算法的多連接查詢(xún)優(yōu)化方法[J].計(jì)算機(jī)工程，2009，35（10）：173?176.

[7] 林桂亞.基于粒子群算法的數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化[J].計(jì)算機(jī)應(yīng)用研究，2012，29（3）：974?975.

[8] 鄭先鋒，王麗艷.自適應(yīng)逃逸動(dòng)量粒子群算法的數(shù)據(jù)庫(kù)多連接查詢(xún)優(yōu)化[J].四川大學(xué)學(xué)報(bào)（自然科學(xué)版），2013，50（3）：100?103.

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

[10] 徐增敏，張昆，丁勇，等.基于動(dòng)態(tài)視圖的數(shù)據(jù)庫(kù)性能調(diào)優(yōu)[J].計(jì)算機(jī)應(yīng)用與軟件，2012，29（12）：58?60.

[11] 林鍵，劉仁義，劉南，等.基于查詢(xún)優(yōu)化器的分布式空間查詢(xún)優(yōu)化方法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（22）：161?165.

[12] GEEM Z W， KIM J H， LOGANATHAN G V. A new heuristic optimization algorithm： harmony search [J]. Simulation， 2001， 76（2）： 60?68.

[13] OMRAN M， MAHDAV M. Global?best harmony search [J]. Applied mathematics and computation， 2008， 198（2）： 643?656.