基于資源描述框架圖切分與頂點(diǎn)選擇性的高效子圖匹配方法

關(guān)皓元 朱斌 李冠宇 蔡永嘉

摘 要：在SPARQL查詢(xún)過(guò)程中，含有復(fù)雜結(jié)構(gòu)的資源描述框架（RDF）圖的查詢(xún)效率低下。為此，通過(guò)分析幾種RDF圖的基本結(jié)構(gòu)與RDF頂點(diǎn)的選擇性，提出RDF三元組模式選擇性（RTPS）——一種基于RDF頂點(diǎn)選擇性的圖結(jié)構(gòu)切分規(guī)則，以提高面向RDF圖的子圖匹配效率。首先，根據(jù)謂詞結(jié)構(gòu)在數(shù)據(jù)圖與查詢(xún)圖中的通性建立RDF相鄰謂詞路徑（RAPP）索引，將數(shù)據(jù)圖結(jié)構(gòu)轉(zhuǎn)化為傳入傳出雙向謂詞路徑結(jié)構(gòu)以確定查詢(xún)頂點(diǎn)的搜索空間，并加快頂點(diǎn)的過(guò)濾;接著，通過(guò)整數(shù)線(xiàn)性規(guī)劃（ILP）問(wèn)題計(jì)算建模將復(fù)雜RDF查詢(xún)圖結(jié)構(gòu)分解為若干結(jié)構(gòu)簡(jiǎn)單的查詢(xún)子圖，通過(guò)分析RDF頂點(diǎn)在查詢(xún)圖中的相鄰子圖結(jié)構(gòu)與特征，確立查詢(xún)頂點(diǎn)的選擇性以確定最優(yōu)切分方式;然后，通過(guò)RDF頂點(diǎn)選擇性與相鄰子圖的結(jié)構(gòu)特征來(lái)縮小查詢(xún)頂點(diǎn)的搜索空間范圍，并在數(shù)據(jù)圖中找到符合條件的RDF頂點(diǎn);最后，遍歷數(shù)據(jù)圖以找到與查詢(xún)子圖結(jié)構(gòu)相匹配的子圖結(jié)構(gòu)，將得到的子圖進(jìn)行連接并將其作為查詢(xún)結(jié)果輸出。實(shí)驗(yàn)采用控制變量法，比較了RTPS、RDF子圖匹配（RSM）、RDF-3X、GraSS與R3F的查詢(xún)響應(yīng)時(shí)間。實(shí)驗(yàn)結(jié)果充分表明，與其他4種方法相比，當(dāng)查詢(xún)圖復(fù)雜度高于9時(shí)，RTPS的查詢(xún)響應(yīng)時(shí)間更短，具有更高的查詢(xún)效率。

關(guān)鍵詞：SPARQL查詢(xún)處理;資源描述框架;子圖匹配;圖結(jié)構(gòu)切分;頂點(diǎn)選擇性

中圖分類(lèi)號(hào)： TP181; TP311

文獻(xiàn)標(biāo)志碼：A

Abstract： As the graph-based query in SPARQL query processing becames more and more inefficient due to the increasing structure complexity of Resource Description Framework （RDF） in the graph， by analyzing the basic structure of RDF graphs and the selectivity of the RDF vertices， RDF Triple Patterns Selectivity （RTPS） was proposed to improve the efficienccy of subgraph matching for graph with RDF， which is a graph structure segmentation rule based on selectivity of RDF vertices. Firstly， according the commonality of the predicate structure in the data graph and the query graph， an RDF Adjacent Predicate Path （RAPP） index was built， and the data graph structure was transformed into incoming-outgoing predicate path structure to determine the search space of query vertices and speed up the filtering of RDF vertices. Secondly， the model of Integer Linear Programming （ILP） problem was built to divide a RDF query graph with complicated structure into several query subgraphs with simple structure. By analyzing the structure characteristics of the RDF vertices in the adjacent subgraphs， the selectivity of the query vertices was established and the optimal segmentation method was determined. Thirdly， with the searching space narrowed down by the RDF vertex selectivity and structure characteristics of adjacent subgraphs， the matchable RDF vertices in the data graph were found. Finally， the RDF data graph was traversed to find the subgraphs whose structure matched the structure of query subgraphs. Then， the result graph was output by joining the subgraphs together. The controlling variable method was used in the experiment to compare the query response time of RTPS， RDF Subgraph Matiching （RSM）， RDF-3X， GraSS and R3F. The experimental results show that， compared with the other four methods， when the number of triple patterns in a query graph is more than 9， RTPS has shorter query response time and higher query efficiency.

