許國(guó)艷，羅章璇，宋 健，呂 鑫

(河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，南京 211100)

(*通信作者電子郵箱gy_xu@126.com)

基于雙層索引結(jié)構(gòu)的起源圖查詢方法

許國(guó)艷*，羅章璇，宋 健，呂 鑫

(河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，南京 211100)

(*通信作者電子郵箱gy_xu@126.com)

為解決現(xiàn)有的起源圖查詢效率低和資源占用率高的問(wèn)題,考慮起源信息和數(shù)據(jù)本身之間的關(guān)聯(lián)關(guān)系以及起源信息內(nèi)部結(jié)構(gòu)特點(diǎn)，提出了一種基于雙層索引結(jié)構(gòu)的起源圖查詢方法。首先，面向起源圖查詢，提出了一種包括基于詞典表全局索引和基于位圖局部索引的雙層索引結(jié)構(gòu)，全局索引用于查詢起源圖所存儲(chǔ)的服務(wù)器節(jié)點(diǎn)，局部索引用于對(duì)全局索引查詢到的服務(wù)器節(jié)點(diǎn)細(xì)化查詢；然后，基于雙層索引結(jié)構(gòu)，設(shè)計(jì)了一種起源圖查詢方法，針對(duì)6種選擇索引和3種join鏈接索引實(shí)現(xiàn)了查詢算法。實(shí)驗(yàn)結(jié)果表明，所提方法既提高了查詢效率，又降低了內(nèi)存資源的浪費(fèi)。

起源圖；雙層索引結(jié)構(gòu)；詞典表；位圖

0 引言

在云平臺(tái)環(huán)境下，隨著大數(shù)據(jù)應(yīng)用的不斷發(fā)展，各種數(shù)據(jù)越來(lái)越多，數(shù)據(jù)的起源信息規(guī)模也就越來(lái)越大。甚至在很多應(yīng)用領(lǐng)域起源信息已經(jīng)超過(guò)其所描述數(shù)據(jù)的信息量，起源信息的管理難度越來(lái)越大。云平臺(tái)環(huán)境下如何高效地查詢起源信息變得尤為重要，如何高效地查詢起源信息成為了一個(gè)亟待解決的問(wèn)題。

數(shù)據(jù)起源[1]是對(duì)數(shù)據(jù)處理的整個(gè)歷史的信息，包括數(shù)據(jù)的來(lái)源和處理這些數(shù)據(jù)的所有后繼過(guò)程。目前，Chebotko等[2]在HBase數(shù)據(jù)庫(kù)基礎(chǔ)上，對(duì)基于資源描述框架(Resource Description Framework， RDF)圖的起源數(shù)據(jù)集的存儲(chǔ)和索引和查詢進(jìn)行了研究：一方面，將數(shù)據(jù)起源圖進(jìn)行分布式存儲(chǔ)，并針對(duì)RDF三元組的查詢?cè)O(shè)計(jì)位圖索引；另一方面，建立Is、Ip、Iss、Ioo、Iso索引提高查詢效率，并在此索引機(jī)制上提出了相應(yīng)的查詢算法。朱敏[3]則充分運(yùn)用HBase提供的Row-key索引，對(duì)RDF數(shù)據(jù)的存儲(chǔ)與查詢進(jìn)行了研究，設(shè)計(jì)了滿足子類、子屬性和逆屬性的查詢算法。

由于上述方法都是采用一次遍歷整個(gè)表或者是將RDF三元組分多表存儲(chǔ)來(lái)設(shè)計(jì)多維索引，以此來(lái)提高查詢效率，不能滿足靈活高效的多維查詢和join等查詢，隨著數(shù)據(jù)集越來(lái)越多，查詢的效率也會(huì)明顯下降。

因此針對(duì)現(xiàn)有研究的不足，本文根據(jù)具體查詢需要細(xì)化索引，提出了一種雙層索引結(jié)構(gòu)，并進(jìn)一步設(shè)立了基于雙層索引結(jié)構(gòu)的起源圖查詢方法。

1 相關(guān)工作

1.1 基于RDF的起源圖描述

RDF[4]提供了一種用于表達(dá)語(yǔ)義信息并使其能在應(yīng)用程序間交換而不喪失語(yǔ)義的通用框架，描述了資源本身的屬性及資源與資源之間存在的關(guān)系。RDF是以三元組形式對(duì)資源的陳述，RDF三元組包括一個(gè)主語(yǔ)(subject)、一個(gè)謂語(yǔ)(predicate)和一個(gè)賓語(yǔ)(object)。RDF圖可以通過(guò)帶有標(biāo)簽的節(jié)點(diǎn)和帶有標(biāo)簽的邊表示，RDF圖中的節(jié)點(diǎn)就是它包含的所有三元組的主語(yǔ)和賓語(yǔ)，邊是所包含的所有謂語(yǔ)。每一個(gè)三元組對(duì)應(yīng)為圖上的一個(gè)“節(jié)點(diǎn)-邊-節(jié)點(diǎn)”的子圖。PROV[5]是數(shù)據(jù)起源模型，可以采用RDF圖描述起源信息。本文起源信息采用PROV建模，并用RDF圖進(jìn)行描述。

