[發(fā)明專(zhuān)利]基于Pregel的分布式起源保障正則路徑查詢算法

在審

• 申請(qǐng)?zhí)枺?/td>: 201810177109.0
• 申請(qǐng)日: 2018-03-04
• 公開(kāi)（公告）號(hào): CN108519994A
• 公開(kāi)（公告）日: 2018-09-11
• 發(fā)明（設(shè)計(jì)）人: 王鑫;辛月祺
• 申請(qǐng)（專(zhuān)利權(quán)）人: 天津大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 天津市北洋有限責(zé)任專(zhuān)利代理事務(wù)所 12201
• 代理人: 劉玥

本發(fā)明公開(kāi)了一種基于Pregel的分布式起源保障正則路徑查詢算法：1)對(duì)于給定的正則路徑查詢Q＝(x,r,y)，根據(jù)正則表達(dá)式r計(jì)算first，last，follow集；2)進(jìn)一步構(gòu)建正則表達(dá)式r所等價(jià)的Glushkov自動(dòng)機(jī)A＝(St,Σ,δ,q0,F)；3)使用Pregel消息傳遞模型在RDF圖數(shù)據(jù)中匹配正則路徑查詢，通過(guò)消息傳遞的方式、以頂點(diǎn)為中心的計(jì)算之后得到結(jié)果路徑；4)統(tǒng)計(jì)所有滿足正則表達(dá)式r的結(jié)果路徑即為查詢結(jié)果。本發(fā)明能夠利用Glushkov自動(dòng)機(jī)，對(duì)于大規(guī)模RDF圖數(shù)據(jù)進(jìn)行起源保障正則路徑查詢，并且通過(guò)引入的優(yōu)化策略，以達(dá)到減少查詢時(shí)間，減少中間結(jié)果以及提高算法擴(kuò)展性的目的。

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

本發(fā)明涉及分布式圖查詢領(lǐng)域，具體來(lái)說(shuō)，涉及面向大規(guī)模RDF圖數(shù)據(jù)的正則路徑查詢領(lǐng)域。

背景技術(shù)

隨著知識(shí)圖譜的日益普及，越來(lái)越多的領(lǐng)域采用資源描述框架(ResourceDescription Framework，RDF)作為數(shù)據(jù)表示和存儲(chǔ)的標(biāo)準(zhǔn)格式。與傳統(tǒng)關(guān)系模型相比，RDF更自然地刻畫(huà)和反應(yīng)現(xiàn)實(shí)世界中的事物及其聯(lián)系。隨著圖數(shù)據(jù)的大規(guī)模涌現(xiàn)，基于多機(jī)集群系統(tǒng)的高效率分布式圖查詢已成為必然選擇。正則路徑查詢(Regular Path Queries，RPQs)是一種不可或缺的基本圖查詢操作，旨在以導(dǎo)航的方式找到所有滿足正則表達(dá)式的路徑，一般情況下返回匹配的一系列數(shù)據(jù)節(jié)點(diǎn)對(duì)。W3C推薦的RDF圖數(shù)據(jù)標(biāo)準(zhǔn)查詢語(yǔ)言SPARQL也在最新版1.1中引入了屬性路徑(property path)特性來(lái)支持RDF圖上的RPQs。

傳統(tǒng)的正則路徑表達(dá)式被定義為Q＝(x,r,y)，在RDF圖T上找到一組資源對(duì) (v₀,v_n)，使得在圖T中從v₀到v_n存在路徑ρ，其中ρ的標(biāo)簽表示為λ(ρ)且λ(ρ)滿足Q 中正則表達(dá)式r。但是，從以上RPQ的傳統(tǒng)語(yǔ)義來(lái)看，我們不能得到從v₀到v_n的路徑的中間信息。為了提供路徑ρ的起源信息，辨析從v₀到v_n的路徑ρ是如何滿足Q的，即研究起源保障的正則路徑查詢(provenance-aware regular path queries)，其結(jié)果返回的是滿足Q的路徑ρ中的所有點(diǎn)和邊，即RDF圖的一個(gè)子圖，能夠更好地反應(yīng)查詢結(jié)果全貌，方便用戶理解。

根據(jù)我們的調(diào)查，目前尚缺少相關(guān)研究工作對(duì)現(xiàn)有的分布式正則路徑查詢算法加以改進(jìn)調(diào)整，適配到Pregel模型下進(jìn)行算法研究與實(shí)驗(yàn)比較。Pregel模型具有“以頂點(diǎn)為中心”計(jì)算的特點(diǎn)，因此更適合并行圖計(jì)算，使用Pregel消息傳遞模型來(lái)進(jìn)行并行圖計(jì)算可以進(jìn)一步提高圖計(jì)算效率。

目前已有的標(biāo)準(zhǔn)語(yǔ)義下的正則路徑查詢算法包括如下：

Calvanese等人在不同的假設(shè)下解決正則路徑查詢問(wèn)題，基于視圖和索引來(lái)檢測(cè)一對(duì)資源對(duì)是否滿足正則表達(dá)式，這種方法的弊端是對(duì)于查詢的種類(lèi)有所限制。Koschmieder等人提出使用“罕見(jiàn)標(biāo)簽”(rare-label)方法對(duì)RPQ進(jìn)行分解，然后進(jìn)行分段求值。該方法實(shí)際上采取了分治策略，但需要通過(guò)預(yù)處理事先確定“罕見(jiàn)標(biāo)簽”，其性能很大程度上取決于具體的查詢分解方法和罕見(jiàn)標(biāo)簽的選擇。面對(duì)海量的RDF圖數(shù)據(jù)，部分求值的方法也被應(yīng)用到分布式正則路徑查詢，查詢過(guò)程分為本地計(jì)算和整合局部答案兩個(gè)階段，本地計(jì)算基于動(dòng)態(tài)規(guī)劃方法，整合階段基于Thompson自動(dòng)機(jī)構(gòu)造方法來(lái)合并上一階段的局部結(jié)果。Sartiani等人提出了Vertigo，一種基于Brzozowski導(dǎo)數(shù)的分布式正則路徑查詢算法。該方法的實(shí)驗(yàn)基于Giraph圖計(jì)算框架，但是僅有ER圖和冪律圖上的測(cè)試，缺少對(duì)合成RDF數(shù)據(jù)集和真實(shí)世界數(shù)據(jù)集的驗(yàn)證實(shí)驗(yàn)。

目前已有的起源保障語(yǔ)義下的正則路徑查詢算法算法包括如下：