Key words： SPARQL query processing; Resource Description Framework （RDF）; subgraph matching; graph structure segmentation; vertex selectivity

0 引言

資源描述框架（Resource Description Framework， RDF）是一種描述語(yǔ)義Web中機(jī)器信息的標(biāo)準(zhǔn)數(shù)據(jù)模型，SPARQL是經(jīng)W3C認(rèn)證的面向RDF圖的標(biāo)準(zhǔn)圖查詢(xún)語(yǔ)言[1]，而模式匹配是SPARQL查詢(xún)處理中的核心問(wèn)題，其目的是在復(fù)雜的RDF圖數(shù)據(jù)中快速地搜索符合查詢(xún)請(qǐng)求的結(jié)果。基于SPARQL圖查詢(xún)語(yǔ)言的性質(zhì)，其表達(dá)模式可由如下所示的基于三元組的關(guān)系模型轉(zhuǎn)換為基于圖的關(guān)系模型（如圖1（a）），因此，面向RDF圖的模式匹配可理解為在RDF數(shù)據(jù)圖（圖1（b））中搜索到同構(gòu)與查詢(xún)圖的數(shù)據(jù)子圖的遍歷過(guò)程（圖1），該問(wèn)題也可以稱(chēng)為子圖匹配問(wèn)題[2]。近年來(lái)，隨著知識(shí)圖譜被廣泛地認(rèn)知，RDF數(shù)據(jù)量被大量發(fā)布，RDF數(shù)據(jù)模型對(duì)語(yǔ)義數(shù)據(jù)的表示也更加復(fù)雜，而以往的基于RDF三元組的連接處理已不再適用于處理復(fù)雜的SPARQL查詢(xún)，復(fù)雜的圖結(jié)構(gòu)會(huì)導(dǎo)致RDF節(jié)點(diǎn)間的重復(fù)連接次數(shù)與三元組之間的連接次數(shù)大大增加;隨著三元組之間連接次數(shù)的增加，產(chǎn)生大量中間結(jié)果冗余的情況也愈發(fā)嚴(yán)重，由于RDF查詢(xún)圖的復(fù)雜性以及數(shù)據(jù)海量性使得在SPARQL查詢(xún)過(guò)程中的時(shí)間效率很難得到保證[3]。

在子圖匹配中，如何快速地在數(shù)據(jù)圖中找到與查詢(xún)圖同構(gòu)的子圖是其核心問(wèn)題，由于RDF圖結(jié)構(gòu)的復(fù)雜性與頂點(diǎn)的不同選擇性（由查詢(xún)圖中頂點(diǎn)的搜索空間和相鄰圖結(jié)構(gòu)決定）使得在處理復(fù)雜查詢(xún)圖時(shí)的頂點(diǎn)選擇順序成為了難題。出于對(duì)謂詞在RDF數(shù)據(jù)圖與查詢(xún)圖中的結(jié)構(gòu)通性的考慮，目前一些解決方案選擇了提取RDF圖中的傳入謂詞路徑的方法，將RDF圖表示為基于頂點(diǎn)的傳入謂詞路徑樹(shù)，并將頂點(diǎn)分類(lèi)存儲(chǔ)到相應(yīng)的謂詞結(jié)構(gòu)中，在傳入謂詞路徑樹(shù)中搜索與查詢(xún)圖謂詞路徑結(jié)構(gòu)相匹配的謂詞路徑并在數(shù)據(jù)圖中提取該謂詞路經(jīng)所在的子圖結(jié)構(gòu)作為查詢(xún)結(jié)果，這種方法雖然縮減了元組模式的連接過(guò)程，但是由于有向圖的特性，會(huì)存在入度為0的RDF頂點(diǎn)而導(dǎo)致該頂點(diǎn)不會(huì)被存入索引中，當(dāng)數(shù)據(jù)圖中某一傳入謂詞路徑過(guò)長(zhǎng)（路徑包含4個(gè)或4個(gè)以上的謂詞），根據(jù)排列組合的思想可知，謂詞路徑樹(shù)中的謂詞結(jié)構(gòu)兩兩組合將導(dǎo)致其構(gòu)建代價(jià)呈指數(shù)上升，并且，將頂點(diǎn)存入相應(yīng)的謂詞結(jié)構(gòu)下，會(huì)導(dǎo)致嚴(yán)重的冗余現(xiàn)象從而浪費(fèi)大量存儲(chǔ)空間。

