王敏,彭承晨,李蓉蓉,彭煜瑋

(武漢大學(xué)計算機學(xué)院,武漢430072)

基于數(shù)據(jù)關(guān)聯(lián)的分布“對象代理數(shù)據(jù)庫劃分方法

王敏,彭承晨,李蓉蓉,彭煜瑋

(武漢大學(xué)計算機學(xué)院,武漢430072)

對象代理數(shù)據(jù)庫是一種先進的具有復(fù)雜信息管理能力的數(shù)據(jù)庫系統(tǒng),隨著數(shù)據(jù)量的劇增,實現(xiàn)其分布式存儲變得十分重要.然而,對象代理數(shù)據(jù)庫中的數(shù)據(jù)存在著很強的關(guān)聯(lián)性,如果按照傳統(tǒng)數(shù)據(jù)劃分方式進行分布式存儲,將導(dǎo)致查詢效率低下.針對這一問題,本文提出了一種基于關(guān)聯(lián)的高效數(shù)據(jù)劃分方法:首先根據(jù)代理層次將關(guān)聯(lián)對象聚集成對象簇,每個簇對應(yīng)一個存儲文件;然后提取對象簇的模式特征和語義特征,通過聚類算法將對象簇集劃分為k個子集分配到各存儲節(jié)點.將本文方法與隨機分布式存儲方法進行了比較實驗,結(jié)果證明本文方法在查詢效率方面具有明顯優(yōu)勢.

分布式;對象代理數(shù)據(jù)庫;關(guān)聯(lián);數(shù)據(jù)劃分;對象簇

0 引言

對象代理模型[1-2]以面向?qū)ο髷?shù)據(jù)庫模型為基礎(chǔ),通過定義代理對象來表現(xiàn)對象的多方面本質(zhì)和動態(tài)變化特性.TOTEM(路珈圖騰數(shù)據(jù)庫)是基于該模型開發(fā)的數(shù)據(jù)庫管理系統(tǒng),它不僅繼承了面向?qū)ο髷?shù)據(jù)庫的優(yōu)點,還具有能夠有效地支持個性化信息服務(wù)、對象動態(tài)分類、復(fù)雜對象的多表現(xiàn)等功能.目前TOTEM已經(jīng)在生物信息管理[3-4]、地理信息管理[5]、Web數(shù)據(jù)管理[6]等諸多領(lǐng)域有著廣泛的應(yīng)用.但應(yīng)用范圍的擴大必然帶來存儲數(shù)據(jù)量的增加,使得單機存儲無法滿足數(shù)據(jù)存儲的需求.在這種情況下,分布式對象代理數(shù)據(jù)庫應(yīng)運而生.如圖1所示,分布式對象代理數(shù)據(jù)庫由應(yīng)用接口層、TOTEM數(shù)據(jù)庫層、分布式存儲層組成.應(yīng)用接口層為系統(tǒng)的上層應(yīng)用提供接口;TOTEM數(shù)據(jù)庫層包括連接管理、查詢處理、事務(wù)處理等3個模塊,系統(tǒng)表用于記錄對象的相關(guān)信息;分布式存儲層為本文研究所在的層次,是通過數(shù)據(jù)分片和數(shù)據(jù)分布操作實現(xiàn)數(shù)據(jù)的分布式存儲.

圖1 分布式對象代理數(shù)據(jù)庫架構(gòu)圖Fig.1Architecture of distributed object deputy database

