图的可达性查询处理是图数据管理中的热点问题之一,可以应用到现实生活中的很多领域,包括语义网、互联网、电信网、无线传感网络及生物信息网等。这些网络数据具有量大且复杂程度高的特点,如何快速回答可达性查询目前仍是极具挑战性的问题。本文从以下几个方面对可达性查询处理方法进行研究,具体研究内容如下。首先,研究发现现有可达性查询算法存在索引规模大、索引时间长、查询处理时间长以及不能高效处理可达查询比例增大的问题,本文针对这些问题进行研究。其次,提出最优生成树的概念,减小可达查询的搜索空间,并证明其在获取可达信息方面相对于其他生成树的最优性。提出时间和空间均为线性的索引构建算法,提出基于深度优先的拓扑排序顺序及其逆序组成的互逆拓扑顺序,减小不可达查询的搜索空间。再次,针对规约图具有无冗余边无等价结点且可达信息不变的特点,提出了基于内嵌树的可达性查询算法。该算法在互逆拓扑标签的基础上,扩展出双向互逆拓扑标签,以减小不可达查询的搜索空间。然后通过分析内嵌树中顶点标签的性质,根据顶点的双向互逆拓扑序号及上下根信息,加快查询处理速度。最后,通过在20个真实数据集上进行实验,对本文方法和已有方法进行了比较和分析,实验结果验证了本文提出方法的高效性和可扩展性。