一種改進的數(shù)據(jù)庫查詢二叉樹啟發(fā)式算法

黃海

（莆田學院 信息工程學院，福建 莆田 351100）

一種改進的數(shù)據(jù)庫查詢二叉樹啟發(fā)式算法

黃海

（莆田學院 信息工程學院，福建 莆田 351100）

針對連接操作是影響數(shù)據(jù)庫查詢性能的關鍵技術，在經典的GMC算法的基礎上提出一種改進的二叉樹啟發(fā)式算法.首先利用GMC算法對查詢建立查詢樹，接著利用啟發(fā)式規(guī)則構建局部最優(yōu)二叉樹，最后通過重建整棵查詢樹得到優(yōu)化的查詢序列.并通過實驗驗證算法的有效性.

二叉樹；局部最優(yōu)；啟發(fā)式

1 引言

查詢是數(shù)據(jù)庫系統(tǒng)的核心，而連接操作是影響查詢性能的主要因素，研究如何進行連接操作的優(yōu)化對提升數(shù)據(jù)庫性能具有重要意義.數(shù)據(jù)庫連接的優(yōu)化主要著眼于優(yōu)化查詢的順序，國內外對此已有較多的研究[1-4].由于連接查詢優(yōu)化問題是NP難題，它隨著問題規(guī)模的擴大，而無法找出最優(yōu)解.

目前針對連接查詢優(yōu)化的研究主要有兩個方向.一種是基于模擬生物或自然界的不確定算法，比較有代表性的是蟻群算法、模擬退火算法[5-7]等，它有時能得到較好的優(yōu)化結果，但它是不確定算法，它的結果經常受各種參數(shù)的影響而無法得到理想的優(yōu)化結果.另一種是基于啟發(fā)式的確定性算法，具有代表性的有[8-10]，它能在較短的時間內給出優(yōu)化系列，但它經常傾向于局部最優(yōu)而得不到較好的優(yōu)化結果. GMC算法[11]是數(shù)據(jù)庫連接啟發(fā)式優(yōu)化的經典算法，但它經常陷入局部最優(yōu)，本文在GMC算法的基礎上利用啟發(fā)式規(guī)則構建局部最優(yōu)二叉樹，并最終重新連接查詢樹來進一步優(yōu)化查詢序列.

2 問題描述

我們給出形式化定義：對于輸入的連接操作關系序列R1R2…Rn，|R|表示關系的個數(shù)，即關系序列的勢.對于每個關系R，它對應的屬性X，用|X|表示屬性X的勢.Cost(R1∞R2)表示R1和R2的連接代價.

問題目標：對于連接操作關系序列R1R2…Rn，選擇某個連接順序使得Cost(R1∞R2∞…∞Rn)最小.

為方便描述我們給出幾個定義和引理.

定義1Cost(R1∞R2)=|R1|+|R2|+|R1∞R2|，它表示關系R1和R2的連接代價.其中|R1∞R2|=|R1|×|R2|/∏p|Xi|，Xi是關系R1和R2的連接屬性.

引理1|R1∞R2∞R3|=|Ri∞Rj∞Rk|，其中i，j，k是1，2，3的置換.

引理 2Cost(R1∞R2∞R3)≠Cost(R3∞R1∞R2)≠Cost (Ri∞Rj∞Rk)，其中i,j,k表示三個不相同的數(shù)，且Cost(Ri∞Rj)=Cost(Rj∞Ri)

定義2G=（V，E），它表示關系的連接查詢圖，其中E表示連接查詢圖的邊（表示兩個頂點的連接屬性）.V表示連接查詢圖的頂點，它是關系R的集合.

我們的二叉樹算法是基于GMC算法基礎上改進的.其中GMC算法的偽代碼是：（1）遍歷G中的每個節(jié)點，對于每對節(jié)點R1和R2，計算他們的代價Cost(R1∞R2)，并尋找出最小值的兩個節(jié)點R1和R2.（2）將這對節(jié)點合并，并用一個新的節(jié)點替代，并重新對這個節(jié)點賦予它的勢，利用這個新節(jié)點重新更新這個圖.（3）一直重復步驟（1）和（2）直到G最終變?yōu)橐粋€點.（4）輸出步驟（1）和步驟（2）生成的合并序列.

下面給出GMC算法計算出的一個連接序列實例.表1表示輸入的連接圖G，表2給出輸出的連接序列.

如果將2048游戲看成兩個人的博弈，玩家會選擇向某一方向移動來使游戲獲取更高的分數(shù)，而作為玩家對手的電腦則會選擇隨機生成一個數(shù)字來影響我的選擇。我們無法判斷對手的好壞，所以玩家在當前情況下冒著極大風險選擇的獲取最高分數(shù)的方向，可能沒有影響，但也可能因為對手的妙手而萬劫不復，所以游戲獲勝的最佳策略是將對手看的極其聰明，即假設電腦每一步生成的數(shù)字都是最壞的情況來保證目前選擇不會變得更糟糕，而玩家選擇的策略不應利益最大，而是以不會出現(xiàn)意外為主。

表1（a） 輸入序列頂點勢

表1（b） 輸入序列邊的勢

表2（a） 輸出序列頂點勢

表2（b） 輸出序列邊的勢

3 改進的二叉樹啟發(fā)式算法:

改進的二叉樹啟發(fā)式算法主要思想是在GMC算法生成二叉樹的基礎上，通過啟發(fā)式規(guī)則擴大節(jié)點的計算規(guī)模，構造極大局部最優(yōu)二叉樹.

下面我們給出改進的二叉樹啟發(fā)式算法的偽代碼：

(1)輸入連接圖G，利用GMC算法生成一顆二叉樹T.二叉樹非葉節(jié)點表示連接合并的新關系.二叉樹的葉節(jié)點表示關系.

(2)輸入設定參數(shù)m，對于二叉樹T中所有葉子節(jié)點數(shù)不超過m的每個子樹T'，使用啟發(fā)式規(guī)則求子樹T'的最優(yōu)子樹T'optimal.其中對于參數(shù)m的設定，要求改進算法的復雜度與GMC的復雜度相同，皆為o(n3).

(3)將把步驟2得到T'optimal下所有的葉子節(jié)點合并為一個新的葉節(jié)點，重新更新連接圖G.

(4)循環(huán)步驟2和3，直到G成為一個節(jié)點.

(5)輸出步驟2和步驟3生成的二叉樹序列.

4 算法分析和實驗

首先我們從理論證明改進的二叉樹啟發(fā)式算法優(yōu)于GMC算法.

定理1二叉樹啟發(fā)式算法的解優(yōu)于GMC生成的解.

為方便證明我們給出幾個定義.

定義3T(x1,x2…xm)，它表示一顆二叉樹，T為二叉樹的根，x表示二叉樹的葉節(jié)點.

證明定理1：

由二叉樹啟發(fā)式算法的步驟1可知，我們的二叉樹是由GMC算法建立的.而算法步驟2中的保證與GMC相同時間復雜度的基礎上，通過擴充節(jié)點的計算更大規(guī)模節(jié)點的最優(yōu)子樹.故步驟2也保證得到的結果優(yōu)于GMC生成的解.同時步驟2中參數(shù)m的設定，使得二叉樹啟發(fā)式算法和GMC具有相同的時間復雜度.故二叉樹啟發(fā)式算法的解優(yōu)于.即定理1得證.

接著我們通過實驗來驗證二叉樹啟發(fā)式算法的有效性.我們結合實際的系統(tǒng)通過仿真實驗來對比GMC算法和改進二叉樹啟發(fā)式算法（以下簡稱二叉算法），為更好的對比我們給出全局最優(yōu)解.圖1給出兩種算法和最優(yōu)解的連接代價趨勢圖.表3給出三種解的對比表.

表3 三種算法的連接代價對比表

圖1 兩種不同策略和最優(yōu)解代價趨勢圖

從表3的實驗結果可以看出，二叉算法優(yōu)于GMC算法，當連接關系的數(shù)目越大時，二叉算法比GMC算法更接近最優(yōu)解.從圖1也可以看出隨著問題規(guī)模越來越大，二叉算法的優(yōu)勢比GMC越來越明顯.

5 結論

本文提出的改進的二叉樹啟發(fā)式算法.它借助GMC算法，并利用啟發(fā)式規(guī)則構建局部最優(yōu)二叉樹，最終得到優(yōu)化查詢序列.并通過理論和實驗證明二叉啟發(fā)式算法能在同為的時間復雜度下取得更好的解，但文章的算法時間復雜度還是n的三次方，以后將嘗試更低的時間復雜度來提升查詢效率.

〔1〕胡楓.一種分布式數(shù)據(jù)庫多元連接查詢優(yōu)化算法及改進[J].計算機工程與應用，2011（16）:125-127.

〔2〕郭麗英.數(shù)據(jù)庫中查詢重寫及基于遺傳算法的多連接查詢優(yōu)化研究[D].沈陽:東北大學,2008.

〔3〕Zheng X'Chen H,Wu Z,et al.Dynamie query optimization approach for semantic database grid[J].Joumal of Computer Seience and Technology,2006(4):67-73.

〔4〕高軍,唐世渭,楊冬青，等.半結構化數(shù)據(jù)查詢重寫[J].計算機研究與發(fā)展,2002,39(2):165-171.

〔5〕陳勇旭，陳夢杰，劉雪冰，宋杰.基于MapReduce的連接聚集查詢算法研究[J].計算機研究與發(fā)展，2013(S1).

〔6〕李文俊，張愛林.數(shù)據(jù)庫多表查詢優(yōu)化技術[J].計算機系統(tǒng)應用，2014(06).

〔7〕畢鑫，王國仁，趙相國，袁野，張盼.XML數(shù)據(jù)中Twig查詢處理與優(yōu)化技術研究綜述[J].計算機科學與探索，2013 (09).

〔8〕陳迎暉，俞軍.分布式異構數(shù)據(jù)庫查詢優(yōu)化方法的研究[J].微計算機信息，2009(12).

〔9〕夏剛，劉林靜，樓文高.基于Schema的XML混合編碼索引查詢技術[J].計算機應用與軟件，2016(02).

〔10〕張愛民.一種面向深層網(wǎng)絡的查詢優(yōu)化方法研究[D].哈爾濱工程大學，2012.

〔11〕Ming-Syan Chen,Senior.Optimization of Parallel Execution for Multi-join Queries.IEEE Transactions on Knowledge and Data Engineering,416～428.1996.

TP301.6

A

1673-260X（2017）02-0038-02

2016-10-22

福建省教育廳A類科技項目（JA15443）；莆田市科技項目（2014G16）