在分布式對象代理數(shù)據(jù)庫中,代理關(guān)系使得對象之間存在相關(guān)性,訪問一個對象時往往需要訪問與其相關(guān)的其他對象,即存在對象級聯(lián)訪問的情況.然而一般的分布式存儲系統(tǒng)并不考慮對象的相關(guān)性,是將對象隨機分配,這樣帶來的問題是:關(guān)聯(lián)對象可能存儲于不同的節(jié)點,級聯(lián)訪問時需要從多個節(jié)點獲取對象,增加了I/O(Input/Output)以及數(shù)據(jù)傳輸?shù)拈_銷,這種開銷也會隨著關(guān)聯(lián)對象的增多而增大.直觀而言,如果把數(shù)據(jù)庫中的對象進行劃分,將關(guān)聯(lián)的對象存儲在相同或盡量少的節(jié)點上,讀取時把與之相關(guān)的對象一起讀進內(nèi)存,B可減少額外的I/O和數(shù)據(jù)傳輸,提高對象訪問的效率.如考慮2個具有代理關(guān)系的對象a和b,如圖2(a)所示,它們存儲于不同的節(jié)點,當(dāng)對a和b進行級聯(lián)讀取時,需要2次I/O和2個緩沖頁面;如果將它們聚集起來存儲在同一個節(jié)點,如圖2(b)所示,讀取時同時讀進內(nèi)存緩沖區(qū),則I/O和緩沖區(qū)數(shù)都減少為原來的一半.然而,對象代理數(shù)據(jù)庫中的數(shù)據(jù)劃分具有一定的挑戰(zhàn)性,原因在于傳統(tǒng)數(shù)據(jù)庫中的數(shù)據(jù)劃分方法是對單個表進行水平劃分或垂直劃分,沒有考慮到對象間的相關(guān)性,因此無法保證關(guān)聯(lián)對象被劃分到一起.

圖2 聚簇存儲對查詢效率的影響Fig.2The influence of clustering storage on the query efficiency

針對這一問題,本文提出了一種基于關(guān)聯(lián)的分布式對象代理數(shù)據(jù)庫數(shù)據(jù)劃分方法.首先,根據(jù)代理關(guān)系反映的顯式關(guān)聯(lián)將對象劃分成多個對象簇,同一個簇中的對象之間具有代理關(guān)系,不同簇的對象不具有代理關(guān)系.對象簇作為分布式存儲中的基本單位,為了將對象簇集合理地分配到節(jié)點中,本文同時考慮對象簇的模式關(guān)聯(lián)性和語義關(guān)聯(lián)性,采用k-means[7]方法將對象簇集劃分為k個子集,每個子集存儲在一個節(jié)點上.實驗證明,本文提出的數(shù)據(jù)劃分方法能夠有效地提高分布式對象代理數(shù)據(jù)庫的查詢效率.

1 相關(guān)工作

單機版對象代理數(shù)據(jù)庫中的對象采用堆文件方式進行存儲[8],同一個類的對象存儲在一個堆文件中,堆文件在磁盤中采用順序存儲的方式.然而在分布式環(huán)境下,這一存儲方式會使得具有代理關(guān)系的對象存放在多個節(jié)點上,查詢效率低.目前還沒有對象代理數(shù)據(jù)庫分布式存儲的相關(guān)研究.

分布式數(shù)據(jù)庫系統(tǒng)的設(shè)計分為數(shù)據(jù)劃分和數(shù)據(jù)在節(jié)點上的分配[9]這兩個步驟.數(shù)據(jù)劃分可分為水平劃分和垂直劃分[10]:水平劃分按元組對關(guān)系表進行劃分;垂直劃分按關(guān)系屬性對數(shù)據(jù)表進行劃分.目前對分布式關(guān)系數(shù)據(jù)庫的數(shù)據(jù)劃分方法已有大量的研究成果: Navathe等人[11]提出了一種兩階段的垂直劃分方法,首先根據(jù)經(jīng)驗?zāi)繕?biāo)函數(shù)對關(guān)系表劃分,然后根據(jù)具體的應(yīng)用環(huán)境進行優(yōu)化.關(guān)于面向?qū)ο髷?shù)據(jù)庫系統(tǒng)的劃分方法,也有很多相關(guān)的研究工作:Ezeife和Barker[12]為了進行數(shù)據(jù)的水平劃分,將數(shù)據(jù)庫中的類分成4個組,采用一定的方法對每個組中的類進行劃分.這些劃分方法沒有考慮到數(shù)據(jù)之間的相關(guān)性,因此不適合對對象代理數(shù)據(jù)庫中具有代理關(guān)系的對象進行劃分.

