SL-tgStore：新的時序知識圖譜存儲模型

李松，王哲，張麗平

(哈爾濱理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150080)

隨著科技的不斷進(jìn)步與發(fā)展，萬物互聯(lián)使人們的生活更加便利，群體智能[1]、生物信息網(wǎng)絡(luò)[2]和社交網(wǎng)絡(luò)[3]等應(yīng)用越來越廣泛.Google首先提出知識圖譜的概念，迅速得到了廣泛關(guān)注和研究[4]，出現(xiàn)了許多大型知識圖譜項目，如大規(guī)模知識圖譜Wikidata[5]、YAGO[6]和DBpedia[7].在知識圖譜中，三元組＜主體、謂詞、客體＞稱為知識或事實.知識隨著時間的推移而變化，例如，＜Messi、servedOn、Barcelona＞的三元組作為事實僅出現(xiàn)在2004—2021年.因此，有必要將時間信息引入知識圖譜形成時序知識圖譜.

時序知識圖譜在生活中廣泛存在[8]，其存儲問題具有重要的研究價值.時序知識圖譜本質(zhì)上是隨時間變化的動態(tài)資源描述框架 (resource description framework，RDF)圖，其節(jié)點和邊以及相關(guān)屬性隨時間不斷變化.當(dāng)考慮RDF圖上的時間維度時，很多RDF圖上的問題變得更加復(fù)雜.以往基于靜態(tài)知識圖譜提出的存儲方法已不能有效地解決時序知識圖譜上的存儲問題.

時序知識圖譜可以由若干個靜態(tài)知識圖譜按時間順序組成，表示為一個RDF圖數(shù)據(jù)集，RDF圖可以存為快照或日志.當(dāng)時序知識圖譜更新時，基于快照的存儲方案會保存所有數(shù)據(jù).如果所有時段的快照都存儲在內(nèi)存，圖處理系統(tǒng)只須通過指針重定向就可以在不同時段間快速切換.然而，由于存儲中的高冗余，快照存儲方案效率較低.基于日志的存儲方案將相關(guān)的增量存儲起來，添加到初始快照中獲得目標(biāo)快照，避免冗余存儲.然而，由于額外計算，它在快照切換時引入了更長的延遲.

為了提升時序知識圖譜的存儲與查詢效率，本研究提出結(jié)合快照和日志模式的時序知識圖譜存儲模型SL-tgStore，能在保證高效查詢的同時，有效地降低存儲開銷.本研究的主要貢獻(xiàn)如下.1）針對當(dāng)前時序知識圖譜存儲模型存在的不足，提出新的時序知識圖譜存儲模型SL-tgStore.引入初始RDF快照圖作為時序知識圖譜存儲和處理的基本單元；在接下來時段內(nèi)捕獲時序知識圖譜的更新信息，并存儲當(dāng)前時段的每條RDF日志圖；生成新的初始快照，然后存儲日志.所提模型平衡了內(nèi)存開銷大和查詢效率低的問題.2）針對初始快照數(shù)量過多導(dǎo)致存儲空間開銷大，增量日志數(shù)量多導(dǎo)致查詢時間成本高的問題.提出相應(yīng)的閾值θ來確定初始快照的生成，以達(dá)到初始快照數(shù)量與增量日志數(shù)量的平衡，并提出臨時快照生成算法.3）為了高效地對時序知識圖譜進(jìn)行查詢，基于新提出的存儲模型SL-tgStore，進(jìn)一步提出4種相應(yīng)的索引結(jié)構(gòu)Ttg-hash、Vtg-tree、Ptg-hash和Ltg-tree，以提高時序知識圖譜的查詢檢索效率.

1 相關(guān)工作

