王紅 王雪君 楊蓉

關(guān)鍵詞： 標(biāo)簽傳播; 圖劃分; 領(lǐng)域本體; 分布式存儲; 民航突發(fā)事件; 相似案例

中圖分類號： TN919?34; TP391 ? ? ? ? ? ? ? ? 文獻標(biāo)識碼： A ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2018）24?0141?05

A domain ontology RDF storage method based on graph partitioning

WANG Hong， WANG Xuejun， YANG Rong

（School of Computer Science and Technology， Civil Aviation University of China， Tianjin 300300， China）

Abstract： As the distributed storage of massive RDF graph data cannot effectively maintain the semantic structure integrity of data， a multi?level graph partitioning method based on the label propagation and label energy function is proposed. In the method， the ID identification of vertexes is conducted for the RDF graph obtained by parsing the domain ontology. The initial label is assigned to the subject of the instance data. The label propagation method is used to set the label for each vertex， so as to form a vertex set with the similar semantic structure. On this basis， the size of the vertex set is limited by means of multi?level graph coarsening and the label energy function， so as to realize semantic partitioning of data. The method is applied to the distributed storage and query for the emergency domain ontology of civil aviation. The edge cut rate is used to analyze and compare the partitioning effect of domain ontology data. The experimental results show that the method can guarantee a high recall rate on the basis of reducing the edge cut rate， and improve the query efficiency of similar emergency cases in civil aviation， which can provide a further methodology support for distributed storage and semantic query of large?scale domain ontology.

Keywords： label propagation; graph partitioning; domain ontology; distributed storage; civil aviation emergency; similar case

領(lǐng)域本體[1]是指對特定領(lǐng)域內(nèi)概念及概念間關(guān)系的形式化表達，通?？梢越馕鰹镽DF[2]（Resource Description Framework）三元組，而RDF本質(zhì)上是一種圖結(jié)構(gòu)數(shù)據(jù)，因此可將其以圖的方式進行分割存儲。

目前海量RDF數(shù)據(jù)分區(qū)算法一般都基于圖分割[3?7]。Pregel等圖處理平臺采用Hash方法進行圖劃分，但破壞了圖自身的社區(qū)結(jié)構(gòu)，產(chǎn)生了大量的切割邊緣，導(dǎo)致圖查詢過程中有大量的通信開銷[4]。Huang等人采用多級分割器METIS來優(yōu)化RDF數(shù)據(jù)分區(qū)，由于RDF圖頂點的鄰居數(shù)是不均勻的，導(dǎo)致METIS的劃分結(jié)果分布不均勻[5?6]。Wang提出了一種基于標(biāo)簽傳播的多級圖劃分（MLP）方法，該方法能夠保留圖的社區(qū)結(jié)構(gòu)，將密集的頂點劃分在一起，但該方法劃分結(jié)果不穩(wěn)定[7]。

文獻[8]將民航突發(fā)事件領(lǐng)域本體[9]以圖的形式存儲查詢，但未實現(xiàn)對大數(shù)據(jù)的分布式處理。為此，本文將標(biāo)簽傳播多級圖劃分算法結(jié)合標(biāo)簽?zāi)芰亢瘮?shù)引入領(lǐng)域本體RDF圖數(shù)據(jù)的劃分，旨在解決大數(shù)據(jù)條件下領(lǐng)域本體RDF圖數(shù)據(jù)分布式存儲的語義結(jié)構(gòu)完整性問題，更好地支撐民航突發(fā)事件的語義查詢。

1 ?研究思路

領(lǐng)域本體RDF多級圖劃分與存儲過程分為以下三部分：

1） 領(lǐng)域本體的ID標(biāo)識與標(biāo)簽預(yù)分配。將領(lǐng)域本體數(shù)據(jù)解析成RDF三元組，為RDF三元組的主語和賓語分配ID編號，并僅為實例數(shù)據(jù)主語進行標(biāo)簽預(yù)分配，為標(biāo)簽傳播處理提供基礎(chǔ)數(shù)據(jù)。