2 問題描述

對象代理數(shù)據(jù)庫中,對象與對象之間、類與類之間的關(guān)聯(lián)性使得數(shù)據(jù)呈現(xiàn)出代理層次結(jié)構(gòu).圖3給出了代理層次的示例,每個表格代表一個類,其中Media為源類,MTV和Music是從Media派生的代理類,CNMusic是Music的下層代理類.表格中每一行表示一個對象,OID(Object Identifier)[13]為對象標(biāo)識符,其余列為對象的屬性.源對象與代理對象之間使用雙向指針(虛線)表示代理關(guān)系;實線表示屬性的繼承關(guān)系,如MTV從Media中繼承了ID(Identification)和DESC(Descend)屬性.類中定義的屬性或代理類中擴展的屬性稱為實屬性;代理類中繼承自源類的屬性稱為虛屬性,圖3中灰色屬性均為虛屬性.

圖3 代理層次示例Fig.3The example of deputy layers

定義1級聯(lián)讀取:代理對象的虛屬性不占實際的物理存儲空間,為了獲取虛屬性的值,需要讀取其源對象中相應(yīng)的實屬性,這種讀取方式為級聯(lián)讀取.

定義2跨類查詢:利用對象間的代理關(guān)系,從一個類的對象出發(fā),可以查詢得到與其存在直接或間接代理關(guān)系的另一個類的對象,即為跨類查詢.

定義3對象簇:對象簇為具有關(guān)聯(lián)關(guān)系的對象的集合,在數(shù)據(jù)庫存儲和讀取時被視為一個整體.

可以看出,代理層次是一個有向圖,我們用DH=〈V,E〉表示代理層次,V={〈v1,T1〉,〈v2,T2〉,···,〈vn,Tn〉}為頂點的集合,表示系統(tǒng)共有n個類,其中,類vi={oi1,oi2,···,oimi} (i=1,2,···,n)表示該類由mi個對象組成,Ti∈{Source,Select,Union,Group,Join}(i= 1,2,···,n)為類的類型,Source代表源類,其余4個值代表4種代理類型;E={〈vi,vj,〉|vi,vj∈V}(i=1,2,···,n,j=1,2,···,n)為有向圖中的邊,表示類之間的代理關(guān)系,〈vi,vj〉∈E表示vi是vj的代理類,邊的總數(shù)目記為f.

本文所解決的問題可描述為:已知代理層次DH和分布式存儲節(jié)點的數(shù)目k,我們希望利用對象之間的關(guān)聯(lián)關(guān)系,將數(shù)據(jù)庫中的對象劃分為k個互不相交的子集C1,C2,···,Ck,使得對于一組查詢Q={q1,q2,···,qt},其查詢開銷最小,其中,Tc為傳輸開銷,Tr為I/O開銷.

3 基于關(guān)聯(lián)的數(shù)據(jù)劃分方法

針對上述問題,本文提出了一種基于關(guān)聯(lián)的數(shù)據(jù)劃分方法,旨在將具有關(guān)聯(lián)關(guān)系的對象存儲到同一個節(jié)點上.該方法有對象聚簇和對象簇集劃分兩種.

3.1 基于代理關(guān)系的對象聚簇

對象聚簇是將數(shù)據(jù)庫中的對象進行劃分,使得不同類中具有代理關(guān)系的對象聚成一個簇,混合存儲在同一個文件中.簇文件一般為小文件,因此可保證分布式環(huán)境下存儲于同一節(jié)點.劃分依據(jù)為代理層次所表示的代理關(guān)系,然而代理層次是一個復(fù)雜的圖結(jié)構(gòu),直接基于該結(jié)構(gòu)進行聚簇的效率較低.因此在聚簇前,我們將代理層次劃分為互不相交的子樹,稱為代理樹,然后根據(jù)劃分后的代理樹集合進行對象的聚簇.代理層次中具有4種類型的代理關(guān)系,下面分別討論代理樹生成時每種代理關(guān)系的處理方法.

(1)Select代理

