張逸風(fēng)，佟國香，劉 軍，屈亞寧

(1.上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093；2.山東山大華天軟件有限公司，山東 濟(jì)南 250000)

1 引言

產(chǎn)品生命周期管理PLM(Product Lifecycle Management)是支持產(chǎn)品信息創(chuàng)建、管理、分發(fā)和應(yīng)用的一系列方案。PLM的核心技術(shù)之一是面向產(chǎn)品全生命周期的數(shù)據(jù)建模技術(shù)。目前PLM系統(tǒng)主要以文檔管理為主，很難解決異構(gòu)平臺(tái)、跨單位、跨階段和跨領(lǐng)域開發(fā)時(shí)的數(shù)據(jù)交互問題，因此，研發(fā)基于模型數(shù)據(jù)庫的復(fù)雜產(chǎn)品全生命周期模型管理原型系統(tǒng)PLMM(Product Lifecycle Management of Model)成為工業(yè)4.0時(shí)代大趨勢(shì)。而產(chǎn)品生命周期中的概念產(chǎn)生、產(chǎn)品設(shè)計(jì)、采購、生產(chǎn)制造、銷售和服務(wù)等各個(gè)階段的數(shù)據(jù)不僅數(shù)據(jù)量大，且相互關(guān)聯(lián)錯(cuò)綜復(fù)雜，目前主流的關(guān)系型數(shù)據(jù)庫和數(shù)據(jù)倉庫都可以作為PLM系統(tǒng)的數(shù)據(jù)服務(wù)支持平臺(tái)。由于PLM系統(tǒng)的數(shù)據(jù)庫結(jié)構(gòu)的復(fù)雜度高，數(shù)據(jù)信息具有多樣性，將數(shù)據(jù)抽象為模型后，模型之間的關(guān)聯(lián)關(guān)系越來越復(fù)雜，耦合性越來越高等諸多因素降低了數(shù)據(jù)檢索的效率，因此，選擇合適的連接查詢算法[1]尤為重要。

在傳統(tǒng)聯(lián)機(jī)事務(wù)處理OLTP(On-Line Transaction Processing)[2]的多表連接查詢方式中，Hash Join[3]是近些年研究人員改進(jìn)得最多的連接查詢算法。因?yàn)槠浞€(wěn)定性和有效性，自誕生以來研究人員就嘗試從各方面對(duì)其進(jìn)行改進(jìn)。文獻(xiàn)[4]介紹了一種散列合并連接算法HMJ(Hash-Merge Join)。它通過不可預(yù)測(cè)的、緩慢的或突發(fā)的網(wǎng)絡(luò)流量處理來自遠(yuǎn)程數(shù)據(jù)源的數(shù)據(jù)項(xiàng)。算法綜合運(yùn)用了非阻塞連接算法X-Join和漸進(jìn)式合并連接算法的優(yōu)點(diǎn)，得到了更優(yōu)的結(jié)果。文獻(xiàn)[5]提出了一種新的基于NOWs(Network Of Workstations)的散列連接處理的負(fù)載共享算法,結(jié)合了分塊方法和散列連接來管理當(dāng)前環(huán)境中發(fā)生的動(dòng)態(tài)變化，可以用于當(dāng)前的單連接處理。文獻(xiàn)[6]提出了一種基于列庫的分布式環(huán)境中散列連接算法，面向數(shù)據(jù)的分布式計(jì)算模型的設(shè)計(jì)，引入分區(qū)聚合和啟發(fā)式優(yōu)化策略，實(shí)現(xiàn)了改進(jìn)的哈希連接算法。

