[發明專利]基于語義的資源描述框架RDF圖劃分方法

有效

• 申請號: 201611169530.4
• 申請日: 2016-12-16
• 公開（公告）號: CN106844445B
• 公開（公告）日: 2020-08-14
• 發明（設計）人: 王鑫;徐強
• 申請（專利權）人: 天津大學
• 主分類號: G06F16/56
• 分類號: G06F16/56;G06F16/532;G06F16/51
• 代理公司: 天津市北洋有限責任專利代理事務所 12201
• 代理人: 劉國威

本發明涉及資源描述框架圖數據劃分領域，為能夠基于語義對大規模的RDF圖進行劃分，實現分布式存儲RDF圖數據，提高數據查詢處理的性能，為此，本發明，基于語義的資源描述框架RDF圖劃分方法，步驟如下：1)得到主語s所屬的類C；2)生成s的直接類；3)生成與RDF圖G對應的RDF模式圖G_S；4)計算比率；5)計算基數因子；6)賦初始rank值；7)設置迭代次數；8)按照rank值的大小選取前k個直接類；9)依次搜索鄰居直接類C'；10)重復步驟8)和步驟9)直到top?k中的直接類被劃分完為止；11)進行后處理。本發明主要應用于數據劃分場合。

技術領域

本發明涉及RDF(資源描述框架)圖數據劃分領域，具體來說，涉及面向大規模RDF三元組數據的語義劃分領域。

背景技術

作為下一代的Web技術，語義Web要在現有Web的基礎上實現機器可讀懂數據，并為人類提供自動服務。由Tim Berners-Lee發起的關聯數據(Linked Data)運動的持續推進，使目前RDF三元組數據已超過520億并且仍在不斷增長。由于資源描述框架(ResourceDescription Framework，簡稱RDF)的數據模型在各領域的可控制性、高度靈活性和擴展性，使得它在處理大規模數據領域方面尤其重要，如在Web語義、政府機構、生物信息及社交網絡方面等。RDF是用于描述網絡資源的W3C(萬維網聯盟)標準，其格式為(主語,謂語,賓語)，即(s,o,p)，其中s表示主語，p表示謂語，o表示賓語。一個三元組中的賓語可作為另一個三元組中的主語，于是RDF語義數據形成了一種有向圖結構。

全球范圍的RDF圖數據庫正在形成，但規模龐大加之發布的數據分散度高，使得單個計算節點已無法容納海量RDF圖數據。面對海量RDF圖數據分布式存儲已勢在必行，其核心技術圖劃分方法對研究RDF圖算法意義重大。大規模RDF圖上的數據查詢代價往往很昂貴，分布式集群中劃分數據不合理，跨站點的邊數目較大，會導致數據查詢(如，連接操作)的通信量激增，降低數據查詢處理性能。目前大量的研究工作關注一般無向圖或有向圖的劃分，針對RDF圖的劃分可以分為兩類，一是簡單的哈希劃分，目前大量RDF引擎，如4store，YARS2都采用哈希算法進行圖劃分，在主語或賓語上建立key(鍵)，通過對key取哈希值隨機地劃分三元組，沒有進一步的處理。二是以傳統的圖劃分為基礎，增加部分優化，其關注點都在圖的結構。部分研究通過經典的圖劃分方法METIS對RDF圖進行劃分，并在此基礎上進行n-跳延伸，對于每個計算節點的邊界頂點，通過復制它的n跳距離內的點到該節點，以減少跨越站點的邊數目，優化數據查詢。此外，也有研究以路徑為劃分單元將RDF圖劃分到不同的計算節點，優化RDF圖上的SPARQL(Simple Protocol and RDF Query Language，是為RDF開發的一種查詢語言和數據獲取協議)查詢。

以上技術僅利用傳統的圖劃分方法對RDF圖進行劃分并做出部分優化，但均未考慮RDF圖內含的豐富語義，它們主要存在如下問題：

1)僅考慮一般圖自身的結構，包括以點、邊、或者路徑為基本單元進行圖劃分，而沒有考慮RDF圖中的RDF模式(RDF schema)信息；

2)以一般圖劃分方法為基礎進行優化，仍具有傳統圖劃分方法的特性，如通過METIS劃分進行n-跳延伸會導致RDF數據劃分不均勻，成為并行計算的瓶頸；

3)哈希圖劃分方法沒有考慮RDF圖的任何結構及語義，劃分結果中跨越節點的邊的數目較多，數據查詢性能較差，對分布式的RDF圖進行處理時性能較低；

4)RDF圖描述真實世界中Web上的資源信息，具有豐富語義，不僅僅是單獨的點、邊、或路徑，傳統圖劃分方法忽略了這些語義，使得劃分結果沒有實際意義。