Select代理有且只有一個源類,源對象與代理對象之間的關(guān)系為一對一或一對零.將Select代理對象與其源對象聚簇存儲在一起是最自然的,而且它們的關(guān)聯(lián)存取也是最頻繁的.因此在遍歷過程中,如果代理類型為Select,則將該代理類與它的源類劃分到同一棵代理樹中.

(2)Group代理與Join代理

Group代理只有一個源類,源對象與代理對象之間的關(guān)系為多對一或多對零.圖4(a)所示為Group代理關(guān)系,代理對象4對應(yīng)1組源對象{1,2,3}.如果要將源對象和代理對象進行聚簇存儲,第一種策略為冗余存儲,即產(chǎn)生多個代理對象的副本,分別與源對象聚簇,這種方式下代理對象4會產(chǎn)生{1,4}、{2,4}、{3,4}3個簇;第二種為非冗余存儲,將代理對象與任意一個源對象聚簇,如采用{1,4}、{2}、{3}的形式存儲.冗余存儲中更新一個代理對象需要更新多個副本,一致性維護開銷大;非冗余存儲雖然不存在更新問題,但是很難決定代理對象與哪一個源對象聚簇效率最高.因此本文不把Group代理對象與其源對象聚簇,所以在代理樹的劃分時將Group代理從代理層次中劃分出去,形成一個單獨的代理樹.Join代理關(guān)系如圖4(b)所示,聚簇存儲時也會遇到類似Group代理關(guān)系的情況,這里不一一說明,代理樹劃分時也將其從代理層次中劃分出去.

(3)Union代理

圖4(c)給出了Union代理關(guān)系的示例,與Select代理關(guān)系相似,其源對象與代理對象之間只可能存在一對一或一對零的關(guān)系.因此在代理樹劃分的過程中可以將1個Union代理關(guān)系分解為2個Select代理關(guān)系,如圖4(d)所示.

圖4 代理關(guān)系示例Fig.4The example of deputy relation

綜上所述,代理樹的根節(jié)點為源、Group代理、Join代理,樹的成員節(jié)點都是Select代理.代理樹生成過程為遍歷代理層次圖,對于每條邊,根據(jù)其代理類型作相應(yīng)的處理;依次處理每個子圖,直到所有子圖都滿足代理樹的條件為止.

代理樹生成算法(Create Deputy Tree,CTD)表示代理樹生成的過程,算法涉及的數(shù)據(jù)結(jié)構(gòu)說明如下:Q為保存代理層次中所有可能的根節(jié)點的隊列;DTS為保存生成的代理樹的集合;Vs為節(jié)點集合,保存形成的代理樹的所有節(jié)點;Es為邊集合,保存形成的代理樹中的所有邊;Qt為保存所有與正在處理的類相關(guān)的節(jié)點,它們都被初始化為φ.

圖5給出了算法CTD執(zhí)行過程的示例.對于圖5(a)中的代理層次圖,可以作為代理樹根節(jié)點的類有v1、v4、v6、v7、v9.首先構(gòu)造以v1為根節(jié)點的代理樹:遍歷與v1具有直接代理關(guān)系的類v2、v3,它們都為Select代理,插入到代理樹中,如圖5(b)所示;然后考察與v2具有直接代理關(guān)系的類,v5作為Select代理被插入到代理樹中,而v6為Group代理,將其從代理樹中劃分出去,得到圖5(c)的結(jié)果;接著考察與v3具有直接代理關(guān)系的類v8,因為它為Union代理,所以進行分解,創(chuàng)建副本v8a并插入到代理樹中,形成圖5(d),至此以v1為根節(jié)點的代理樹構(gòu)造完畢.以同樣的方式可生成以v4、v6、v7、v9為根節(jié)點的代理樹,最終得到圖5(e)中所示的5棵代理樹.