2） 領(lǐng)域本體RDF多級圖劃分。迭代使用標(biāo)簽傳播算法完成RDF圖中各頂點標(biāo)簽值的更新形成粗化頂點集合，并針對數(shù)據(jù)更新產(chǎn)生的數(shù)據(jù)集合不均衡問題，設(shè)置標(biāo)簽?zāi)芰亢瘮?shù)限制頂點集合的大小，實現(xiàn)數(shù)據(jù)的語義分區(qū)。

3） 領(lǐng)域本體RDF圖的存儲與查詢。采用邊割率對領(lǐng)域本體RDF圖的劃分效果進行分析與切割處理，實現(xiàn)RDF圖語義數(shù)據(jù)的分區(qū)存儲，通過航空器與非航空器突發(fā)事件相似案例的查詢驗證數(shù)據(jù)劃分的有效性。

其具體流程如圖1所示。

2 ?RDF的多級圖劃分方法

2.1 RDF圖的標(biāo)簽傳播

領(lǐng)域本體主要由類、關(guān)系、實例三部分組成。在對其解析過程中首先對模式數(shù)據(jù)即類進行解析，再對實例數(shù)據(jù)進行解析。將本體的類與實例解析為RDF圖數(shù)據(jù)的頂點，將本體的關(guān)系解析為RDF圖數(shù)據(jù)的有向邊。對RDF圖數(shù)據(jù)的頂點進行標(biāo)識是對領(lǐng)域本體解析所得的RDF三元組中每個主體和客體采用整型數(shù)從1遞增分配ID編號的過程。

2.1.1 ?領(lǐng)域本體RDF的標(biāo)簽預(yù)分配

定義1 對于給定的RDF圖[G=（V，E）]，[V]是RDF三元組中所有主體和客體對應(yīng)的頂點的集合，[E]是所有的有向邊集合。其中[n=V，m=E]分別表示頂點數(shù)量和有向邊數(shù)量。如果頂點[v∈V]，則[N（v）]表示頂點[v]的鄰居數(shù)量，[deg（v）]表示頂點[v]的度數(shù)。標(biāo)簽預(yù)分配是選度數(shù)較高的頂點進行標(biāo)簽設(shè)置（如圖2中L1，L2，L3），為標(biāo)簽的傳播提供依據(jù)。考慮到為每個頂點分配標(biāo)簽會使更新速度緩慢，若對模式數(shù)據(jù)分配初始標(biāo)簽，在頂點更新過程中會造成數(shù)據(jù)規(guī)模過大的問題，因此，在初始階段僅對實例數(shù)據(jù)主語進行標(biāo)簽預(yù)分配。

2.1.2 ?RDF圖的標(biāo)簽傳播過程

RDF圖的標(biāo)簽傳播是針對RDF圖中未設(shè)置標(biāo)簽的頂點通過檢測其鄰居頂點中具有相同標(biāo)簽值且數(shù)量最多的標(biāo)簽作為自身標(biāo)簽的過程。標(biāo)簽傳播一般不考慮頂點自身的語義，在傳播過程中只需對各頂點ID編號以及頂點標(biāo)簽進行計算。由于本體RDF圖數(shù)據(jù)是由具有語義關(guān)系的概念構(gòu)成，故標(biāo)簽傳播將形成語義結(jié)構(gòu)相似的頂點子集，如圖2所示。圖2中頂點1，2，3為領(lǐng)域本體RDF圖對應(yīng)的實例主體，其他頂點為各實例主體對應(yīng)的客體。初始階段為頂點1，2，3依次分配標(biāo)簽L1，L2，L3，在根據(jù)ID編號依次遍歷各頂點時，由于頂點4，5只有一個鄰居頂點1，故只能接收鄰居頂點1的標(biāo)簽L1，同理頂點8，10和頂點11，12分別接收標(biāo)簽L2和L3。而對于頂點6，由于可接收的標(biāo)簽有L1，L2，L3，且每個標(biāo)簽的數(shù)量都為1，此時考慮每個標(biāo)簽對應(yīng)頂點的度數(shù)，選擇度數(shù)大的頂點標(biāo)簽進行標(biāo)簽設(shè)置;當(dāng)出現(xiàn)多個頂點的度相同時，則隨機選取其中一個標(biāo)簽，圖2中頂點1的度為4，其他兩個頂點度為5，故應(yīng)在L2和L3中隨機選取。以此類推可以進行頂點7，9的標(biāo)簽設(shè)置。

