中文摘要：

图模型具有强大的表达能力,被广泛用于各种应用领域的数据建模.如何在大规模图数据库中进行高效子图包含查询是当前的研究难点之一.由于子图同构是一个NP完全问题,在现有的子图包含查询算法中,基于图特征的索引技术被广泛用来提高查询处理性能,但是这些索引结构的维护代价较高.针对有向无环图提出了一种基于拓扑序列的子图包含查询算法,首先根据图中节点的偏序关系将有向图分层拓扑为一个序列,然后利用序列间的匹配关系过滤出候选结果集,最后通过子图同构检测验证得到最终结果集.相关性能测试表明,该算法无需构造复杂的索引结构,便于图数据库的动态维护,在有向无环图在线查询性能上表现出色.

英文摘要：

图模型具有强大的表达能力,被广泛用于各种应用领域的数据建模.如何在大规模图数据库中进行高效子图包含查询是当前的研究难点之一.由于子图同构是一个NP完全问题,在现有的子图包含查询算法中,基于图特征的索引技术被广泛用来提高查询处理性能,但是这些索引结构的维护代价较高.针对有向无环图提出了一种基于拓扑序列的子图包含查询算法,首先根据图中节点的偏序关系将有向图分层拓扑为一个序列,然后利用序列间的匹配关系过滤出候选结果集,最后通过子图同构检测验证得到最终结果集.相关性能测试表明,该算法无需构造复杂的索引结构,便于图数据库的动态维护,在有向无环图在线查询性能上表现出色.