算法：算法CTD輸入：DH=〈V,E〉輸出：代理樹集合DTS 1:循環(huán)將DH中所有的源類、Group代理、Join代理加入節(jié)點隊列Q中; 2:while Q非空do//從根節(jié)點出發(fā)構(gòu)造代理樹3:從Q中取出第一個節(jié)點u;初始化Qt、Vs、Es,將u加入Qt中并從Q中刪除; 4:While Qt非空do 5:取出Qt中的第一個節(jié)點w,將w插入Vs; 6:for each e=＜vi,vj,＞in E 7:if(vj==w且vi為Select代理) 8:將vi插入Vs、Qt,將e插入Es中并從E中刪除; 9:if(vj==w且vi為Group或Join代理) 10:將e從E中刪除; 11:if(vj==w且vi為Union代理) 12:從E中刪除e,創(chuàng)建vi的Select副本v′i; 13:創(chuàng)建邊＜v′i,vj＞并加入Es中;插入v′i到Vs、Qt中; 14:end for 15:將w從Qt中刪除; 16:end while 17:根據(jù)Vs、Es生成代理樹DT,插入到DTS中; 18:end while

圖5 代理樹劃分過程Fig.5The process of deputy tree partition

算法CTD的時間復(fù)雜度為O(n×f),n和f分別為頂點數(shù)和邊數(shù),算法執(zhí)行過程中只用到幾個集合類型的存儲結(jié)構(gòu),因此空間復(fù)雜度為O(1).

通過劃分得到代理樹后,根據(jù)代理樹進行對象聚簇.具體方法是:對于代理樹根節(jié)點中的每個對象,尋找所有與其具有代理關(guān)系的對象,形成一個對象簇,記為pi.可以看出,如果代理樹根節(jié)點存在N個實例對象,將產(chǎn)生N個對象簇.圖6為聚簇過程的示例,根據(jù)圖6(a)中的代理樹可將圖6(b)中的對象聚成圖6(c)所示的2個簇,圖中虛線連接起來的2個對象具有代理關(guān)系.

圖6 對象聚簇Fig.6Clustering of objects

3.2 對象簇集劃分

對象聚簇之后,系統(tǒng)中存在多個對象簇,然而節(jié)點的個數(shù)遠小于對象簇的個數(shù),這就需要考慮如何將大量的對象簇分配到少量的節(jié)點中.為了解決這一問題,本文首先提取對象簇的特征,將其表達成特征向量,然后根據(jù)對象簇之間的相似性,采用k-means方法將對象簇集劃分為k個子集,分別存儲于各節(jié)點.

3.2.1 特征選擇

本文考慮對象簇的兩方面特征:模式特征和語義特征.模式特征指對象簇本身所表現(xiàn)的結(jié)構(gòu)特征;而語義特征是指對象簇反映的客觀實體的語義.

(1)模式特征

對象簇是具有關(guān)聯(lián)關(guān)系的對象集合,它本身具有一定的邏輯結(jié)構(gòu)特征,稱為模式特征.我們認(rèn)為模式上相同或相似的對象簇有很大可能被同時訪問,如圖6(c)所示的2個對象簇,它們的源對象都屬于Media類,代理對象所屬類中有2個類是相同的,當(dāng)我們執(zhí)行Select*from Media獲取Media中的所有對象時,這2個簇就需要被同時訪問,而且這種掃描同一類的查詢在數(shù)據(jù)庫中很頻繁,因此有必要將模式相似的對象存儲在同一節(jié)點.本文選取簇包含的類集合、簇的代理層次深度作為模式特征,代理層次深度是指簇中代理對象到根源對象的路徑的最大長度.圖6中2個簇的模式特征分別為({Media,Music,MTV},1)和({Media,Music,MTV,CNMusic},2).

(2)語義特征

語義上具有相似性的對象被同時訪問的概率比較大,如2個簇都具有“中文歌”這一語義,它們很有可能被同時訪問.因此將語義相似的對象簇存儲到同一物理節(jié)點可提高查詢效率.針對不同的應(yīng)用領(lǐng)域,對象簇的語義特征有所不同,本文以音樂領(lǐng)域為例,選取歌曲名、歌手名、專輯名、曲風(fēng)、年代等5種衡量對象簇特征的語義.