定義1 數(shù)據(jù)起源集。一個(gè)數(shù)據(jù)起源集D包含一個(gè)或者多個(gè)RDF圖{G1,G2,…,Gn},n≥0。其中每一個(gè)數(shù)據(jù)起源圖擁有唯一的ID標(biāo)識(shí)Gi∈D。

定義2 起源圖。一個(gè)起源圖G為一次工作流所產(chǎn)生的起源信息，由多個(gè)RDF三元組{t1,t2,…,tn}構(gòu)成，n=|G|，ti∈G。其中每一個(gè)RDF三元組ti∈G都由(S，P，O)組成，S表示主語(yǔ)，P表示謂語(yǔ)，用于描述主語(yǔ)和謂語(yǔ)之間的關(guān)系，O表示賓語(yǔ)。

1.2 起源圖存儲(chǔ)與索引

1.2.1 起源圖存儲(chǔ)

本文采用基于一致性二叉樹(shù)的起源圖分布存儲(chǔ)模型。一致性二叉樹(shù)分布模型基于二叉樹(shù)結(jié)構(gòu)，在每一層次節(jié)點(diǎn)都被分為多個(gè)互不相交的有限集中，其中每一個(gè)集合本身又是一棵樹(shù)，從而將所有存儲(chǔ)節(jié)點(diǎn)分到不同層次的不同組里。葉子節(jié)點(diǎn)中存放相應(yīng)的服務(wù)器編號(hào)。

定義3 一致性二叉分布樹(shù)。一致性二叉分布樹(shù)是由n個(gè)節(jié)點(diǎn)的有限集T組成的二叉樹(shù)，T={V，E}，V是節(jié)點(diǎn)的集合，E是邊的集合。

有限集T中每一個(gè)葉子表示云服務(wù)器位置。對(duì)于每個(gè)節(jié)點(diǎn)，可以用唯一的一個(gè)數(shù)字序列定義，從左至右依次代表該節(jié)點(diǎn)所經(jīng)歷過(guò)路徑的編號(hào)，其中子樹(shù)從左邊到右邊依次編號(hào)0，1，00，…。如圖1中查詢D節(jié)點(diǎn)編號(hào)為11，這棵一致性分布樹(shù)中也就唯一確定了D節(jié)點(diǎn)在樹(shù)中的具體位置，即查詢D節(jié)點(diǎn)經(jīng)過(guò)1和1兩條路徑。

1.2.2 一致性哈希索引

一致性哈希算法[6]是在哈希算法基礎(chǔ)上提出的，其主要思想是：首先得出每個(gè)服務(wù)節(jié)點(diǎn)的Hash值，并將其配置到一個(gè)0～232的圓環(huán)區(qū)間上；其次使用同樣的方法求出數(shù)據(jù)key的Hash值，也將其映射到這個(gè)圓環(huán)上；然后從數(shù)據(jù)映射到的位置開(kāi)始順時(shí)針查找，將數(shù)據(jù)保存到找到的第一個(gè)服務(wù)節(jié)點(diǎn)上。如果超過(guò)232仍然找不到服務(wù)節(jié)點(diǎn)，就會(huì)保存到第一個(gè)節(jié)點(diǎn)上。一致性哈希算法最大限度地抑制了Hash鍵的重新分配，在一定程度上很好地解決了數(shù)據(jù)的均衡和擴(kuò)展性問(wèn)題[7]。一致性哈希算法索引示意如圖2所示。

1.2.3 位圖索引

位圖索引[8]其核心思想是利用一個(gè)位向量(BitVector)來(lái)表示被索引對(duì)象的某一個(gè)取值是否在被索引數(shù)據(jù)中存在，在處理大量數(shù)據(jù)包含相同屬性時(shí)有很好的效果，目前被用于云數(shù)據(jù)管理[9-10]。

定義4 位圖索引。位圖索引即通過(guò)一個(gè)位向量來(lái)表示被索引的值或者屬性是否在文件中。其中如果被索引的值出現(xiàn)在文件中，該位向量中對(duì)應(yīng)的位置將被置1，否則置0。

對(duì)RDF三元組進(jìn)行索引時(shí)，對(duì)于主語(yǔ)、謂語(yǔ)或者賓語(yǔ)其中一項(xiàng)是相同的三元組僅僅只需要一個(gè)向量，使用向量中的bit來(lái)表示主語(yǔ)相同的不同三元組存放位置。