2.2 ?RDF圖的粗化

2.2.1 ?RDF粗化圖的定義

定義2 對給定的RDF圖[G=（V，E）]進行粗化是將[G]中連接緊密的頂點集折疊成一個頂點后形成的圖[G′=（V′，E′）]，其中[V′，E′]是具有權(quán)重的頂點和邊的集合，對于粗化頂點[vi′∈V′]，其頂點和邊權(quán)重定義如下：

1） 頂點權(quán)重：

[w（vi′）=u∈v′iw（u）] （1）

2） 邊的權(quán)重：

[w（vi′，ui′）=e（u，v）∈E，u∈v′i，v∈v′jwe（u，v）] （2）

式中：[w（u）]代表鄰居頂點的權(quán)重;[w（e（u，v））]代表連接粗化頂點的邊的權(quán)重。

2.2.2 ?RDF圖的粗化過程

RDF圖逐級粗化的思想是在標(biāo)簽傳播的基礎(chǔ)上，按照以下規(guī)則對具有相同標(biāo)簽的頂點不斷合并形成粗化圖的過程：

1） 若RDF圖中任意兩個頂點同時具有多個語義結(jié)構(gòu)相似的鄰居頂點，則將具有相同標(biāo)簽的頂點合并成新的頂點。

2） 若RDF圖中某一頂點只有一條有向邊，則說明該頂點只與鄰居頂點具有相關(guān)性，故直接將其與鄰居頂點合并成粗化頂點。

各頂點在首輪標(biāo)簽傳播后均可形成不同標(biāo)簽構(gòu)成的子結(jié)構(gòu)，如圖3所示。

將標(biāo)簽相同的頂點進行逐級合并，直到粗化圖收斂成小規(guī)模圖，可以形成粗化頂點以及粗化邊。圖3中第二級的粗化頂點[C21，C22，C23，C24]，本質(zhì)上是第一級圖中具有相同標(biāo)簽的頂點的集合。由式（1）、式（2）可以計算出[C21，C22，C23，C24]四個點的頂點權(quán)重分別為5，6，6，4，而[C22，C23]之間的邊權(quán)重為2。

2.3 ?RDF圖的多級劃分

定義3 對于給定的RDF圖的分區(qū)[P]，其[k]路分割是將圖[G]分成[k]個不相交的子圖，即[P={G1，G2，…，Gk}]，其中 [i=1kVi=V]。

定義4 切割邊是指橫跨[P]的不同分區(qū)的邊，對于給定了[G]的k路分區(qū)[P]，其切割邊數(shù)量[EC（P）]的定義為：

[EC（P）=i=1kj>ike（Vi，Vj）] （3）

式中，[e（Vi，Vj）]是[Vi]和[Vj]之間的切割邊?？紤]到SPARQL查詢中的通信開銷，需要保證數(shù)據(jù)分區(qū)的負(fù)載均衡，即每個分區(qū)[Vi≈nk]，并使[EC（P）]最小化。

2.3.1 ?標(biāo)簽?zāi)芰亢瘮?shù)

