支持动态图数据的子图查询方法

Subgraph Queries over Dynamic Graph Data

近年来,子图查询作为图数据库管理的一项重要课题受到国内外学者的广泛关注。在现实应用中大部分图数据是频繁更新的,而现有方法对图数据的频繁更新的维护代价较高。子图查询本身就是NP完全问题,在动态图数据上子图查询问题就变得更加困难。针对上述问题,提出了支持动态图数据的子图查询方法。该方法首先构造出每张图的拓扑层次序列作为索引,在序列中加入标号以便数据更新后对索引进行维护,再根据序列间的匹配关系过滤出候选集合,最后采用图同构算法验证候选集中的图,最终得到结果集合。该方法的索引构造简单且体积小,并且在图数据库更新后无需重构索引,不仅支持动态图数据上的子图查询,在静态图数据上也表现出良好的性能。

Subgraph query has attracted wide attention of scholars as an important topic of graph database manage-ment in recent years. In real life most of the graph data are frequently updated, and maintenance cost of the existing methods for frequently updated graph data is higher. Subgraph query is a NP complete problem, while frequently updated subgraph queries will become more difficult. In light of the above problem, this paper proposes the method of subgraph queries over dynamic graph data. Firstly the method constructs every graph’s topological hierarchical sequence as index, then filters out the candidate set according to the sequence matching relationship, and finally uses graph isomorphism algorithm to verify the candidate set and gets final result set. The index is constructed easily and its size is small. The method doesn’t need to rebuild index after database updating, and it not only supports sub-graph queries on dynamic graph data, but also shows good performance on static graph data.