摘要：由于數(shù)據(jù)量巨大，梅沙系統(tǒng)的數(shù)據(jù)存儲(chǔ)在分布式數(shù)據(jù)庫(kù)中，受限于系統(tǒng)落后的查詢策略，在查詢過(guò)程中經(jīng)常碰到延時(shí)等待甚至死機(jī)的狀況，本文主要采用CGA算法（compact genetic algorithm，緊湊遺傳算法）針對(duì)梅沙系統(tǒng)中的分布式數(shù)據(jù)庫(kù)查詢優(yōu)化進(jìn)行研究，通過(guò)引入CGA算法進(jìn)一步提高梅沙系統(tǒng)查詢效率。

關(guān)鍵詞：梅沙系統(tǒng)；分布式數(shù)據(jù)庫(kù)；緊湊遺傳算法

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 （2012） 15-0000-02

梅沙系統(tǒng)是全國(guó)邊防檢查工作第四代綜合管理系統(tǒng)，梅沙系統(tǒng)通過(guò)與國(guó)家基礎(chǔ)數(shù)據(jù)庫(kù)共享數(shù)據(jù)，可以實(shí)現(xiàn)信息查詢、檔案查詢、證件發(fā)放、執(zhí)法辦案等程序，真正實(shí)現(xiàn)了居民出入境邊防檢查工作的智能化、電子化管理。

1 梅沙系統(tǒng)數(shù)據(jù)查詢的不足

在梅沙系統(tǒng)對(duì)居民身份進(jìn)行查詢的過(guò)程中的出入境人員資料、證件簽發(fā)資料、居民身份證資料、在控人員資料等在國(guó)家各級(jí)數(shù)據(jù)庫(kù)、公安部數(shù)據(jù)庫(kù)、各省市出入境部門都有備份。即數(shù)據(jù)在分布式數(shù)據(jù)庫(kù)節(jié)點(diǎn)中有多個(gè)備份，在系統(tǒng)查詢時(shí)需要從適合的數(shù)據(jù)節(jié)點(diǎn)選擇數(shù)據(jù)表進(jìn)行連接查詢。目前梅沙系統(tǒng)所使用的策略是根據(jù)區(qū)域最近原則選擇“最近”數(shù)據(jù)庫(kù)節(jié)點(diǎn)中的數(shù)據(jù)表進(jìn)行連接，這種數(shù)據(jù)表連接方式由于數(shù)據(jù)庫(kù)繁忙、網(wǎng)絡(luò)阻塞、網(wǎng)絡(luò)故障等原因，區(qū)域最近很可能并不是查詢代價(jià)最小，因此難以實(shí)現(xiàn)查詢效率的最優(yōu)。為了解決這個(gè)問(wèn)題，就需要對(duì)系統(tǒng)中的數(shù)據(jù)庫(kù)節(jié)點(diǎn)進(jìn)行動(dòng)態(tài)分析，通過(guò)分析查詢語(yǔ)句的連接樹，查找數(shù)據(jù)庫(kù)查詢代價(jià)最小的最優(yōu)解，實(shí)現(xiàn)數(shù)據(jù)庫(kù)查詢效率最優(yōu)。

目前，國(guó)內(nèi)外許多專家學(xué)者都針對(duì)分布式數(shù)據(jù)庫(kù)查詢優(yōu)化問(wèn)題進(jìn)行了研究。并且通過(guò)研究表明，在類似梅沙系統(tǒng)這種需要對(duì)大量數(shù)據(jù)庫(kù)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)查詢的系統(tǒng)中，采用遺傳算法進(jìn)行數(shù)據(jù)庫(kù)查詢優(yōu)化是一個(gè)不錯(cuò)的選擇[3]，但是大量數(shù)據(jù)庫(kù)節(jié)點(diǎn)的連續(xù)編碼會(huì)造成存儲(chǔ)空間的耗費(fèi)。為此，本文主要采用CGA（compact genetic algorithm，緊湊遺傳算法）來(lái)對(duì)梅沙系統(tǒng)中數(shù)據(jù)查詢的實(shí)現(xiàn)和優(yōu)化進(jìn)行研究。

2 基于CGA算法的梅沙系統(tǒng)查詢優(yōu)化策略

CGA與傳統(tǒng)遺傳算法最大不同之處在于：CGA算法可以降低連續(xù)編碼時(shí)的空間耗費(fèi)。而CGA算法的實(shí)現(xiàn)流程與傳統(tǒng)遺傳算法實(shí)現(xiàn)流程類似：

2.1 確定編碼方案

編碼方法的好壞是決定CGA算法是否成功的關(guān)鍵因素。在梅沙系統(tǒng)分布式數(shù)據(jù)庫(kù)中，使用連接樹的形式來(lái)表示多連接表達(dá)式。但是，由于連接樹不僅表示了表之間的連接關(guān)系，同時(shí)還表示了樹的形狀，因此為了保留連接樹的特征，不能夠使用簡(jiǎn)單的二進(jìn)制編碼方式，而應(yīng)該采用形式編碼對(duì)連接樹進(jìn)行編碼，其中用0表示連接樹中的非葉子節(jié)點(diǎn)，而用序號(hào)表示葉子節(jié)點(diǎn)編號(hào)。例如在查詢語(yǔ)句Q=（A∞B）and（B∞C）and（C∞D(zhuǎn)）and（D∞E）and（D∞F）中，連接樹的形式編碼如圖2-1所示：