對(duì)于聯(lián)機(jī)分析處理OLAP(On-Line Analytical Processing)[7]多表連接查詢，由于數(shù)據(jù)量過于巨大，牽扯的關(guān)聯(lián)表數(shù)量也大幅增加。Ripple Join[8]是主流的估算聚合值方法，輪流在每個(gè)表中隨機(jī)采樣，將采樣的結(jié)果放入內(nèi)存,對(duì)新放入內(nèi)存的結(jié)果和所有現(xiàn)存的結(jié)果進(jìn)行連接查詢。這種方法要求采樣的數(shù)據(jù)分布具有隨機(jī)性，而現(xiàn)代數(shù)據(jù)庫數(shù)據(jù)被聚類存放，因此不具有隨機(jī)分布的特性。文獻(xiàn)[9]對(duì)Ripple Join算法進(jìn)行了并行性和采樣方面的改進(jìn)，該方法的局限性是，一旦內(nèi)存無法再加載數(shù)據(jù)時(shí)，估計(jì)結(jié)果將不具有統(tǒng)計(jì)意義。Chris 等人[10]將sort-merge思想應(yīng)用到Ripple Join算法中，對(duì)內(nèi)存轉(zhuǎn)出到外存的數(shù)據(jù)進(jìn)行隨機(jī)化處理，從而保證估計(jì)結(jié)果的統(tǒng)計(jì)意義，并在引擎DBO(Date Base Owner)上實(shí)現(xiàn)了該方法，提升了Ripple Join的部分效率。文獻(xiàn)[11]介紹了Invisible Join，其思想是將表的相關(guān)列映射成位圖，對(duì)維表主鍵屬性相應(yīng)的外鍵列建立一個(gè)事實(shí)表位圖，根據(jù)所需要選擇的位圖和屬性獲得相應(yīng)連接結(jié)果。文獻(xiàn)[12]提出的Flash/Five Join是一種基于索引的多路等值的列式數(shù)據(jù)庫連接算法，對(duì)連接列屬性值進(jìn)行排序，同時(shí)索引號(hào)隨之變動(dòng)，再將連接列屬性值物化得到物化后的值，最后對(duì)索引號(hào)排序得到連接結(jié)果。Wander Join[13,14]是一種通過采樣計(jì)算聚合值[15]的方法，設(shè)計(jì)了一個(gè)步行計(jì)劃選擇器代替隨機(jī)采樣，使得采樣更有目的性，效率更高。通過合理應(yīng)用Wander Join連接查詢，用戶將獲得更高的聚合值返回效率，數(shù)據(jù)庫系統(tǒng)可以支持更多元的運(yùn)算。它的問題在于復(fù)雜性和適用性，以及對(duì)分組查詢的查詢速度不盡如人意。

本文將蟻群遺傳混合算法[16]與Wander Join相結(jié)合，提出了優(yōu)化連接順序的連接查詢算法。該算法通過一個(gè)連接選擇器計(jì)算出連接表之間的代價(jià)，用于連接圖建模時(shí)的順序選擇。執(zhí)行連接圖對(duì)應(yīng)的連接計(jì)劃后，使用剪枝策略對(duì)樣本多余的節(jié)點(diǎn)進(jìn)行剪枝操作，保留高選擇性的節(jié)點(diǎn)，以減少節(jié)點(diǎn)的數(shù)量，避免重復(fù)搜索。最后將提出的混合連接算法在TPC-H(Transaction process Performance Council-H)數(shù)據(jù)集和TPC-DS(Transaction process Performance Council-DS)數(shù)據(jù)集[17,18]上分別進(jìn)行了仿真驗(yàn)證。

2 Wander Join查詢算法

Wander Join查詢算法使采樣過程更加集中，避免了盲目地從每個(gè)表中抽取樣本進(jìn)行連接操作，只從其中一個(gè)表中隨機(jī)抽取一個(gè)元組，從該元組開始進(jìn)行隨機(jī)遍歷，在隨機(jī)遍歷的每一步中，只考慮當(dāng)前已采樣元組及其相鄰元組。與Ripple Join連接算法的“盲目搜索”相比，它是一種引導(dǎo)探索。

具體方法是將表之間的連接建模為連接圖，然后在該連接圖中執(zhí)行隨機(jī)遍歷。由于可以用不同的順序?qū)ο嗤倪B接執(zhí)行隨機(jī)遍歷，所以Wander Join查詢算法設(shè)計(jì)了一個(gè)優(yōu)化器來選擇最優(yōu)的遍歷計(jì)劃。由于每一條路徑被選擇的概率不相同，易導(dǎo)致采樣不均勻，為了判斷遍歷計(jì)劃的優(yōu)劣，Wander Join引入HT(Horvitz-Thompson)估計(jì)量，用式(1)來估算樣本總體的期望值[19]：

(1)

其中,n表示采樣數(shù)目，XIi表示采樣這個(gè)Ii得到的值，πIi表示出現(xiàn)采樣的概率。而選擇概率如式(2)所示：

(2)

其中,γ表示不同時(shí)刻，Rλ(1)表示第1個(gè)表里總記錄的條數(shù)，dλ(i)(tp(i))表示從第i-1個(gè)表的某條記錄連接到第i個(gè)表的邊的數(shù)目。

