改進粒子群優化算法的數據庫查詢優化方法

王崑凌

(西安工程大學 計算機科學學院， 西安 710048)

0 引言

隨著信息化技術和數據處理技術的不斷發展和融合，而人們對數據管理的要求越來越高，在此背景下現了大量的數據庫管理系統。近年來了，數據量不斷的增加，數據庫管理系統的規模越來越大，數據庫的查詢和更新更加復雜，其中數據庫查詢是最為頻繁操作，而查詢操作是衡量一個數據庫管理系統性能好壞的一個重要指標，因此數據庫的查詢優化是一直數據庫管理系統研究中的一個重要方向[1-3]。

為了使數據庫管理系統的工作性能更優，更加穩定可靠，國內外相關學者以及專家對數據庫查詢優化問題進行了深入的研究，當前存在許多有效的數據庫查詢優化方法[4]。當前數據庫查詢優化方法可以劃為兩大數，一類為確定性的數據庫查詢優化方法，其包括：貪心算法、動態規劃算法[5,6]，它們對數據庫全部可能的查詢方案進行搜索，最后形成一個完整的查詢樹，根據查詢樹得到最優數據庫查詢優化方案，對于小規模的數據庫查詢優化問題，它們可以快速、準確找到最優數據庫查詢優化方案，但是對于大規模的數據庫查詢優化問題，它們的缺陷十分明顯，存在數據庫查詢時間長、查詢效率極低等，無法滿足現代數據庫管理系統的查詢要求[7]。另一類為隨機搜索的數據庫查詢優化方法，主要包括：遺傳算法、蟻群算法以及模擬退火算法，相對于為確定性的數據庫查詢優化方法，它們可以提高數據庫查詢的效率，而且可以得到較優的數據庫查詢結果[8,9]。但是在實際應用中，遺傳算法、蟻群算法以及模擬退火算法均存在一定的不足，如遺傳算法后期收斂速度慢，蟻群算法前期信息缺陷，搜索速度慢，模擬退火算法易陷入局部最優解[10]。

粒子群優化算法(particle swarm optimization，PSO)是一種常用隨機搜索算法，其比遺傳算法、蟻群算法、模擬退火算法有更好的搜索能力，為了解決當前數據庫查詢優化過程存在的一些缺陷，設計了改進粒子群優化算法的數據庫查詢優化方法。仿真對比實驗結果表明，改進粒子群優化算法找到最優數據庫查詢優化方案的時間短，加快了數據庫查詢優化速度，改善提高了數據庫查詢結果。

2 數據庫查詢優化問題的描述

數據庫管理系統的發展經歷了幾個階段，最初采用層次性的數據庫管理系統，該數據庫管理系統一般是一個單位或者一個公司的局部數據管理，數據無法進行實時共享，隨后出現網絡數據庫管理系統，通過網絡將不同單位或者公司的數據庫管理系統連接在一起，實現數據共熟，由于不同單位的數據結構不一樣，因此這些數據庫管理系統具有一定的異構性，但是由于數據爆炸式增長，人們對數據處理功能要求越來越高，網絡數據庫管理系統的局限性也不斷體現出來，出現分布式數據庫管理系統。分布式數據庫管理系統是一種更加符合社會需求的數據庫管理系統，數據協作、共享更加方便，是當前主要數據庫管理方式。查詢技術是分布式數據庫管理系統的最基本操作，而查詢技術包括查詢處理和查詢優化兩個方面，本文針對查詢優化進行研究。分布式數據庫管理系統的查詢優化目標就是查詢總代價盡可能小，同時保證查詢響應時間最短，其中查詢總代價主要包括：輸入和輸出開銷、存儲開銷、計算開銷、通信開銷，而查詢響應時間指從接收查詢命令到輸出查詢結果所需要的時間。一個分布式數據庫系統里查詢代價計算公式可以表示為式(1)。

T=I/O代價+CPU代價+通信代價

(1)

通信代價的計算公式為式(2)。

T(X)=C0+C1×X

(2)

式中，C0表示兩個節點的通信時間，C1表示傳輸率，X表示數據傳輸量。

由于分布式數據庫管理系統的工作環境十分復雜，查詢方案有許多種，要從中搜索一種最優方案作為分布式數據庫管理系統的最終查詢結果，因此分布式數據庫管理系統查詢問題求解的原理如圖1所示。

圖1 數據庫查詢問題的求解原理

2 改進粒子群群優化算法

2.1 標準粒子群優化算法

粒子群優化算法是一種模擬受鳥群生活習性的搜索優化算法，每一個粒子均有與其相關的鄰近粒子，它們的速度相同，粒子速度對優化問題的方向，但是每一個粒子的位置不一樣，粒子對應優化問題的可行解，粒子均可以向任意方向進行運動，可控參數少、編碼容易，在許多領域得到了成功應用[11,12]。第i個粒子的當前速度、當前位置和當前歷史最優位置分別為：Xi=(xi1,xi2,…,xid)和Vi=(vi1,vi2,…,vid)；Pi=(pi1,pi2,…,pid)，整個粒子群當前的歷史最優位置為：Pg=(pg1,pg2,…,pgd)，第k+1代、第i個粒子的速度和位置更新方式為式(3)、式(4)。

(3)

(4)