基于此，本文通過(guò)挖掘RDF數(shù)據(jù)圖與查詢(xún)圖的結(jié)構(gòu)與語(yǔ)義信息，建立一種高效處理子圖匹配問(wèn)題的方法——RDF三元組模式選擇性（RDF Triple Patterns Selectivity， RTPS）。為了保證RDF信息的完整性，在該方法中提出了基于分類(lèi)思想學(xué)方法與RDF頂點(diǎn)選擇性的RDF圖結(jié)構(gòu)切分規(guī)則，并按照該規(guī)則將復(fù)雜查詢(xún)圖切分為多個(gè)結(jié)構(gòu)簡(jiǎn)單的查詢(xún)子圖，以降低整個(gè)執(zhí)行過(guò)程的計(jì)算復(fù)雜度，減少由于過(guò)多的頂點(diǎn)連接而產(chǎn)生的中間結(jié)果冗余情況。謂詞是RDF數(shù)據(jù)語(yǔ)義關(guān)系的表示形式，在基于圖的查詢(xún)處理中，謂詞結(jié)構(gòu)在RDF數(shù)據(jù)圖與查詢(xún)圖中是相通的，通過(guò)對(duì)該語(yǔ)義信息的分析，提出了基于RDF相鄰謂詞結(jié)構(gòu)（RDF Adjacent Predicate Structure， RAPS）的倒排索引，索引整體為樹(shù)型結(jié)構(gòu)，對(duì)比以往的單向謂詞路徑索引，同時(shí)考慮了數(shù)據(jù)圖中的頂點(diǎn)作為主題與賓語(yǔ)的不同謂詞結(jié)構(gòu)，通過(guò)該索引將數(shù)據(jù)圖中的頂點(diǎn)按照不同的謂詞結(jié)構(gòu)分類(lèi)存儲(chǔ)以確定查詢(xún)頂點(diǎn)的初始搜索空間。該索引加快了頂點(diǎn)過(guò)濾，而且因?yàn)榈古潘饕姆奖阈耘c高效性，不會(huì)因?yàn)閿?shù)據(jù)圖結(jié)構(gòu)復(fù)雜而產(chǎn)生巨大搭建代價(jià)的后果。在查詢(xún)圖切分之后，通過(guò)任意兩個(gè)相鄰的查詢(xún)子圖結(jié)構(gòu)來(lái)縮小搜索空間的范圍，在最終確定的搜索空間中尋找頂點(diǎn)所在的子圖結(jié)構(gòu)并作為查詢(xún)子圖的綁定子圖。最后，將幾個(gè)綁定子圖進(jìn)行連接并作為最終結(jié)果圖輸出。

本文的主要工作如下：

1）提出并建立了RDF相鄰謂詞路徑（RDF Adjacent Predicate Path， RAPP）索引結(jié)構(gòu)。分別提取RDF數(shù)據(jù)圖中頂點(diǎn)作為主題與賓語(yǔ)時(shí)的謂詞結(jié)構(gòu)，將該結(jié)構(gòu)組成傳入傳出謂詞路徑樹(shù)，樹(shù)中的節(jié)點(diǎn)代表謂詞結(jié)構(gòu)。數(shù)據(jù)圖中的頂點(diǎn)按照其謂詞結(jié)構(gòu)分類(lèi)存儲(chǔ)至每個(gè)謂詞結(jié)構(gòu)下的頂點(diǎn)列表V-list中，以便確立查詢(xún)頂點(diǎn)的搜索空間，加快RDF頂點(diǎn)的過(guò)濾。

2）提出了基于整數(shù)線(xiàn)性規(guī)劃（Integer Linear Programming， ILP）建模與RDF頂點(diǎn)選擇性的查詢(xún)圖切分規(guī)則。將搜索最小子圖結(jié)構(gòu)的處理過(guò)程抽象為ILP問(wèn)題的建模，通過(guò)頂點(diǎn)的搜索空間與圖中的度確立RDF頂點(diǎn)選擇性，在得到的多種切分方案下加入對(duì)RDF頂點(diǎn)選擇性的考慮，最終確定最優(yōu)切分方案將復(fù)雜查詢(xún)圖進(jìn)行切分以得到若干結(jié)構(gòu)簡(jiǎn)單的查詢(xún)子圖。

