作为一种通用的数据结构，图被广泛用来建模和表示多种复杂的结构化数据。近年来，对累积的大量图数据(即图数据库)的管理受到研究者的关注。子图查询是一种具有很强现实意义的查询类型，主要包括精确子图查询和相似性子图查询。具体来说，给定图数据库D，查询图q，精确子图查询返回集合{g∈D|ョg’∈g，s．t g’与q是同构图)，相似子图查询返回集合{g∈D|ョg’∈g，s．tg’与q是相似图)。本文针对上述两种子图查询给出有效解决方法。对于精确子图查询，本文采用过滤验证机制，从数据库中提取出的特定频繁子图称为特征，过滤器即是由特征压缩而成的一棵索引树，由于特征之间共享诱导子图，过滤阶段多个特征所共享的诱导子图只与查询图做一次子图同构检测，所以过滤效率明显优于现有方法。考虑到提取特征开销较大，本文又提出一种高效的提取特征方法，该方法可以保证提取出的特征的过滤效果。理论分析与实验验证均表明我们提出方法优于现有方法。对于相似性子图查询，相似图定义为满足拓扑同构的两图之间编辑距离小于某一给定域值，现有方法多数采用过滤验证框架，在此框架下，这些工作主要集中精力于建立有效索引来提高过滤效果上，却很少考虑设计高效的验证方法，这些方法在验证查询图q与数据库中图g是否满足相似性子图查询要求时均需枚举g中的与q拓扑同构的子图，直至找到一个与q距离小于域值的子图为止。枚举拓扑子图计算代价巨大。本文提出方法无需枚举子图，而是将问题转化到高效计算两图编辑距离上来．通过分析问题具有的特殊性质，设计一种巧妙的计算编辑距离的启发式方法，来显著提高验证阶段的效率。另外，考虑到计算编辑距离是一个NP难问题，我们又设计一个线性规划方法来在多项式时间内快速计算编辑距离的下界，相似性子图查询算法利用此下界提前过虑部分非结果集。在真实和人造合成两类数据集上的大量实验结果表明，提出方法显著优于现有方法。