近年来,计算机应用正以各种方式越来越快地渗透到各个领域之中。其中以数据库,尤其是关系数据库的应用最为广泛。关系数据库以集合代数为基础,利用关系模型来建立问题和领域结构模型。然而这种建模方式有一定的局限性,难以直接且深入的描述现实世界对象间复杂联系。图形是一种描述性很强的数据结构。通过加以标记的顶点和边,图形既可以深入描述一组实体间的关系,也可以直观地描述这些关系间的属性。在复杂结构数据建模方面,如化合物分子结构,蛋白质基因结构,电路结构,Web和XML文档等,图形起着很重要的作用,图形数据库也由此得到广泛的关注及应用。 随着图形数据库越来越大,对于快速有效图形查询搜索系统的需要也越来越迫切。现有的图形搜索方法是将数据库中的频繁结构碎片作为索引项,根据各个图形所包含的结构碎片边的特性做高维索引,查询时把图形进行分解,在索引中查找包含所有碎片的图形。但是图形频繁结构碎片需由图形数据库的挖掘获得,频繁结构边数的不同使得每个索引项的维数也不确定,而且查询图形难以实现最优分解。 GString技术是目前图形表示的最新方法,该方法给出了三种基本结构及语法规则来描述基本子图,进而通过基本子图的组合表示图形。本文以此为基础,构建了一个图形修改空间,通过不同的权值分配,把每个基本子图顶点,分支和边的修改作为其在图形修改空间中各方向的位移。在此修改空间基础上,本文为属于相同类型的基本子图建立三维R-tree索引,并对R-tree索引的相关算法进行修改,以满足对图形修改的特定需要。图形修改空间的实例和模拟试验结果均表明本文所提出的方法避免了最优分解计算,同时有效降低了索引的复杂性,提高了查询性能。此外在基本子图Top-K查询基础上,本文运用模糊查询思想提出了两种新的查询方式：合取查询和析取查询,给出了查询算法,并证明了其正确性。与以往单纯的子图查询不同,这两种方式可以根据目标结果的部分结构和结构间的逻辑组合关系进行查询,从而满足用户的不同需求。