2 面向起源圖查詢的雙層索引結(jié)構(gòu)

2.1 雙層索引結(jié)構(gòu)

現(xiàn)在分布式環(huán)境下起源信息基本都是基于主鍵來(lái)查詢，但是缺少提供多維和join等查詢的高效的索引結(jié)構(gòu)。本文針對(duì)現(xiàn)有的起源圖查詢效率低和資源占用率高的問(wèn)題,面向起源圖查詢，提出了一種包括基于詞典表全局索引和基于位圖局部索引的雙層索引結(jié)構(gòu)，具體如圖3所示。全局索引用于查詢起源圖所存儲(chǔ)的服務(wù)器節(jié)點(diǎn)，局部索引用于對(duì)全局索引查詢到的服務(wù)器節(jié)點(diǎn)細(xì)化查詢，最終查詢到所需的起源信息。全局索引分布在云環(huán)境下每一個(gè)節(jié)點(diǎn)上，當(dāng)用戶請(qǐng)求到達(dá)時(shí)，只需參照本地服務(wù)器的全局索引結(jié)構(gòu)即能得出所要查詢起源圖所在節(jié)點(diǎn)位置。局部索引是只建立在本地服務(wù)器所存儲(chǔ)的起源信息的索引，每一個(gè)節(jié)點(diǎn)之間的局部索引并沒(méi)有依賴關(guān)系。

圖3 雙層索引結(jié)構(gòu)

2.2 基于詞典表全局索引

全局索引設(shè)計(jì)的目的是查詢到數(shù)據(jù)所存放的服務(wù)器節(jié)點(diǎn)，起源信息的全局索引設(shè)計(jì)不僅要能夠根據(jù)起源信息查詢到服務(wù)器節(jié)點(diǎn)，而且要能夠關(guān)聯(lián)起源信息與數(shù)據(jù)本身。雖然詞典表索引在查詢效率上不如哈希索引，但是詞典表能夠同時(shí)滿足對(duì)服務(wù)器節(jié)點(diǎn)查詢需求和對(duì)數(shù)據(jù)起源與數(shù)據(jù)本身之間的關(guān)聯(lián)關(guān)系查詢的需求。所以，本文提出了基于詞典表的云計(jì)算環(huán)境下起源信息的全局索引方案，具體設(shè)計(jì)了詞典表結(jié)構(gòu)。

根據(jù)數(shù)據(jù)起源特點(diǎn)，從兩方面設(shè)計(jì)詞典表HCPTable。首先，存儲(chǔ)起源圖名稱和對(duì)應(yīng)數(shù)據(jù)項(xiàng)。數(shù)據(jù)項(xiàng)就是起源所描述的數(shù)據(jù)，將一次工作流中的所有數(shù)據(jù)都對(duì)應(yīng)一個(gè)起源圖，粗粒度地描述起源與數(shù)據(jù)之間的關(guān)系。其次，存儲(chǔ)[11]起源圖名稱與對(duì)應(yīng)ID。每一次工作流的執(zhí)行會(huì)產(chǎn)生一個(gè)數(shù)據(jù)起源圖，起源ID則在存儲(chǔ)過(guò)程中依據(jù)Hash(key)映射產(chǎn)生。全局索引中起源圖ID為一致性哈希索引算法的輸入項(xiàng)，根據(jù)起源ID可以快速計(jì)算出起源圖所存儲(chǔ)服務(wù)器節(jié)點(diǎn)。設(shè)計(jì)的詞典表HCPTable的存儲(chǔ)結(jié)構(gòu)實(shí)例如圖4所示，其中G1，G2，…，Gn為n個(gè)起源圖，Gn.name為起源圖Gn的名稱，Gn.id為起源圖Gn的Hash(key)映射產(chǎn)生的id號(hào)，Artifactnn為Gn所關(guān)聯(lián)的第n個(gè)實(shí)體(數(shù)據(jù))，Processnn為Gn所關(guān)聯(lián)的第n個(gè)過(guò)程，Agentnn為Gn所關(guān)聯(lián)的第n個(gè)代理。

圖4 詞典表HCPTable的存儲(chǔ)結(jié)構(gòu)

2.3 基于位圖局部索引