在給定的時(shí)間內(nèi)，最終估計(jì)量的方差與Var[X1]E[T]/T成正比，如式(3)所示：

(3)

其中,W表示游走總步數(shù)，Xi表示第i個(gè)隨機(jī)游走的估計(jì)值，E[T]表示隨機(jī)游走中查找的索引條目的平均值，T表示總運(yùn)行時(shí)間，最終估計(jì)量的方差越小，越接近最優(yōu)的游走方案。

3 改進(jìn)的連接查詢算法

本文引入蟻群遺傳混合算法和裁剪搜索空間對(duì)Wander Join算法進(jìn)行優(yōu)化，算法流程如算法1和圖1所示。

算法1改進(jìn)的連接查詢算法

Step1表節(jié)點(diǎn)建模：將N個(gè)表上的連接建模為連接圖;

Step2連接順序確定：引入蟻群遺傳混合算法確定表連接順序;

Step3執(zhí)行選擇計(jì)劃：根據(jù)新的連接順序執(zhí)行計(jì)劃;

Step4樣本選擇：采用剪枝策略縮小選擇范圍;

Step5完成連接查詢。

Figure 1 Flow chart of improved algorithm 圖1 改進(jìn)算法流程圖

3.1 表節(jié)點(diǎn)建模

數(shù)據(jù)庫連接查詢優(yōu)化問題與傳統(tǒng)的旅行商問題類似，目標(biāo)是尋求一條代價(jià)最小的路徑。本文提出的改進(jìn)算法將需要進(jìn)行連接查詢的數(shù)據(jù)表建模成連接圖，以最小代價(jià)提供連接查詢路徑，流程如下所示：

Step1初始化節(jié)點(diǎn):每個(gè)表被建模為一個(gè)節(jié)點(diǎn)ci，i=1,2,…,N;

Step2節(jié)點(diǎn)連接:若2表之間存在連接條件，則2表之間形成一條邊;

Step3形成連接圖:整合節(jié)點(diǎn)和邊形成連接圖G(V,E)，其中V={ci|i=1,2,…,N},E為所有邊組成的集合。

3.2 連接順序確定

實(shí)體和群體的能力描述代表了它們執(zhí)行任務(wù)的能力，是進(jìn)行任務(wù)規(guī)劃的根本依據(jù)。能力描述還將組織任務(wù)的可完成性判斷轉(zhuǎn)化成了描述任務(wù)邏輯的定理證明。另外，群體中成員的變更可能導(dǎo)致組織能力的變化，能力描述也能自然地將這種變化表現(xiàn)出來。

由于模擬生物或自然界的不確定算法易陷入局部最優(yōu)，而基于啟發(fā)式的確定算法存在收斂速度慢等問題，本文算法將蟻群算法與遺傳算法相結(jié)合，將蟻群算法每次迭代的結(jié)果作為遺傳算法的初始種群，用遺傳算法產(chǎn)生的結(jié)果更新蟻群算法的信息素。同時(shí)，引入2種新的交叉算子，后期使用兩元素優(yōu)化(2-opt)算法，避免了算法過早陷入局部最優(yōu)解，加快了算法的收斂速度，流程如下所示：

Step1生成初始種群。

(1)定義啟發(fā)式信息素因子α，啟發(fā)式期望值因子β，表節(jié)點(diǎn)連接代價(jià)d，信息素τ，啟發(fā)式信息η，信息素強(qiáng)度q，交叉概率pe，變異概率pm，信息素?fù)]發(fā)系數(shù)ρ等。

(2)禁忌表初始化為空。

(3)將螞蟻釋放在N個(gè)表節(jié)點(diǎn)上。

(4)狀態(tài)及轉(zhuǎn)移方向初始化，如式(4)所示：

(4)

(5)將表節(jié)點(diǎn)按照被遍歷的順序組成編碼，把蟻群算法中所有螞蟻遍歷一次后的完整路徑作為遺傳算法的初始種群。

Step2執(zhí)行選擇。

按照1∶1的比例，采用輪盤賭方法和最優(yōu)個(gè)體保存法對(duì)種群中的個(gè)體進(jìn)行選擇。第k個(gè)個(gè)體適應(yīng)度被選擇的概率pk和前k個(gè)個(gè)體被選擇的累計(jì)概率qk如式(5)和式(6)所示：

(5)

(6)

其中，f(k)為適應(yīng)度函數(shù)。