知識圖譜領(lǐng)域的一個核心問題是如何有效地存儲RDF數(shù)據(jù)集，目前對于靜態(tài)知識圖譜數(shù)據(jù)庫的底層存儲已經(jīng)有了廣泛的研究.一種是基于關(guān)系型數(shù)據(jù)的RDF數(shù)據(jù)存儲，包括三元組表、水平表、屬性表、垂直劃分、全索引策略和部分索引策略.Harris等[9]采用三元組表存儲知識圖譜，實現(xiàn)起來簡單明了，但在查詢時會產(chǎn)生大量自連接操作導(dǎo)致效率不高.Pan等[10]采用水平表存儲知識圖譜，這種方法使查詢變得更為簡單，但表中的列過多，存在大量空值.Wilkinson[11]采用屬性表存儲知識圖譜，既克服了三元組表的自連接問題,又解決了水平表中列過多的問題，但對大規(guī)模知識圖譜，空值和多值問題仍然存在.Abadi等[12]采用垂直劃分存儲知識圖譜，解決了空值和多值問題，但須建立等同于謂詞數(shù)量的表，維護(hù)更新和查詢開銷都較大.Neumann等[13]采用全索引策略，生成主體、謂詞和客體的6種順序的冗余索引，以提升查詢效率.Yuan等[14]提出2類索引結(jié)構(gòu)，每個謂詞對應(yīng)一個2維位矩陣.另一種是基于圖模型的RDF數(shù)據(jù)存儲，最具代表性的2種管理方案為面向?qū)傩詧D的Neo4j[15]存儲和面向RDF圖的gStore[16]存儲.

現(xiàn)有的時序圖建模形式主要有3類：第1類是時序圖的邊帶有時間信息的標(biāo)簽；第2類以時間為節(jié)點構(gòu)建副本，將時序圖轉(zhuǎn)換成靜態(tài)圖；第3類在離散的時間上為時序圖構(gòu)建相應(yīng)的快照，如將知識圖譜添加單獨的時間維度構(gòu)成時序知識圖譜[17].Han等[18]提出基于快照模型的時序圖存儲分析引擎，其核心設(shè)計包含時序圖內(nèi)存布局和計算調(diào)度.Khurana等[19]提出基于快照的存儲模型，通過管理元素映射表，在有限的內(nèi)存中存儲所有時段的快照.Haubenschild等[20]提出基于日志的存儲模型，將所有快照簡化為4種操作：節(jié)點的增加和刪除、邊的增加和刪除.Ying等[21]提出基于快照和日志組合的混合存儲模型，通過偏斜性感知的策略將2種模型組合使用.Massri等[22]使用優(yōu)化技術(shù)在時序圖管理系統(tǒng)中實現(xiàn)復(fù)制+日志技術(shù).

已有的時序圖存儲模型在使用快照存儲時內(nèi)存開銷大，在使用日志存儲時查詢效率低.為了彌補(bǔ)已有模型的不足，提出新的時序知識圖譜存儲模型SL-tgStore.

2 主要定義

定義1 時序.ti為由特定的時間序列定義的最小不可分解的時間單位（可以是1 min，也可以是1 a，由系統(tǒng)分配的圖形更新的事務(wù)時間來確定），也稱為時段.時序可以形式化表示為T={ti|i∈N}，即為一組完全有序的時段.

定義2 時序知識圖譜.知識圖譜為三元組G=＜V、E、W＞.其中，V表示節(jié)點集合，對應(yīng)所有的主體和客體；E?V×V表示一組有向邊，對應(yīng)謂詞的集合；W:V→R表示節(jié)點權(quán)重值，R∈[0,1.0].時序知識圖譜示意圖如圖1所示.時序知識圖譜TG[t1,tn]表示時間間隔 [t1,tn]內(nèi)一組靜態(tài)知識圖譜的序列{Gt1,Gt2,···,Gtn}，其中時段ti由一組離散時間點組成，Gti表示時段ti的靜態(tài)知識圖譜.

圖1 時序知識圖譜示意圖Fig.1 Schematic diagram of temporal knowledge graph

定義3 快照存儲模型.快照存儲模型是指時序知識圖譜由一系列離散時刻的靜態(tài)快照圖組成，每個靜態(tài)快照包含一個節(jié)點集和一個邊集組成的RDF數(shù)據(jù)集，其形式化定義為

定義4 日志存儲模型.日志存儲模型由一系列日志組成，每個日志包含了該時段節(jié)點和邊的更新數(shù)據(jù)，其形式化定義為

