基于圖的RDF數(shù)據(jù)劃分方法的研究與實現(xiàn)

史騰飛 楊夢倫

摘 要：RDF作為支持數(shù)據(jù)語義描述的統(tǒng)一標(biāo)準的數(shù)據(jù)模型，在數(shù)據(jù)表示、數(shù)據(jù)交換及系統(tǒng)框架支撐方面提供了很好的技術(shù)支撐。為了滿足異構(gòu)數(shù)據(jù)的存儲和處理需求，本文針對RDF數(shù)據(jù)管理及處理進行了研究，提出了基于圖拆分的RDF數(shù)據(jù)存儲及優(yōu)化查詢方法，改善RDF數(shù)據(jù)存儲及查詢效率。首先把原始RDF文本數(shù)據(jù)轉(zhuǎn)換成RDF數(shù)據(jù)圖，然后運用新的算法將數(shù)據(jù)圖進行語義拆分，使RDF數(shù)據(jù)劃分為耦合度較低的若干部分。通過對邊割比率進行實驗，將基于點權(quán)重的劃分算法與METIS算法和哈希算法進行對比，分析三種方法的優(yōu)缺點。

關(guān)鍵詞：計算機應(yīng)用；算法分析；METIS算法；圖

隨著計算機和網(wǎng)絡(luò)技術(shù)的快速發(fā)展，信息系統(tǒng)的數(shù)量和規(guī)模越來越大，目前web數(shù)據(jù)的管理和處理面臨著半結(jié)構(gòu)化數(shù)據(jù)、數(shù)據(jù)量大、查詢速度緩慢、檢索效率低下、可擴展性、普適性等6大主要問題。這些數(shù)據(jù)的特點使異構(gòu)數(shù)據(jù)整合成為一個挑戰(zhàn)性的問題。RDF作為支持數(shù)據(jù)語義描述的一種統(tǒng)一標(biāo)準的數(shù)據(jù)模型，在數(shù)據(jù)表示、數(shù)據(jù)交換及系統(tǒng)框架支撐方面提供了很好的技術(shù)支撐。如何對分布式存儲的數(shù)據(jù)進行較好地劃分是目前需要解決的重要問題。

因此，本文主要以提高使用SPARQL查詢語句在RDF大數(shù)據(jù)中檢索效率為主要目標(biāo)，依據(jù)METIS算法核心思想，提出了一種新的圖劃分算法方案——基于圖的RDF數(shù)據(jù)存儲及查詢方法，該方法能改善RDF數(shù)據(jù)存儲及查詢效率，為數(shù)據(jù)的處理提供更好的系統(tǒng)和方法上的支撐。

相關(guān)技術(shù)

數(shù)據(jù)形式——RDF

資源描述框架（RDF）作為支持數(shù)據(jù)語義描述的一種統(tǒng)一標(biāo)準的數(shù)據(jù)模型，在數(shù)據(jù)表示、數(shù)據(jù)交換及系統(tǒng)框架支撐方面提供了很好的技術(shù)支撐。RDF使用一個圖數(shù)據(jù)模型，其中不同實體是圖中的頂點，它們之間的關(guān)系用邊來表示。關(guān)于每個實體的信息用從頂點到該實體發(fā)出的有向邊表示，其中邊是連接頂點到其他實體的，或者到特殊的“文字的”頂點，該頂點包括對于該實體的一個特殊的屬性值。

圖1顯示一個RDF示例圖。例如，圖中的邊表示實體“教師0”是“教授類型”類型的，屬于“院系0”，教了“課程1”。在這個圖中，每一個和“教師0”相連的實體能有它們自己的連接集；例如，通過“類型”關(guān)系，“教師0”被顯示和“教授”實體相連。大部分RDF存儲是將RDF圖表示為一個三元組表，表中有一個針對RDF圖的邊的三元組。三元組使用<主語，謂語，賓語>的形式，其中主語是從邊發(fā)出的實體，謂詞是邊的標(biāo)簽，賓語是邊的另一端上的實體或文字的名稱。

0.1圖的數(shù)據(jù)結(jié)構(gòu)圖是一種復(fù)雜的非線性結(jié)構(gòu)。

0.2在處理RDF三元組數(shù)據(jù)時，論文采用的方法是將RDF三元組數(shù)據(jù)按照圖的形式進行劃分，在數(shù)據(jù)結(jié)構(gòu)中，常用的方法是鄰接矩陣、鄰接表和十字鏈表三種存儲形式。本文采用的是鄰接表的形式。偽代碼如下表1。

偽代碼中將主語和賓語用節(jié)點表示，謂語用邊表示。針對每個點，根據(jù)點的ID區(qū)分，ID采用整數(shù)表示，在圖劃分程序中并不存儲每個點的語義。由于采用的是超圖的思想，即每一節(jié)點都是由若干點組成，所以在節(jié)點中記錄了當(dāng)前節(jié)點所包含點的個數(shù)，這主要是為計算權(quán)重所服務(wù)的。節(jié)點的最后一個信息是當(dāng)前的節(jié)點被哪個節(jié)點所包含，在初始化的時候這個值是當(dāng)前節(jié)點的ID，即說明當(dāng)前節(jié)點是被自己所包含，如果這個值在計算最后仍然是自己的ID，說明這個節(jié)點只包含自己一個點。將謂語抽象成邊，只需要知道哪個節(jié)點和哪個節(jié)點有關(guān)系即可，所以在圖劃分程序中只存儲自己的ID和點之間的關(guān)系，對于邊的語義信息和點的類似。

