基于图划分的领域本体RDF存储方法

王红 王雪君 杨蓉

关键词： 标签传播; 图划分; 领域本体; 分布式存储; 民航突发事件; 相似案例

中图分类号： 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]是指对特定领域内概念及概念间关系的形式化表达，通常可以解析为RDF[2]（Resource Description Framework）三元组，而RDF本质上是一种图结构数据，因此可将其以图的方式进行分割存储。

目前海量RDF数据分区算法一般都基于图分割[3?7]。Pregel等图处理平台采用Hash方法进行图划分，但破坏了图自身的社区结构，产生了大量的切割边缘，导致图查询过程中有大量的通信开销[4]。Huang等人采用多级分割器METIS来优化RDF数据分区，由于RDF图顶点的邻居数是不均匀的，导致METIS的划分结果分布不均匀[5?6]。Wang提出了一种基于标签传播的多级图划分（MLP）方法，该方法能够保留图的社区结构，将密集的顶点划分在一起，但该方法划分结果不稳定[7]。

文献[8]将民航突发事件领域本体[9]以图的形式存储查询，但未实现对大数据的分布式处理。为此，本文将标签传播多级图划分算法结合标签能量函数引入领域本体RDF图数据的划分，旨在解决大数据条件下领域本体RDF图数据分布式存储的语义结构完整性问题，更好地支撑民航突发事件的语义查询。

1  研究思路

领域本体RDF多级图划分与存储过程分为以下三部分：

1） 领域本体的ID标识与标签预分配。将领域本体数据解析成RDF三元组，为RDF三元组的主语和宾语分配ID编号，并仅为实例数据主语进行标签预分配，为标签传播处理提供基础数据。

2） 领域本体RDF多级图划分。迭代使用标签传播算法完成RDF图中各顶点标签值的更新形成粗化顶点集合，并针对数据更新产生的数据集合不均衡问题，设置标签能量函数限制顶点集合的大小，实现数据的语义分区。

3） 领域本体RDF图的存储与查询。采用边割率对领域本体RDF图的划分效果进行分析与切割处理，实现RDF图语义数据的分区存储，通过航空器与非航空器突发事件相似案例的查询验证数据划分的有效性。

其具体流程如图1所示。

2  RDF的多级图划分方法

2.1 RDF图的标签传播

领域本体主要由类、关系、实例三部分组成。在对其解析过程中首先对模式数据即类进行解析，再对实例数据进行解析。将本体的类与实例解析为RDF图数据的顶点，将本体的关系解析为RDF图数据的有向边。对RDF图数据的顶点进行标识是对领域本体解析所得的RDF三元组中每个主体和客体采用整型数从1递增分配ID编号的过程。

2.1.1  领域本体RDF的标签预分配

定义1 对于给定的RDF图[G=（V，E）]，[V]是RDF三元组中所有主体和客体对应的顶点的集合，[E]是所有的有向边集合。其中[n=V，m=E]分别表示顶点数量和有向边数量。如果顶点[v∈V]，则[N（v）]表示顶点[v]的邻居数量，[deg（v）]表示顶点[v]的度数。标签预分配是选度数较高的顶点进行标签设置（如图2中L1，L2，L3），为标签的传播提供依据。考虑到为每个顶点分配标签会使更新速度缓慢，若对模式数据分配初始标签，在顶点更新过程中会造成数据规模过大的问题，因此，在初始阶段仅对实例数据主语进行标签预分配。

2.1.2  RDF图的标签传播过程

RDF图的标签传播是针对RDF图中未设置标签的顶点通过检测其邻居顶点中具有相同标签值且数量最多的标签作为自身标签的过程。标签传播一般不考虑顶点自身的语义，在传播过程中只需对各顶点ID编号以及顶点标签进行计算。由于本体RDF图数据是由具有语义关系的概念构成，故标签传播将形成语义结构相似的顶点子集，如图2所示。图2中顶点1，2，3为领域本体RDF图对应的实例主体，其他顶点为各实例主体对应的客体。初始阶段为顶点1，2，3依次分配标签L1，L2，L3，在根据ID编号依次遍历各顶点时，由于顶点4，5只有一个邻居顶点1，故只能接收邻居顶点1的标签L1，同理顶点8，10和顶点11，12分别接收标签L2和L3。而对于顶点6，由于可接收的标签有L1，L2，L3，且每个标签的数量都为1，此时考虑每个标签对应顶点的度数，选择度数大的顶点标签进行标签设置;当出现多个顶点的度相同时，则随机选取其中一个标签，图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图逐级粗化的思想是在标签传播的基础上，按照以下规则对具有相同标签的顶点不断合并形成粗化图的过程：