式中：Lti表示所在的時段ti的增量日志，Lti主要包括節(jié)點和邊的增加和刪除、屬性值及權(quán)重的修改.

定義5 時間窗口.時間窗口是每個時段ti所對應(yīng)的知識圖譜的相應(yīng)檢查點的邏輯容器，每個時間窗口存儲RDF快照圖或RDF日志圖，在ti時段，將此時段的時序知識圖譜（TGti）存儲為Gti或Lti.

定義6 時間桶.將時序知識圖譜存儲在時間上不相交的時間段序列中，每個時間桶由若干個時間窗口組成，在每個時間桶的第1個時間窗口存儲初始快照，在其他時間窗口存儲增量日志，其形式化定義為

3 時序知識圖譜存儲方法

3.1 SL-tgStore模型總體結(jié)構(gòu)

SL-tgStore由若干時間桶組成，每個時間桶由一系列的時間窗口組成，引入初始快照作為時序知識圖譜的存儲和處理的基本單元，即在1個時間桶中的第1個時間窗口存儲初始快照.SLtgStore在指定時間段內(nèi)捕獲時序知識圖譜更新信息，然后在接下來的時間窗口存儲增量日志，每條增量數(shù)據(jù)在被存于RDF日志的同時，也用于更新內(nèi)存中的臨時快照.當(dāng)臨時快照滿足閾值條件θ時，SL-tgStore創(chuàng)建一個新的時間桶，時間桶中的初始快照為該時段的臨時快照.時間桶隨著時序知識圖譜的不斷發(fā)展而添加，時序知識圖譜信息可以基于增量日志進(jìn)行擴(kuò)展.

基于SL-tgStore數(shù)據(jù)結(jié)構(gòu)的時序知識圖譜是由所有時間窗口中的初始快照和全部的日志合并而成的，其形式定義為

式中：TG[t1,tn]表示時段t1～tn的時序知識圖譜；Gti表示為第i個時間桶的初始快照，Ltij表示第i個時間桶中第j個時間窗口的增量日志；n表示時間桶的數(shù)目，同時也是初始快照的數(shù)量；m表示時間窗口的數(shù)量.

如圖2所示，在時段t1下，SL-tgStore創(chuàng)建一個新的時間桶，并采用初始快照Gt1存儲，在之后的時段(此時滿足閾值θ)，SL-tgStore采用日志存儲.在接下來的時段t2,t3,···,tn，SL-tgStore依舊建立新的時間桶，并重復(fù)以上存儲模式.

圖2 SL-tgStore存儲結(jié)構(gòu)Fig.2 SL-tgStore storage structure

SL-tgStore存儲模型采用基于時間屬性排列的時間桶存儲模型，保留了一個圖的所有歷史信息，既可以保證良好的存儲開銷，又具備較高的更新和查詢效率.初始快照組Gti包含足夠的信息保證在時段ti可以有效地訪問時序知識圖譜，在存儲開銷方面相比完全快照存儲具備更好的性能.

3.2 時序知識圖譜快照存儲

為了在不犧牲性能的情況下創(chuàng)建緊湊的布局，SL-tgStore引入初始快照作為時序知識圖譜每個時間桶的存儲和處理的基本單元.初始快照負(fù)責(zé)時間桶內(nèi)的第1個時段，也是第1個時間窗口.初始快照將時段t1的時序知識圖譜存儲為基于S、P、O索引結(jié)構(gòu)的鄰接表.初始快照Gt1存儲每個時間桶的開始時段t1的完整RDF圖數(shù)據(jù)，包含足夠的信息以在時段t1內(nèi)的任何點都能訪問RDF圖形數(shù)據(jù).當(dāng)目標(biāo)查詢時段為其他時間窗口時，通過時間桶內(nèi)的初始快照和相鄰的日志完成查詢?nèi)蝿?wù).

時間桶內(nèi)每個初始快照存儲形式由該時段的所有節(jié)點和邊組成，并且加入該時段的節(jié)點權(quán)重信息，初始快照存儲形式定義為