3）給出了基于貪心思想與頂點(diǎn)相鄰結(jié)構(gòu)的子圖匹配處理過(guò)程。在查詢(xún)圖切分之后，將RDF頂點(diǎn)選擇性與貪心算法思想相結(jié)合，并設(shè)計(jì)相關(guān)算法來(lái)表示子圖匹配與子圖連接的處理過(guò)程。

4）與相關(guān)方法進(jìn)行對(duì)比以驗(yàn)證本文方法的有效性。分別采用真實(shí)世界數(shù)據(jù)集與合成數(shù)據(jù)集進(jìn)行廣泛的實(shí)驗(yàn)來(lái)評(píng)估RTPS方法的適用性與高效性，實(shí)驗(yàn)過(guò)程采用控制變量法，綜合實(shí)驗(yàn)結(jié)果表明RTPS的綜合查詢(xún)處理性能要優(yōu)于RDF子圖匹配（RDF SubgraphMatching， RSM）[5]、RDF-3X[6]、R3F[7]與Grass[8]。

1 相關(guān)工作

子圖匹配也被稱(chēng)為子圖同構(gòu)，是基于圖的查詢(xún)處理中的核心問(wèn)題，對(duì)該問(wèn)題的研究已經(jīng)成為熱點(diǎn)[9-10]。本文將目前的一些查詢(xún)優(yōu)化方法按照處理模型分為基于RDF三元組的優(yōu)化方法與基于RDF圖特征的優(yōu)化方法來(lái)分別介紹。

1）基于RDF三元組的優(yōu)化方法。Kalayci等[11]提出了基于蟻群優(yōu)化（Ant Colony Optimization， ACO）算法的RDF三元組模式重排序方法，其核心在于將三元組模式抽象為權(quán)重矩陣，以三元組的選擇性作為矩陣的權(quán)重，通過(guò)螞蟻?zhàn)杂蛇x擇道路所留下的信息素密度，將三元組模式的輸入順序打亂并重新排序。該方法的缺陷在于權(quán)重矩陣的構(gòu)建對(duì)于包含環(huán)的查詢(xún)會(huì)產(chǎn)生路徑冗余的情況，使得螞蟻信息素的重復(fù)產(chǎn)生從而導(dǎo)致權(quán)重計(jì)算的偏差，最終得到的三元組模式的基數(shù)值會(huì)高于實(shí)際值;而且當(dāng)輸入的三元組模式數(shù)量龐大時(shí)，ACO算法給出的可行解會(huì)在一定程度上偏離最優(yōu)解。

RDF-3X[6]是一種基于三元組關(guān)系表的SPARQL查詢(xún)引擎，它使用B+樹(shù)作為底層索引結(jié)構(gòu)，以三元組〈s， p， o〉分別作為索引基準(zhǔn)與排序關(guān)鍵Key設(shè)計(jì)了6種索引屬性表來(lái)分類(lèi)存儲(chǔ)RDF數(shù)據(jù)。每個(gè)屬性表中設(shè)置一個(gè)查詢(xún)優(yōu)化器，它將屬性表中的RDF頂點(diǎn)統(tǒng)計(jì)信息轉(zhuǎn)換為基于B+樹(shù)的連接樹(shù)，連接樹(shù)決定了查詢(xún)性能，但是表中的元素在連接過(guò)程中產(chǎn)生的自我連接與表間元素的跨表連接會(huì)產(chǎn)生較高的查詢(xún)代價(jià)，因此，隨著RDF數(shù)據(jù)量增大，其查詢(xún)代價(jià)呈指數(shù)性增長(zhǎng)。Jena[12]和Sesame[13]通過(guò)建立大型三元組屬性倒排列表，以謂詞為排序關(guān)鍵Key來(lái)將連接同一謂詞屬性的RDF頂點(diǎn)進(jìn)行分類(lèi)存儲(chǔ)，在表中可根據(jù)謂詞同時(shí)訪(fǎng)問(wèn)幾個(gè)RDF屬性值并將其進(jìn)行聚類(lèi)以提高頂點(diǎn)過(guò)濾速度并減少三元組的連接次數(shù)，這種基于三元組屬性值的倒排列表雖然提高了過(guò)濾速度，并以倒排列表的優(yōu)勢(shì)減少了存儲(chǔ)空間的浪費(fèi)，但是它需要用戶(hù)提供聚類(lèi)決策并保留先前的查詢(xún)?nèi)罩荆圆⒉痪哂衅者m性;而且由于表的建立非規(guī)范化，很容易導(dǎo)致連接過(guò)程中的空值與屬性值重復(fù)，從而存在查詢(xún)返回結(jié)果為空值的情況，因此降低了查準(zhǔn)率。

