基于分布式的RDF数据分割方法研究

吴建胜，冯锡炜，陈 浩，侯 伟，李品乐，赵 驰，王超琦，桂亚飞

（辽宁石油化工大学信息与控制工程学院，抚顺 113001）

0 引言

在现阶段的社会中，语义网络是计算机探究的热门方向，而资源描述框架（resource description framework,RDF）作为语义网中的一个核心技术也成为了人们研究的热门话题。RDF数据的存储自然也成为当下研究热点，许多学者在这方面进行了各种各样的研究。并且随着RDF 数据集的增加，在一台机器上管理和查询RDF 数据的性能问题就出现了，这促使学者们对此类问题采取分布式的解决方案［1］。目前，RDF 数据的存储方式可以大致分为基于关系存储的表结构存储方式，以及基于非关系型存储的图结构存储，而大多数如Sesame、Jena、RDF-3X 等管理系统都是使用关系型数据库来存储相关数据［2］。关系数据库的局限性在于不够灵活，也不容易扩展。根据RDF 数据的图特征，在存储中考虑图模型的方式来管理RDF 数据。由于RDF 数据随着时间的积累数据量越来越大，这就需要采用分布式的解决方案［3］。本文将围绕图结构来研究RDF 数据的存储及其分布式存储方案设计。

1 研究背景

1.1 RDF数据模型

RDF 是由W3C 提出的一种数据模型，它提供了一个统一的标准，用于描述实体/资源。RDF 数据由这三个元素组成：主体S、属性P、客体O，其是描述Web 上资源的属性以及这些资源之间关系的基本单位［4］。RDF 数据中简单的一条数据就可以表示为一个无向图，其中主体S 和客体O 是顶点，属性P 是边，属性名是边标签。

1.2 图数据库

由于RDF 数据天然的三元组的性质，其本身就很容易用图的形式来表现，为了解决计算机领域的RDF 数据存储问题，需要使用不同的存储技术。在许多存储技术中，关系数据库出现较早并长期以来一直占据主导地位。随着Web 技术的应用、社交网络的兴起，内部数据的依赖性和复杂性逐渐增加，关系数据库出现了越来越多的问题。在此之后，出现了图形数据库。近年来出现了一些高性能图形数据库的产品环境，如Neo4j、Infinite、Graph、DEX、InfoGrid、HyperGraphDB、Trinity 等［5］。其中，Neo4j 是目前主流的一款基于Java 的开源软件，其内核是一个速度非常快的图形引擎，具有恢复、两阶段提交、支持XA 事务等数据库产品特性。Neo4j 是一个嵌入式的、基于磁盘的、完全事务性的Java 持久引擎，它将结构化的数据存储在网络中而不是表中，并且Neo4j还是一个优秀的图形数据库工具，它以图形的形式存储数据，可以表示具有节点、边和属性的对象［6］。

2 RDF 数据分布式分割与存储实现

2.1 RDF数据分布式存储方案

2.1.1 设计理念

以传统的思维来看待数据一般是从关系模型或者对象数据模型角度出发，但RDF 数据是以三元组的形式来记录并存放的。由于RDF 数据并没有明显的关系模型特性，对于使用关系型数据库或者基于对象的数据库来存储会产生许多冗余的数据，使得RDF 数据的存储有许多结构上的限制。但对于图数据库而言，RDF 本身的特性也决定了数据对于图的适配性很强。到目前为止，由于NoSQL 技术的日益成熟，使得图数据库渐渐进入人们的视野。相较于传统数据库，图数据库的数据处理虽然复杂，但其数据模式简单，数据之间的关系清晰明了，非常适用于处理大规模的半结构化和非结构化数据。RDF 数据模型与图数据库的数据一致，是天然的图模型［7］。

2.1.2 索引数据库

Redis 是一种基于内存的高性能数据库，可以用来存储索引信息等索引数据。在分布式RDF 图数据中，可以使用Redis 数据库存储RDF数据位置信息的索引数据，以便在查询时快速定位到包含所需信息的节点。在Redis 中，使用Hash 类型创建索引，其中键值为索引名称，每个属性和关系作为Hash 中的字段，其值是一个有序集合。有序集合中的成员为节点ID，其分值为该节点属性或关系的值［8］。RDF 数据存储时是以一条条语句存储，每次存储一条语句便执行插入，语句中三元组的主体S、属性P、客体O 代表着图形的两个顶点和一条边，存储时对顶点和边都建立索引，在查询时可以利用图的算法进行查找并定位到相应位置。通过记录这些RDF 数据文件的存储信息，能够便于后续查询，提高查询效率。