式中：Gti表示ti時的初始快照，Vi表示ti時的節(jié)點集合，對應(yīng)于所有的主體和客體；EiVi×Vi表示ti時的一組有向邊，對應(yīng)謂詞的集合；由于TG[t1,tn]中節(jié)點的權(quán)重不斷變化，用Wi:Vi→R(R∈[0,1.0])表示ti時的節(jié)點權(quán)重.

使用基于S、P、O索引的鄰接表來存儲初始快照Gti.每個節(jié)點V由鄰接表[ID，Label，W，S，O，P]表示，其中ID為節(jié)點ID，Label為其對應(yīng)的URI，W為其對應(yīng)的權(quán)重，S為輸出邊和對應(yīng)相鄰節(jié)點的列表，O為輸入邊和對應(yīng)相鄰節(jié)點的列表，P為自身屬性列表.首先將每個Label根據(jù)類型進(jìn)行分類并存儲在一個塊中，然后再按每個Label的權(quán)重大小對其在塊中排序.每個謂詞根據(jù)流行度（現(xiàn)實世界中被檢索的頻率）進(jìn)行排序，以便在查詢中更快定位到流行度更高的謂詞鏈接的節(jié)點.

對時間桶為2021年的時序知識圖譜初始快照的存儲進(jìn)行分析.如圖1為時序知識圖譜快照Gti，如圖3所示為其數(shù)據(jù)結(jié)構(gòu).第1個存儲的是類型為“person”的塊，第2個存儲的是類型為“club”的塊，塊中鏈表頭按權(quán)重大小排序順序.從節(jié)點ID為“Messi”開始第1條邊謂詞為“Husband”，指向“Antonella”，然后以謂詞“Friend”開始，指向“Neymar”，由S塊指向.從節(jié)點“Messi”開始的第2條邊謂詞為“Awards”，指向“Ballon d'Or”，然后以謂詞“servedOn”開始，指向“PSG”，由O塊指向.節(jié)點Messi”的第3條邊存儲了“Messi”的屬性集合如“hasName”，“gender”，由P塊指向.

圖3 RDF快照存儲Fig.3 RDF snapshot storage

3.3 時序知識圖譜日志存儲

日志存儲模型在以時間屬性為索引的RDF圖中存儲了所有增量日志，其支持更新節(jié)點和邊的值直接插入，不涉及任何壓縮和轉(zhuǎn)換操作，具有較高的日志更新效率和存儲效率.日志組由初始快照Gti到Gti+1之間每個時段的圖形狀態(tài)更新組成，并且以時段為索引，以便查詢時快速找到日志.所有日志操作簡化為5種：節(jié)點的增加(NINS)和刪除(NDEL)、邊的增加(EINS)和刪除(EDEL)以及節(jié)點權(quán)重的更改（NMOD）.全部更新日志按時段劃分，存儲在相應(yīng)的時間窗口中，日志存儲形式化定義為

每個操作方式由三元組組成，形式化定義如下：

式中：destination為操作的目的節(jié)點，op-type為5種操作類型，value為操作值.

每個增量日志由鄰接表構(gòu)成，不需要存儲邊的源，因為鏈表只包含具有相同源節(jié)點的操作.在具體實現(xiàn)中須將增量日志的2個實例組合在一起.使用基于INS、DEL的鄰接表來存儲增量日志每個節(jié)點U由鄰接表[ID，Label，W，INS，DEL]表示，其中INS為節(jié)點或邊插入的列表，當(dāng)指向節(jié)點為本身ID時，插入的是節(jié)點本身或權(quán)重，當(dāng)指向節(jié)點為屬性時，插入的是節(jié)點本身屬性，否則插入的是節(jié)點之間的關(guān)系；DEL為節(jié)點或邊刪除的列表，當(dāng)指向節(jié)點為本身ID時，刪除的是節(jié)點本身，否則是節(jié)點與節(jié)點之間的關(guān)系；插入節(jié)點時直接在日志中插入節(jié)點的ID.

圖4 RDF日志存儲Fig.4 RDF log storage