2）基于RDF圖特征的優(yōu)化方法。該類(lèi)優(yōu)化方法普遍通過(guò)在RDF三元組的基礎(chǔ)上添加對(duì)圖結(jié)構(gòu)特征的考慮。GRIN[14]使用圖分割技術(shù)并參考RDF圖中頂點(diǎn)距離的信息來(lái)建立基于圖查詢(xún)的索引，索引結(jié)構(gòu)為平衡二叉樹(shù)，其中，樹(shù)的節(jié)點(diǎn)代表一個(gè)RDF三元組，這種結(jié)構(gòu)間的轉(zhuǎn)換形式可大大節(jié)省數(shù)據(jù)的存儲(chǔ)空間;但是索引結(jié)構(gòu)存儲(chǔ)在內(nèi)存中，當(dāng)數(shù)據(jù)量較大時(shí)，索引的運(yùn)行將產(chǎn)生高昂的代價(jià)。在g-index[15]中，提出了“子圖辨別比率”這一因素，通過(guò)一些方法計(jì)算子圖的“辨別力”，當(dāng)數(shù)據(jù)圖中某一子圖結(jié)構(gòu)“辨別力”很強(qiáng)時(shí)，便以該子圖作為索引特征項(xiàng)，這使得g-index具有很好的子圖過(guò)濾性能;但是這種以圖結(jié)構(gòu)特征為過(guò)濾核心的索引要求RDF數(shù)據(jù)圖必須含有特征鮮明的子圖結(jié)構(gòu)，當(dāng)一個(gè)數(shù)據(jù)圖中子圖結(jié)構(gòu)的選擇性較差時(shí)，索引的優(yōu)勢(shì)并不能完全體現(xiàn)。

GraSS[8]則是把處理的核心放在星型結(jié)構(gòu)上，以?xún)蓚€(gè)星型子圖的公共頂點(diǎn)作為索引項(xiàng)并提取其謂詞結(jié)構(gòu)和與該謂詞相鄰的屬性值作為索引項(xiàng)，并采取了基于hash函數(shù)的模式編碼來(lái)消減RDF屬性值的多樣性以增強(qiáng)圖結(jié)構(gòu)特征的選擇性，通過(guò)在含有星型結(jié)構(gòu)的查詢(xún)圖中搜索符合特征項(xiàng)的邊界頂點(diǎn)來(lái)進(jìn)行子圖匹配，以此來(lái)看，GraSS對(duì)于星查詢(xún)的SPARQL查詢(xún)是十分高效的，但是對(duì)于鏈查詢(xún)以及環(huán)查詢(xún)則沒(méi)有好的應(yīng)對(duì)方法。RSM[5]采用了圖形切分的方式處理復(fù)雜查詢(xún)圖，但是其采用的NP-hard切分模型為了節(jié)省時(shí)間會(huì)把第一個(gè)滿(mǎn)足條件的切分方式作為最優(yōu)方式而沒(méi)有相關(guān)的最優(yōu)驗(yàn)證，因此在圖結(jié)構(gòu)十分復(fù)雜的情況下，計(jì)算得出的切分方式會(huì)在一定程度上偏離最優(yōu)解;并且RSM的連接計(jì)劃采用了基于元組模式的成本模型，是在處理查詢(xún)圖的同時(shí)進(jìn)行連接，因此會(huì)產(chǎn)生少量中間連接結(jié)果冗余的情況。R3F[7]通過(guò)提取RDF圖中的傳入謂詞路徑結(jié)構(gòu)來(lái)建立謂詞路徑索引，其目的是在數(shù)據(jù)圖中尋找與查詢(xún)圖謂詞路徑相同的子圖結(jié)構(gòu)并將其作為查詢(xún)結(jié)果輸出;但是僅僅依靠傳入謂詞路徑無(wú)法遍歷到數(shù)據(jù)圖中所有的RDF頂點(diǎn)，因?yàn)橛邢驁D的邊具有指向性，會(huì)存在入度或出度為0的頂點(diǎn)（圖1（b）中的RDF頂點(diǎn)”John Davis”），這類(lèi)頂點(diǎn)無(wú)法被遍歷，因此導(dǎo)致了查詢(xún)過(guò)程中產(chǎn)生遺漏現(xiàn)象。