3.2.2 基于聚類的劃分方法

由于k-means方法可將數(shù)據(jù)集劃分為k個子集,而且時間復(fù)雜度接近于線性,具有可伸縮性,因此本文采用該方法進行對象簇集的劃分.假設(shè)數(shù)據(jù)集D={p1,p2,···,pl},pi(i=1,2,···,l)代表對象簇,l為對象簇的個數(shù),每個對象簇采用d維特征向量(x1,x2,···,xd)表示.k-means就是一種將D劃分為k個子集C1,C2,···,Ck的方法.其基本流程為:首先從l個對象簇中任意選擇k個簇作為k個子集的初始中心;對于剩下的其他對象簇,根據(jù)它們與這些中心的相似度,分配到與之最相似的中心所代表的子集;分配完所有對象簇后,重新計算每個子集的均值并將此作為新的子集中心;重復(fù)上述過程,直到度量函數(shù)E開始收斂為止.

本文使用距離度量對象簇之間的相似性,距離越小表示其相似性越大.我們將特征分為3類:集合型;枚舉型;數(shù)值型.針對不同類型特征,采用不同的距離計算公式.

集合型特征是指特征的值為一個集合,本文中簇包含的類集合與歌名都被作為該類型的特征.對于該類型特征,我們采用Jaccard距離[14].在計算距離之前,需要將歌名轉(zhuǎn)換成詞集合的形式,中文可通過分詞的方法進行轉(zhuǎn)換,英文則以空格為分隔符進行分割.設(shè)x,y為2個集合型屬性,其距離計算公式為

枚舉型特征的值限定于可列舉出的一組值之內(nèi),如歌手、專輯、曲風(fēng)都屬于該類型.計算枚舉型特征的距離公式為

如果2個屬性的值相等,則認(rèn)為其距離為0,不相等則為1.

數(shù)值型特征采用公式

表示的歐氏距離進行度量,簇的代理層次深度、年代為該類型特征.

得到每種類型特征的距離之后,對于2個對象簇pi和pj,pi=(x1,x2,···,xd),pj= (y1,y2,···,yd),它們之間的距離計算公式為

目標(biāo)函數(shù)E被定義為數(shù)據(jù)集中所有對象的誤差平方和,計算公式為

其中,ci為子集Ci的中心.這個目標(biāo)函數(shù)使生成的結(jié)果簇盡可能緊湊和獨立.

3.3 數(shù)據(jù)讀取與數(shù)據(jù)更新

由于數(shù)據(jù)存儲方式發(fā)生了改變,數(shù)據(jù)讀取的方式也需要做相應(yīng)的修改.在新的存儲方式下,為了獲取用戶需要的查詢結(jié)果,在系統(tǒng)表中記錄每個對象所屬的對象簇和節(jié)點.用戶提交查詢語句后,根據(jù)系統(tǒng)表獲得對象所在的簇號和節(jié)點號,然后從節(jié)點中讀取對象簇,解析后返回查詢結(jié)果.

數(shù)據(jù)庫是一個動態(tài)變化的系統(tǒng),當(dāng)發(fā)生數(shù)據(jù)更新時,需要對生成的對象簇進行維護.對象代理數(shù)據(jù)庫中,插入對象和刪除對象都會對對象簇的結(jié)構(gòu)產(chǎn)生影響.

(1)插入對象

對象代理數(shù)據(jù)庫中,插入的對象只能是源對象.根據(jù)本文的聚簇方法,每個簇中有且僅有一個源對象,因此當(dāng)插入源對象時,創(chuàng)建一個新的簇,存儲到與之最相似的子集所在的節(jié)點中,并在系統(tǒng)表中添加對象與簇的對應(yīng)關(guān)系.

(2)刪除對象

如果刪除的對象為源對象,將會級聯(lián)刪除與之相關(guān)的代理對象,因此刪除源對象時會將其所在簇整體刪除.刪除代理對象時,首先找到其所在簇,然后把對象從簇中刪除.

4 實驗