首先新建節(jié)點Barcelona，并將其權(quán)重更改為0.45，并插入節(jié)點ID為4的相關(guān)鏈接和自身屬性；刪除節(jié)點Messi與節(jié)點PSG的關(guān)系以及節(jié)點Messi與節(jié)點Ballon d'Or的關(guān)系，并增加節(jié)點Messi與節(jié)點Barcelona的servedOn關(guān)系以及節(jié)點Neymar與節(jié)點Ballon d'Or的Awards關(guān)系；最后刪除ID為2的節(jié)點Nasser.

3.4 時間桶生成

時序知識圖譜由若干時間桶組成，SL-tgStore必須決定如何調(diào)度跨越多個時間桶的計算.一個有效方法是為每個初始快照更新迭代計算，更新存儲過程主要包括3個步驟：更新數(shù)據(jù)存儲到增量日志；增量日志合并到初始快照形成臨時快照；將合并完成的初始快照和日志組存儲到時間桶中.由于臨時快照須在滿足一定條件時被存于新的時間桶中作為初始快照，則初始快照的選取和相應(yīng)的閾值設(shè)置尤為重要.初始快照不僅決定了每個時間桶的規(guī)模，而且直接影響SL-tgStore的存儲開銷和查詢成本.如果相鄰時間桶之間的時間跨度過大，則時間桶中的日志規(guī)模變大，導(dǎo)致查詢檢索的數(shù)據(jù)合并規(guī)模增大，進(jìn)而增加了查詢時間；如果時間跨度過小，則時間桶中初始快照數(shù)目增多，進(jìn)而增加了存儲空間開銷.

基于日志規(guī)模的方法生成新的時間桶，即臨時快照在滿足一定條件時被存儲于下一個時間桶中作為初始快照，初始快照存儲的選取的相應(yīng)閾值根據(jù)多個相鄰日志中操作數(shù)總和與當(dāng)前時間桶中的初始快照中邊與節(jié)點總和的比值θ來設(shè)置.

當(dāng)θ滿足如下公式時，將生成的臨時快照存儲為初始快照Gti+1：

式中：|Gti|表示時段ti初始快照的節(jié)點和邊的總數(shù)表示時間段ti后續(xù)時段的相鄰日志操作次數(shù)總和.

為了更有效率地生成初始快照，提出臨時快照生成算法.時段的臨時快照是由時段的日志合并到時段ti的初始快照所生成的.將時段ti+1的更新日志合并到ti時的快照，生成時段ti+1的臨時快照.先在時段ti的初始快照中找到日志中的源節(jié)點，再按照其操作類型對節(jié)點或邊進(jìn)行刪除或添加.臨時快照生成算法如算法1所示.

算法1臨時快照生成算法.

3.5 索引設(shè)計

為了更高效地對SL-tgStore進(jìn)行查詢，提出4種索引結(jié)構(gòu)來支持查詢操作.第1種是基于時間窗口建立的哈希索引(Ttg-hash)，用于索引對應(yīng)查詢圖的初始快照和日志；第2種是結(jié)合哈希和B+樹結(jié)構(gòu)的索引(Vtg-tree)，用于索引初始快照中已知節(jié)點的查詢；第3種是基于謂詞建立的哈希索引(Ptg-hash)，用于對初始快照中的謂詞進(jìn)行索引；第4種索引類似于第2種，是結(jié)合哈希和B+樹結(jié)構(gòu)的索引(Ltg-tree)，用于索引日志中已知節(jié)點的查詢.

1）Ttg-hash索引是基于hash分塊的索引結(jié)構(gòu)，SL-tgStore結(jié)構(gòu)為具有時間順序的一系列時間窗口.索引是一個hash塊，其大小等于初始快照的數(shù)量，每個時間桶中的時間窗口映射到同一個hash塊中，用來直接找到初始快照或相關(guān)增量日志在內(nèi)存中的位置.

如圖5所示為Ttg-hash索引的詳細(xì)結(jié)構(gòu).圖中，t1表示在時段t1時的初始快照，表示在時段時的增量日志，表示在時段時的增量日志.

