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

關皓元 朱斌 李冠宇 蔡永嘉

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

關鍵詞：SPARQL查詢處理;資源描述框架;子圖匹配;圖結構切分;頂點選擇性

中圖分類號： TP181; TP311

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

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

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

本文的主要工作如下：

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

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

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

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

1 相關工作

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

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

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

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

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

基于上述研究現狀的優缺點分析，提出了基于ILP建模與RDF頂點選擇性的RDF圖切分規則（RTPS），將復雜RDF查詢圖結構分解為多個結構簡單的查詢子圖，以解決因RDF圖結構復雜導致查詢圖的頂點選擇性變弱而在查詢中產生大量中間結果冗余的問題。為了體現圖切分規則的優勢，本文不考慮RDF頂點與謂詞的標簽值帶來的影響（以通配符代替）。在圖結構切分之前，首先建立了RAPP索引以確定查詢頂點的搜索空間，關于RDF圖、SPARQL元組模式的定義與索引結構的建立將在第2章詳細闡述。

5 結語

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

參考文獻：

[1] 黃映輝，李冠宇.語義物聯網：物聯網內在矛盾之對策[J]. 計算機應用研究，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] 關皓元， 朱斌， 李冠宇， 等. 基于RDF圖結構切分的高效子圖匹配方法[J].計算機應用，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.