局部索引設(shè)計(jì)的目的是對(duì)單個(gè)云存儲(chǔ)服務(wù)器節(jié)點(diǎn)上的起源圖細(xì)化查詢。起源圖查詢包含兩部分：?jiǎn)蝹€(gè)TriplePattern查詢和join查詢。在原有的位圖索引中，針對(duì)單個(gè)TriplePattern的查詢?cè)O(shè)計(jì)的索引存在一些不足：比如對(duì)給定的主語(yǔ)謂語(yǔ)，在查詢時(shí)不能直接從索引表中得到所需信息，必須首先查詢?cè)撝髡Z(yǔ)的位圖向量，然后查詢?cè)撝^語(yǔ)的位圖向量，最后進(jìn)行邏輯計(jì)算方可獲得。為了提高查詢起源圖效率，考慮用戶查詢時(shí)語(yǔ)句多樣性，針對(duì)兩種查詢方式，本文提出了一種改進(jìn)的基于位圖的多維局部索引。多維索引的主要思想是通過(guò)三元組中的非變量查詢變量，比如三元組中的主語(yǔ)為變量，那么可以通過(guò)賓語(yǔ)和謂語(yǔ)來(lái)查詢確定該三元組的主語(yǔ)，即為了彌補(bǔ)選擇索引Is、Ip、Io在對(duì)單個(gè)TriplePattern的查詢時(shí)的不足，對(duì)主語(yǔ)謂語(yǔ)已知的三元組設(shè)計(jì)索引Isp和Ips，對(duì)謂語(yǔ)賓語(yǔ)已知的三元組設(shè)計(jì)索引Ipo和Iop，對(duì)主語(yǔ)賓語(yǔ)已知的三元組設(shè)計(jì)索引Iso和Ios，形成完整的局部位圖索引結(jié)構(gòu)，包括選擇索引Is、Ip、Io、Isp、Ipo、Iso和join索引Is′、Io′、Iso′。

綜上，本文采用索引Is、Ip、Io、Isp、Ipo和Iso對(duì)主語(yǔ)、謂語(yǔ)、賓語(yǔ)、主語(yǔ)謂語(yǔ)、謂語(yǔ)賓語(yǔ)或者主語(yǔ)賓語(yǔ)已知的三元組進(jìn)行查詢；采用索引Is′、Io′、Iso′、Ios′用于處理主語(yǔ)共享變量、賓語(yǔ)共享變量和主語(yǔ)賓語(yǔ)共享變量的join查詢請(qǐng)求，因此，本文位圖索引存儲(chǔ)框架如表1所示。

3 基于雙層索引結(jié)構(gòu)的起源圖查詢算法

3.1 基于詞典表全局索引的節(jié)點(diǎn)查詢算法

全局查詢的目的在于定位起源圖所在服務(wù)器節(jié)點(diǎn)，本文根據(jù)一致性分布式存儲(chǔ)將不同起源圖均勻存儲(chǔ)到樹(shù)中不同的葉子節(jié)點(diǎn)中。在查詢起源圖時(shí)，從樹(shù)的root節(jié)點(diǎn)開(kāi)始，根據(jù)起源圖ID查詢起源所存儲(chǔ)在樹(shù)中的服務(wù)器節(jié)點(diǎn)。起源節(jié)點(diǎn)查詢算法Match_Node具體如下所示。

算法1 起源節(jié)點(diǎn)查詢算法Match_Node。

輸入：起源圖G.id、一致性樹(shù)tree。 輸出：節(jié)點(diǎn)node。 算法： //在一致性樹(shù)tree中查詢id編號(hào)的起源圖 node Map(id,tree){ node=tree.root; int temp=1; in_id=id; //如果node是葉子節(jié)點(diǎn)則返回存儲(chǔ)起源圖ID的服務(wù)器節(jié)點(diǎn) //如果不是葉子節(jié)點(diǎn)，則接著執(zhí)行循環(huán)進(jìn)行計(jì)算查找 While(node is not leaf){ temp=node.Number; node=node.Children[in_id%node.Number]; in_id=id/temp;} return node;}

表1 位圖索引存儲(chǔ)TD

3.2 基于位圖局部索引的細(xì)化查詢算法

根據(jù)起源圖Triple Pattern查詢和join查詢兩個(gè)部分以及本文所設(shè)計(jì)的局部索引，節(jié)點(diǎn)內(nèi)查詢起源圖的算法包括對(duì)單個(gè)Triple Pattern的查詢算法ASI_TP和對(duì)join查詢的算法ASI_JP，單個(gè)Triple Pattern查詢和join查詢是基礎(chǔ)。BGP(Basic Graph Pattern)是常見(jiàn)的起源圖模式，BGP圖的查詢主要包括單個(gè)Triple Pattern查詢和join查詢，BGP查詢的算法Match_BGP主要通過(guò)調(diào)用ASI_TP和AJI_TP實(shí)現(xiàn)。

3.2.1 ASI_TP算法

對(duì)單個(gè)Triple Pattern的查詢算法ASI_TP根據(jù)三元組中已知項(xiàng)查詢未知項(xiàng)，如下所示。