圖5 Ttg-hash索引示意圖Fig.5 Schematic diagram of Ttg-hash index

2）Vtg-tree是2層索引，第1層索引先通過哈希函數(shù)定位到具體的節(jié)點類型分塊；索引的第2部分是類似B+樹的結(jié)構(gòu)，葉節(jié)點的格式為＜key,ptr＞，其中key為節(jié)點，可以是主體或客體，ptr為以key開頭或以key結(jié)尾的謂詞列表.非葉節(jié)點的條目格式為＜key,subptr＞，其中key用于比較和路由，確定搜索方向，subptr是指向子樹根節(jié)點的指針，指引搜索的下一層非葉子節(jié)點.

如圖6所示為Vtg-tree第2層索引的詳細(xì)結(jié)構(gòu).Vi為節(jié)點標(biāo)簽，當(dāng)標(biāo)簽為0時，P為記錄為＜Pi，Vptr，Vnext＞的項目列表，Pi為以Vi開頭的邊的謂詞，Vptr為物理存儲中的塊，Vnext為下一項；當(dāng)標(biāo)簽為1時，Pi為以Vi結(jié)尾的邊的謂詞；當(dāng)標(biāo)記為2時，Pi為與Vi相鄰的所有屬性.

圖6 Vtg-tree索引示意圖Fig.6 Schematic diagram of Vtg-tree index

3）如果一個查詢想要知道所有人在給定時段內(nèi)的俱樂部效力經(jīng)歷，那么只有相應(yīng)查詢圖的謂詞“serverdOn”是已知的.顯然，根據(jù)Vtg-tree索引結(jié)構(gòu)不能快速找到謂詞，因此提出能快速匹配謂詞的哈希索引Ptg-hash.鏈接邊上的謂詞標(biāo)簽被存放到哈希函數(shù)中，如圖7所示為Ptg-hash的結(jié)構(gòu).

圖7 Ptg-hash索引示意圖Fig.7 Schematic diagram of Ptg-hash index

首先采用hashPJW算法為謂詞建立哈希函數(shù)，Pi表示謂詞，謂詞鍵Pi與主體鍵{S1,S2,···,Sn}的排序列表相關(guān)聯(lián)，每個主體Si鏈接到客體鍵{O1,O2,···,On}.例如，f(servedOn)可以通過哈希函數(shù)找出包含鍵“servedOn”的塊，可以從塊中查詢謂詞“servedOn”.很容易獲得滿足時間要求的快照中的主體和客體.

4）查詢只在知識圖譜的局部區(qū)域上進(jìn)行，因此在查詢存儲日志的時間窗口時，直接基于快照查詢結(jié)果在日志上查詢.Ltg-tree索引與Vtg-tree索引類似，用于快速定位到日志中的節(jié)點，用以生成臨時快照或直接進(jìn)行查詢.第1層索引通過hash函數(shù)映射到節(jié)點的類型，如圖8所示為Ltgtree第2層索引的詳細(xì)結(jié)構(gòu).圖中，Vi為節(jié)點標(biāo)簽.當(dāng)標(biāo)簽為0時，P為刪除的記錄為＜Vptr，Vnext＞的項目列表，Vptr為物理存儲中的塊，Vnext為下一項；當(dāng)標(biāo)簽為1時，P為插入的記錄為＜Vptr，Pi，Vnext＞的項目列表，Pi為以Vi結(jié)尾的鏈接邊的謂詞.

圖8 Ltg-tree索引示意圖Fig.8 Schematic diagram of Ltg-tree index

4 實驗設(shè)計與分析

對所提出的時序知識圖譜存儲模型SLtgStore的整體性能進(jìn)行實驗分析.首先分析通過配置適當(dāng)?shù)膮?shù)θ來調(diào)整SL-tgStore的性能，接著分別在模型SL-tgStore的快照和日志模式下對索引性能進(jìn)行實驗分析，最后將SL-tgStore和現(xiàn)有存儲模型在真實數(shù)據(jù)集上對查詢時間和存儲開銷進(jìn)行實驗分析.