在具体实现中，可以将每个节点和边看做是一个Redis 哈希表，用一个键来表示这个哈希表，这个键可以是节点或边的ID，值则是哈希表中的键值对。在本文中，对于分区后的RDF子图建立相应索引，本文引入双重索引模式，主要分为块索引和块内索引，块内索引包含关键字列表、关键字表的映射、块内入口节点表和块内入口节点距离图四个数据，块索引主要包括块关键字列表和入口关键字表两个数据，这里将每个子图看作一个块，然后将每个子图索引存储到Redis 数据库中，这样就可以快速地定位到包含所需信息的节点，从而提高查询效率。

2.2 RDF数据分布式分割与存储方案

2.2.1 RDF图数据分割方案

（1）RDF图数据转化

在RDF 数据转化之前对数据集进行标准化和清洗。清洗是为了提高数据质量，消除数据中的重复、错误或者不一致等问题，以确保数据准确性和一致性。在RDF图数据分割过程中，如果数据没有进行清洗，可能会导致分割后的子图中存在重复的三元组，甚至出现不一致的情况，从而影响数据的正确性。RDF 数据模型虽然是一个图模型，但RDF 数据仍需要转换为图才能进行存储，这里需要进行映射，在使用RDF 数据中，Neo4j 提供了一个Neosemantics 的插件，它能够以无损的方式在Neo4j中存储RDF数据并使导入的RDF 随后可以在导出过程中不丢失任何三元组，也能按需将Neo4j的属性图数据导出为RDF。

（2）RDF图分割

分布式RDF 图分割通常是指将一个RDF 图数据集分割为多个子图，每个子图可以分配到不同的计算节点进行处理。这种分割是为了实现分布式RDF 处理，提高RDF 数据处理的性能和可扩展性。本文基于顶点的分割算法是一种将RDF 图数据分割成多个子图的方法，其中每个子图包含一组顶点及其相关的边。本文将使用贪心算法来确定如何将顶点分配到每个子图中，以最小化不同子图之间的边数。图1为该算法的流程图，其中包括RDF 图数据集的输入、顶点的排序、顶点的分配和子图的输出等步骤。

图1 RDF图分割流程

具体的RDF 图数据基于顶点的贪婪分割算法的伪代码描述如下：

当节点数量或者数据量发生变化时，重新执行该算法，重新分割子图并更新索引。算法通过贪心的思想，每次将度数和最大的顶点移到度数和最小的相邻子图中，以实现子图的负载均衡。同时，算法也采用了顶点分割算法中的相邻顶点分割策略，通过将相邻的顶点放在同一个子图中提高查询效率，并通过索引优化查询操作。同时，该算法还需要对节点数量和数据量的变化进行重新分割，以保证数据均衡分布和查询效率。

（3）RDF分区的确定

在分布式系统中，选择合适的分区数是非常重要的，它直接影响系统的可扩展性、性能和负载均衡等方面。一般会根据具体的业务需求和系统特点来确定。同时，随着数据量的增长和访问模式和数据特征等的变化，分区数也需要动态调整和优化。本文根据RDF 数据的分割效果来确定数据的分区数。主要根据割边率来区分分割图的质量［9-13］。

2.2.2 RDF图数据存储方案

RDF数据存储方案的流程如图2所示。具体数据分布式存储方案是将M个RDF 图数据子图通过分区策略放入K个分区，并记录相应redis索引数据的过程。分区策略是依据顶点的相似性进行分区分割。首先给出分区策略的分区计算函数Partition(vi)。选择权重最大的分区，如果有多个分区满足要求，则随机选择一个。P={P(1),P(2),…,P(k) }是当前所有分区的状态集。P(i)表示分区i的顶点和边的当前状态。|P(i)|表示分区i的顶点数量。对于图G=(V,E)，V={v1,v2,…,vn}表示顶点集，E={e1,e2,…,en}表示边集。e(vi)表示顶点vi的邻边。f(vi)表示顶点vi的邻顶点集。|e(vi) |表示邻边的个数。|f(vi) |表示相邻顶点的个数。

图2 RDF图存储流程

对于任意顶点的分割，首先要计算子图的大小，计算其包含的节点和边的数量，这将有助于确定每个子图需要多少计算资源。其次计算分区的大小来确定每个分区所需的资源。并据此计算每个分区的权重，然后选择一个分区，使每个分区的资源使用率尽可能接近。

假设分区的存储容量上限为C，计算每个分区中vi的相邻顶点的数量。Nji表示分区j中vi的相邻顶点个数，设置权重函数wj= 1 -。这个权重函数意味着它使用每个分区的剩余容量作为权重。Wj表示当前分区的权重，则Wj=Nij×wj。分区选择函数描述如下:

以下为RDF 图数据子图通过Redis 放入K个分区并记录相应的索引数据的伪代码描述：