通過(guò)將連接樹編碼之后，則可以用（0，0，0，0，1，2，3，0，4，5，6）字符串與連接樹一一對(duì)應(yīng)，有利于在CGA算法中隊(duì)連接樹進(jìn)行各種變形操作。

2.2 設(shè)定遺傳算子

在梅沙系統(tǒng)數(shù)據(jù)查詢過(guò)程中，采用屬性編碼來(lái)表示數(shù)據(jù)查詢時(shí)的數(shù)據(jù)表連接，而傳統(tǒng)遺傳算法中的交叉算子和變異算子并不能夠滿足樹形結(jié)構(gòu)，因此這兩個(gè)遺傳算子需要重新進(jìn)行定義。

2.2.1 選擇算子

在梅沙系統(tǒng)中，采用了最優(yōu)保存策略來(lái)進(jìn)行分布式數(shù)據(jù)庫(kù)的查詢優(yōu)化。即淘汰當(dāng)前種群中代價(jià)最大的個(gè)體，并且保證代價(jià)最小個(gè)體不參加變異和交叉運(yùn)算，從而保證CGA算法的收斂性。

2.2.2 交叉算子

由于算法中的個(gè)體代表了一個(gè)表示數(shù)據(jù)表連接表達(dá)式的樹形結(jié)構(gòu)，因此簡(jiǎn)單的較差可能會(huì)導(dǎo)致得到的個(gè)體不能組成一個(gè)二叉樹。因此，需要將算法中的兩個(gè)個(gè)體中的等大小字?jǐn)?shù)進(jìn)行交換。但是在交叉之后，有可能會(huì)導(dǎo)致基因的重復(fù)，因此在交叉之后還需要進(jìn)行再次加工來(lái)完成個(gè)體之間基因的交叉。

2.2.3 變異算子

與交叉算子相同，個(gè)體變異之后必須也是一個(gè)表示一個(gè)數(shù)據(jù)表連接的二叉樹，因此，為了保證樹形不變，只進(jìn)進(jìn)行連接樹的葉節(jié)點(diǎn)交換，而樹中的根節(jié)點(diǎn)不進(jìn)行交換。

2.3 確定代價(jià)函數(shù)

梅沙系統(tǒng)的分布式數(shù)據(jù)庫(kù)時(shí)建立在計(jì)算機(jī)網(wǎng)絡(luò)上的，而不同的網(wǎng)絡(luò)模型對(duì)查詢的優(yōu)化有很大的影響。國(guó)家基礎(chǔ)數(shù)據(jù)庫(kù)采用結(jié)構(gòu)廣播式網(wǎng)絡(luò)模型，各個(gè)數(shù)據(jù)庫(kù)節(jié)點(diǎn)可以同時(shí)訪問(wèn)任意數(shù)量的數(shù)據(jù)庫(kù)節(jié)點(diǎn)，而且訪問(wèn)的通信費(fèi)用與訪問(wèn)的數(shù)據(jù)庫(kù)節(jié)點(diǎn)數(shù)量無(wú)關(guān)。因此，一個(gè)數(shù)據(jù)庫(kù)節(jié)點(diǎn)發(fā)送X個(gè)字節(jié)給另外一個(gè)數(shù)據(jù)庫(kù)節(jié)點(diǎn)的通信費(fèi)用可以表示為：C[X]=C0+C1*X，其中C0和C1是只與網(wǎng)絡(luò)有關(guān)的常數(shù)。

2.4 確定適度函數(shù)

由于分布式數(shù)據(jù)庫(kù)之間的節(jié)點(diǎn)采用高速光纖通信，因此查詢的時(shí)間主要是數(shù)據(jù)庫(kù)對(duì)查詢的響應(yīng)時(shí)間，而數(shù)據(jù)在網(wǎng)絡(luò)中傳輸時(shí)間代價(jià)可以忽略不計(jì)。同時(shí)，在每一個(gè)數(shù)據(jù)庫(kù)節(jié)點(diǎn)中都包含有大量的數(shù)據(jù)，不能將參加連接的數(shù)據(jù)表一次全部裝入內(nèi)存中，因此數(shù)據(jù)庫(kù)對(duì)查詢的響應(yīng)時(shí)間主要由I/O時(shí)間。除此之外，在針對(duì)分布式數(shù)據(jù)庫(kù)的查詢中，每一個(gè)染色體都是一個(gè)連接樹，有可能在染色體交叉和變異之后所新生成的染色體不存在公共屬性，從而導(dǎo)致查詢代價(jià)急劇上升，在這種情況下，需要給查詢代價(jià)增加一個(gè)懲罰值。最后，在CGA算法中確定一個(gè)染色體的查詢代價(jià)表示為：fitness=cost+penalty；其中fitness表示連接樹的適應(yīng)度，cost表示兩個(gè)子樹的查詢代價(jià)，penalty為懲罰值。