1） 若RDF图中任意两个顶点同时具有多个语义结构相似的邻居顶点，则将具有相同标签的顶点合并成新的顶点。

2） 若RDF图中某一顶点只有一条有向边，则说明该顶点只与邻居顶点具有相关性，故直接将其与邻居顶点合并成粗化顶点。

各顶点在首轮标签传播后均可形成不同标签构成的子结构，如图3所示。

将标签相同的顶点进行逐级合并，直到粗化图收敛成小规模图，可以形成粗化顶点以及粗化边。图3中第二级的粗化顶点[C21，C22，C23，C24]，本质上是第一级图中具有相同标签的顶点的集合。由式（1）、式（2）可以计算出[C21，C22，C23，C24]四个点的顶点权重分别为5，6，6，4，而[C22，C23]之间的边权重为2。

2.3  RDF图的多级划分

定义3 对于给定的RDF图的分区[P]，其[k]路分割是将图[G]分成[k]个不相交的子图，即[P={G1，G2，…，Gk}]，其中 [i=1kVi=V]。

定义4 切割边是指横跨[P]的不同分区的边，对于给定了[G]的k路分区[P]，其切割边数量[EC（P）]的定义为：

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

式中，[e（Vi，Vj）]是[Vi]和[Vj]之间的切割边。考虑到SPARQL查询中的通信开销，需要保证数据分区的负载均衡，即每个分區[Vi≈nk]，并使[EC（P）]最小化。

2.3.1  标签能量函数

由于标签传播方法产生的RDF粗化图数据集规模大小不同，将导致数据分区的不平衡。针对这一问题，通过为每个初始标签设置标签能量函数，利用标签能量函数限制粗化过程中数据集的大小。设定标签能量阈值[ε]，如果顶点[v]的标签能量小于[ε]，则顶点[v]不会涉及另一个顶点更新。假设顶点[v]的标签为[l]，则顶点[v]的标签能量[El（v）]为：

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

式中，[δ]是衰减因子，根据各顶点的度数设定，用来限制标签的传播范围，从而控制粗化集群的大小。

2.3.2  RDF图多级粗化图的算法实现

在多级框架下，基于标签传播和标签能量函数的RDF图粗化算法如下：

输入：RDF图[G=（V，E）]， [ε]，衰减因子[δ]。

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

实现过程：

1） 对解析后的RDF数据ID編号，标签分配。

2） 为每个标签分配能量值1。

3） 依次遍历每个顶点，判断其邻居顶点标签能量值，若大于[ε]则根据邻居顶点的标签进行更新。

4） 若有多个标签数量相同则选取标签对应的顶点度数最大的顶点标签，若顶点度数相同，则随机选取。

5） 更新标签并且根据式（4）更新能量值。

6） 具有相同标签的顶点形成粗化顶点以及粗化边集合。

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

8） 如果t值很大，则[C]作为新的输入，转到过程2）继续执行。

9） 将最终的粗化集合与原始数据对应，并进行分区，即[P={G1，G2，…，Gk}]。

3  基于多级图划分的领域本体存储

3.1  领域本体RDF图的标识

民航突发事件应急管理领域本体主要包括应急预案、应急资源、应急演练、突发事件、自愿报告、应急处置、善后处理7大类。每个大类由多个子类构成，如突发事件由航空器突发事件和非航空器突发事件两个子类组成，其中每个子类对应多个实例。

表1为民航突发事件领域本体中非航空器突发事件部分实例数据解析后得到的RDF三元组及其ID编号的标识情况。

3.2  领域本体RDF图的多级图划分与存储

