可达性查询是图的基本操作之一,是研究者关注的热点问题之一。可达性查询用于判断两个点之间是否存在一条路径,可达性查询处理广泛应用于在线社交网络、生物网络、交通网络等。过去十多年,研究者已提出许多标签方案来提高查询效率,但是现存的算法只能较为快速的回答可达查询或不可达查询,无法同时高效回答两种查询。本文对可达性查询处理方法进行研究,具体研究内容如下。首先,针对现存算法不能同时有效的回答可达和不可达两种查询,本文提出了一种基于完整标签方案的算法(Complete-YesNo,CYN)。CYN的基本思想是先使用No标签快速回答不可达查询,再用基于No标签的扩展Yes标签来高效的回答可达查询。最后提出利用扩展的Yes标签来减小2hop标签,用于高效回答剩余的可达性查询。提出了相应的高效算法来快速构建No标签,扩展的Yes标签以及2hop标签。其次,针对CYN算法可达查询覆盖率仍然较低和2hop标签较大的问题,提出了两种优化策略。一种是为稠密结点建立Dense标签,用于回答可达查询,并可根据该标签从图中移除稠密结点和冗余边进一步简化给定的数据图。另一种是建立逆向标签,用于提高可达和不可达查询的覆盖率,能进一步缩减数据图,生成规模更小的2hop标签来更高效回答查询。最后,在25个真实数据集上将本文算法和已有算法进行了实验比较与分析。实验结果验证了本文算法的平均查询性能要优于所有现有算法。