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

在審

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

1.一種基于進(jìn)化算法的數(shù)據(jù)庫(kù)多連接查詢優(yōu)化方法，其特征在于：包括如下步驟:

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

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

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

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

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

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

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

2.根據(jù)權(quán)利要求1所述的一種基于進(jìn)化算法的數(shù)據(jù)庫(kù)多連接查詢優(yōu)化方法，其特征在于：步驟一所述對(duì)原始數(shù)據(jù)進(jìn)行預(yù)處理，構(gòu)建出查詢圖G的方法如下：

(1)在各個(gè)分布數(shù)據(jù)庫(kù)節(jié)點(diǎn)上執(zhí)行投影操作，精簡(jiǎn)原始數(shù)據(jù)；

(2)按照每一個(gè)屬性對(duì)精簡(jiǎn)數(shù)據(jù)進(jìn)行歸并排序：按照順序從每個(gè)排序的子表中讀取一個(gè)塊的內(nèi)容放入內(nèi)存中，在內(nèi)存中統(tǒng)一對(duì)這些塊中的記錄執(zhí)行歸并操作，每次選擇最大的記錄放入數(shù)據(jù)庫(kù)中，同時(shí)刪除子表中相應(yīng)的記錄；

(3)當(dāng)子表在內(nèi)存中的塊被取空時(shí)，從子表中順序讀取一個(gè)新的塊放入內(nèi)存中繼續(xù)執(zhí)行歸并操作，當(dāng)歸并操作完成時(shí)，將關(guān)系表示為查詢圖G。

3.根據(jù)權(quán)利要求1所述的一種基于進(jìn)化算法的數(shù)據(jù)庫(kù)多連接查詢優(yōu)化方法，其特征在于：步驟二所述獲取有益雙向半連接集合BS的方法如下：

(1)確定多連接查詢涉及到的屬性行和列；

(2)計(jì)算查詢圖G中所有雙向半連接的收益和通訊代價(jià)；

(3)確定有益雙向半連接，并將其加入到有益雙向半連接集合BS。

4.根據(jù)權(quán)利要求1所述的一種基于進(jìn)化算法的數(shù)據(jù)庫(kù)多連接查詢優(yōu)化方法，其特征在于：步驟三所述構(gòu)建并行遺傳算法的初始種群的方法如下：

(1)將有益雙向半連接集合BS里的元素構(gòu)造成連接樹(shù)；

(2)對(duì)該連接樹(shù)進(jìn)行后根遍歷；

(3)采用整數(shù)序列對(duì)葉子節(jié)點(diǎn)進(jìn)行編碼；

(4)利用編碼結(jié)果作為并行遺傳算法的初始種群。

5.根據(jù)權(quán)利要求1所述的一種基于進(jìn)化算法的數(shù)據(jù)庫(kù)多連接查詢優(yōu)化方法，其特征在于：步驟四所述執(zhí)行并行遺傳算法，得到規(guī)約最優(yōu)查詢路徑的方法如下：

(1)確定并行遺傳算法的參數(shù)：適應(yīng)度函數(shù)、種群大小、交叉變異概率、迭代次數(shù)；

(2)建立遺傳算子：選擇遺傳算子、交叉遺傳算子、變異遺傳算子；

(3)對(duì)染色體并行執(zhí)行選擇、交叉、變異操作，直到算法達(dá)到收斂條件或最大進(jìn)化步數(shù)；

(4)輸出種群中最好的個(gè)體作為規(guī)約最優(yōu)查詢路徑。

6.根據(jù)權(quán)利要求1所述的一種基于進(jìn)化算法的數(shù)據(jù)庫(kù)多連接查詢優(yōu)化方法，其特征在于：步驟五所述構(gòu)建多個(gè)蟻群的初始種群的方法如下：

(1)初始化蟻群算法的參數(shù)：蟻群的種群大小、多蟻群的數(shù)目；

(2)利用規(guī)約最優(yōu)查詢路徑初始化蟻群算法的信息素矩陣；

(3)將螞蟻放到發(fā)起查詢請(qǐng)求的網(wǎng)絡(luò)節(jié)點(diǎn)，建立多個(gè)蟻群的初始種群。

7.根據(jù)權(quán)利要求1所述的一種基于進(jìn)化算法的數(shù)據(jù)庫(kù)多連接查詢優(yōu)化方法，其特征在于：步驟六所述執(zhí)行多蟻群算法的方法如下：

(1)按照多蟻群算法的轉(zhuǎn)移概率公式來(lái)進(jìn)行路徑搜索，子蟻群中的螞蟻開(kāi)始路徑搜索，并更新局部的信息素；

(2)重復(fù)步驟(1)，直到子蟻群中的螞蟻已完成所有目的節(jié)點(diǎn)的搜索，則更新最優(yōu)查詢計(jì)劃和全局的信息素；

(3)進(jìn)行子蟻群間的信息素互相學(xué)習(xí)；

(4)重復(fù)步驟(1)到(3)，直到當(dāng)前迭代次數(shù)滿足算法的終止條件。

8.根據(jù)權(quán)利要求1所述的一種基于進(jìn)化算法的數(shù)據(jù)庫(kù)多連接查詢優(yōu)化方法，其特征在于：步驟七所述輸出最終的查詢執(zhí)行策略的方法如下：

(1)輸出多蟻群算法中的最優(yōu)個(gè)體作為最優(yōu)解；

(2)將該最優(yōu)解解碼為對(duì)應(yīng)的查詢執(zhí)行策略。