随着数据库技术的广泛应用，数据管理的对象从非结构化数据向结构化数据延伸。依赖于图数据结构强大的表述能力，一些新兴数据库如XML文档数据库、社会关系网、化合物分子数据库以及蛋白质基因结构匹配数据库等都采用图数据结构建模。 另一方面，作为信息获取的重要工具，查询操作是数据库领域经久不衰的研究课题之一。基于图数据结构的数据库，不仅引入了新的数据模型，同时由于图结构自身的复杂性，给查询问题带来了新的挑战。 图数据库上的查询问题指的是查找并验证查询图在图数据库上的所有出现。回答该查询问题通常可以分为两个阶段，即查询过滤阶段与查询验证阶段。不同于相关工作聚焦于查询过滤阶段，本文把更多的注意力放在查询验证阶段，通过对数据库的索引以及关键信息统计，加速该阶段的性能。本文的研究成果主要有： (1)提出了查询验证时间开销的度量模型。本文从基本的子图匹配算法入手，继而研究了其搜索空间，并给出了形式化的度量模型。在该度量模型的指导下，发现查询验证阶段的性能瓶颈。同时，该度量模型也给本文提出的查询验证阶段的加速技术提供了理论依据。 (2)发现了调整查询图的边序可以加速查询验证过程。提出了边序重排的启发式算法框架，并分别给出了基于概率模型以及基于木桶模型的启发式算法eSI_prob以及eSI_barrel。实验表明，两个算法都能够有效的提高查询验证阶段的性能。与此同时，eSI_prob和eSI_barrel使用的统计信息，与图数据库本身比较，只占用了很小的存储空间。 (3)发现了索引子图片段在数据库中的出现可以加速查询验证过程。提出了索引高度自同构的频繁子图或索引分布距离较远的频繁子图两种索引项选择方案，并使用有向无环图组织索引项的索引，形成了基于片段索引的子图查询方案pSI_auto以及pSI_cluster。实验表明，两个算法均可以进一步的提高子图验证的性能。当图数据库中的自同构结构频繁出现时，pSI_auto效果更为显著。同时，本文讨论了当数据库执行插入、删除与修改时，索引的更新操作，并提出了索引自动重建策略。 (4)通过集成查询过滤算法c-tree和GIndex，形成了子图查询系统的原型。实验证明，本文研究的查询验证加速技术与相关工作研究的查询过滤技术可以低耦合的结合使用，互为补充。