式中，d=1,2,…,D，D表示搜索空間維數，c1表示個體認知能力，c2表示社會認知能力；r1,r2表示0到1之間的隨機數。

3.2 標準粒子群優化算法的改進

從標準粒子群優化算法的工作過程可以看出，影響算法性能為速度和位置，然而在實際應用中，還有許多其它因素會對算法的性能產生影響，這樣使得標準粒子群優化算法穩定性較差，因此本文從以下幾個方面對標準粒子群優化算法進行改進，以提高其工作穩定性。

(1) 引入慣性權重。將慣性權重加入到粒子飛行的速度中，用于平穩粒子的調節全局和局部搜索能力，那么式(3)變為式(5)。

(5)

式中，W表示慣性權重。

由于粒子群優化算法在工作過程中，前期全局搜索能力要強，后期局部搜索能力要強，因此慣性權重W的變化方式為式(6)。

(6)

式中，Wmax和Wmin分別表示慣性權重的最大值和最小值，iter表示粒子群的當前迭代次數，Itermax表示粒子群的最大迭代次數。

(2) 混沌方式產生初始粒子群。初始粒子群質量的好壞，影響種群的多樣性，標準粒子群優化算法采用隨機方式產生粒子群，到了工作后期，種群多樣性變差，難以找到問題的最優解，為此本文采用混沌方式產生初始粒子群。Logistic混沌映射公式為式(7)。

(7)

式中，t表示種群序號，u表示控制參數。

當t=1,2,…,NP時，通式(7)可以產生NP個粒子初始種群，通過式(8)的逆混沌映射得到相應的變量空間為式(8)。

(8)

3 改進粒子群優化算法的數據查詢優化方法具體設計

分布式數據庫管理系統查詢問題是一個NP難題，要從中找到最優方案十分困難，為此本文引入改進粒子群優化算法對其進行求解，以求找到最優的分布式數據庫管理系統查詢方案，具體步驟為：

(1) 建立分布式數據庫管理系統查詢方案的可行解集合。

(2) 根據混沌映射方式產生與分布式數據庫管理系統查詢方案的可行解數量相同的粒子群。

(3) 設迭代次數t=0，對粒子群的最大迭代次數Itermax，參數c1，c2以及Wmax和Wmin的值進行設置。

(4) 建立分布式數據庫管理系統查詢目標的約束條件，本文選擇查詢代價最小，響應時間最短。

(5) 根據分布式數據庫管理系統查詢目標的約束條件構建粒子的適應度函數。

(6) 根據適應度函數對每一個粒子的好壞進行衡量，找到當前最優歷史位置。

(7) 根據式(6)對權值進行調整，并根據式(5)和式(4)更新粒子的速度和位置。

(8) 迭代次數t=t+1。

(9) 如果t>Itermax，就停止執行，不然返回到式(6)繼續。

(10) 根據粒子群的最優位置得到最終分布式數據庫管理系統查詢方案。

4 數據庫查詢方法的性能測試

4.1 測試平臺

為了測試本文的改進粒子群優化算法的數據庫查詢優化方法性能，采用測試平臺為：AMD Ryzen 5 2600X CPU，威剛XPG DDR4 3200 8G RAM， 金士頓A1000 NVMe M.2 240G 硬盤，Linux 操作系統，編程環境為：VC++6.0，選擇遺傳算法、標準粒子群優化算法進行對照測試，以分析數據庫查詢優化結果的優劣。

4.2 結果與分析

統計所有數據庫查詢優化方法的查詢代價和最優查詢方法的生成時間，結果如圖2和圖3所示。

圖2 數據庫查詢代價對比

圖3 最優查詢方案的生成時間對比

對比圖2和圖3進行分析可以知道，本文方法的數據庫查詢代價遠遠低于遺傳算法、標準粒子群優化算法的數據庫查詢代價，得到了最優數據庫查詢方案更優，同時最優查詢方案的生成時間更短，提高了最優查詢優化效率。

統計所有數據庫查詢優化方法的成功率，其進行5次測試實驗，每次進行100次查詢，結果如表1所示。

表1 數據庫查詢成功率對比

從表1可知，本文方法的數據庫查詢成功率遠遠高于遺傳算法、標準粒子群優化算法的數據庫查詢成功率，降低了數據庫查詢錯誤率，數據庫查詢方法的整體性能更優。

5 總結

查詢優化研究一直是數據庫管理領域的一個熱點問題，針對當前數據庫查詢優化方法構建過程中存一些難題，設計了改進粒子群算法的數據庫查詢方法，并采用相同實例與其它數據庫查詢方法進行了對比測試，結果表明：

(1) 傳統數據庫查詢方法的工作效率低、找到最優數據庫查詢方案的時間長，使得數據庫查詢代價比較大，無法適應現代數據庫向大規模發展的要求。

(2) 粒子群優化算法較好的克服了當前數據庫查詢方法存在一些難題，找到最優數據庫查詢方案的時間短，有降低了數據庫查詢代價，得到了比較理想的數據庫查詢方案。

(3) 對標準粒子群優化算法進行了改進，提高了找到數據庫查詢最優方案的成功率，減少了數據庫查詢的錯誤率，數據庫查詢效果更佳，在數據庫管理領域具有更加廣泛的應用前景。