基于图的RDF数据划分方法的研究与实现

史腾飞 杨梦伦

摘 要：RDF作为支持数据语义描述的统一标准的数据模型，在数据表示、数据交换及系统框架支撑方面提供了很好的技术支撑。为了满足异构数据的存储和处理需求，本文针对RDF数据管理及处理进行了研究，提出了基于图拆分的RDF数据存储及优化查询方法，改善RDF数据存储及查询效率。首先把原始RDF文本数据转换成RDF数据图，然后运用新的算法将数据图进行语义拆分，使RDF数据划分为耦合度较低的若干部分。通过对边割比率进行实验，将基于点权重的划分算法与METIS算法和哈希算法进行对比，分析三种方法的优缺点。

关键词：计算机应用；算法分析；METIS算法；图

随着计算机和网络技术的快速发展，信息系统的数量和规模越来越大，目前web数据的管理和处理面临着半结构化数据、数据量大、查询速度缓慢、检索效率低下、可扩展性、普适性等6大主要问题。这些数据的特点使异构数据整合成为一个挑战性的问题。RDF作为支持数据语义描述的一种统一标准的数据模型，在数据表示、数据交换及系统框架支撑方面提供了很好的技术支撑。如何对分布式存储的数据进行较好地划分是目前需要解决的重要问题。

因此，本文主要以提高使用SPARQL查询语句在RDF大数据中检索效率为主要目标，依据METIS算法核心思想，提出了一种新的图划分算法方案——基于图的RDF数据存储及查询方法，该方法能改善RDF数据存储及查询效率，为数据的处理提供更好的系统和方法上的支撑。

相关技术

数据形式——RDF

资源描述框架（RDF）作为支持数据语义描述的一种统一标准的数据模型，在数据表示、数据交换及系统框架支撑方面提供了很好的技术支撑。RDF使用一个图数据模型，其中不同实体是图中的顶点，它们之间的关系用边来表示。关于每个实体的信息用从顶点到该实体发出的有向边表示，其中边是连接顶点到其他实体的，或者到特殊的“文字的”顶点，该顶点包括对于该实体的一个特殊的属性值。

图1显示一个RDF示例图。例如，图中的边表示实体“教师0”是“教授类型”类型的，属于“院系0”，教了“课程1”。在这个图中，每一个和“教师0”相连的实体能有它们自己的连接集；例如，通过“类型”关系，“教师0”被显示和“教授”实体相连。大部分RDF存储是将RDF图表示为一个三元组表，表中有一个针对RDF图的边的三元组。三元组使用<主语，谓语，宾语>的形式，其中主语是从边发出的实体，谓词是边的标签，宾语是边的另一端上的实体或文字的名称。

0.1图的数据结构图是一种复杂的非线性结构。

0.2在处理RDF三元组数据时，论文采用的方法是将RDF三元组数据按照图的形式进行划分，在数据结构中，常用的方法是邻接矩阵、邻接表和十字链表三种存储形式。本文采用的是邻接表的形式。伪代码如下表1。

伪代码中将主语和宾语用节点表示，谓语用边表示。针对每个点，根据点的ID区分，ID采用整数表示，在图划分程序中并不存储每个点的语义。由于采用的是超图的思想，即每一节点都是由若干点组成，所以在节点中记录了当前节点所包含点的个数，这主要是为计算权重所服务的。节点的最后一个信息是当前的节点被哪个节点所包含，在初始化的时候这个值是当前节点的ID，即说明当前节点是被自己所包含，如果这个值在计算最后仍然是自己的ID，说明这个节点只包含自己一个点。将谓语抽象成边，只需要知道哪个节点和哪个节点有关系即可，所以在图划分程序中只存储自己的ID和点之间的关系，对于边的语义信息和点的类似。

1.基于超图模型的RDF数据划分

本篇论文中采用的是METIS算法的思想，该算法是由明尼苏达大学计算机科学与信息技术工程系开发并且免费发布的。METIS的实现算法是基于多级图形分割范例。它可以迅速产生高质量的分割。在多层次模式上，总共有三个阶段组成：图粗糙化，图分割，图还原。

1.1 图粗糙化

METIS算法中的图粗糙化是最重要的一个步骤，这个步骤是将图中的节点根据一定的算法合并成一个新的节点，这样会将图中总节点数降低，最后得到一个比较小的图形。在粗糙化阶段，需要将大图简化成较小的图，在简化的过程中，首先将悬挂点与之相关联的点进行合并，对于合并后的网图，根据每个点的密集程度进行合并，采用合并密集程度最大点的所有关联点。

在一个图中，度数为1的顶点称为悬挂顶点。与它关联的边称为悬挂边。在将悬挂点进行化简的过程中，已经将简单图变为超图。在这个图中找到密集度最大的点进行化简，并迭代化简。在将图进行粗糙化的过程中，需要牵扯到计算点的权重这个问题。这是因为在进行图的粗糙化的过程中，需要将节点进行合并，由单个点聚集成超点，这样才能将超大的图粗糙化，简化成比较简单的图进行接下来的图分割步骤。在对点的权重计算过程中，主要依据两个原则：

（1）一个点与其他点连接的越多，说明这些点越紧密，在未来查询过程中越有可能同时被查询到，需要将这些点存储在一个存储节点中。所以，对于这种情况，应该将这些点进行合并，成为超点。

（2）对于语义相同的点应该尽可能的进行合并，成为同一个超点，并且存储在一个存储节点中。这些节点是同一类型的，在未来的查询过程中很有可能同时被查询到。

依据以上两点，给出计算点的权重公式如下：

