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

在審

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

1.一種基于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ù)中匹配正則路徑查詢，通過消息傳遞的方式、以頂點(diǎn)為中心的計(jì)算之后得到結(jié)果路徑；

4)統(tǒng)計(jì)所有滿足正則表達(dá)式r的結(jié)果路徑即為查詢結(jié)果。

2.根據(jù)權(quán)利要求1所述的一種基于Pregel的分布式起源保障正則路徑查詢算法，步驟1)中，所述的正則表達(dá)式被遞歸定義為r：：＝ε|p|r/r|r|r|r^*，其中ε為空串，p為字母表Σ中的任意字符，/代表連接、|代表連接、*代表閉包。

3.根據(jù)權(quán)利要求1所述的一種基于Pregel的分布式起源保障正則路徑查詢算法，步驟2)中，基于正則表達(dá)式構(gòu)建Glushkov自動(dòng)機(jī)時(shí)，用Por(r)＝{1,...,|r|}表示r中字符位置的集合，其中|r|表示r的長(zhǎng)度，i∈Pos(r)是r[i]的索引。

4.根據(jù)權(quán)利要求1所述的一種基于Pregel的分布式起源保障正則路徑查詢算法，步驟1)中，所述的first集為正則表達(dá)式r所表示的語言L(r)中的任一字符串開頭字符所對(duì)應(yīng)的狀態(tài)集合，所述的last集為L(zhǎng)(r)中的任一字符串結(jié)尾字符所對(duì)應(yīng)的狀態(tài)集合，所述的follow集為L(zhǎng)(r)中的任一字符串中某個(gè)位置字符的接下來字符所對(duì)應(yīng)狀態(tài)集。

5.根據(jù)權(quán)利要求1所述的一種基于Pregel的分布式起源保障正則路徑查詢算法，步驟3)中，所述的計(jì)算的過程并行在每個(gè)頂點(diǎn)進(jìn)行，在滿足自動(dòng)機(jī)轉(zhuǎn)換函數(shù)的條件下向前擴(kuò)展一個(gè)狀態(tài)q∈St來匹配v∈V，直至匹配到結(jié)束狀態(tài)或不再有頂點(diǎn)v能夠與自動(dòng)機(jī)中的狀態(tài)q相匹配，具體包括以下步驟：

3.1)給出判斷條件：對(duì)于RDF圖數(shù)據(jù)T＝(V,E,l)中的每個(gè)頂點(diǎn)v∈V，如果每個(gè)頂點(diǎn)v的出邊屬性標(biāo)簽與first集中狀態(tài)對(duì)應(yīng)的字符一致，則該頂點(diǎn)v與first集中狀態(tài)可以相匹配；

3.2)根據(jù)步驟3.1)的判斷條件，計(jì)算與每個(gè)頂點(diǎn)v可能匹配的狀態(tài)q，形成匹配f＝(v,q)，完成第一步匹配；

3.3)形成的匹配作為消息m發(fā)送給其他鄰居頂點(diǎn)，其他鄰居頂點(diǎn)接收消息集M；

3.4)根據(jù)接收到消息集M中已有的匹配f，計(jì)算當(dāng)前匹配的下一個(gè)可能的狀態(tài)q'，即通過follow集繼續(xù)擴(kuò)展，通過頂點(diǎn)v的出邊屬性與follow集中狀態(tài)對(duì)應(yīng)的字符是否一致，判斷該頂點(diǎn)v與follow集中狀態(tài)是否可以匹配，如果可以匹配，向前拓展一個(gè)狀態(tài)以此來滿足正則表達(dá)式r；

3.5)重復(fù)步驟3.3)、3.4)直至當(dāng)前頂點(diǎn)匹配到的狀態(tài)屬于last集，當(dāng)前路徑為結(jié)果集中的路徑；

3.6)對(duì)于已經(jīng)完成的路徑重復(fù)步驟3.5)，直至不再有新的結(jié)果路徑產(chǎn)生。

6.根據(jù)權(quán)利要求1所述的一種基于Pregel的分布式起源保障正則路徑查詢算法，步驟4)中，對(duì)于步驟3)中獲得的每條結(jié)果路徑在該路徑中匹配結(jié)束狀態(tài)的頂點(diǎn)中保存，遍歷RDF數(shù)據(jù)圖的每個(gè)頂點(diǎn)v∈V，即可獲取該查詢的全部結(jié)果路徑。

7.根據(jù)權(quán)利要求1所述的一種基于Pregel的分布式起源保障正則路徑查詢算法，步驟4)中，由于從匹配起始狀態(tài)的頂點(diǎn)及其匹配對(duì)(v₀,q₀)，到匹配結(jié)束狀態(tài)的頂點(diǎn)及其匹配對(duì)(v_n,q_n)，存在一條從v₀到v_n路徑(v₀,v₁,...,v_n)，且q_i+1＝δ(q_i,(v_i,v_i+1))，因此，滿足正則表達(dá)式r的結(jié)果路徑即為查詢結(jié)果。