由于標(biāo)簽傳播方法產(chǎn)生的RDF粗化圖數(shù)據(jù)集規(guī)模大小不同，將導(dǎo)致數(shù)據(jù)分區(qū)的不平衡。針對這一問題，通過為每個初始標(biāo)簽設(shè)置標(biāo)簽?zāi)芰亢瘮?shù)，利用標(biāo)簽?zāi)芰亢瘮?shù)限制粗化過程中數(shù)據(jù)集的大小。設(shè)定標(biāo)簽?zāi)芰块撝礫ε]，如果頂點[v]的標(biāo)簽?zāi)芰啃∮赱ε]，則頂點[v]不會涉及另一個頂點更新。假設(shè)頂點[v]的標(biāo)簽為[l]，則頂點[v]的標(biāo)簽?zāi)芰縖El（v）]為：

[El（v）=argmaxj∈Nl（v）E（j）-δ] （4）

式中，[δ]是衰減因子，根據(jù)各頂點的度數(shù)設(shè)定，用來限制標(biāo)簽的傳播范圍，從而控制粗化集群的大小。

2.3.2 ?RDF圖多級粗化圖的算法實現(xiàn)

在多級框架下，基于標(biāo)簽傳播和標(biāo)簽?zāi)芰亢瘮?shù)的RDF圖粗化算法如下：

輸入：RDF圖[G=（V，E）]， [ε]，衰減因子[δ]。

輸出：[C={c1，c2，…，ct}]。

實現(xiàn)過程：

1） 對解析后的RDF數(shù)據(jù)ID編號，標(biāo)簽分配。

2） 為每個標(biāo)簽分配能量值1。

3） 依次遍歷每個頂點，判斷其鄰居頂點標(biāo)簽?zāi)芰恐担舸笥赱ε]則根據(jù)鄰居頂點的標(biāo)簽進行更新。

4） 若有多個標(biāo)簽數(shù)量相同則選取標(biāo)簽對應(yīng)的頂點度數(shù)最大的頂點標(biāo)簽，若頂點度數(shù)相同，則隨機選取。

5） 更新標(biāo)簽并且根據(jù)式（4）更新能量值。

6） 具有相同標(biāo)簽的頂點形成粗化頂點以及粗化邊集合。

7） 輸出粗化集合[C={c1，c2，…，ct}]。

8） 如果t值很大，則[C]作為新的輸入，轉(zhuǎn)到過程2）繼續(xù)執(zhí)行。

9） 將最終的粗化集合與原始數(shù)據(jù)對應(yīng)，并進行分區(qū)，即[P={G1，G2，…，Gk}]。

3 ?基于多級圖劃分的領(lǐng)域本體存儲

3.1 ?領(lǐng)域本體RDF圖的標(biāo)識

民航突發(fā)事件應(yīng)急管理領(lǐng)域本體主要包括應(yīng)急預(yù)案、應(yīng)急資源、應(yīng)急演練、突發(fā)事件、自愿報告、應(yīng)急處置、善后處理7大類。每個大類由多個子類構(gòu)成，如突發(fā)事件由航空器突發(fā)事件和非航空器突發(fā)事件兩個子類組成，其中每個子類對應(yīng)多個實例。

表1為民航突發(fā)事件領(lǐng)域本體中非航空器突發(fā)事件部分實例數(shù)據(jù)解析后得到的RDF三元組及其ID編號的標(biāo)識情況。

3.2 ?領(lǐng)域本體RDF圖的多級圖劃分與存儲

實驗基于5個節(jié)點的分布式環(huán)境，其中包括1個主節(jié)點以及4個從節(jié)點。開發(fā)環(huán)境為ubuntu16.04，mpich3.14，gStore[10?11]，64位Linux操作系統(tǒng)。采用世界民航事故調(diào)查跟蹤信息報告以及民航突發(fā)事件應(yīng)急管理領(lǐng)域本體作為實驗數(shù)據(jù)，其中包含289個類，171個對象屬性，1 203個數(shù)據(jù)屬性及7 214個實例。將實驗數(shù)據(jù)分成43 MB，656 MB，3.8 GB三組不同大小的數(shù)據(jù)。實驗過程中設(shè)置標(biāo)簽的初始能量值為1，衰減因子[δ]的值設(shè)為0.2。

