可达性查询处理是图数据管理与分析的基本操作之一,一直以来都是研究者广泛关注的热点问题。现有方法通常使用树区间或者基于部分结点的2hop标签来加速查询处理的速度。实际应用中,这种加速查询处理的方法存在两方面的问题。一是在给定特定数据图的前提下,没有人研究应该使用哪种索引比较合适;二是即使使用了树区间或者基于部分结点的2hop标签,也没有人研究应该使用多少个区间或者使用多少个结点来构建2hop标签才合适。本文对区间及结点2hop标签的可达查询覆盖率计算问题展开研究,具体研究内容如下:首先,现有使用树区间来加速可达性查询处理的方法不能明确使用多少个区间。针对该问题,提出通过求解区间覆盖率的方式来解决。针对基础算法时间复杂度太大、不能在大图上使用的问题,提出一种快速计算区间覆盖率的k-DFSIC优化算法。该方法在计算过程中,通过判断生成树中每个结点到其后代结点之间的可达性查询是否能通过区间回答,可避免基础方法枚举传递闭包的代价,加速覆盖率的计算。基于得到的区间覆盖率,可以协助用户在实际应用环境的限制下确定合适的区间个数。其次,现有使用部分结点构建2hop标签的方法不能确定使用多少个结点构建2hop标签合适。针对该问题,提出一种计算部分2hop结点覆盖率的2hop LC算法。该方法在计算过程中,通过在构建2hop标签的过程中对遍历到的结点进行分组,并基于哈希计数索引对分组信息进行组织,可避免枚举传递闭包的高昂代价,加速覆盖率的计算。基于所得到的部分2hop结点覆盖率,可协助用户确定合适的结点个数,从而加速可达性查询处理的速度。最后,基于20个真实数据集进行了实验。实验结果验证了本文所提出方法的可行性和高效性。