計(jì)算個(gè)體適應(yīng)度在整個(gè)種群適應(yīng)度中被選擇概率和累計(jì)概率，最后通過0～1的隨機(jī)數(shù)r與累計(jì)概率qk來決定被保留的個(gè)體。

適應(yīng)度的計(jì)算采用目標(biāo)函數(shù)和適應(yīng)度函數(shù)，目標(biāo)函數(shù)如式(7)所示：

(7)

其中，d(ci,cj)表示表節(jié)點(diǎn)ci到表節(jié)點(diǎn)cj的距離,Lk則代表螞蟻k在一次迭代中走過的路徑長度。

適應(yīng)度函數(shù)選取目標(biāo)函數(shù)f(Lk)的倒數(shù)，如式(8)所示：

(8)

可知，路徑長度影響適應(yīng)度，路徑越長適應(yīng)度越小。

Step3執(zhí)行交叉。

按照交叉概率進(jìn)行交叉操作。從種群中隨機(jī)確定個(gè)體a和個(gè)體b作為子代路徑的父?jìng)€(gè)體，隨機(jī)確定一個(gè)交叉節(jié)點(diǎn)rc作為子代路徑的起始節(jié)點(diǎn)。計(jì)算父?jìng)€(gè)體a和b路徑中節(jié)點(diǎn)rc與其下一個(gè)節(jié)點(diǎn)ca1和cb1之間的距離da1和db1，計(jì)算節(jié)點(diǎn)rc與ca2和cb2之間的距離da2和db2，如果da1+db2*r≤da2+db2*r,0

Step4執(zhí)行變異。

對(duì)交叉后得到的結(jié)果采用對(duì)換變異，將隨機(jī)選取的若干基因按照變異概率pm互換，初始概率選擇較大的值，以便在更大范圍內(nèi)搜索，盡可能減小丟失最優(yōu)解的概率。根據(jù)進(jìn)化代數(shù)令變異概率pm遞減，最終鎖定最優(yōu)解。

Step52元素優(yōu)化(2-opt)。

從當(dāng)前解中任意選擇2條路徑，拆成2個(gè)部分。在不構(gòu)成環(huán)路的前提下，將第1部分的路徑反接回另一條路徑，比較產(chǎn)生的路徑與原路徑的長度，并保留路徑相對(duì)較短的解。針對(duì)不同的路徑重復(fù)進(jìn)行2-opt，最終得到局部優(yōu)化后的解。

Step6用式(9)更新信息素：

(9)

(10)

Step7若迭代次數(shù)大于最大循環(huán)次數(shù)或遺傳算法的結(jié)果滿足當(dāng)前要求的最優(yōu)解，輸出最優(yōu)連接路徑結(jié)果P(x1,x2,…,xn)。

3.3 執(zhí)行選擇計(jì)劃

根據(jù)3.2節(jié)中得到的新的查詢連接順序P(x1,x2,…,xn)，執(zhí)行新的選擇計(jì)劃。

以圖2為例，如果按照原始的查詢順序A→B→C，連接一次成功率為3/5，但是在優(yōu)化連接順序后，新的選擇計(jì)劃的查詢順序?yàn)镃→B→A，則連接的一次成功率為4/5，達(dá)到了優(yōu)化效果。

Figure 2 Data connection diagram圖2 數(shù)據(jù)連接示意圖

3.4 樣本選擇優(yōu)化

刪除未通過篩選的節(jié)點(diǎn)可以對(duì)高選擇性查詢樣本進(jìn)行優(yōu)化，防止查詢節(jié)點(diǎn)失敗，使用更少的節(jié)點(diǎn)進(jìn)行查詢，以加快查詢速度。優(yōu)化過程如下所示：

Step1初始化權(quán)重。

在實(shí)踐中，當(dāng)發(fā)出過濾查詢時(shí)，統(tǒng)一設(shè)置每個(gè)節(jié)點(diǎn)的權(quán)重。

Step2更新權(quán)重。

在進(jìn)行抽樣時(shí)，如果遇到一個(gè)節(jié)點(diǎn)未能通過篩選，將該節(jié)點(diǎn)的權(quán)值設(shè)置為0，并將此節(jié)點(diǎn)視為查詢失敗。通過將權(quán)值設(shè)置為0，保證不再對(duì)這個(gè)失敗的節(jié)點(diǎn)采樣。

Step3裁剪。

