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