在数据库领域中,越来越多的数据通过图结构的方式进行存储,比如社交网络、生物信息学以及XML数据等。针对这些图数据的查询,很多时候需要更强大的计算机资源进行处理。为解决该问题,比较经济实用的方法是将这些数据外包给一个第三方的服务提供商(Service Provider, SP),让它去为我们提供查询服务。然而,SP并不是一直可以值得信赖,它可能对外包到它上面的数据比较感兴趣,以获得商业利益。除此之外,数据拥有者(Data Owner)不希望他的数据被不信任的人获取,同时查询者也不希望他的查询内容被他人得知。可达性查询作为数据库领域一个最基础的问题,本文针对可达性查询过程中可能产生的隐私问题,提出了图数据上可达性查询的隐私保护方法。我们的隐私保护目标主要包括：客户端查询信息和图数据结构信息。针对我们提出的隐私保护目标,我们在基于传统的2-hop索引方法上,根据图数据不同的稀疏性质,提出了pp-2-hop和·ppm-2-hop两种索引方法。在这两种索引方法中,我们对原始的2-hop索引通过不同的添加人工代理中心点策略,使得对于任何的可达性查询,其查询结果大小一致,进而SP无法从相同大小的查询结果中获取关于查询的信息。同时,我们通过对索引进行加密,使得所有的可达性查询在密文域中进行,进一步阻止SP对索引内容进行推理。本文对两种索引算法分别在基于密文攻击和基于集合大小的攻击模式下进行安全性分析。最后,分别对两种索引算法在合成数据集和真实数据集上进行实验研究。