[發明專利]一種基于多層劃分框架的RDF分布式存儲方法

有效

• 申請號: 201810803364.1
• 申請日: 2018-07-20
• 公開（公告）號: CN109344259B
• 公開（公告）日: 2022-02-22
• 發明（設計）人: 劉均;王瑞杰;晉毓澤;張鐸;魏筆凡;王萌;姚思雨;曾宏偉
• 申請（專利權）人: 西安交通大學
• 主分類號: G06F16/36
• 分類號: G06F16/36;G06F16/35
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 徐文權

本發明公開了一種基于多層劃分框架的RDF分布式存儲方法，主要步驟包括：(1)通過MMA算法優化RDF圖中的頂點移動，保護了RDF圖中小社團；(2)通過MSLM算法對RDF圖進行粗糙化，發現了RDF圖中的社團結構，并且在此基礎了縮小了RDF數據的規模；(3)通過B_AP算法實現了對RDF圖的k?way分割，使得各個物理存儲節點之間的數據量相對平衡并且降低了節點之間的通信代價。本發明提出了完整的RDF分布式存儲方法，為提升RDF的查詢效率奠定了基礎。

技術領域

本發明屬于分布式存儲領域，具體涉及一種基于多層劃分框架的RDF分布式存儲方法。

背景技術

隨著語義網的高速發展，RDF(Resource Description Framework)作為語義網的核心標準也呈現爆炸式的增長，對大規模RDF數據的存儲和查詢管理成為了當前研究的熱點。傳統基于單機的RDF存儲和查詢由于數據擴展性差等問題在面對超大規模的RDF數據時難以管理，所以基于分布式的RDF存儲和查詢成為了研究趨勢，而如何更好地將RDF分割且進行分布式查詢成為了在分布式系統上對RDF研究的重點。

分布式系統和云計算平臺因為存儲空間大，可擴展性強等優勢而在各個領域取得長足發展。而RDF數據集的日漸增長也使得對RDF的存儲和查詢的研究在近些年來越來越多地向基于分布式系統或者云計算平臺發展。分布式系統存儲RDF圖數據主要涉及到在分布式環境下的布局形式，分割算法，冗余算法等諸多問題。現有的RDF分布式存儲技術主要包括基于哈希的RDF分割方法，基于鍵值對的RDF分割方法，基于圖模型的RDF分割方法和基于多層劃分框架的RDF分割方法，其中當前最為流行的就是基于多層劃分框架思想的RDF分割方法。

針對RDF分布式存儲方法，申請人通過查詢，檢索到2篇與本發明相關的發明專利：

(1)一種分布式層次化的RDF數據的存儲方法，申請號：201310658588.5；該專利公開了一種分布式層次化的RDF數據的存儲方法，包括：對所有RDF數據進行索引；采用兩個存儲層以存儲索引后的RDF數據，從底層到上層依次為：持久化存儲層和分布式內存存儲層；所有RDF數據首先存儲到持久化存儲層，然后，將常用的RDF數據存儲到分布式內存存儲層；將所有存儲在持久化存儲層的RDF數據自動保持多個備份；當檢測到分布式內存存儲層的節點發生數據失效時，在下次查詢到該節點中的RDF數據時，從持久化存儲層去獲取相應的數據。

(2)一種高效的分布式的RDF數據存儲方法，申請號：201610064516.1；該專利公開了一種高效的分布式的RDF數據存儲方法。包括：1)用戶為待上傳的每一三元組選取一命名圖或設定一新的命名圖；并根據業務需求為該三元組設定一有效謂詞及其三元組；2)數據控制系統對用戶上傳的RDF數據中的每條三元組進行解析，提取該三元組的謂詞及該三元組的命名圖的有效謂詞；然后根據該有效謂詞，將該三元組拆分成具有相同唯一標識的兩個三元組：同一主語的完整謂詞的三元組和同一主語的有效謂詞的三元組；有效謂詞為完整謂詞中一部分謂詞；3)數據控制系統將得到的同一主語的完整謂詞的三元組數據和同一主語的有效謂詞的三元組數據分別存儲到不同的數據庫集群。

上述的兩個專利方案中均沒有從宏觀上考慮RDF的社團特性與分布式系統的通信代價問題，從而可能導致各個物理節點之間交叉邊數目過多而使得查詢效率下降，無法達到高效存儲的目的。

發明內容

本發明的目的在于提供一種基于多層劃分框架的RDF分布式存儲方法，以克服現有技術存在的物理節點之間低平衡性與高通信代價的缺陷。

本發明采用如下技術方案來實現的：

一種基于多層劃分框架的RDF分布式存儲方法，該方法通過MMA算法和MSLM算法實現對RDF圖的粗糙化，通過B_AP算法實現對RDF圖的k-way分割，具體步驟如下：

Step1執行以下初始化操作：