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

黃海

（莆田學(xué)院 信息工程學(xué)院，福建 莆田 351100）

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

黃海

（莆田學(xué)院 信息工程學(xué)院，福建 莆田 351100）

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

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

1 引言

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

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

2 問題描述

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

問題目標(biāo)：對(duì)于連接操作關(guān)系序列R1R2…Rn，選擇某個(gè)連接順序使得Cost(R1∞R2∞…∞Rn)最小.

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

定義1Cost(R1∞R2)=|R1|+|R2|+|R1∞R2|，它表示關(guān)系R1和R2的連接代價(jià).其中|R1∞R2|=|R1|×|R2|/∏p|Xi|，Xi是關(guān)系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表示三個(gè)不相同的數(shù)，且Cost(Ri∞Rj)=Cost(Rj∞Ri)

定義2G=（V，E），它表示關(guān)系的連接查詢圖，其中E表示連接查詢圖的邊（表示兩個(gè)頂點(diǎn)的連接屬性）.V表示連接查詢圖的頂點(diǎn)，它是關(guān)系R的集合.

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

下面給出GMC算法計(jì)算出的一個(gè)連接序列實(shí)例.表1表示輸入的連接圖G，表2給出輸出的連接序列.

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

表1（a） 輸入序列頂點(diǎn)勢(shì)

表1（b） 輸入序列邊的勢(shì)

表2（a） 輸出序列頂點(diǎn)勢(shì)

表2（b） 輸出序列邊的勢(shì)

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

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

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

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

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

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

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

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

4 算法分析和實(shí)驗(yàn)

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

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

為方便證明我們給出幾個(gè)定義.

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

證明定理1：

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

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

表3 三種算法的連接代價(jià)對(duì)比表

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

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

5 結(jié)論

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

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

〔2〕郭麗英.數(shù)據(jù)庫(kù)中查詢重寫及基于遺傳算法的多連接查詢優(yōu)化研究[D].沈陽(yáng):東北大學(xué),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〕高軍,唐世渭,楊冬青，等.半結(jié)構(gòu)化數(shù)據(jù)查詢重寫[J].計(jì)算機(jī)研究與發(fā)展,2002,39(2):165-171.

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

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

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

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

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

〔10〕張愛民.一種面向深層網(wǎng)絡(luò)的查詢優(yōu)化方法研究[D].哈爾濱工程大學(xué)，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類科技項(xiàng)目（JA15443）；莆田市科技項(xiàng)目（2014G16）