RDF Subgraph Matching by Means of Star Decomposition
RDF Subgraph Matching by Means of Star Decomposition
复制标题
通过星分解的RDF子图匹配
DOI：
10.53106/160792642022122307015
复制
发表时间：
2022-12
影响因子：
1.6
通讯作者：
Ying Pan
中科院分区：
文献类型：
--
作者：
Mingyan Wang;Qingrong Huang;Nan Wu;Ying Pan
随着网络的不断发展，RDF数据规模越来越大。面对大规模的RDF数据处理，传统的数据库查询方法已经无法满足需求。由于子图匹配的特性有限，现有的大多数算法在查询过程中往往存在重复遍历多个子图的现象，导致中间结果集大量，查询效率低下。要解决的核心问题是如何高效地匹配子图。为了提高海量RDF数据图中RDF子图的查询效率，解决RDF子图查询过程中部分图重复计算的问题，提出一种基于星型分解的RDF子图查询算法。该算法使用图结构将RDF子图分解为星形，并使用自定义的节点成本模型来计算星形子图的查询顺序。通过分解，减少了子图之间的通信量，降低了查询处理的通信成本。而且，利用查询顺序进行RDF子图匹配可以有效减少中间结果集的生成，加快子图匹配的效率。在此基础上，在两个不同的数据集上对所提出的算法和其他几种广泛使用的算法的性能进行了比较和分析。实验表明，该算法在数据库重建、内存大小、执行效率等方面具有较好的优势。
With the continuous development of the network, the scale of RDF data is becoming larger and larger. In the face of large-scale RDF data processing, the traditional database query method has been unable to meet the needs. Due to the limited characteristics of subgraph matching, most existing algorithms often have the phenomenon that many subgraphs are repeatedly traversed during the query process, resulting in a large number of intermediate result sets and low query efficiency. The core problem to be solved is how to efficiently match subgraphs. In order to improve the query efficiency of RDF subgraphs in massive RDF data graphs and solve the problem of repeated calculation of some graphs in the query process of RDF subgraphs, an RDF subgraph query algorithm based on star decomposition is proposed in this paper. The algorithm uses graph structure to decompose RDF subgraphs into stars and uses a custom node cost model to calculate the query order of the star subgraphs. By decomposing, the amount of communication among subgraphs is reduced, and the communication cost for query processing is lowered. Moreover, utilizing the query order for RDF subgraph matching can effectively reduce the generation of intermediate result sets and accelerate the efficiency of subgraph matching. On this basis, the performances of the proposed algorithm and several other widely used algorithms are compared and analyzed on two different datasets. Experiments show that the proposed algorithm has better advantages in database recreation, memory size, and execution efficiency.