实验基于5个节点的分布式环境，其中包括1个主节点以及4个从节点。开发环境为ubuntu16.04，mpich3.14，gStore[10?11]，64位Linux操作系统。采用世界民航事故调查跟踪信息报告以及民航突发事件应急管理领域本体作为实验数据，其中包含289个类，171个对象属性，1 203个数据属性及7 214个实例。将实验数据分成43 MB，656 MB，3.8 GB三组不同大小的数据。实验过程中设置标签的初始能量值为1，衰减因子[δ]的值设为0.2。

由于每个粗化顶点具有相同的标签，因此存储过程是根据每个顶点的标签将语义结构相似的数据迁移到相同的存储节点。数据划分过程中产生的切割边对应在不同分区的顶点，考虑到要保证结果的查全率以及查询时的通信开销，将切割边对应的顶点分别存储在其对应节点，在对数据进行查询时，根据这些顶点对应的切割边进行连接操作。

3.3 基于图划分的查询与效果分析

3.3.1  边割率的分析

边割率是在图划分过程中，两个相邻的顶点被划分在不同节点的边的个数与总边个数的比值，即切割边[数总边数]。这个比值描述了数据划分效果对查询时的通信代价，比值越大，在查询时两个节点的通信概率及次数就越高，反之说明通信概率及次数越低。

表2给出了分区个数分别为4和8时，采用本文算法与Hash和Metis方法三者对应的边割率对比分析。

由表2的实验结果可以看出，当数据量较少时，本文方法与Metis的边割率没有明显区别，但随着数据的增长，边割率将进一步低于Metis方法，而Hash算法由于没有考虑到RDF数据之间的关联性，所以产生了大量的切割边。

3.3.2  案例的查询及分析

将分区文件分别存储到对应的节点，采用gStore作为查询工具，根据SPARQL查询语句不拆分的策略进行查询，将每个节点查询得到的含有切割边的局部结果都将其在主节点进行拼接，得到最终查询结果。

通过对民航突发事件的相关案例查询，对三种分区方法的查询响应时间进行比较，验证该划分与存储方法的有效性：

1） 针对非航空器突发事件案例的查询Q1。通过对飞行员操作失误、天气原因、空管指挥不当等多个原因对应的案例以及其造成的结果分别进行查询，并对其查询响应时间取平均值。Q1的平均查询速度的对比如图4所示。

Q1查询涉及的关联较少且内容简单，由于Hash分割没有考虑到三元组之间的联系，所以当数据量增加时查询时间会明显增长，而Metis算法因为一定程度上保留了数据的语义结构，所以在简单查询时，有较高的查询效率。

2） 针对航空器突发事件原因的查询Q2。通过对航空器坠毁、航空器重着陆、航空器冲偏出跑道等多个结果对应的相似案例名称、原因、时间、遇难人数以及应急处置等分别进行查询，并取查询响应时间平均值。Q2查询速度对比效果如图5所示。

Q2查询涉及的关联较多且查询内容复杂，因此查询时需要消耗较多的时间。采用Metis划分得到的结果相对较差，当执行复杂查询时得到的局部结果较多，故在主节点需要消耗较多的组合时间。因此，当查询数据量较大且复杂时，由于本文算法得到的中间结果较少，对局部结果拼接所耗费的时间较少，优于其他分割方法。通过对三种划分方法进行查询结果对比可知，当执行较复杂的查询时本文算法查询时间在三种方法中具有明显优势。

4  结  语

本文提出一种在多级框架下利用标签传播算法与能量函数结合的划分方法，有效保留了RDF图数据的语义结构。并将该方法应用到民航突发事件领域本体的分布式存储，通过实验验证了该方法在领域本体数据RDF图数据的语义结构存储与案例查询中的优势，为民航突发事件应急管理领域本体在大数据平台下的数据存储提供了进一步的方法支撑。下一步将对RDF图数据的分布式全局索引技术进行研究，进一步提高查询效率。

参考文献

[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] 崔义童，冯志勇，王鑫，等.基于图聚类算法的大规模RDF数据查询方法研究[J].小型微型计算机系统，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.