【摘 要】數(shù)據(jù)庫(kù)系統(tǒng)在實(shí)際工作中應(yīng)用非常廣泛，對(duì)數(shù)據(jù)庫(kù)進(jìn)行查詢(xún)優(yōu)化對(duì)推動(dòng)計(jì)算機(jī)技術(shù)的發(fā)展具有十分重要的意義。并行數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化的研究主要圍繞具有多個(gè)JOIN操作的復(fù)雜關(guān)系數(shù)據(jù)庫(kù)查詢(xún)的優(yōu)化問(wèn)題進(jìn)行，本文主要對(duì)并行數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化技術(shù)進(jìn)行探索。

【關(guān)鍵詞】查詢(xún)優(yōu)化；并行數(shù)據(jù)庫(kù)；語(yǔ)義查詢(xún)；機(jī)群

1 引言

并行數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化主要圍繞具有多個(gè)JOIN 操作的復(fù)雜關(guān)系數(shù)據(jù)庫(kù)查詢(xún)（簡(jiǎn)稱(chēng)MJ查詢(xún)）的優(yōu)化問(wèn)題進(jìn)行研究。1990年，Schneider等研究了查詢(xún)樹(shù)模型，提出了左線(xiàn)性樹(shù)（Left-Deep Trees）、右線(xiàn)性樹(shù)（RIGHT-Deep Trees）和濃密樹(shù)（Bushy Trees）的概念。一個(gè)MJ查詢(xún)可以表示為一個(gè)查詢(xún)樹(shù)T=（V，E），其中V是結(jié)點(diǎn)集合，E是邊集合。每個(gè)葉子結(jié)點(diǎn)表示一個(gè)關(guān)系，每個(gè)內(nèi)結(jié)點(diǎn)表示一個(gè)JOIN操作，同時(shí)表示這個(gè)JOIN操作的結(jié)果關(guān)系，每條邊表示一個(gè)JOIN操作，JOIN謂詞也可以由邊來(lái)表示，即MJ查詢(xún)的查詢(xún)樹(shù)是一個(gè)二叉樹(shù)。查詢(xún)樹(shù)分為三類(lèi)左線(xiàn)性樹(shù)、右線(xiàn)性樹(shù)和濃密樹(shù)。

語(yǔ)義查詢(xún)優(yōu)化技術(shù)，將一個(gè)查詢(xún)變換成一個(gè)或數(shù)個(gè)語(yǔ)義等價(jià)的查詢(xún)，進(jìn)而尋找并執(zhí)行這些等價(jià)查詢(xún)中具有較好實(shí)現(xiàn)策略的一個(gè)；基于遺傳算法的并行優(yōu)化算法主要是基于機(jī)群并行數(shù)據(jù)庫(kù)中關(guān)系存儲(chǔ)的選擇、多連接查詢(xún)優(yōu)化和查詢(xún)處理等關(guān)鍵技術(shù)。

2 左線(xiàn)性樹(shù)查詢(xún)優(yōu)化算法（簡(jiǎn)稱(chēng)LDT算法）

LDT方法把兩個(gè)JOIN關(guān)系分為內(nèi)關(guān)系和外關(guān)系，把HASH-JOIN分為BUILD和PROBE兩個(gè)基本操作，BUILD操作掃描內(nèi)關(guān)系，建立HASH表；PROBE操作掃描外關(guān)系，搜索匹配HASH表，完成JOIN操作。具體算法如下：

（1）搜索給定MJ查詢(xún)的左線(xiàn)性樹(shù)空間，選擇具有最小響應(yīng)時(shí)間的優(yōu)化左線(xiàn)性樹(shù)T；

（2）由T產(chǎn)生數(shù)據(jù)相關(guān)圖DG；

（3）根據(jù)DG產(chǎn)生優(yōu)化并行查詢(xún)執(zhí)行計(jì)劃P；

（4）運(yùn)行優(yōu)化查詢(xún)計(jì)劃P。

3 右線(xiàn)性樹(shù)的查詢(xún)優(yōu)化算法

