史騰飛 楊夢(mèng)倫

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

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

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

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

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

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

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

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

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

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

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

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

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

1.1 圖粗糙化

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

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

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

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

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

1.2 圖分割

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

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

2.實(shí)驗(yàn)及分析

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

2.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

2.2 實(shí)驗(yàn)結(jié)果與分析

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

實(shí)驗(yàn)中除了對(duì)比METIS算法和自己提出的算法，還與哈希算法（采用主語(yǔ)ID取模）進(jìn)行比較。目的是因?yàn)楣Ｋ惴梢暂^為平均的將數(shù)據(jù)集進(jìn)行劃分，可以通過這個(gè)算法作為參考。

2.3 實(shí)驗(yàn)結(jié)論

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

3 結(jié)論

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

參考文獻(xiàn)

[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ù)存儲(chǔ)及檢索方法的研究與實(shí)現(xiàn)[D]. 北京：北京交通大學(xué)，2012.

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

作者簡(jiǎn)介

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