王紅 王雪君 楊蓉

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

中圖分類號： TN919?34; TP391 ? ? ? ? ? ? ? ? 文獻標識碼： 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

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

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

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

1 ?研究思路

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

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

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

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

其具體流程如圖1所示。

2 ?RDF的多級圖劃分方法

2.1 RDF圖的標簽傳播

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

2.1.1 ?領域本體RDF的標簽預分配

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

2.1.2 ?RDF圖的標簽傳播過程

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

2.2 ?RDF圖的粗化

2.2.1 ?RDF粗化圖的定義

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

1） 頂點權重：

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

2） 邊的權重：

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

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

2.2.2 ?RDF圖的粗化過程

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

1） 若RDF圖中任意兩個頂點同時具有多個語義結構相似的鄰居頂點，則將具有相同標簽的頂點合并成新的頂點。

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

各頂點在首輪標簽傳播后均可形成不同標簽構成的子結構，如圖3所示。

將標簽相同的頂點進行逐級合并，直到粗化圖收斂成小規(guī)模圖，可以形成粗化頂點以及粗化邊。圖3中第二級的粗化頂點[C21，C22，C23，C24]，本質(zhì)上是第一級圖中具有相同標簽的頂點的集合。由式（1）、式（2）可以計算出[C21，C22，C23，C24]四個點的頂點權重分別為5，6，6，4，而[C22，C23]之間的邊權重為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ū)的負載均衡，即每個分區(qū)[Vi≈nk]，并使[EC（P）]最小化。

2.3.1 ?標簽能量函數(shù)

由于標簽傳播方法產(chǎn)生的RDF粗化圖數(shù)據(jù)集規(guī)模大小不同，將導致數(shù)據(jù)分區(qū)的不平衡。針對這一問題，通過為每個初始標簽設置標簽能量函數(shù)，利用標簽能量函數(shù)限制粗化過程中數(shù)據(jù)集的大小。設定標簽能量閾值[ε]，如果頂點[v]的標簽能量小于[ε]，則頂點[v]不會涉及另一個頂點更新。假設頂點[v]的標簽為[l]，則頂點[v]的標簽能量[El（v）]為：

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

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

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

在多級框架下，基于標簽傳播和標簽能量函數(shù)的RDF圖粗化算法如下：

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

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

實現(xiàn)過程：

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

2） 為每個標簽分配能量值1。

3） 依次遍歷每個頂點，判斷其鄰居頂點標簽能量值，若大于[ε]則根據(jù)鄰居頂點的標簽進行更新。

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

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

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

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

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

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

3 ?基于多級圖劃分的領域本體存儲

3.1 ?領域本體RDF圖的標識

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

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

3.2 ?領域本體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ā)事件應急管理領域本體作為實驗數(shù)據(jù)，其中包含289個類，171個對象屬性，1 203個數(shù)據(jù)屬性及7 214個實例。將實驗數(shù)據(jù)分成43 MB，656 MB，3.8 GB三組不同大小的數(shù)據(jù)。實驗過程中設置標簽的初始能量值為1，衰減因子[δ]的值設為0.2。

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

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

3.3.1 ?邊割率的分析

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

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

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

3.3.2 ?案例的查詢及分析

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

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

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

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

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

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

4 ?結 ?語

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

參考文獻

[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的領域本體存儲方法研究[J].計算機應用研究，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] 王紅，楊璇，王靜，等.基于本體的民航應急決策知識表達與推理方法研究[J].計算機工程與科學，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.