1.2 图分割

在图分割之前，需要确定参数k（k>=1且为整数），k表示将大图化简为k个部分。用图粗糙化的方法进行化简至到超图中节点数等于k或者是到超图中节点数小于k之前的一步。如果可以化简为k个节点，那么就把k个节点划分为k个部分。若不能正好化简为k个部分，则在节点数小于k之前的一步停止。伪代码如下表2：

在图划分的整体算法中，主要通过while循环，一步一步将图粗糙化，通过节点的合并，最终达到划分目标。在两个主要步骤中，收缩函数主要负责节点的合并，每次在收缩时，通过循环遍历图中的所有点找到权重最大的节点maxVertex，将这个节点相关的周围所有节点合并产生新的超点，在合并的过程中处理这些点的关系和这些点间边的关系，为接下来图还原的过程做好准备。在程序中采用的方法是对处理每个与权重最大的节点有关联的节点relateVertex，首先修改关联的节点的信息，使之成为最大权重节点（超点）的成员，然后删除关联的节点，最后删除原始权重最大的节点和关联的节点边的信息，计算权重函数是对上一步中有变动的节点信息的更新，主要更新新节点的权重、包含点数等信息。对于权重依据的就是前一节所述的方法。以下分别是Contract函数与CalculateHeavy函数的伪代码：

2.实验及分析

本节根据前文提出的图拆分算法和经典的METIS算法以及哈希算法进行对比测试，分析各自算法的优缺点。由于METIS提供一组独立的命令行程序，用于计算分割，而且也提供了应用程序编程接口（API），它可以通过C/C+ +或FORTRAN等程序来调用。为了有较好的比较性，论文中的图分割算法也是采用C++编写。下面的METIS算法采用了标准单机METIS图划分算法。

2.1 实验数据集

测试RDF数据的benchmark有很多种，LUBM是其中一种主流的测试样例集。基准的目的是在一个大的数据集中，通过提交到一个单一的现实本体进行查询来评估系统的性能。它由一个大学领域本体，可定制和可重复的合成数据，一组测试查询和几个性能指标组成。通过LUBM提供的数据产生器，实验建立了四组测试数据集，下表5显示了具体数据集：

根据资料，METIS算法比较适合于百万级别的数据量，因此在测试数据集的选择上都在百万级别，以便可以区分这三种算法的效果。在之前文章中介绍了METIS算法的输入是一个邻接矩阵图，因此系统的输入方式都是相同的邻接矩阵图格式的原始数据。

2.2 实验结果与分析

对于4个不同大小的数据集，采用三种不同的算法做对比实验，分别测试了划分4、8、16等三种不同数量区域的实验。实验对比的主要影响因素是边割比率（通信代价）。边割比率指的是在三元组中，主语和宾语被划分在两个不同的节点个数与总的三元组个数的比值，也就是边割数/总边数。用这个比值来描述通信的代价，这个比值越大，说明系统在查询时，两个节点的通信频率和概率就越高，反之则说明概率越低。

实验中除了对比METIS算法和自己提出的算法，还与哈希算法（采用主语ID取模）进行比较。目的是因为哈希算法可以较为平均的将数据集进行划分，可以通过这个算法作为参考。

2.3 实验结论

通过上面实验和分析，可以看到，本文所提出的图划分算法与METIS和哈希算法在边割比率（通信代价）方面有各自的优势与劣势。虽然METIS算法和本文的算法在主要思想上是类似的，但是由于METIS算法在粗糙化过程中采用的是最大边覆盖算法，而本文在粗糙化过程中采用的是超图的思想，因此在两个对比方面，本文提出的图划分算法都与其他两种算法有较大的不同。由于哈希算法均匀划分数据，因此使得在边割比率方面具有较高的数值，而本文和METIS算法都相对于哈希算法的结果较好，因此在通信代价方面能得到较好的效果，虽然本文的算法并不是最好的，但和METIS算法相差不大。

3 结论

本文介绍了基于METIS算法的整体思想，采用超图的方法，对RDF数据图进行划分的理论，通过对RDF数据图的粗糙化、基于点的权重划分数据、还原RDF数据图三个主要步骤的介绍，详细的说明了如何将大量RDF数据一步一步划分并存储在集群中，为整个系统提供底层数据支持。在本章最后将基于点权重的划分算法与METIS算法和哈希算法通过边割比率方面进行实验对比，分析了三种方法的优缺点。

参考文献

[1]Kolas D， Emmons I， Dean M， Efficient Linked-List RDF Indexing in Parliament. In the Proceedings of the Scalable Semantic Web （SSWS） Workshop of ISWC， 2009.

[2]Li P， Zeng Y， Kotoulas S， et al. The Quest for Parallel Reasoning on the Semantic Web， Lecture Notes in Computer Science， 2009， 5820：430-441.

[3]Hendler J， Web 3.0： The Dawn of Semantic Search[J]. Computer， 2010，43（1）：77-80.

[4]L Zou， J Mo， L Chen， et al. gStore： answering SPARQL queries via subgraph matching. PVLDB， 2011， 4（8）：482-493.

[5]J Huang， DJ Abadi， K Ren. Scalable SPARQL Querying of Large RDF Graphs.

[6】曹佳硕. 基于RDF的云制造资源数据存储及检索方法的研究与实现[D]. 北京：北京交通大学，2012.

[7]杨梦伦. 基于图的RDF数据存储及查询方法的研究与实现[D]. 北京：北京交通大学，2015.

作者简介

史腾飞（1992-），男，汉族，硕士研究生，研究方向：云计算。