基于雙層索引結構的起源圖查詢方法

許國艷，羅章璇，宋 健，呂 鑫

(河海大學 計算機與信息學院，南京 211100)

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

基于雙層索引結構的起源圖查詢方法

許國艷*，羅章璇，宋 健，呂 鑫

(河海大學 計算機與信息學院，南京 211100)

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

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

起源圖；雙層索引結構；詞典表；位圖

0 引言

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

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

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

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

1 相關工作

1.1 基于RDF的起源圖描述

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

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

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

1.2 起源圖存儲與索引

1.2.1 起源圖存儲

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

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

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

1.2.2 一致性哈希索引

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

1.2.3 位圖索引

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

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

對RDF三元組進行索引時，對于主語、謂語或者賓語其中一項是相同的三元組僅僅只需要一個向量，使用向量中的bit來表示主語相同的不同三元組存放位置。

2 面向起源圖查詢的雙層索引結構

2.1 雙層索引結構

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

圖3 雙層索引結構

2.2 基于詞典表全局索引

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

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

圖4 詞典表HCPTable的存儲結構

2.3 基于位圖局部索引

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

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

3 基于雙層索引結構的起源圖查詢算法

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

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

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

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

表1 位圖索引存儲TD

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

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

3.2.1 ASI_TP算法

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

算法2 對單個Triple Pattern的查詢算法ASI_TP。

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

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

//主語是非變量

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

thenv=v∧Is(tp.sp)；

//賓語是非變量

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

thenv=v∧Io(tp.op)；

//謂語是非變量

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

thenv=v∧Ip(tp.pp)；

//主語、謂語是非變量

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

thenv=v∧Isp(tp.sp)；

//謂語、賓語是非變量

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

thenv=v∧Ipo(tp.po)；

//主語、賓語是非變量

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

thenv=v∧Isp(tp.so)；

//主語、賓語是非變量

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算法

對join查詢的算法AJI_TP能夠在兩個三元組各自的主語、賓語、主語和謂語、謂語和賓語、主語和謂語分別相同時快速匹配，如下所示。

算法3 對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,其中樹中位置K的三元組tk與tp的主語、主語、賓語、主語和謂語、謂語和賓語或者主語和謂語相匹配。 算法：

v[p]=0;

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

//主語相同變量匹配

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

Thenv=v∧Is′(p)；

//賓語主語相同變量配

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

Thenv=v∧Io′(p)；

//主語與謂語相同變量匹配

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

Thenv=v∧Iso(p)；

//謂語與主語相同變量匹配

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

Thenv=v∧Ios(p)；

Returnv;

3.2.3Match_BGP算法

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

算法4BGP查詢的算法Match_BGP。

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

//第一個TriplePattern處理結果集合

ifS=?，returnS；

endif

endif

endfor

//當前TriplePattern所在圖中位置

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

endfor

S=Sjoin

ifS=?,thenreturnS

endif;

endfor

//替換S中triple位置為TriplePattern

returnS

4 實驗結果

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

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

4.2 空間占用分析

本文局部索引技術在文獻[2]基礎上改進，是在文獻[2]的基礎上增加了3個新索引來提高查詢效率，所以存儲空間要多出3個索引所占存儲空間。

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

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

圖5 索引空間占用百分比

4.3 查詢性能分析

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

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

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

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

圖6 查詢性能比較

5 結語

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

)

[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ù)存儲與查詢研究[D].南京：南京大學,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] 楊彧劍,林波.分布式存儲系統(tǒng)中一致性哈希算法的研究[J].電腦知識與技術,2011,7(22):5295-5296.(YANGYJ,LINB.Researchonconsistenthashingmethodindistributedstoragesystem[J].ComputerKnowledgeandTechnology, 2011, 7(22): 5295-5296.)

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

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

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

[11] 郭棟,王偉,曾國蓀.基于一致性樹分布的數(shù)據(jù)分布式存儲方法[J].計算機應用,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。 基金項目:國家863計劃項目(2013BAB06B04)；中國華能集團公司總部科技項目(HNKJ13-H17-04)；江蘇省自然科學基金資助項目(BK20130852)；水利部公益性行業(yè)科研專項經(jīng)費項目(201501007)。

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

1001-9081(2017)01-0048-06

10.11772/j.issn.1001-9081.2017.01.0048

TP311

A