【作者】 王楠；

【导师】 杨晓春；

【作者基本信息】 东北大学 ， 计算机应用技术， 2013， 硕士

【摘要】 图作为一种复杂的数据结构被应用到各个领域中,如分子化学和社会网络领域,图查询作为图数据库管理的一项重要课题在近些年来受到国内外学者的广泛关注。图查询问题是在图数据库中找到满足条件的数据图集合,其中分为子图查询和超图查询。随着数据量的日益增加,图查询在为用户提供更强大更全面的功能的同时也使得查询处理过程及索引构建更加复杂。如何高效地支持静态图数据和动态图数据上的图查询问题至关重要。目前,已经有许多工作致力于解决图查询问题。其中大部分工作采用“过滤—验证”框架处理图查询问题,主要集中精力于建立索引等数据结构来提前过滤掉部分非结果集,再将查询图与候选集合中的图逐个做子图同构检测,最终得到结果集合。现有解决图查询问题的方法大致分为基于特征过滤和不基于特征过滤的,这些方法都是基于静态图数据的,而在现实应用中大部分图数据是频繁更新的,现有方法对于动态图数据上的图查询问题代价较高。图查询问题本身就是NPC问题,在动态图数据上图查询问题就变得更加困难。针对上述问题本文提出了支持动态图数据的子图查询方法和支持增量图数据的超图查询方法。支持动态图数据的子图查询方法首先构造出每张图的拓扑层次序列作为索引,再根据序列间的匹配关系过滤出候选集合,最后用图同构算法验证候选集中的图最终得到结果集合。该方法的索引构造简单且体积小,在图数据库更新后无需重构索引,不仅支持动态图数据上的子图查询,在静态图数据上也表现出良好的性能。支持增量图数据的超图查询方法基于“分治法”思想,将数据图分解成直至单个顶点的子图,然后从单个顶点的子图开始求它到查询图的子图同构,直到求出数据图到查询图的子图同构结果。该方法的优点是在数据图增加时只需将新加入的数据图进行分解即可,不必重新计算,时问复杂度不随数据图的增加而呈线性增长,节省了时间和空间代价。最后,本文方法在真实数据集上进行了大量的实验。通过实验结果本身及对实验结果的分析证明了本文提出的方法都能够高效地解决动态图数据和增量图数据上的图查询问题。更多还原

【Abstract】 Graph is applied to various fields as a kind of complex data structure, such as molecular chemistry and social networks. Graph query has attracted wide attention of scholars as an important topic of graph database management in recent years. Graph query problem is to find the qualified datagraph set from graph database, is divided into subgraph query and supergraph query. With the increasing amount of data, graph query provides users with more powerful and more comprehensive functions on the one hand. On the other hand, it makes the query process and indexing more complex. Therefore, it is crucial to make graph query efficiently on both static and dynamic graph data.At present, there is a lot of work committed to solve the problem of graph query. Most of the work use the "Filter-Verification" framework to handle graph query, mainly focus on constructing index and other data structures to filter out some non-result set in advance. Then query graph does subgraph isomorphism testing with graphs in candidate set individually. Ultimately, the method gets the result set. Existing methods can be divided into feature-based filtering and non-feature-based filtering, are all based on static datagraph. Nevertheless, in real life most of the graph data are frequently updated, and the cost of existing methods for frequently updated graph data is higher. Graph query is a NP complete problem, while frequently updated graph queries will become more difficult.In the light of the above problem this paper proposes the method of subgraph queries over dynamic graph data and the method of supergraph queries over incremental graph data. The first method constructs every graph’s topological hierarchical sequence as index firstly, then filters out the candidate set according to the sequence matching relationship, and finally uses graph isomorphism algorithm to verify the candidate set then we can get 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. The second method is based on the "Divide and Conquer" thought, decompose datagraph until the datagraph has only one vertex, then judge whether it is a subgraph to the query graph from one vertex graph to the whole datagraph. The advantage is that when datagraphs increase the method only need to "decompose the newly added datagraphs and dosen’t need to query again.Time complexity doesn’t have a linear growth with the datagraphs increasing. Generally the method saves time and space cost.Finally, many experiments on real data sets are made. Experimental results and analysis of experimental results prove that the proposed methods are capable of solving graph query problems on both static and dynamic graph data efficiently.更多还原