本文提出的數(shù)據(jù)劃分方法已在對象代理數(shù)據(jù)庫系統(tǒng)中實現(xiàn).本節(jié)通過實驗將本文方法與隨機分布式存儲方式進行對比,分析二者在數(shù)據(jù)庫查詢開銷方面的差異.

4.1 實驗設(shè)計

實驗數(shù)據(jù):實驗數(shù)據(jù)集是通過元搜索引擎從Web上獲得的跨媒體數(shù)據(jù),總共包括24萬余條數(shù)據(jù)及相關(guān)信息,從這些數(shù)據(jù)中隨機選取2.6萬條作為源對象進行實驗.代理對象通過源對象派生.數(shù)據(jù)庫模式使用圖1所示的代理層次,其中各個類的數(shù)據(jù)規(guī)模如表1所示.

表1 各個類的數(shù)據(jù)量Tab.1Data size of classes

實驗方法:實驗對隨機存儲方法和劃分存儲方法進行對比.隨機存儲方法是指對象被隨機分配到物理存儲節(jié)點;劃分存儲方法是指通過劃分,將關(guān)聯(lián)對象存在同一物理節(jié)點.為了體現(xiàn)劃分過程中模式特征的重要性,實驗還對比了有模式特征的劃分方法和無模式特征的劃分方法之間的差異.

實驗環(huán)境:實驗使用3臺PC機模擬12個存儲節(jié)點,采用TOTEM2.2數(shù)據(jù)庫系統(tǒng),分布式文件系統(tǒng)為ceph0.8[15].

4.2 實驗結(jié)果分析

對比實驗從3方面進行:一是對單個源類查詢的影響;二是對單個代理類查詢的影響;三是對跨類查詢的影響.每組實驗針對100個樣本查詢,通過平均查詢時間衡量方法的性能.

圖7 對單個源類查詢的影響Fig.7Impact on the query of source class

圖7為3種方法在單個源類查詢方式下查詢效率的差異.由于源類查詢不涉及對象的級聯(lián)讀取,因此本文方法對源類查詢效率的提升不是很大,如果不考慮模式特征,源類中的對象會被分配到不同節(jié)點,查詢效率低于有模式特征的劃分方法,甚至低于隨機分配的方法.圖8展示了對跨類查詢效率的影響.從圖8可以看出,不管是有模式特征的劃分還是無模式特征的劃分,對查詢效率都有很大的提升,而且考慮了模式特征的方法性能更優(yōu).

圖8 對跨類查詢的影響Fig.8Impact on the cross-class query

圖9 對代理類查詢的影響Fig.9Impact on the query of deputy class

圖9為3種方法對代理類查詢的影響,實驗分別比較了3種方法對一級代理類(MTV、Music)查詢和二級代理類(CNMusic)查詢的影響.從圖中可以看出,本文方法對二級代理類查詢效率提升的幅度大于一級代理類,這種優(yōu)勢隨著代理層次的增加會更明顯.對比圖9(a)和圖9(b),由于MTV中的元組個數(shù)多于Music,加入模式特征將屬于同一類的簇存入同一節(jié)點,可更大地提升查詢效率.

綜上,對于源類查詢、跨類查詢和代理類查詢,本文方法在查詢效率方面均優(yōu)于隨機存儲的方法,同時也證明了劃分過程中模式特征的重要性.

5 結(jié)束語

本文針對分布式對象代理數(shù)據(jù)庫中,對象隨機存儲而導(dǎo)致的級聯(lián)讀取效率低下這一問題,提出了一種基于關(guān)聯(lián)的數(shù)據(jù)劃分方法,使分布式存儲時關(guān)聯(lián)對象存儲在同一個節(jié)點.實驗證明,本文提出的方法能夠有效地提高分布式對象代理數(shù)據(jù)庫級聯(lián)讀取的效率,具有良好的性能效果.未來的工作應(yīng)該進一步研究代理樹生成過程中Group代理關(guān)系、Join代理關(guān)系的處理方法,以及對象簇動態(tài)更新過程的優(yōu)化.