算法2 對(duì)單個(gè)Triple Pattern的查詢算法ASI_TP。

輸入：起源圖G.id,Triple Pattern tp=(sp,pp,op),tableTD。 輸出：位圖向量v，v[k]=1。tripletk=pos(k)。其中樹(shù)中位置K的三元組tk與tp匹配。 算法：

//TD中row-key為G.id所在行中Is、Ip、Io分別作為索引

//主語(yǔ)是非變量

if tp.sp非變量，tp.op和tp.pp是變量

thenv=v∧Is(tp.sp)；

//賓語(yǔ)是非變量

elseiftp.op非變量,tp.spandtp.pp是變量

thenv=v∧Io(tp.op)；

//謂語(yǔ)是非變量

elseiftp.pp非變量,tp.sp和tp.op為變量

thenv=v∧Ip(tp.pp)；

//主語(yǔ)、謂語(yǔ)是非變量

elseiftp.sp和tp.pp非變量,tp.op為變量

thenv=v∧Isp(tp.sp)；

//謂語(yǔ)、賓語(yǔ)是非變量

elseiftp.pp和tp.op非變量,tp.sp為變量

thenv=v∧Ipo(tp.po)；

//主語(yǔ)、賓語(yǔ)是非變量

elseiftp.sp和tp.op非變量,tp.pp為變量

thenv=v∧Isp(tp.so)；

//主語(yǔ)、賓語(yǔ)是非變量

elseiftp.sp、tp.op和tp.pp均為變量

thenv=v∧Is(tp.sp)‖Io(tp.op)‖Ip(tp.pp)‖Isp(tp.sp)‖Ipo(tp.po)‖Iso(tp.so)；returnv;

3.2.2AJI_TP算法

對(duì)join查詢的算法AJI_TP能夠在兩個(gè)三元組各自的主語(yǔ)、賓語(yǔ)、主語(yǔ)和謂語(yǔ)、謂語(yǔ)和賓語(yǔ)、主語(yǔ)和謂語(yǔ)分別相同時(shí)快速匹配，如下所示。

算法3 對(duì)join查詢的算法AJI_TP。

輸入：起源圖G.id、已知位置TriplePatterntp=(sp,pp,op),tp在圖中位置p,tripletp=pos-1(p)、tableTD以及所需join操作TriplePatterntp′。 輸出：位圖向量v，v[k]=1。tripletk=pos(k)。tk∈G,其中樹(shù)中位置K的三元組tk與tp的主語(yǔ)、主語(yǔ)、賓語(yǔ)、主語(yǔ)和謂語(yǔ)、謂語(yǔ)和賓語(yǔ)或者主語(yǔ)和謂語(yǔ)相匹配。 算法：

v[p]=0;

//TD中row-key為G行中Is′、Io′、Iso′分別作為索引

//主語(yǔ)相同變量匹配

iftp.sp與tp′.sp非變量并且tp.sp=tp′.sp

Thenv=v∧Is′(p)；

//賓語(yǔ)主語(yǔ)相同變量配

elseiftp.op與tp′.op非變量并且tp.op=tp′.op

Thenv=v∧Io′(p)；

//主語(yǔ)與謂語(yǔ)相同變量匹配

elseiftp.sp與tp′.op非變量并且tp.sp=tp′.op

Thenv=v∧Iso(p)；

//謂語(yǔ)與主語(yǔ)相同變量匹配

elseiftp.op與tp′.sp非變量并且tp.op=tp′.sp

Thenv=v∧Ios(p)；

Returnv;

3.2.3Match_BGP算法

Match_BGP算法首先將BGP中所有的TriplePattern進(jìn)行預(yù)處理，即重新排序，確立選擇度高的TriplePattern排序靠前；然后調(diào)用ASI_TP算法和AJI_TP算法實(shí)現(xiàn)最終結(jié)果集，如下所示。

算法4BGP查詢的算法Match_BGP。

vseva=ASI_TP(G.id,tpi,TD);

//第一個(gè)TriplePattern處理結(jié)果集合

ifS=?，returnS；

endif

endif

endfor

//當(dāng)前TriplePattern所在圖中位置

Sjoin=Sjoin∪({s}×Stpi);

endfor

S=Sjoin

ifS=?,thenreturnS

endif;

endfor

//替換S中triple位置為T(mén)riplePattern

returnS

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

4.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集

