图形是一种描述性很强的数据结构。通过加以标记的顶点和边，图形既可以深入描述一组实体间的关系，也可以直观地描述这些关系间的属性。在复杂结构数据建模方面，如化合物分子结构，蛋白质基因结构，电路结构，Web和XML文档等，图形起着很重要的作用，图形数据库也由此得到广泛的关注和应用。在与图形相关的应用中，存在一个共同且关键的问题，即如何有效地处理图形查询和检索问题。通常，应用是否成功直接依赖于查询处理系统的有效性。　　 本文主要讨论图形数据库的Top-K查询问题，即给定一个查询图，返回数据库中与其最相似的K个图形。将查询图与数据库中的图逐个地进行两两比较是非常耗时的。一般地图形数据库的查询主要分为查询过滤和查询验证两个阶段。在过滤阶段中，数据库中不符合条件的图应尽可能多地被过滤，并生成一个候选图形集合。在查询验证阶段，进一步筛除掉不满足条件的图形，获得最终结果。在过滤阶段，关注如何对图形建立索引以减小候选图形集合。在验证阶段，一般使用子图同构技术进行验证。　　 针对图形数据库查询处理和优化需求，重点分析和研究了图形数据库的索引技术和图形同构技术，在上述的两个技术中均使用DFS编码对图进行序列化。在此基础上，进一步研究了图形数据库的Top-K查询。　　 在图形数据库的索引技术方面，提出基于频繁语义结构的图形数据库的索引方法，称为GSIndex。GSIndex使用GString技术来表示图形，把图形表示成由语义信息的裂片组成的串，然后找出频繁的具语义信息的裂片，用DFS编码对这些裂片进行序列化，在此基础上对这些裂片构造索引树。由这些有语义的裂片构造的索引更加贴近实际的应用。　　 在图形同构方面，通过深入分析经典图形同构的算法，根据最小DFS编码的性质，即两个图同构当且仅当它们的最小DFS编码相同，提出了基于DFS编码的子图同构算法。　　 在Top-K查询方面，根据图形相似性的度量标准，提出基于GSIndex技术的Top-K查询方法，并论述了两种新的查询方式：析取查询和合取查询。这两种查询方式可以根据用户的需要，按照部分特定的基本子图及它们间的逻辑组合关系进行查询。　　 实验结果表明，以上技术和方法可有效提高过滤率和验证的准确性，提高查询性能。