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

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

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

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

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

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

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

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

0 引言

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

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

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

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

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

1 相關(guān)工作

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

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

2 問(wèn)題描述

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

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

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

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

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

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

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

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

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

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

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

(1)Select代理

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

(2)Group代理與Join代理

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

(3)Union代理

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

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

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

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

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

算法：算法CTD輸入：DH=〈V,E〉輸出：代理樹(shù)集合DTS 1:循環(huán)將DH中所有的源類、Group代理、Join代理加入節(jié)點(diǎn)隊(duì)列Q中; 2:while Q非空do//從根節(jié)點(diǎn)出發(fā)構(gòu)造代理樹(shù)3:從Q中取出第一個(gè)節(jié)點(diǎn)u;初始化Qt、Vs、Es,將u加入Qt中并從Q中刪除; 4:While Qt非空do 5:取出Qt中的第一個(gè)節(jié)點(diǎn)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生成代理樹(shù)DT,插入到DTS中; 18:end while

圖5 代理樹(shù)劃分過(guò)程Fig.5The process of deputy tree partition

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

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

圖6 對(duì)象聚簇Fig.6Clustering of objects

3.2 對(duì)象簇集劃分

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

3.2.1 特征選擇

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

(1)模式特征

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

(2)語(yǔ)義特征

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

3.2.2 基于聚類的劃分方法

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)插入對(duì)象

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

(2)刪除對(duì)象

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

4 實(shí)驗(yàn)

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

4.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

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

對(duì)比實(shí)驗(yàn)從3方面進(jìn)行:一是對(duì)單個(gè)源類查詢的影響;二是對(duì)單個(gè)代理類查詢的影響;三是對(duì)跨類查詢的影響.每組實(shí)驗(yàn)針對(duì)100個(gè)樣本查詢,通過(guò)平均查詢時(shí)間衡量方法的性能.

圖7 對(duì)單個(gè)源類查詢的影響Fig.7Impact on the query of source class

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

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

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

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

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

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

本文針對(duì)分布式對(duì)象代理數(shù)據(jù)庫(kù)中,對(duì)象隨機(jī)存儲(chǔ)而導(dǎo)致的級(jí)聯(lián)讀取效率低下這一問(wèn)題,提出了一種基于關(guān)聯(lián)的數(shù)據(jù)劃分方法,使分布式存儲(chǔ)時(shí)關(guān)聯(lián)對(duì)象存儲(chǔ)在同一個(gè)節(jié)點(diǎn).實(shí)驗(yàn)證明,本文提出的方法能夠有效地提高分布式對(duì)象代理數(shù)據(jù)庫(kù)級(jí)聯(lián)讀取的效率,具有良好的性能效果.未來(lái)的工作應(yīng)該進(jìn)一步研究代理樹(shù)生成過(guò)程中Group代理關(guān)系、Join代理關(guān)系的處理方法,以及對(duì)象簇動(dòng)態(tài)更新過(guò)程的優(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］彭智勇,黃澤謙,劉俊.基于對(duì)象代理數(shù)據(jù)庫(kù)的微生物信息服務(wù)系統(tǒng)[J].計(jì)算機(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］彭智勇,彭煜瑋,翟博譞.一個(gè)基于對(duì)象代理模型的多表現(xiàn)地信息系統(tǒng)[J].計(jì)算機(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］黃澤謙.對(duì)象代理數(shù)據(jù)庫(kù)聚簇策略與查詢優(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］施源,彭智勇,莊繼峰,等.對(duì)象關(guān)系數(shù)據(jù)庫(kù)中OID回收機(jī)制[J].計(jì)算機(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

國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目(61232002)

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

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