本文所提出的基于雙層索引結(jié)構(gòu)的起源圖查詢方法用到的實(shí)驗(yàn)環(huán)境及平臺(tái)如下：分布式Hadoop集群系統(tǒng)的硬件環(huán)境為包含4個(gè)節(jié)點(diǎn)，其中1臺(tái)作為HBasemaster節(jié)點(diǎn)，其他3臺(tái)機(jī)器作為slave節(jié)點(diǎn)。集群系統(tǒng)使用操作系統(tǒng)為Ubuntu12.04、Hadoop版本為1.0.0、開(kāi)發(fā)環(huán)境為JavaSE1.6、HBase版本為0.94.3。本文所采用的數(shù)據(jù)集是德克薩斯大學(xué)起源數(shù)據(jù)標(biāo)準(zhǔn)(UniversityofTexasProvenanceBenchmark,UTPB)[11]產(chǎn)生的起源圖。

4.2 空間占用分析

本文局部索引技術(shù)在文獻(xiàn)[2]基礎(chǔ)上改進(jìn)，是在文獻(xiàn)[2]的基礎(chǔ)上增加了3個(gè)新索引來(lái)提高查詢效率，所以存儲(chǔ)空間要多出3個(gè)索引所占存儲(chǔ)空間。

一次工作流中產(chǎn)生400個(gè)RDF三元組中相同的主語(yǔ)、謂語(yǔ)或者賓語(yǔ)的三元組會(huì)多次出現(xiàn)，索引Is、Ip和Io并不用對(duì)每一個(gè)三元組都建立索引項(xiàng)。含有相同元素的三元組，采用位圖向量的bit來(lái)標(biāo)記即可。比如相同主語(yǔ)只需要在位圖索引中對(duì)該主語(yǔ)首次建立的位圖向量中對(duì)應(yīng)位置1即可。該位置表示其在數(shù)據(jù)庫(kù)中存儲(chǔ)的邏輯位置。

對(duì)于工作流記錄的起源圖中相同主語(yǔ)謂語(yǔ)、謂語(yǔ)賓語(yǔ)和主語(yǔ)賓語(yǔ)的三元組重復(fù)項(xiàng)同樣很多，那么對(duì)于重復(fù)項(xiàng)只需在首次建立的向量中不同位置設(shè)置“1”即可，存儲(chǔ)時(shí)只需存儲(chǔ)一個(gè)位圖索引，因此，本文在原有的6個(gè)索引的基礎(chǔ)上添加3個(gè)索引項(xiàng)，索引的數(shù)量增加了50%，而索引存儲(chǔ)空間僅僅增加了25%左右，如圖5所示。

圖5 索引空間占用百分比

4.3 查詢性能分析

基于詞典表全局索引查詢算法具有更高的效率，首先，流程每一次的執(zhí)行都會(huì)選擇樹(shù)的一個(gè)葉子節(jié)點(diǎn)，執(zhí)行從root節(jié)點(diǎn)開(kāi)始到葉子節(jié)點(diǎn)，查詢方法類似折半查找，所以算法時(shí)間復(fù)雜度為O(logn)。其次，本文采用一致性二叉樹(shù)分布存儲(chǔ)，這樣的二叉樹(shù)結(jié)構(gòu)存儲(chǔ)方式也會(huì)比其他多叉樹(shù)的效率高很多。

基于位圖方式對(duì)起源存儲(chǔ)建立索引，起源圖所包含三元組的個(gè)數(shù)直接決定了位圖向量的位數(shù)，由于計(jì)算機(jī)對(duì)于二進(jìn)制數(shù)計(jì)算擅長(zhǎng)，對(duì)位圖向量處理時(shí)速度較快，因此，本文在應(yīng)付海量查詢語(yǔ)句時(shí)，能夠快速匹配到三元組，減少用戶查詢的響應(yīng)時(shí)間。