實驗對比指標(biāo)包括存儲時序知識圖譜的內(nèi)存開銷和查詢?nèi)我鈺r刻快照的時間開銷.實驗隨機(jī)生成100個查詢時段，然后采用類SPARQL[23]的查詢語句計算SL-tgStore、Pensieve、Copy+Log[21]和Neo4j[15]的平均查詢時間.查詢中使用的時間點是在數(shù)據(jù)集的時間跨度內(nèi)統(tǒng)一選擇的，以避免偏向于更接近檢查點的時間點的分布，并且同時保證每一個查詢時段僅對應(yīng)一個時間窗口.

4.1 實驗配置和數(shù)據(jù)集

所使用的計算機(jī)操作系統(tǒng)為 Windows 10（64位），Intel? CoreTMi7-8550U CPU @1.80 GHz 2.0 GHz處理器，32 GB運行內(nèi)存.

實驗選用4個基準(zhǔn)測試數(shù)據(jù)集：1）GDELT數(shù)據(jù)庫，記錄了1969年至今的每個國家的新聞，且每隔15 min更新一次數(shù)據(jù)；2）ICEWS數(shù)據(jù)庫，涵蓋100多個數(shù)據(jù)源以及250個國家和區(qū)域的政治事件，且每天更新一次數(shù)據(jù)；3）協(xié)作式多語言輔助知識庫Wikidata；4）馬克斯·普朗克研究所研制的鏈接數(shù)據(jù)庫YAGO.數(shù)據(jù)集的節(jié)點權(quán)重被定義為節(jié)點度數(shù)除以所有節(jié)點度數(shù)的最大值.具體信息如表1所示.表中，|V|、|E|、|T|分別表示節(jié)點個數(shù)、邊條數(shù)、時序知識圖譜的更新間隔.

表1 實驗數(shù)據(jù)集信息Tab.1 Experimental dataset information

4.2 參數(shù)θ的設(shè)定

1）存儲空間評估.實驗評估利用SL-tgStore模型在真實數(shù)據(jù)集上所獲得的存儲空間增益.如圖9(a)所示，展示了通過SL-tgStore處理數(shù)據(jù)集Wikidata、ICEWS、GDELT、YAGO時的空間開銷Mc情況.可以看出，當(dāng)參數(shù)θ從0.01增加到0.08時，數(shù)據(jù)集占用的空間顯著減少.隨著θ的增大，SL-tgStore存儲的增量日志增多，占用的空間較少.在θ＜0.01的情況下，因為此時存儲的增量日志較少，占用的內(nèi)存空間則會增加.

圖9 不同θ下的內(nèi)存開銷與查詢時間對比Fig.9 Comparison of memory overhead and query time under different θ

2）查詢時間評估.進(jìn)一步評估模型在真實數(shù)據(jù)集上的查詢時間.如圖9(b)所示為θ對查詢時間開銷tc的影響，結(jié)果驗證了隨著參數(shù)θ從0.01增加到0.08，查詢時間開銷輕微增加，這是因為隨著θ的增大，SL-tgStore存儲的增量日志增多，須生成查詢時刻的臨時快照才能得出查詢結(jié)果.在θ＞0.08的情況下，此時存儲的增量日志較多，查詢所消耗的時間較多.

對 SL-tgStore 更新過程中，何時生成初始快照，即相應(yīng)的參數(shù) θ 的選取合理性進(jìn)行驗證分析.在 SL-tgStore 處理不同真實數(shù)據(jù)集時，不同參數(shù) θ下的內(nèi)存開銷和查詢時間成本之間對比情況如圖 9 所示.可以看出，雖然處理的數(shù)據(jù)集規(guī)模不同，但是內(nèi)存開銷和查詢時間隨著參數(shù) θ 變化的趨勢基本一致，SL-tgStore 存儲模型的內(nèi)存開銷隨著 θ 的增加呈下降趨勢，而查詢時間成本隨著 θ的增加呈上升趨勢.可以看出，在處理不同時序知識圖譜真實數(shù)據(jù)集時，SL-tgStore 存儲模型的內(nèi)存開銷和查詢時間在參數(shù) θ ≈ 0.03時為明顯拐點，此時SL-tgStore存儲模型的效率最優(yōu)，因此，選取參數(shù) θ=0.03 作為新時間桶生成條件.

