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

有效

• 申請(qǐng)?zhí)枺?/td>: 201810803364.1
• 申請(qǐng)日: 2018-07-20
• 公開（公告）號(hào): CN109344259B
• 公開（公告）日: 2022-02-22
• 發(fā)明（設(shè)計(jì)）人: 劉均;王瑞杰;晉毓?jié)?/a>;張鐸;魏筆凡;王萌;姚思雨;曾宏偉
• 申請(qǐng)（專利權(quán)）人: 西安交通大學(xué)
• 主分類號(hào): G06F16/36
• 分類號(hào): G06F16/36;G06F16/35
• 代理公司: 西安通大專利代理有限責(zé)任公司 61200
• 代理人: 徐文權(quán)

本發(fā)明公開了一種基于多層劃分框架的RDF分布式存儲(chǔ)方法，主要步驟包括：(1)通過MMA算法優(yōu)化RDF圖中的頂點(diǎn)移動(dòng)，保護(hù)了RDF圖中小社團(tuán)；(2)通過MSLM算法對(duì)RDF圖進(jìn)行粗糙化，發(fā)現(xiàn)了RDF圖中的社團(tuán)結(jié)構(gòu)，并且在此基礎(chǔ)了縮小了RDF數(shù)據(jù)的規(guī)模；(3)通過B_AP算法實(shí)現(xiàn)了對(duì)RDF圖的k?way分割，使得各個(gè)物理存儲(chǔ)節(jié)點(diǎn)之間的數(shù)據(jù)量相對(duì)平衡并且降低了節(jié)點(diǎn)之間的通信代價(jià)。本發(fā)明提出了完整的RDF分布式存儲(chǔ)方法，為提升RDF的查詢效率奠定了基礎(chǔ)。

技術(shù)領(lǐng)域

本發(fā)明屬于分布式存儲(chǔ)領(lǐng)域，具體涉及一種基于多層劃分框架的RDF分布式存儲(chǔ)方法。

背景技術(shù)

隨著語義網(wǎng)的高速發(fā)展，RDF(Resource Description Framework)作為語義網(wǎng)的核心標(biāo)準(zhǔn)也呈現(xiàn)爆炸式的增長，對(duì)大規(guī)模RDF數(shù)據(jù)的存儲(chǔ)和查詢管理成為了當(dāng)前研究的熱點(diǎn)。傳統(tǒng)基于單機(jī)的RDF存儲(chǔ)和查詢由于數(shù)據(jù)擴(kuò)展性差等問題在面對(duì)超大規(guī)模的RDF數(shù)據(jù)時(shí)難以管理，所以基于分布式的RDF存儲(chǔ)和查詢成為了研究趨勢，而如何更好地將RDF分割且進(jìn)行分布式查詢成為了在分布式系統(tǒng)上對(duì)RDF研究的重點(diǎn)。

分布式系統(tǒng)和云計(jì)算平臺(tái)因?yàn)榇鎯?chǔ)空間大，可擴(kuò)展性強(qiáng)等優(yōu)勢而在各個(gè)領(lǐng)域取得長足發(fā)展。而RDF數(shù)據(jù)集的日漸增長也使得對(duì)RDF的存儲(chǔ)和查詢的研究在近些年來越來越多地向基于分布式系統(tǒng)或者云計(jì)算平臺(tái)發(fā)展。分布式系統(tǒng)存儲(chǔ)RDF圖數(shù)據(jù)主要涉及到在分布式環(huán)境下的布局形式，分割算法，冗余算法等諸多問題。現(xiàn)有的RDF分布式存儲(chǔ)技術(shù)主要包括基于哈希的RDF分割方法，基于鍵值對(duì)的RDF分割方法，基于圖模型的RDF分割方法和基于多層劃分框架的RDF分割方法，其中當(dāng)前最為流行的就是基于多層劃分框架思想的RDF分割方法。

針對(duì)RDF分布式存儲(chǔ)方法，申請(qǐng)人通過查詢，檢索到2篇與本發(fā)明相關(guān)的發(fā)明專利：

(1)一種分布式層次化的RDF數(shù)據(jù)的存儲(chǔ)方法，申請(qǐng)?zhí)枺?01310658588.5；該專利公開了一種分布式層次化的RDF數(shù)據(jù)的存儲(chǔ)方法，包括：對(duì)所有RDF數(shù)據(jù)進(jìn)行索引；采用兩個(gè)存儲(chǔ)層以存儲(chǔ)索引后的RDF數(shù)據(jù)，從底層到上層依次為：持久化存儲(chǔ)層和分布式內(nèi)存存儲(chǔ)層；所有RDF數(shù)據(jù)首先存儲(chǔ)到持久化存儲(chǔ)層，然后，將常用的RDF數(shù)據(jù)存儲(chǔ)到分布式內(nèi)存存儲(chǔ)層；將所有存儲(chǔ)在持久化存儲(chǔ)層的RDF數(shù)據(jù)自動(dòng)保持多個(gè)備份；當(dāng)檢測到分布式內(nèi)存存儲(chǔ)層的節(jié)點(diǎn)發(fā)生數(shù)據(jù)失效時(shí)，在下次查詢到該節(jié)點(diǎn)中的RDF數(shù)據(jù)時(shí)，從持久化存儲(chǔ)層去獲取相應(yīng)的數(shù)據(jù)。

(2)一種高效的分布式的RDF數(shù)據(jù)存儲(chǔ)方法，申請(qǐng)?zhí)枺?01610064516.1；該專利公開了一種高效的分布式的RDF數(shù)據(jù)存儲(chǔ)方法。包括：1)用戶為待上傳的每一三元組選取一命名圖或設(shè)定一新的命名圖；并根據(jù)業(yè)務(wù)需求為該三元組設(shè)定一有效謂詞及其三元組；2)數(shù)據(jù)控制系統(tǒng)對(duì)用戶上傳的RDF數(shù)據(jù)中的每條三元組進(jìn)行解析，提取該三元組的謂詞及該三元組的命名圖的有效謂詞；然后根據(jù)該有效謂詞，將該三元組拆分成具有相同唯一標(biāo)識(shí)的兩個(gè)三元組：同一主語的完整謂詞的三元組和同一主語的有效謂詞的三元組；有效謂詞為完整謂詞中一部分謂詞；3)數(shù)據(jù)控制系統(tǒng)將得到的同一主語的完整謂詞的三元組數(shù)據(jù)和同一主語的有效謂詞的三元組數(shù)據(jù)分別存儲(chǔ)到不同的數(shù)據(jù)庫集群。

上述的兩個(gè)專利方案中均沒有從宏觀上考慮RDF的社團(tuán)特性與分布式系統(tǒng)的通信代價(jià)問題，從而可能導(dǎo)致各個(gè)物理節(jié)點(diǎn)之間交叉邊數(shù)目過多而使得查詢效率下降，無法達(dá)到高效存儲(chǔ)的目的。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供一種基于多層劃分框架的RDF分布式存儲(chǔ)方法，以克服現(xiàn)有技術(shù)存在的物理節(jié)點(diǎn)之間低平衡性與高通信代價(jià)的缺陷。

本發(fā)明采用如下技術(shù)方案來實(shí)現(xiàn)的：

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

Step1執(zhí)行以下初始化操作：