本文針對(duì)德克薩斯大學(xué)起源數(shù)據(jù)標(biāo)準(zhǔn)數(shù)據(jù)集分別測(cè)試了11條UTPB查詢語(yǔ)句來(lái)測(cè)試本發(fā)明所設(shè)計(jì)索引結(jié)構(gòu)的查詢性能。11條UTPB查詢語(yǔ)句用Q1,Q2,…,Q11表示，其中Q1是查詢所有起源圖的標(biāo)識(shí)，Q2是查詢一個(gè)指定標(biāo)識(shí)的起源圖，Q3是查詢一個(gè)指定起源圖的所有數(shù)據(jù)的起源關(guān)系，Q4是查詢一個(gè)指定起源圖的所有過(guò)程的觸發(fā)關(guān)系，Q5是查詢一個(gè)指定起源圖的所有數(shù)據(jù)的使用關(guān)系，Q6是查詢一個(gè)指定起源圖的所有數(shù)據(jù)的生成關(guān)系，Q7是查詢一個(gè)指定起源圖的所有控制關(guān)系，Q8是查詢一個(gè)指定起源圖的所有數(shù)據(jù)，Q9是查詢一個(gè)指定起源圖中的一個(gè)執(zhí)行工作流涉及的所有輸入和輸出數(shù)據(jù)，Q10是查詢一個(gè)指定起源圖的所有過(guò)程，Q11是查詢一個(gè)指定起源圖的所有因?yàn)殄e(cuò)誤停止的過(guò)程。采用UTPB的“DatabaseExperiment”工作流來(lái)產(chǎn)生起源圖，每次工作流所產(chǎn)生的RDF三元組描述一次完整工作流過(guò)程，共生成D1、D2、D3、D4、D5五個(gè)數(shù)據(jù)集，具體如表2所示。實(shí)驗(yàn)對(duì)D1、D2、D3、D4、D5五個(gè)數(shù)據(jù)集分別進(jìn)行了UTPB的11條查詢語(yǔ)句的測(cè)試。由于面向起源圖查詢的雙層索引結(jié)構(gòu)的設(shè)計(jì)，可以通過(guò)本地服務(wù)器的全局索引直接找到起源圖所存儲(chǔ)的服務(wù)器節(jié)點(diǎn)，通過(guò)上一步找到的服務(wù)器節(jié)點(diǎn)中的局部索引可以直接查詢到所需的起源信息，具體通過(guò)完整的包括選擇索引Is、Ip、Io、Isp、Ipo、Iso和join索引Is′、Io′、Iso′的局部位圖索引結(jié)構(gòu)實(shí)現(xiàn)每一種不同種類起源信息的直接查詢，所以，設(shè)計(jì)可以有效提升查詢效率。通過(guò)實(shí)驗(yàn)，證明了本文所提出的雙層索引結(jié)構(gòu)在應(yīng)對(duì)海量起源圖存儲(chǔ)時(shí)，隨著數(shù)據(jù)量的增加，其存儲(chǔ)和查詢性相對(duì)優(yōu)越，客戶查詢請(qǐng)求響應(yīng)及時(shí)，面對(duì)復(fù)雜的查詢請(qǐng)求時(shí)性能依然較好。具體查詢性能情況如圖6所示。

表2 起源圖數(shù)據(jù)集

圖6 查詢性能比較

5 結(jié)語(yǔ)

本文在現(xiàn)有起源圖索引結(jié)構(gòu)研究基礎(chǔ)上，結(jié)合數(shù)據(jù)起源圖自身特點(diǎn)以及在云計(jì)算環(huán)境下查詢所面臨的新難點(diǎn)，提出了基于雙層索引結(jié)構(gòu)的起源圖查詢方法。在基于一致性二叉樹(shù)的分布存儲(chǔ)策略基礎(chǔ)上，給出了基于詞典表全局索引和基于位圖局部索引，設(shè)計(jì)云環(huán)境下起源圖查詢算法，并驗(yàn)證了算法的可行性。總之，提出的基于雙層索引結(jié)構(gòu)的起源圖查詢方法具有高效性，有應(yīng)用價(jià)值和前景。

)

[1]DAVIDSONSB,LUDASCHERB,MCPHILIPST,etal.Provenanceinscientificworkflowsystems[J].IEEEDataEngineeringBulletin, 2007, 30(4): 44-50.

[2]CHEBOTKOA,ABRAHAMJ,BRAZIERP,etal.Storing,indexingandqueryinglargeprovenancedatasetsasRDFgraphsinApacheHBase[C]//Proceedingsofthe2013IEEENinthWorldCongressonServices.Piscataway,NJ:IEEE, 2013: 1-8.

[3] 朱敏.基于HBase的RDF數(shù)據(jù)存儲(chǔ)與查詢研究[D].南京：南京大學(xué),2013:24-48.(ZHUM.ResearchonstorageandqueryofRDFdatabasedonHBase[D].Nanjing:NanjingUniversity, 2013: 24-48.)

[4]W3C.RDF1.1conceptsandabstractsyntax[EB/OL].[2016-06-15].https://www.w3.org/TR/2014/REC-rdf11-concepts-20140225.

[5]W3C.PROV—overview[EB/OL].[2016-06-15].https://www.w3.org/TR/2013/NOTE-prov-overview-20130430/.

[6]ATREM,CHAOJIV,ZAKIMJ,etal.Matrixbitloaded:ascalablelightweightjoinqueryprocessorforRDFdata[C]//Proceedingsofthe19thInternationalConferenceonWorldWideWeb.NewYork:ACM, 2010: 41-50.

[7] 楊彧?jiǎng)?林波.分布式存儲(chǔ)系統(tǒng)中一致性哈希算法的研究[J].電腦知識(shí)與技術(shù),2011,7(22):5295-5296.(YANGYJ,LINB.Researchonconsistenthashingmethodindistributedstoragesystem[J].ComputerKnowledgeandTechnology, 2011, 7(22): 5295-5296.)