输入阶段的分区K根据节点数确定，在RDF数据集存放到Neo4j数据库后，将其索引数据信息存放到Redis 数据库中，当进行数据查询时需要先在Redis中查找其位置，确定Neo4j数据库，然后再根据Neo4j的查询语法将查询语法利用文献［7］的方法转化为Cypher 语句，再到对应节点上进行查询，查询后返回相应的RDF三元组。

3 实验

3.1 实验环境和数据集

实验硬件方面，本文利用5台计算机进行实验，每台机器的配置为:2.93 GHz Intel（R）Core（TM）2 CPU，2 GB DDR4 内存。每台机器操作系统为centos6，索引数据数据库为Redis5.0.4，RDF 数据库为Neo4j3.5，JDK 版本为1.8，关系数据库为MySQL 5.5。系统各个模块用Java 实现。本文采用人工数据集WatDiv［10］创建的4 个数据集。具体信息见表1。

表1 RDF数据集

3.2 RDF数据分割的算法比较

实验主要验证本文提出的RDF 数据分割算法的性能以及存储方案的适用性。实验从两个方面来衡量数据分割算法的性能，一方面是分割算法的可行性，这里对比了不同数据量的分割算法的表现情况；另一方面是对分割算的性能进行对比，通过分割算法的运行时间分别对比基于加权图分割算法、基于最小算法并与分布式框架中常用的Hash分割方法做比较。

从表2可以看出，分割算法随数据量的增加依旧可以保持相当的运行速度，说明数据分割算法的有效性。算法运行时间在各数据集的运行情况比较也可以从表2中看出。相较于其他分割算法的分割时间，随着数据量的增加本文采用的数据分割算法的分割时间明显要少于其他的分割算法。

表2 分割算法在不同数据集执行时间单位：ms

3.3 RDF数据分区的选取

本文存储实验的分区数会根据分割图的割边率来确定具体的分区数。图3为选取不同的分区与割边率的关系图。本文根据文献［9］设置分区数为2，4，8，16，32，64。具体实验结果如图3所示。

图3 不同数据集下分区随割边率的变化曲线

从图3可以看出，在不同的数据集中分区数的选取也会影响查询的响应时间，在数据量较小时分区并没有明显的表现，但随着分区数量的增加，RDF 数据分割会变得越来越困难，而且从结果中也可以看出,分割子区数量越少，分割效果就越明显。但大致分区的数量在超过8之后就十分的明显。在后续实验中本文将采取分区数为8以下的分区策略。

3.4 Neo4j图数据库与MySQL数据库存储方案比较

本文存储实验从存储空间、数据查询两个方面进行比较。这里基于MySQL 设置了两个存储方案。方案一使用简单的三列方案，它只创建一个有三列的表，列分别对应RDF 数据的主题、谓词和对象；方案二使用完整的索引方案，它创建了六个表，每个表的结构都与简单的三列表相同，它向每个表添加不同类型的复合索引。例如，复合索引的顺序可以是：主语、谓语、宾语。复合索引的另一个顺序可以是：主语、宾语、谓词。因此，它总共有六种组合。基于图的存储方案一是先采用启发式贪婪策略，通过大图数据分割算法对RDF 图数据进行分割，然后采用Redis存储索引数据，再用Neo4j图数据库存储；方案二对图进行遍历，当节点到达分区给定容量后直接用Neo4j图数据库存储数据。

数据集在每个数据库中所消耗的存储空间见表3。其中GDB1 和GDB2 分别表示第一种和第二种图形数据库存储方案，RDB1 和RDB2 分别表示使用第一种和第二种存储方案的关系数据库。可以看出，RDB1 占用的存储空间最小，RDB2占用的存储空间是GDB的两倍左右。这是由于存储方案产生的索引的海量存储，RDF 数据量越大，区别就越明显。

表3 数据集存入数据库的大小单位：MB

对于每个数据集，设计了五个查询用于测试，从表4 的结果可以看出，GDB 和RDB2 的查询性能要远远优于RDB1。从表3 的实验结果可以看出，GDB方案消耗的存储空间是RDB2方案的两倍左右。并且从表4 也能看出，GDB1 明显匹配效率要强于GDB2，这也间接说明了图分割算法的有效性。因此，本文采用的基于图数据库的存储方法在综合方面是优于基于关系数据库的存储方法。

表4 在数据集上查询三元组匹配模式的平均时间单位：ms

4 结语

本文通过分析RDF 的特性以及现有的分布式图数据库，并选取Neo4j作为存储RDF数据的图数据库。根据对图数据库的发展和研究，提出一种基于图数据库的RDF 存储模式和数据分割算法，实现了RDF 数据的分布式存储，并通过实验验证了该分割算法性能以及对RDF 数据存储的可行性。但是对于RDF 数据的分割仍有改进的空间，接下来将深入研究RDF 图数据分割问题，对当前的存储模式以及后续的相关的查询问题进行实验的对比，进一步完善分布式的RDF存储框架。