基于上述研究現(xiàn)狀的優(yōu)缺點(diǎn)分析，提出了基于ILP建模與RDF頂點(diǎn)選擇性的RDF圖切分規(guī)則（RTPS），將復(fù)雜RDF查詢(xún)圖結(jié)構(gòu)分解為多個(gè)結(jié)構(gòu)簡(jiǎn)單的查詢(xún)子圖，以解決因RDF圖結(jié)構(gòu)復(fù)雜導(dǎo)致查詢(xún)圖的頂點(diǎn)選擇性變?nèi)醵诓樵?xún)中產(chǎn)生大量中間結(jié)果冗余的問(wèn)題。為了體現(xiàn)圖切分規(guī)則的優(yōu)勢(shì)，本文不考慮RDF頂點(diǎn)與謂詞的標(biāo)簽值帶來(lái)的影響（以通配符代替）。在圖結(jié)構(gòu)切分之前，首先建立了RAPP索引以確定查詢(xún)頂點(diǎn)的搜索空間，關(guān)于RDF圖、SPARQL元組模式的定義與索引結(jié)構(gòu)的建立將在第2章詳細(xì)闡述。

5 結(jié)語(yǔ)

為了提高基于復(fù)雜查詢(xún)圖結(jié)構(gòu)的SPARQL查詢(xún)處理效率，本文提出了基于RDF圖切分與頂點(diǎn)選擇性的子圖匹配方法——RTPS，并設(shè)計(jì)了相鄰謂詞路徑索引（RAPP）對(duì)數(shù)據(jù)進(jìn)行預(yù)處理以加快RDF頂點(diǎn)的過(guò)濾，最后根據(jù)頂點(diǎn)選擇性與相鄰頂點(diǎn)結(jié)構(gòu)進(jìn)行了子圖搜索與連接。本文為整體處理過(guò)程提供了相關(guān)的問(wèn)題建模計(jì)算與詳細(xì)實(shí)例。在實(shí)驗(yàn)評(píng)估部分，采用了控制變量法，在真實(shí)世界數(shù)據(jù)集YAGO2、虛擬合成數(shù)據(jù)集LUBM和SNIB上與主流查詢(xún)方法RDF-3X、R3F、GraSS及最新子圖匹配方法RSM進(jìn)行的實(shí)驗(yàn)驗(yàn)證了RTPS的普適性與高效性。綜合實(shí)驗(yàn)結(jié)果表明，在進(jìn)行基于復(fù)雜查詢(xún)圖結(jié)構(gòu)的SPARQL查詢(xún)時(shí)，RTPS的查詢(xún)響應(yīng)時(shí)間較短，具有更高的查詢(xún)效率。在未來(lái)的工作中，將對(duì)RTPS的可擴(kuò)展性進(jìn)行充分研究，使其與Hadoop、Spark等分布式框架相結(jié)合，將RTPS應(yīng)用在RDF動(dòng)態(tài)流數(shù)據(jù)平臺(tái)上。

參考文獻(xiàn)：

[1] 黃映輝，李冠宇.語(yǔ)義物聯(lián)網(wǎng)：物聯(lián)網(wǎng)內(nèi)在矛盾之對(duì)策[J]. 計(jì)算機(jī)應(yīng)用研究，2010，27（11）：4087-4090. （HUANG Y H， LI G Y. Semantic Web of things： strategy for Internet of things intrinsic contradiction [J]. Application Research of Computers， 2010， 27（11）： 4087-4090.）

[2] GROBE M. RDF， Jena， SparQL and the ‘Semantic Web[C]// SIGUCCS 09Proceedings of the 37th Annual ACM SIGUCCS Fall Conference on User Services. New York： ACM， 2009： 131-138.