4.3 索引評估

從基于快照查詢和日志查詢2個角度來評估使用索引的查詢性能.如圖10所示為不同數(shù)據(jù)集上的查詢時間開銷.可以看出，基于初始快照的查詢在4個數(shù)據(jù)集上都具有一定的查詢成本，但在使用本研究提出的Ttg-hash和Ptg-hash索引結(jié)構(gòu)的情況下，基于快照查詢的時間開銷有大幅度的降低；在使用本研究提出的Ltg-tree索引結(jié)構(gòu)的情況下，基于日志查詢的時間開銷有了大幅度的降低.

圖10 索引對查詢時間的影響Fig.10 Impact of index on query time

4.4 模型對比與分析

將SL-tgStore的存儲開銷和查詢時間與其他存儲模型的進(jìn)行對比與分析，比較對象包括快照和日志結(jié)合的混合存儲模型Pensieve和Copy+Log，以及面向知識圖譜的商業(yè)圖形數(shù)據(jù)庫Neo4j.其中，在Neo4j上開發(fā)了一個時間層，以實現(xiàn)時序知識圖譜的存儲和評估.如圖11所示為各個系統(tǒng)在不同真實數(shù)據(jù)集上的總體性能對比情況.

圖11 不同模型的內(nèi)存開銷和查詢時間對比Fig.11 Comparison of memory overhead and query time of different models

1）內(nèi)存開銷對比.如圖11(a)所示為處理不同圖數(shù)據(jù)集時各個系統(tǒng)的內(nèi)存開銷情況.Neo4j的內(nèi)存開銷明顯大于SL-tgStore、Pensieve和Copy+Log的，主要原因是Neo4j并沒有考慮事務(wù)時間上的問題，只是存儲靜態(tài)知識圖譜，每個時刻都以快照形式存儲數(shù)據(jù)，造成了存儲的冗余.相比于固定快照和日志數(shù)量的Copy+Log模型和通過偏斜性感知組合快照和日志的Pensieve模型，SLtgStore模型的內(nèi)存開銷略高，主要是由于SLtgStore模型為了優(yōu)化查詢速度采用了索引結(jié)構(gòu)，增加了一定的存儲開銷.

2）查詢時間對比.如圖11(b)所示，在處理不同數(shù)據(jù)集時，SL-tgStore的查詢效率明顯優(yōu)于Copy+Log、Pensieve和Neo4j，其中Neo4j的效率最差.當(dāng)在SL-tgStore中評估查詢時間時，搜索空間被修剪為多個選定的時間窗口，這些時間窗口的時間間隔與查詢的時間范圍相交，可以直接在這些時間窗口的臨時快照上查詢.SL-tgStore模型在查詢效率上相比Copy+Log和Pensieve模式有大幅度的提升，主要因為Copy+Log和Pensieve模式并未采用有效的索引形式來降低查詢檢索時間.Neo4j是基于屬性圖存儲開發(fā)出的圖形數(shù)據(jù)庫，相比于存儲RDF三元組＜S、P、O＞類型的關(guān)系型數(shù)據(jù)庫，所需要的查詢時間開銷更大.

5 結(jié)語

針對時序知識圖譜的存儲模型和查詢方法進(jìn)行深入研究，提出結(jié)合快照和日志存儲模式的RDF動態(tài)圖存儲模型SL-tgStore.該模型存儲RDF快照和RDF日志，并設(shè)定參數(shù)θ作為生成初始RDF快照的條件.為了有效地對SL-tgStore進(jìn)行查詢，提出4種索引結(jié)構(gòu)來支持后續(xù)的查詢操作.進(jìn)一步在真實數(shù)據(jù)集上進(jìn)行評估測試.實驗結(jié)果表明，SL-tgStore模型在內(nèi)存消耗和查詢時間方面具有較大的優(yōu)勢.下一步研究重點將主要集中在時序知識圖譜上的查詢優(yōu)化方面.