[8] 趙彥榮,王偉平,孟丹,等.基于Hadoop的高效連接查詢處理算法CHMJ[J].軟件學(xué)報(bào),2012,23(8):2032-2041.(ZHAOYR,WANGWP,MENGD,etal.EfficientjoinqueryprocessingalgorithmCHMJbasedonHadoop[J].JournalofSoftware, 2012, 23(8): 2032-2041.)

[9] 郭峻峰.數(shù)據(jù)倉(cāng)庫(kù)查詢優(yōu)化方法及索引技術(shù)研究[D].合肥：合肥工業(yè)大學(xué),2010:14-43.(GUOJF.Researchofqueryoptimizationandindexofdatawarehouse[D].Hefei:HefeiUniversityofTechnology, 2010: 14-43.)

[10] 孟必平,王騰蛟,李紅燕,等.分片位圖索引:一種適用于云數(shù)據(jù)管理的輔助索引機(jī)制[J].計(jì)算機(jī)學(xué)報(bào),2012,35(11):2306-2316.(MENGBP,WANGTJ,LIHY,etal.Slicebitmapindex:anauxiliaryindexingmechanismforclouddatamanagement[J].ChineseJournalofComputers, 2012, 35(11): 2306-2316.)

[11] 郭棟,王偉,曾國(guó)蓀.基于一致性樹(shù)分布的數(shù)據(jù)分布式存儲(chǔ)方法[J].計(jì)算機(jī)應(yīng)用,2013,33(12):3432-3436.(GUOD,WANGW,ZENGGS.Distributeddatastoragemethodbasedonconsistenttreedistribution[J].JournalofComputerApplications, 2013, 33(12): 3432-3436.)

[12]UniversityofTexasProvenanceBenchmark(UTPB) [EB/OL].[2016-06-12].http://faculty.utpa.edu/chebotkoa/utp.

ThisworkispartiallysupportedbytheNationalHighTechnologyResearchandDevelopmentProgram(863Program)ofChina(2013BAB06B04),theTechnologyProjectofChinaHuanengGroupHeadquarters(HNKJ13-H17-04),theNaturalScienceFoundationofJiangsuProvince(BK20130852),theSpecialFundforPublicWelfareIndustryoftheMinistryofWaterResourcesofChina(201501007).

XU Guoyan, born in 1971, Ph.D., associate professor.Her research interests include big data, data provenance.

LUO Zhangxuan, born in 1989, M.S.candidate.His research interest is data provenance management.

SONG Jian, born in 1991, M.S.candidate.His research interest is big data management.

LYU Xin, born in 1983, Ph.D., lecturer.His research interests include cryptography, network information security.

Provenance graph query method based on double layer index structure

XU Guoyan*, LUO Zhangxuan, SONG Jian, LYU Xin

(CollegeofComputerandInformation,HohaiUniversity,NanjingJiangsu211100,China)

To solve the problem of low query efficiency and high resource occupancy of the existing provenance graph query system, and consider the internal structure characteristics of provenance information, the relationship between the provenance of information and the data itself, a provenance graph query method based on double layer index structure was proposed.Firstly, for provenance graph query, a double layer index structure including global index based on dictionary table and local index based on bitmap was established.Global index was used to query the server nodes stored in provenance graph, and local index was for refining the query inside one server node.Secondly, based on the dual index structure, a provenance graph query method was designed, in view of the six kinds of selection index and three kinds of join link index.The experimental results show that the proposed method not only improves the query efficiency, but also reduces the waste of memory resources.

provenance graph; double layer index structure; dictionary table; bitmap

2016-07-20;

2016-08-06。 基金項(xiàng)目:國(guó)家863計(jì)劃項(xiàng)目(2013BAB06B04)；中國(guó)華能集團(tuán)公司總部科技項(xiàng)目(HNKJ13-H17-04)；江蘇省自然科學(xué)基金資助項(xiàng)目(BK20130852)；水利部公益性行業(yè)科研專項(xiàng)經(jīng)費(fèi)項(xiàng)目(201501007)。

許國(guó)艷(1971—)，女，內(nèi)蒙古赤峰人，副教授，博士，主要研究方向：大數(shù)據(jù)、數(shù)據(jù)起源； 羅章璇(1989—)，男，安徽滁州人，碩士研究生，主要研究方向：數(shù)據(jù)起源管理； 宋健(1991—)，男，江蘇鹽城人，碩士研究生，主要研究方向：大數(shù)據(jù)管理； 呂鑫(1983—)，男，江蘇南京人，講師，博士，主要研究方向：密碼學(xué)、網(wǎng)絡(luò)信息安全。

1001-9081(2017)01-0048-06

10.11772/j.issn.1001-9081.2017.01.0048

TP311

A