关键词: 子图查询, 动态图数据, 拓扑序列, 图索引

Abstract: Subgraph query has attracted wide attention of scholars as an important topic of graph database management 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 subgraph queries on dynamic graph data, but also shows good performance on static graph data.

Key words: subgraph query, dynamic graph data, topological sequence, graph index