由于MJ查詢(xún)的左線(xiàn)性樹(shù)優(yōu)化并行查詢(xún)算法最多只允許兩個(gè)JOIN操作并行執(zhí)行，存在明顯局限性。為此，Schneider等研究了基于右線(xiàn)性樹(shù)的MJ查詢(xún)優(yōu)化問(wèn)題，并給出了基于右線(xiàn)性樹(shù)的查詢(xún)化化算法（簡(jiǎn)稱(chēng)RDT算法）。該算法類(lèi)似于LDT算法，RDT算法產(chǎn)生的查詢(xún)執(zhí)行計(jì)劃具有相當(dāng)高的并行性，所以N個(gè)JOIN操作皆可并行執(zhí)行。

該算法基本思想是：在BUILD階段，每個(gè)JOIN關(guān)系被分成兩部分，一部分進(jìn)入內(nèi)存，建立HASH表，另一部分留駐外存，等以后處理；在PROBE階段，每個(gè)JOIN操作的結(jié)果也被分成兩部分，一部分直接用來(lái)進(jìn)行下一個(gè)JOIN操作的PROBE處理，另一部分存入外存，等以后處理。

4 基于濃密樹(shù)的查詢(xún)優(yōu)化算法

濃密樹(shù)GBT（General-Bushy-Tree）的MJ查詢(xún)優(yōu)化算法的查詢(xún)計(jì)劃分為同步和非同步兩類(lèi)。在同步查詢(xún)計(jì)劃中，一個(gè)MJ查詢(xún)的處理過(guò)程劃分為多個(gè)同步執(zhí)行階段，各個(gè)同步執(zhí)行階段順序執(zhí)行。在每一同步執(zhí)行階段，多個(gè)JOIN操作并行執(zhí)行，其他的查詢(xún)計(jì)劃稱(chēng)為非同步執(zhí)行計(jì)劃。

文獻(xiàn)[2]以同步執(zhí)行計(jì)劃為目標(biāo)，提出了三種產(chǎn)生優(yōu)化同步執(zhí)行計(jì)劃的啟發(fā)工MJ查詢(xún)優(yōu)化算法，第一個(gè)算法稱(chēng)之為GP算法，是一種貪心算法，算法思想核心是同步執(zhí)行段的劃分，循環(huán)地為每一同步執(zhí)行階段選擇盡量多的可并行執(zhí)行的JOIN操作。該算法時(shí)間復(fù)雜性較大，為解決此問(wèn)題，繼而提出算法GPt，它僅產(chǎn)生如下類(lèi)型的計(jì)劃：只有第一同步執(zhí)行階段并行執(zhí)行多個(gè)JOIN，其余同步執(zhí)行階段僅執(zhí)行一個(gè)JOIN操作。

GBT查詢(xún)優(yōu)化方法具備了很高的并行性，但該執(zhí)行計(jì)劃空間十分龐大，因此查詢(xún)優(yōu)化算法的開(kāi)銷(xiāo)也非常大。

5 語(yǔ)義查詢(xún)優(yōu)化方法

語(yǔ)義查詢(xún)比較有趣，它不同于上述優(yōu)化方法。所謂語(yǔ)義優(yōu)化是指對(duì)一指定的查詢(xún)問(wèn)題，寫(xiě)出不同的查詢(xún)語(yǔ)句，從中挑出DBMS能夠?yàn)橹业阶罡咝?shí)現(xiàn)方法的語(yǔ)句。據(jù)統(tǒng)計(jì)，語(yǔ)義完整性規(guī)則可能占一個(gè)數(shù)據(jù)庫(kù)系統(tǒng)的概念模式描述內(nèi)容的80%。

語(yǔ)義優(yōu)化的實(shí)現(xiàn)，遵照以下步驟：確立約束目標(biāo)，即確定對(duì)哪些關(guān)系應(yīng)增加補(bǔ)充約束或者引入索引，或者引入、刪除哪些關(guān)系；選擇完整性約束；產(chǎn)生屬性上的新約束；約束合并；查詢(xún)約束的消除；形成等價(jià)的語(yǔ)義查詢(xún)。有文獻(xiàn)的對(duì)比實(shí)驗(yàn)表明，利用語(yǔ)義完整性規(guī)則進(jìn)行查詢(xún)優(yōu)化，能夠顯著地提高效率。

