图结构数据有助于数据的相关性挖掘,近年来使用图结构来表示大型数据变得越来越流行,其中资源描述框架（RDF）系统逐渐被广泛使用在公共知识库和网页内容的存储上,并给用户提供使用SPARQL语言进行查询的服务。大量的RDF图查询系统被研究界和工业界提出来,这些RDF系统致力于提供给用户在大型RDF数据集中进行高并发度和低延迟的查询服务。查询优化器作为查询系统必不可少的组成部分成为提升查询整体性能的关键,新软件和硬件优化方法的出现给查询优化器的设计和实现提出了新的挑战。查询优化器由三部分组成:基数估计模块、开销模型模块和遍历算法模块。这三部分共同协作对外提供查询优化服务,每一部分都对查询优化的效果和性能都有着至关重要的影响。本文通过数据测试和分析发现传统的基于三元组连接的查询优化器存在许多问题:在基数估计方面,采用基于两元谓词关系的方法进行基数估计,并用两元谓词选择率的乘积来代替多元谓词间的依赖,该基数估计方法也无法适用于新型的基于图探索的系统;在开销模型方面,由于新型查询系统Wukong^[1]的出现,查询语义的不同导致成熟的开销模型无法直接移植和复用。针对这些问题,本文首先设计和实现了基于全历史的图探索系统Wukong+Tr,使优化器更加贴合图探索的查询场景,估计准确度和查询性能得到了大幅度提升。本文进一步通过测试来分析Wukong+Tr的各个模块,发现基于两元谓词关系的查询优化器仍然存在一些问题:在基数估计方面,由于忽略了多元谓词间的依赖导致估计的大量错误;在开销模型方面,图探索的语义需要一个更细粒度的开销模型;在遍历算法方面,由于硬件和软件优化的结合使得查询性能大幅度提升,小型查询中查询优化时间会成为瓶颈。针对上述问题,本文提出了基于类型的查询优化方法Wukong+P,这是在Wukong+Tr上的进一步优化。本文基于相同类型的点通常含有相同的谓词组合这一观察,围绕类型来进行统计数据和基数估计,通过将多元谓词依赖嵌入类型中的做法,使得基数估计能够考虑多元谓词之间的依赖关系,同时充分考虑了图探索的语义,采用了细粒度的开销模型,针对查询优化时间的问题,采用了有区分的查询优化策略,解决了传统优化器中存在的问题。通过测试结果发现,Wukong+P和最先进的查询优化器相比,在基数估计方面提升了2个数量级的的准确度;在开销模型方面,估计开销和真实时间的趋势基本吻合;在查询优化时间方面,将小型查询的优化时间降低至0.01毫秒;在整体性能方面,单个查询的性能最高提升2.32倍,选择的查询计划和最优查询计划的平均性能差被缩小到2%。