[3] LIU C， WANG H， YU Y， et al. Towards efficient SPARQL query processing on RDF data [J]. Tsinghua Science and Technology， 2010， 15（6）： 613-622.

[4] VILLAZON-TERRAZAS B， GARCIA-SANTA N， REN Y， et al. Knowledge graph foundations [M]// Exploiting Linked Data and Knowledge Graphs in Large Organisations. Cham： Springer， 2017： 17-55.

[5] 關(guān)皓元， 朱斌， 李冠宇， 等. 基于RDF圖結(jié)構(gòu)切分的高效子圖匹配方法[J].計(jì)算機(jī)應(yīng)用，2018，38（7）：1898-1904，1909. （GUAN H Y， ZHU B， LI GUAN Y， et al. Eifficient subgraph matching method based on structure segmentation of RDF graph） [J]. Journal of Computer Applications， 2018， 38（7）： 1898-1904， 1909.）

[6] NEUMANN T， WEIKUM G. RDF-3X： a RISC-style engine for RDF [J]. Proceedings of the VLDB Endowment， 2008， 1（1）： 647-659.

[7] KIM K， MOON B， KIM H-J. R3F： RDF triple filtering method for efficient SPARQL query processing [J]. World Wide Web — Internet & Web Information Systems， 2015， 18（2）： 317-357.

[8] LYU X， WANG X， LI Y-F， et al. GraSS： an efficient method for RDF subgraph matching [C]// WISE 2015Proceedings of the 16th International Conference on Web Information Systems Engineering， Part I， LNCS 9418. Berlin： Springer， 2015： 108-122.

[9] BUNKE H. Graph matching： theoretical foundations， algorithms， and applications [C]// Proceedings of the 2000 Vision Interface. Montreal： [s.n.]， 2000： 82-88.

http：//citeseerx.ist.psu.edu/viewdoc/download;jsessionid=9256E5E770F37544CDEE0501AD87D2DA？doi=10.1.1.492.1637&rep=rep1&type=pdf

[10] CONTE D， FOGGIA P， SANSONE C， et al. Thirty years of graph matching in pattern recognition[J]. International Journal of Pattern Recognition and Artificial Intelligence， 2008， 18（3）： 265-298.

[11] KALAYCI E G， KALAYCI T E， BIRANT D. An ant colony optimisation approach for optimising SPARQL queries by reordering triple patterns [J]. Information Systems， 2015， 50：51-68.

[12] HE H， WANG H， YANG J， et al. BLINKS：ranked keyword searches on graphs [C]// SIGMOD 07 Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2007： 305-316.

[13] BROEKSTRA J， KAMPMAN A， van HARMELEN F. Sesame： a generic architecture for storing and querying RDF and RDF schema[C]// ISWC 2002Proceedings of the 2002 First International Semantic Web Conference， LNCS 2342. Berlin： Springer， 2002： 54-68.

[14] UDREA O， PUGLIESE A， SUBRAHMANIAN V S. GRIN： a graph based RDF index [C]// AAAI07Proceedings of the 2007 National Conference on Artificial Intelligence. Menlo Park， CA： AAAI Press， 2007： 1465-1470.

[15] YAN X， YU P S， HAN J. Graph indexing：a frequent structure-based approach [C]// SIGMOD 04Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2004： 335-346.

[16] ZOU L， ZSU M T， CHEN L， et al. gStore： a graph-based SPARQL query engine[J]. The VLDB Journal， 2014， 23（4）： 565-590.

[17] RIVERO C R， JAMIL H M. Efficient and scalable labeled subgraph matching using SGMatch [J]. Knowledge and Information Systems， 2017， 51（1）： 61-87.

[18] HE H， SINGH A K. Graphs-at-a-time：query language and access methods for graph databases [C]// SIGMOD 2008Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2008： 405-417.

[19] HOFFART J， SUCHANEK F M， BERBERICH K， et al. YAGO2： a spatially and temporally enhanced knowledge base from Wikipedia [J]. Artificial Intelligence， 2013， 194： 28-61.

[20] GUO Y， PAN Z， HEFLIN J. LUBM： A benchmark for OWL knowledge base systems [J]. Journal of Web Semantics： Science， Services and Agents on the World Wide Web， 2005，3（2/3）：158-182.