有向无环图(DAG)的可达性查询处理是图数据管理中的热点问题之一,可以应用到现实生活中的很多领域,包括语义网、互联网、电信网、无线传感网络、社交网络及生物信息网等。可达性查询就是在有向无环图G上,给定任意的2个结点u和v,回答u是否能够到达v。通过分析现有可达性查询算法,发现已有的算法构建索引的时间较长,查询效率低。本文主要从以上2个方面对可达性查询处理进行研究,研究内容如下。首先,提出基于影子定位的索引构建算法SP。SP算法基于区间扩展策略为每个结点设定标签。给定需要处理的n个结点,不同于以往算法需要多次的遍历才能完成当前结点的处理,SP算法基于影子定位技术,将待处理结点分别存放在待处理栈和待扫描链表中,待处理栈中每个结点记录了其在待扫描链表中的位置,从而将已有方法的O(logn)搜索代价降低为O(1)代价,加速了索引构建的效率。其次,提出双向编码方案和基于巨大结点的剪枝策略来提升查询处理的效率。通过正向和反向进行编码,为每个结点指定相应的索引标签,增强了区间过滤的能力。为了进一步的增强可达查询的处理能力,提出巨大结点的位标签过滤策略。该策略选取k个度最大的hop结点,根据每个结点与这k个结点之间的关系建立压缩后的位标签,来快速回答可达查询。最后,在25个真实数据集上进行实验,对本文方法和已有方法进行了深入的比较和分析,实验结果验证了本文提出方法的高效性和扩展性。