［1］PENG Z Y,KAMBAYASHI Y.Deputy mechanisms for object-oriented database[C]//Proceedings of the 11th International Conference on Data Engineering.1995:333-340.

［2］KAMBAYASHI Y,PENG Z Y.Object deputy model and its applications[C]//Proceedings of the 4th Inernational Conference on Database Systems for Advenced Applications.1995:1-15.

［3］彭智勇,黃澤謙,劉俊.基于對象代理數(shù)據(jù)庫的微生物信息服務(wù)系統(tǒng)[J].計算機應(yīng)用,2010(1):5-9.

［4］PENG Z Y,SHI Y,ZHAI B X.Realization of biological data management by object deputy database system[C]//Transaction on Computational Systems Biology V.Berlin:Springer,2006:49-67.

［5］彭智勇,彭煜瑋,翟博譞.一個基于對象代理模型的多表現(xiàn)地信息系統(tǒng)[J].計算機應(yīng)用,2006(9):2016-2019.

［6］彭智勇.Web數(shù)據(jù)管理系統(tǒng):201010140168.4[P].2010-09-15.

［7］MACQUEEN J.Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability.1967:281-297.

［8］黃澤謙.對象代理數(shù)據(jù)庫聚簇策略與查詢優(yōu)化技術(shù)研究[D].武漢:武漢大學(xué),2011.

［9］BAI?AO F,MATTOSO M,ZAVERUCHA G.A distribution design methodology for object DBMS[J].Distributed and Parallel Databases,2004,16(1):45-90.

［10］?ZSU M T,VALDURIEZ P.Principles of Distributed Database Systems[M].New York:Springer-Verlag,2002.

［11］NAVATHE S B,RA M.Vertical partitioning for database design:A graphical algorithm[J].ACM Sigmod Record, 1989,18(2):440-450.

［12］EZEIFE C,BARKER K.A comprehensive approach to horizontal class fragmentation in a distributed object based system[J].International Journal of Distributed and Parallel Databases,1995(3):247-272.

［13］施源,彭智勇,莊繼峰,等.對象關(guān)系數(shù)據(jù)庫中OID回收機制[J].計算機科學(xué),2004,31(10):566-568+581.

［14］SHAMEEM M U S,FERDOUS R.An efficient k-means algorithm integrated with Jaccard distance measure for document clustering[C]//Proceedings of the Asian Himalayas International Conference on Internet.2009:1-6.

［15］WEIL S A.Ceph:Reliable,scalable,and high-performance distributed storage[D].Santa Cruz:University of California Santa Cruz,2007.

(責(zé)任編輯:李藝)

Data correlation-based partition approach for distributed deputy database

WANG Min,PENG Cheng-chen,LI Rong-rong,PENG Yu-wei
(Computer School,Wuhan University,Wuhan430072,China)

Object deputy database(ODDB)is an advanced database system with strong ability of complex information processing.With the rapid development of data,distributed storage becomes more and more important to ODDB.However,there exist correlations between objects in ODDB,which makes the traditional data portioning method of distributed storage unsuitable.To solve this problem,we propose a data correlation-based partition approach for ODDB.Firstly,we cluster correlated objects according to the deputy tree,and each object cluster is considered as a heap file in storage.Secondly,on the basis of schema feature and semantic feature,we divide object clusters into k subsets using k-means,each subset is stored on one of the storage nodes.Finally,we compare our method with random distributed storage,the results show that our approach is obviously better in query efficiency.

distributed;object deputy database;correlation;data partition; object cluster

TP311

A

10.3969/j.issn.1000-5641.2016.05.006

1000-5641(2016)05-0045-11

2016-05

國家自然科學(xué)基金重點項目(61232002)

王敏,女,碩士研究生,研究方向為數(shù)據(jù)管理.E-mail:wangmin1992@whu.edu.cn.

李蓉蓉,女,博士,講師,研究方向為數(shù)據(jù)抽取與數(shù)據(jù)管理.E-mail:rrli@whu.edu.cn.