2.5 確定終止準(zhǔn)則

由于CGA是一個(gè)循環(huán)的過(guò)程，因此需要確定循環(huán)終止的準(zhǔn)則。在梅沙系統(tǒng)設(shè)計(jì)中，主要通過(guò)以下兩種方法來(lái)控制CGA算法的執(zhí)行：

2.5.1 最優(yōu)規(guī)則

即在算法執(zhí)行時(shí)給定一個(gè)閾值，當(dāng)某個(gè)染色體的fitness小于閾值時(shí)，CGA算法結(jié)束，并且選定該染色體為最優(yōu)解。

2.5.2 執(zhí)行最大數(shù)

即給定一個(gè)閾值，當(dāng)CGA算法的循環(huán)次數(shù)大于或等于這個(gè)閾值時(shí)，CGA算法結(jié)束，并且選定當(dāng)前群集中fitness最小的染色體為最優(yōu)解。

3 CGA算法設(shè)計(jì)

在分布式數(shù)據(jù)庫(kù)查詢中，由于存在符合一個(gè)表在多個(gè)數(shù)據(jù)庫(kù)節(jié)點(diǎn)中存在副本等問(wèn)題，這要求我們對(duì)副本進(jìn)行選擇，使得查詢代價(jià)最小。其步驟是：首先將用戶查詢進(jìn)行分解，然后利用本文前面所述的查詢策略來(lái)進(jìn)行優(yōu)化，找到查詢代價(jià)最小的數(shù)據(jù)表選擇集合。其具體的流程如圖3-1所示：

CGA算法實(shí)現(xiàn)流程如下：

（1）系統(tǒng)初始化，設(shè)定初始種群數(shù)、設(shè)定fitness閾值stopstandard、設(shè)定循環(huán)次數(shù)閾值m、設(shè)置當(dāng)前循環(huán)數(shù)k=0、隨機(jī)生成n棵連接樹。（2）如果當(dāng)前種群中存在染色體的fitness小于設(shè)定的stopstandard，或者當(dāng)循環(huán)次數(shù)大于閾值時(shí)，轉(zhuǎn)到第四步，否則執(zhí)行第三步。（3）保留一定數(shù)量的最優(yōu)個(gè)體不變，將其它個(gè)體進(jìn)行交叉和變異，轉(zhuǎn)到第二步。（4）選取當(dāng)前種群中fitness最小的染色體作為最終的查詢連接樹。

4 結(jié)束語(yǔ)

在梅沙系統(tǒng)的數(shù)據(jù)庫(kù)查詢過(guò)程中，國(guó)家基礎(chǔ)信息庫(kù)中的數(shù)據(jù)呈分布式存儲(chǔ)，通過(guò)若干仿真實(shí)驗(yàn)對(duì)比分析運(yùn)用CGA算法和傳統(tǒng)算法在處理梅沙系統(tǒng)分布式數(shù)據(jù)庫(kù)查詢優(yōu)化問(wèn)題上的性能，結(jié)果證明采用CGA算法進(jìn)一步提高了查詢效率，在算法中采用了連續(xù)編碼方式來(lái)降低存儲(chǔ)空間的耗費(fèi)，實(shí)現(xiàn)了通過(guò)減少I/O操作來(lái)提高查詢效率，因此可以認(rèn)為我們的CGA梅沙系統(tǒng)查詢算法是CGA在梅沙系統(tǒng)分布式存儲(chǔ)查詢問(wèn)題中的一個(gè)成功應(yīng)用。

參考文獻(xiàn)：

[1]聶文燕. SQLServer數(shù)據(jù)查詢的優(yōu)化方法[J].中國(guó)新技術(shù)新產(chǎn)品，2006（4），67-69

[2]雷宏偉，王魁生，屈展.基于SQL的關(guān)系數(shù)據(jù)查詢優(yōu)化策略[J].北京電子科技學(xué)院學(xué)報(bào)，2004，12（2），14-18

[3]邵佩英.分布式數(shù)據(jù)庫(kù)系統(tǒng)及應(yīng)用.科學(xué)出版社，2000

[4]曾偉全.科技強(qiáng)警促通關(guān).中國(guó)國(guó)門時(shí)報(bào)，2009，13-14

[5]施國(guó)君.連續(xù)型CGA算法的研究，上海交通大學(xué)計(jì)算機(jī)技術(shù)與應(yīng)用[D].上海交通大學(xué)計(jì)算機(jī)學(xué)院碩士論文，2008（12）

[6]王文川，程春田，徐冬梅.基于混沌遺傳算法的水電站優(yōu)化調(diào)度模型及應(yīng)用[J].水力發(fā)電學(xué)報(bào)，2007（06），7-11

[7]顏穎，緱錦.改進(jìn)的模糊交叉算子及其在CGA中的應(yīng)用[J].計(jì)算機(jī)工程，2008 （05），176-178