6 遺傳算法

遺傳算法（Genetic Algorithm，GA）是近年發(fā)展起來(lái)的一種嶄新的全局優(yōu)化算法，1962年由Holland教授首次提出，它借用了生物遺傳學(xué)的觀點(diǎn)，通過(guò)自然選擇、遺傳、變異等作用機(jī)制，實(shí)現(xiàn)各個(gè)個(gè)體的適應(yīng)性的提高。這一點(diǎn)體現(xiàn)了自然界中“物競(jìng)天擇、適者生存”的進(jìn)化過(guò)程。

傳統(tǒng)的遺傳算法中有關(guān)并行調(diào)度的討論和代價(jià)估算是基于無(wú)共享資源的體系結(jié)構(gòu)，首先，關(guān)系的分布算法在選擇關(guān)系的分布屬性、分布方式和處理機(jī)集合時(shí)，充分考慮了機(jī)群系統(tǒng)中引起數(shù)據(jù)重分布的因素，減少了額外的通信開(kāi)銷(xiāo)；同時(shí)兼顧了并行系統(tǒng)中的三種并行。其次，查詢(xún)優(yōu)化部分，提出了基于遺傳算法的機(jī)群環(huán)下多連接查詢(xún)的并行優(yōu)化算法（簡(jiǎn)稱(chēng)BGA）。該算法研究了資源分配在查詢(xún)執(zhí)行代價(jià)估算中的作用和方法，提高了查詢(xún)優(yōu)化的效優(yōu)選法。與此同時(shí)，為了節(jié)省風(fēng)絡(luò)通信的開(kāi)銷(xiāo)，查詢(xún)計(jì)劃代價(jià)模型的計(jì)算將網(wǎng)絡(luò)的通信代價(jià)考慮在內(nèi)，充分利用了查詢(xún)中各關(guān)系的物理存儲(chǔ)信息，減小了不必要的通信開(kāi)銷(xiāo)。

7 結(jié)論

傳統(tǒng)的并行數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化技術(shù)有基于左線(xiàn)性樹(shù)、右線(xiàn)性樹(shù)、濃密樹(shù)、操作森林的并行數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化，各有優(yōu)劣。目前使用的遺傳算法進(jìn)行查詢(xún)優(yōu)化的方法中，我們認(rèn)為仍存在兩個(gè)問(wèn)題：（1）在估算查詢(xún)計(jì)劃的代價(jià)時(shí)，沒(méi)有考慮資源的分配情況，數(shù)據(jù)操作間的并行性得不到充分的開(kāi)發(fā)；（2）在無(wú)共享體系結(jié)構(gòu)的查詢(xún)優(yōu)化中，沒(méi)有考慮網(wǎng)絡(luò)的通信代價(jià)，無(wú)法避免額外的通信開(kāi)銷(xiāo)。

算法研究方面，遺傳算法才剛起步，A算法、A*算法、模擬退火算法、神經(jīng)網(wǎng)絡(luò)算法在計(jì)算機(jī)的諸多方面都取得了巨大的成績(jī)，但在并行數(shù)據(jù)庫(kù)的查詢(xún)優(yōu)化方面基本還是一個(gè)空白，仍需積極探索。

參考文獻(xiàn)

[1]厲陽(yáng)春.基于線(xiàn)性濃密樹(shù)的并行數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化算法[J].湖南理工學(xué)院學(xué)報(bào)：自然科學(xué)版，2006，19（1）：20-23

[2]玄萍.并行數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化的遺傳算法[R].哈爾濱：黑龍江大學(xué)，2004

[3]許新華，胡世港，唐勝群等.數(shù)據(jù)查詢(xún)優(yōu)化技術(shù)的歷史、現(xiàn)狀與未來(lái)[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（18）：156-161

作者簡(jiǎn)介：譚玲麗，女，湖北武漢人。漢族。碩士。武漢東湖學(xué)院計(jì)算機(jī)科學(xué)學(xué)院，講師。研究方向：軟件工程，數(shù)據(jù)庫(kù)技術(shù)。