如圖3所示，對(duì)于3張表A、B、C，可以看到2條可能的采樣路徑是A1→B1→C2和A1→B2→C2。如果連接選擇了A1，B1，而節(jié)點(diǎn)C2沒有通過篩選，則將C2的權(quán)重置為0，并裁剪。這樣不僅消除了A1→B1→C2這條可能的路徑，也消除了A1→B2→C2路徑。刪除沒有通過篩選的節(jié)點(diǎn)，防止了任何路徑對(duì)該節(jié)點(diǎn)進(jìn)行再次采樣。

Figure 3 Node clipping diagram圖3 節(jié)點(diǎn)裁剪示意圖

Step4輸出裁剪后結(jié)果。如果再次執(zhí)行同一查詢計(jì)劃，查詢正確率將有所提升。

4 實(shí)驗(yàn)及結(jié)果討論

本文實(shí)驗(yàn)環(huán)境為Python 3.6.5，實(shí)驗(yàn)數(shù)據(jù)集為TPC-H與TPC-DS。

實(shí)驗(yàn)參數(shù)設(shè)置：蟻群遺傳混和算法種群規(guī)模M(k)=25,啟發(fā)式信息素因子α=2,啟發(fā)式期望值因子β=3,信息素?fù)]發(fā)系數(shù)ρ=0.7,釋放的信息素總量q=100,交叉概率pe=0.75,變異概率pm=0.05,遺傳算法進(jìn)化代數(shù)設(shè)為20，混合算法的總迭代次數(shù)達(dá)到100代時(shí)輸出結(jié)果。

基于相對(duì)錯(cuò)誤率、置信區(qū)間寬度、平均權(quán)重和執(zhí)行時(shí)間對(duì)算法性能進(jìn)行評(píng)估，并將蟻群遺傳混合算法+剪枝策略+Wander Join改進(jìn)的算法(本文算法，記作S-WJ-P)分別與蟻群遺傳混合算法+Wander Join改進(jìn)的算法(記作S-WJ)以及Wander Join算法(記作WJ)進(jìn)行了對(duì)比實(shí)驗(yàn)。

相對(duì)錯(cuò)誤率如式(11)所示：

(11)

其中,v表示方差，Ns表示抽樣個(gè)數(shù)。

置信區(qū)間的左右值分別用L-int和R-int表示，半寬度(ε-width)公式為：

(12)

平均權(quán)重如式(13)所示：

(13)

其中,n為樣本數(shù)量，wi為權(quán)重。

4.1 模擬多表連接順序優(yōu)化

把每個(gè)表節(jié)點(diǎn)映射為一個(gè)二維數(shù)組后，基于TPC-H數(shù)據(jù)集和本文算法獲得的優(yōu)化表連接路徑如圖4所示。

Figure 4 Minimum cost path of table join圖4 表連接最小代價(jià)路徑

為了驗(yàn)證在更大數(shù)量表連接時(shí)算法的可行性，模擬實(shí)驗(yàn)了20和50個(gè)表連接的情況，本文算法獲得的優(yōu)化表連接路徑如圖5所示。

Figure 5 Minimal cost path for a large number of table join圖5 大量表連接最小代價(jià)路徑

由圖4和圖5可見，表節(jié)點(diǎn)數(shù)量越多，路徑選擇就越多，本文算法容易找到相對(duì)最優(yōu)解進(jìn)行連接，從而減少連接的相對(duì)錯(cuò)誤率。

4.2 實(shí)驗(yàn)結(jié)果分析

將置信度設(shè)置為95%，分別在樣本數(shù)量為10 000和100 000的條件下，測(cè)試了3種算法在6個(gè)檔次選擇率情況下的相對(duì)錯(cuò)誤率、執(zhí)行時(shí)間、平均權(quán)重和置信區(qū)間寬度,結(jié)果如表1和表2所示。

對(duì)比表1和表2，在不同選擇概率ch下，WJ的相對(duì)錯(cuò)誤率波動(dòng)較大，這是因?yàn)?.2節(jié)中提到的WJ的隨機(jī)游走會(huì)導(dǎo)致路徑不同，從而影響選擇成功率，而S-WJ和S-WJ-P的相對(duì)錯(cuò)誤率波動(dòng)較小，說明改進(jìn)的算法具有良好的魯棒性。S-WJ-P和S-WJ的置信區(qū)間寬度與平均權(quán)重也均小于WJ的。以上實(shí)驗(yàn)結(jié)果表明，本文算法達(dá)到95%置信區(qū)間的收斂速度比WJ快，換言之，達(dá)到相同置信區(qū)間所需的樣本數(shù)量比WJ的少。此外，由于剪枝策略的加入，裁剪了大量沒有遍歷的節(jié)點(diǎn)，因此在低選擇率條件下獲得了更好的優(yōu)化效果，從而本文算法的估算結(jié)果更精確。

