数十年来,随着物联网、社交网络等领域的发展,我们将面对日益增长的海量网状拓扑数据集,原本成熟健全的关系型数据库在处理这类数据时做的却并不好,主要原因是关系模型会造成大量表连接的操作从而带来极大的运算代价,而大多数No SQL数据库,无论是键值数据库、文档数据库还是列式数据库,它们都很难用于关联数据和图,因此图数据库由此而生。图数据库拥抱联系,是存储和处理这类数据的最优选择。本文针对图数据库的查询引擎进行研究,针对图数据库Neo4j的Cypher查询语言,基于成熟的关系型数据库的一些查询优化技术设计并实现了图数据库的查询编译系统,并对于查询编译器的正确性测试提出了一个具有创新性和可行性的设计。本文主要工作要点如下:1.基于Cypher查询语言设计并实现了图数据库的查询编译器,查询优化部分采用基于代价估计的模型,在代价估计中针对特定的事务机制引入反映存储引擎中节点和边并发访问的参数,从而进一步优化计划执行的性能。2.设计并实现基于Cypher语句的随机语句生成器,采用基于Cypher文法产生式的随机覆盖算法来生成一系列随机Cypher语句。3.设计并实现了验证执行计划正确性的伪执行算法,在不提供底层计算和存储引擎的情况下也能对查询引擎的结果进行正确性验证。伪执行算法包括两个执行阶段,一是检查执行计划中每个算子是否可以执行并根据算子中的信息进一步更新执行阶段的查询图和过滤树作为执行结果。第二是与原Cypher语句中的查询图和过滤树进行对比,根据对比结果来判断当前执行计划是否可以正确执行。本文提出的针对图查询编译器的测试方法在实际使用中帮助定位了许多在查询编译阶段出现的错误,简化了图数据库内核开发的测试难度,在工程实践中具有很强的实用价值。