1.基于超圖模型的RDF數(shù)據(jù)劃分

本篇論文中采用的是METIS算法的思想，該算法是由明尼蘇達大學(xué)計算機科學(xué)與信息技術(shù)工程系開發(fā)并且免費發(fā)布的。METIS的實現(xiàn)算法是基于多級圖形分割范例。它可以迅速產(chǎn)生高質(zhì)量的分割。在多層次模式上，總共有三個階段組成：圖粗糙化，圖分割，圖還原。

1.1 圖粗糙化

METIS算法中的圖粗糙化是最重要的一個步驟，這個步驟是將圖中的節(jié)點根據(jù)一定的算法合并成一個新的節(jié)點，這樣會將圖中總節(jié)點數(shù)降低，最后得到一個比較小的圖形。在粗糙化階段，需要將大圖簡化成較小的圖，在簡化的過程中，首先將懸掛點與之相關(guān)聯(lián)的點進行合并，對于合并后的網(wǎng)圖，根據(jù)每個點的密集程度進行合并，采用合并密集程度最大點的所有關(guān)聯(lián)點。

在一個圖中，度數(shù)為1的頂點稱為懸掛頂點。與它關(guān)聯(lián)的邊稱為懸掛邊。在將懸掛點進行化簡的過程中，已經(jīng)將簡單圖變?yōu)槌瑘D。在這個圖中找到密集度最大的點進行化簡，并迭代化簡。在將圖進行粗糙化的過程中，需要牽扯到計算點的權(quán)重這個問題。這是因為在進行圖的粗糙化的過程中，需要將節(jié)點進行合并，由單個點聚集成超點，這樣才能將超大的圖粗糙化，簡化成比較簡單的圖進行接下來的圖分割步驟。在對點的權(quán)重計算過程中，主要依據(jù)兩個原則：

（1）一個點與其他點連接的越多，說明這些點越緊密，在未來查詢過程中越有可能同時被查詢到，需要將這些點存儲在一個存儲節(jié)點中。所以，對于這種情況，應(yīng)該將這些點進行合并，成為超點。

（2）對于語義相同的點應(yīng)該盡可能的進行合并，成為同一個超點，并且存儲在一個存儲節(jié)點中。這些節(jié)點是同一類型的，在未來的查詢過程中很有可能同時被查詢到。

依據(jù)以上兩點，給出計算點的權(quán)重公式如下：

1.2 圖分割

在圖分割之前，需要確定參數(shù)k（k>=1且為整數(shù)），k表示將大圖化簡為k個部分。用圖粗糙化的方法進行化簡至到超圖中節(jié)點數(shù)等于k或者是到超圖中節(jié)點數(shù)小于k之前的一步。如果可以化簡為k個節(jié)點，那么就把k個節(jié)點劃分為k個部分。若不能正好化簡為k個部分，則在節(jié)點數(shù)小于k之前的一步停止。偽代碼如下表2：

在圖劃分的整體算法中，主要通過while循環(huán)，一步一步將圖粗糙化，通過節(jié)點的合并，最終達到劃分目標(biāo)。在兩個主要步驟中，收縮函數(shù)主要負責(zé)節(jié)點的合并，每次在收縮時，通過循環(huán)遍歷圖中的所有點找到權(quán)重最大的節(jié)點maxVertex，將這個節(jié)點相關(guān)的周圍所有節(jié)點合并產(chǎn)生新的超點，在合并的過程中處理這些點的關(guān)系和這些點間邊的關(guān)系，為接下來圖還原的過程做好準備。在程序中采用的方法是對處理每個與權(quán)重最大的節(jié)點有關(guān)聯(lián)的節(jié)點relateVertex，首先修改關(guān)聯(lián)的節(jié)點的信息，使之成為最大權(quán)重節(jié)點（超點）的成員，然后刪除關(guān)聯(lián)的節(jié)點，最后刪除原始權(quán)重最大的節(jié)點和關(guān)聯(lián)的節(jié)點邊的信息，計算權(quán)重函數(shù)是對上一步中有變動的節(jié)點信息的更新，主要更新新節(jié)點的權(quán)重、包含點數(shù)等信息。對于權(quán)重依據(jù)的就是前一節(jié)所述的方法。以下分別是Contract函數(shù)與CalculateHeavy函數(shù)的偽代碼：

2.實驗及分析

