给定有向无环图G,以及图上的任意两点u、v。回答u是否能够到达v的可达性查询是图的基本操作之一。随着现代化信息技术的快速发展,图被广泛应用于生物学、社交网络、语义网络、模式识别等领域,图的可达性查询是图数据管理中的热点问题之一。大量的学者投入精力改进可达性查询算法的效率。但是已存在的可达性查询算法,由于索引占用空间太大、查询效率低下等原因,在面对规模不断增长的数据图时,效率低、扩展性差。本文从以下几个方面对可达性查询问题进行研究。首先,分析现有可达性查询问题,发现已有算法构建索引时间长,索引占用空间大,查询效率低下。其次,本文提出线性时间复杂度的索引构建算法,在拓扑排序的过程中,为每个结点指定相应的索引标签,包含一对互逆的拓扑序号和该结点在生成树上的区间。提出压缩的索引表示方式,索引的空间复杂度为O(n)。提出基于孩子结点的区间扩展策略,对于要扩展的结点u,将其用于覆盖生成树上孩子的区间扩展到图中覆盖出邻居结点的区间,增强了回答肯定性可达查询的能力。再次,在进一步研究结点的拓扑号和区间的关系后,提出基于后代结点的区间扩展策略。对于将要扩展的结点u,把u的后代结点作为扩展目标,进行区间扩展。将其用于覆盖生成树上后代的区间扩展到图中覆盖可达结点的区间,增大了区间扩展的幅度、增强了区间过滤的能力。最后,在25个不同规模的真实数据集上,通过实验从不同角度对算法的性能进行深入比较和分析。实验结果验证了本文算法的高效性和扩展性。