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

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

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

中圖分類號： TP181; TP311

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

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

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

本文的主要工作如下：

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

5 結(jié)語

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

參考文獻：

[1] 黃映輝，李冠宇.語義物聯(lián)網(wǎng)：物聯(lián)網(wǎng)內(nèi)在矛盾之對策[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].計算機應(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.