本節(jié)根據(jù)前文提出的圖拆分算法和經(jīng)典的METIS算法以及哈希算法進行對比測試，分析各自算法的優(yōu)缺點。由于METIS提供一組獨立的命令行程序，用于計算分割，而且也提供了應(yīng)用程序編程接口（API），它可以通過C/C+ +或FORTRAN等程序來調(diào)用。為了有較好的比較性，論文中的圖分割算法也是采用C++編寫。下面的METIS算法采用了標(biāo)準單機METIS圖劃分算法。

2.1 實驗數(shù)據(jù)集

測試RDF數(shù)據(jù)的benchmark有很多種，LUBM是其中一種主流的測試樣例集。基準的目的是在一個大的數(shù)據(jù)集中，通過提交到一個單一的現(xiàn)實本體進行查詢來評估系統(tǒng)的性能。它由一個大學(xué)領(lǐng)域本體，可定制和可重復(fù)的合成數(shù)據(jù)，一組測試查詢和幾個性能指標(biāo)組成。通過LUBM提供的數(shù)據(jù)產(chǎn)生器，實驗建立了四組測試數(shù)據(jù)集，下表5顯示了具體數(shù)據(jù)集：

根據(jù)資料，METIS算法比較適合于百萬級別的數(shù)據(jù)量，因此在測試數(shù)據(jù)集的選擇上都在百萬級別，以便可以區(qū)分這三種算法的效果。在之前文章中介紹了METIS算法的輸入是一個鄰接矩陣圖，因此系統(tǒng)的輸入方式都是相同的鄰接矩陣圖格式的原始數(shù)據(jù)。

2.2 實驗結(jié)果與分析

對于4個不同大小的數(shù)據(jù)集，采用三種不同的算法做對比實驗，分別測試了劃分4、8、16等三種不同數(shù)量區(qū)域的實驗。實驗對比的主要影響因素是邊割比率（通信代價）。邊割比率指的是在三元組中，主語和賓語被劃分在兩個不同的節(jié)點個數(shù)與總的三元組個數(shù)的比值，也就是邊割數(shù)/總邊數(shù)。用這個比值來描述通信的代價，這個比值越大，說明系統(tǒng)在查詢時，兩個節(jié)點的通信頻率和概率就越高，反之則說明概率越低。

實驗中除了對比METIS算法和自己提出的算法，還與哈希算法（采用主語ID取模）進行比較。目的是因為哈希算法可以較為平均的將數(shù)據(jù)集進行劃分，可以通過這個算法作為參考。

2.3 實驗結(jié)論

通過上面實驗和分析，可以看到，本文所提出的圖劃分算法與METIS和哈希算法在邊割比率（通信代價）方面有各自的優(yōu)勢與劣勢。雖然METIS算法和本文的算法在主要思想上是類似的，但是由于METIS算法在粗糙化過程中采用的是最大邊覆蓋算法，而本文在粗糙化過程中采用的是超圖的思想，因此在兩個對比方面，本文提出的圖劃分算法都與其他兩種算法有較大的不同。由于哈希算法均勻劃分數(shù)據(jù)，因此使得在邊割比率方面具有較高的數(shù)值，而本文和METIS算法都相對于哈希算法的結(jié)果較好，因此在通信代價方面能得到較好的效果，雖然本文的算法并不是最好的，但和METIS算法相差不大。

3 結(jié)論

本文介紹了基于METIS算法的整體思想，采用超圖的方法，對RDF數(shù)據(jù)圖進行劃分的理論，通過對RDF數(shù)據(jù)圖的粗糙化、基于點的權(quán)重劃分數(shù)據(jù)、還原RDF數(shù)據(jù)圖三個主要步驟的介紹，詳細的說明了如何將大量RDF數(shù)據(jù)一步一步劃分并存儲在集群中，為整個系統(tǒng)提供底層數(shù)據(jù)支持。在本章最后將基于點權(quán)重的劃分算法與METIS算法和哈希算法通過邊割比率方面進行實驗對比，分析了三種方法的優(yōu)缺點。

參考文獻

[1]Kolas D， Emmons I， Dean M， Efficient Linked-List RDF Indexing in Parliament. In the Proceedings of the Scalable Semantic Web （SSWS） Workshop of ISWC， 2009.

[2]Li P， Zeng Y， Kotoulas S， et al. The Quest for Parallel Reasoning on the Semantic Web， Lecture Notes in Computer Science， 2009， 5820：430-441.

[3]Hendler J， Web 3.0： The Dawn of Semantic Search[J]. Computer， 2010，43（1）：77-80.

[4]L Zou， J Mo， L Chen， et al. gStore： answering SPARQL queries via subgraph matching. PVLDB， 2011， 4（8）：482-493.

[5]J Huang， DJ Abadi， K Ren. Scalable SPARQL Querying of Large RDF Graphs.

[6】曹佳碩. 基于RDF的云制造資源數(shù)據(jù)存儲及檢索方法的研究與實現(xiàn)[D]. 北京：北京交通大學(xué)，2012.

[7]楊夢倫. 基于圖的RDF數(shù)據(jù)存儲及查詢方法的研究與實現(xiàn)[D]. 北京：北京交通大學(xué)，2015.

作者簡介

史騰飛（1992-），男，漢族，碩士研究生，研究方向：云計算。