图论是组合数学领域的一个分支，20世纪60年代末，随着计算机技术的产生和发展，组合数学，特别是图论理论得到了人们越来越多的关注，时至今日，人们面对的计算模型以及数据结构仍然在变得越来越复杂，由于图可以很方便的表示关系数据模型，因此图论中的许多与关系数据表示相关的理论及算法被广泛的应用到数据建模以及数据库设计领域中来。　　 在数据库设计中，图结构经常被用来存储以及表示关系数据，例如一些复杂的文档格式(XML文档)，蛋白质化学结构，大分子的化学式，向量图形等等，图论中的一些基本算法如最小生成树算法，最短路径算法，以及完美匹配算法也是许多最优调度问题的基础，最近的一些图论的成果已经被大量应用在图像处理，生物信息学，以及网络拓扑结构的研究中。　　 图的匹配是图数据库领域中近年来一个热点的研究问题，即对于一个包含大量图的集合，如何在这个集合中迅速找到满足给定查询要求的答案。相比于精确图查询，相似性查询是一个较为新颖且难度较大的问题。针对这个问题，本文对图数据库中的相似性查询方法以及数据库的索引方法进行了深入研究，提出了一种在大规模图数据库上建立索引以加快相似查询速度的高效方法。本文的主要工作总结如下：　　 (1)本文首先提出了一种新的衡量图相似性的标准，这种标准利用编辑距离的定义方式，很精确地表达了两个图之间的近似程度，相对于其他度量方式，编辑距离能好的反映两个图之间基于编辑操作的相似性，从而更方便地描述图和图之间的转化关系。　　 (2)针对以往方法只能在两个图上做编辑距离计算的不足，利用一种新的索引结构——k-邻接子图，提出了一种基于邻接子图比对的数据库倒排索引方法以避免时间和空间效率都很差的顺序查找。这种方法在编辑距离阈值相对不大的稀疏图数据库查询中有很好的过滤性能。　　 (3)由于邻接子图匹配在子图规模较大时的高复杂性，我们进一步提出将邻接子图以邻接树的形式表示的方法，通过放宽严格的同构匹配条件，并利用在图的邻接树上做伪同构匹配的方法，加快了数据库索引的构造以及提取在线查询的特征信息的速度。　　 (4)在邻接子树以及邻接子图索引过滤原理的基础上，本文设计了一种高效的相似性查询过滤算法，并将其与目前应用广泛的另外一种方法G-Index作了全面的比较。实验证明，k-邻接子图索引在编辑距离查询阈值相对不大的情况下过滤后所得到的候选集可以很好的趋近真实结果集，并且k-邻接子图索引的平均运行时间要远远小于G-Index索引。