圖6～圖9給出了不同樣本數(shù)量時(shí)的算法對(duì)比情況。從圖6和圖7給出的相對(duì)錯(cuò)誤率的對(duì)比情況來看，在2種不同樣本數(shù)量條件下，S-WJ-P在大部分選擇率區(qū)間內(nèi)的相對(duì)錯(cuò)誤率均低于WJ和S-WJ的，只有在低選擇率區(qū)間內(nèi)S-WJ的相對(duì)錯(cuò)誤率略低。3種算法的執(zhí)行效率如圖8和圖9所示，S-WJ-P和S-WJ的執(zhí)行時(shí)間均高于WJ的。這是因?yàn)橐氲南伻哼z傳混合算法和剪枝策略增加了算法的計(jì)算時(shí)間，但在樣本數(shù)量大幅度增加后,由于剪枝策略有效減少了表節(jié)點(diǎn)數(shù)量，3種算法時(shí)間趨于一致，因此犧牲部分時(shí)間減少20%～70%的相對(duì)錯(cuò)誤率是值得的。樣本數(shù)量較少時(shí)的效率問題仍是后續(xù)改進(jìn)算法的方向。

Table 1 Comparison of partial experimental results of 10 000 samples表1 10 000個(gè)樣本部分實(shí)驗(yàn)結(jié)果對(duì)比

Table 2 Comparison of partial experimental results of 100 000 samples表2 100 000個(gè)樣本部分實(shí)驗(yàn)結(jié)果對(duì)比

Figure 6 Comparison of relative error rate of 10 000 samples圖6 10 000個(gè)樣本相對(duì)錯(cuò)誤率對(duì)比

Figure 7 Comparison of relative error rate of 100 000 samples圖7 100 000個(gè)樣本相對(duì)錯(cuò)誤率對(duì)比

Figure 8 Execution time of 10 000 samples圖8 10 000個(gè)樣本執(zhí)行時(shí)間

Figure 9 Execution time of 100 000 samples圖9 100 000個(gè)樣本執(zhí)行時(shí)間

為了驗(yàn)證改進(jìn)算法的普適性，基于TPC-DS數(shù)據(jù)集再次驗(yàn)證，從圖10、圖11與圖6、圖7中相對(duì)錯(cuò)誤率的對(duì)比情況來看，在相同樣本數(shù)量條件下，S-WJ-P在大部分選擇率區(qū)間內(nèi)的相對(duì)錯(cuò)誤率均低于WJ和S-WJ的。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法具有更高的正確率和更好的魯棒性。

Figure 10 Comparison of relative error rates of 10 000 samples on TPC-DS圖10 TPC-DS上10 000個(gè)樣本相對(duì)錯(cuò)誤率對(duì)比圖

Figure 11 Comparison of relative error rates of 100 000 samples on TPC-DS圖11 TPC-DS上100 000個(gè)樣本相對(duì)錯(cuò)誤率對(duì)比

5 結(jié)束語

本文提出了一種基于Wander Join改進(jìn)的數(shù)據(jù)庫連接查詢算法，利用蟻群遺傳混合算法優(yōu)化表連接的路徑選擇，結(jié)合Wander Join算法，使連接查詢得到部分優(yōu)化。按照新的連接順序進(jìn)行連接后，引入剪枝策略，減少連接節(jié)點(diǎn)數(shù)量。實(shí)驗(yàn)表明，算法在控制相對(duì)錯(cuò)誤率和控制樣本數(shù)量方面取得了較好的效果。選擇率為10%左右時(shí)，改進(jìn)算法表現(xiàn)最佳，相對(duì)錯(cuò)誤率只有Wander Join算法的1/5。改進(jìn)算法在數(shù)據(jù)庫更新操作時(shí)會(huì)破環(huán)剪枝的效果，加上蟻群算法的處理時(shí)間，導(dǎo)致執(zhí)行時(shí)間增加。今后的研究可以嘗試連接算法的并行化，或與其它啟發(fā)式算法結(jié)合，引入強(qiáng)化學(xué)習(xí)算法全面提升其性能。