由于每個粗化頂點具有相同的標(biāo)簽，因此存儲過程是根據(jù)每個頂點的標(biāo)簽將語義結(jié)構(gòu)相似的數(shù)據(jù)遷移到相同的存儲節(jié)點。數(shù)據(jù)劃分過程中產(chǎn)生的切割邊對應(yīng)在不同分區(qū)的頂點，考慮到要保證結(jié)果的查全率以及查詢時的通信開銷，將切割邊對應(yīng)的頂點分別存儲在其對應(yīng)節(jié)點，在對數(shù)據(jù)進行查詢時，根據(jù)這些頂點對應(yīng)的切割邊進行連接操作。

3.3 基于圖劃分的查詢與效果分析

3.3.1 ?邊割率的分析

邊割率是在圖劃分過程中，兩個相鄰的頂點被劃分在不同節(jié)點的邊的個數(shù)與總邊個數(shù)的比值，即切割邊[數(shù)總邊數(shù)]。這個比值描述了數(shù)據(jù)劃分效果對查詢時的通信代價，比值越大，在查詢時兩個節(jié)點的通信概率及次數(shù)就越高，反之說明通信概率及次數(shù)越低。

表2給出了分區(qū)個數(shù)分別為4和8時，采用本文算法與Hash和Metis方法三者對應(yīng)的邊割率對比分析。

由表2的實驗結(jié)果可以看出，當(dāng)數(shù)據(jù)量較少時，本文方法與Metis的邊割率沒有明顯區(qū)別，但隨著數(shù)據(jù)的增長，邊割率將進一步低于Metis方法，而Hash算法由于沒有考慮到RDF數(shù)據(jù)之間的關(guān)聯(lián)性，所以產(chǎn)生了大量的切割邊。

3.3.2 ?案例的查詢及分析

將分區(qū)文件分別存儲到對應(yīng)的節(jié)點，采用gStore作為查詢工具，根據(jù)SPARQL查詢語句不拆分的策略進行查詢，將每個節(jié)點查詢得到的含有切割邊的局部結(jié)果都將其在主節(jié)點進行拼接，得到最終查詢結(jié)果。

通過對民航突發(fā)事件的相關(guān)案例查詢，對三種分區(qū)方法的查詢響應(yīng)時間進行比較，驗證該劃分與存儲方法的有效性：

1） 針對非航空器突發(fā)事件案例的查詢Q1。通過對飛行員操作失誤、天氣原因、空管指揮不當(dāng)?shù)榷鄠€原因?qū)?yīng)的案例以及其造成的結(jié)果分別進行查詢，并對其查詢響應(yīng)時間取平均值。Q1的平均查詢速度的對比如圖4所示。

Q1查詢涉及的關(guān)聯(lián)較少且內(nèi)容簡單，由于Hash分割沒有考慮到三元組之間的聯(lián)系，所以當(dāng)數(shù)據(jù)量增加時查詢時間會明顯增長，而Metis算法因為一定程度上保留了數(shù)據(jù)的語義結(jié)構(gòu)，所以在簡單查詢時，有較高的查詢效率。

2） 針對航空器突發(fā)事件原因的查詢Q2。通過對航空器墜毀、航空器重著陸、航空器沖偏出跑道等多個結(jié)果對應(yīng)的相似案例名稱、原因、時間、遇難人數(shù)以及應(yīng)急處置等分別進行查詢，并取查詢響應(yīng)時間平均值。Q2查詢速度對比效果如圖5所示。

Q2查詢涉及的關(guān)聯(lián)較多且查詢內(nèi)容復(fù)雜，因此查詢時需要消耗較多的時間。采用Metis劃分得到的結(jié)果相對較差，當(dāng)執(zhí)行復(fù)雜查詢時得到的局部結(jié)果較多，故在主節(jié)點需要消耗較多的組合時間。因此，當(dāng)查詢數(shù)據(jù)量較大且復(fù)雜時，由于本文算法得到的中間結(jié)果較少，對局部結(jié)果拼接所耗費的時間較少，優(yōu)于其他分割方法。通過對三種劃分方法進行查詢結(jié)果對比可知，當(dāng)執(zhí)行較復(fù)雜的查詢時本文算法查詢時間在三種方法中具有明顯優(yōu)勢。

4 ?結(jié) ?語

本文提出一種在多級框架下利用標(biāo)簽傳播算法與能量函數(shù)結(jié)合的劃分方法，有效保留了RDF圖數(shù)據(jù)的語義結(jié)構(gòu)。并將該方法應(yīng)用到民航突發(fā)事件領(lǐng)域本體的分布式存儲，通過實驗驗證了該方法在領(lǐng)域本體數(shù)據(jù)RDF圖數(shù)據(jù)的語義結(jié)構(gòu)存儲與案例查詢中的優(yōu)勢，為民航突發(fā)事件應(yīng)急管理領(lǐng)域本體在大數(shù)據(jù)平臺下的數(shù)據(jù)存儲提供了進一步的方法支撐。下一步將對RDF圖數(shù)據(jù)的分布式全局索引技術(shù)進行研究，進一步提高查詢效率。

參考文獻

[1] BOZSAK E， EHRIG M， HANDSCHUH S， et al. KAON： towards a large scale semantic web [C]// Proceedings of International Conference on Electronic Commerce and Web Technologies. Berlin： Springer?Verlag， 2002： 304?313.

[2] RDF Working Group. Resource ?description ?framework （RDF） [EB/OL]. [2014?02?25]. http：//www.w3.org/RDF/.

[3] 崔義童，馮志勇，王鑫，等.基于圖聚類算法的大規(guī)模RDF數(shù)據(jù)查詢方法研究[J].小型微型計算機系統(tǒng)，2015，36（12）：2625?2628.

CUI Yitong， FENG Zhiyong， WANG Xin， et al. Research on large?scale RDF data query method based on graph clustering [J]. Journal of Chinese computer systems， 2015， 36（12）： 2625?2628.

[4] MALEWICZ G， AUSTERN M H， BIK A J C， et al. Pregel： a system for large?scale graph processing [C]// Proceedings of ACM SIGMOD International Conference on Management of Data. Indianapolis： ACM， 2010： 135?146.

[5] HUANG J， ABADI D J， REN K. Scalable SPARQL querying of large RDF graphs [J]. Proceedings of the Vldb Endowment， 2012， 4（11）： 1123?1134.

[6] Karypis Lab. METIS： serial graph partitioning and fill?reducing Matrix ordering [EB/OL]. [2016?10?30]. http：//glaros.dtc.umn.edu/gkhome/views/metis.

[7] WANG L， XIAO Y， SHAO B， et al. How to partition a billion?node graph [C]// Proceedings of IEEE 30th International Conference on Data Engineering. Chicago： IEEE， 2014： 568?579.

[8] 王紅，張青青，蔡偉偉，等.基于Neo4j的領(lǐng)域本體存儲方法研究[J].計算機應(yīng)用研究，2017，34（8）：2404?2407.

WANG Hong， ZHANG Qingqing， CAI Weiwei， et al. Research on storage method for domain ontology based on Neo4j [J]. Application research of computers， 2017， 34（8）： 2404?2407.

[9] 王紅，楊璇，王靜，等.基于本體的民航應(yīng)急決策知識表達與推理方法研究[J].計算機工程與科學(xué)，2011，33（4）：129?133.

WANG Hong， YANG Xuan， WANG Jing， et al. Research on ontology?based knowledge presentation and ?reasoning in civil ?aviation emergency decision [J]. Computer engineering & science， 2011， 33（4）： 129?133.

[10] PENG P， ZOU L， CHEN L， et al. Processing SPARQL queries over distributed RDF graphs [J]. International journal on very large data bases， 2016， 25（2）： 243?268.

[11] ZOU L， ?ZSU M T， CHEN L， et al. gStore： a graph?based SPARQL query engine [J]. International journal on very large data bases， 2014， 23（4）： 565?590.