k步可达查询处理在现实世界中有着广泛的应用,例如好友推荐、交通线路查询、网络路由等。k步可达查询用于回答两个顶点之间是否存在一条长度不超过k的路径。相较于传统的可达性查询,k步可达查询可以提供更多的信息。然而,现有的k步可达查询算法大多只能应用在有向无环图上。能应用于带环有向图的k步可达查询算法又存在索引规模大,索引构建时间长以及查询效率低等诸多问题。本文研究带环有向图上的k步可达查询处理问题,研究内容如下。首先,提出了一种基于贪心思想的近似最小顶点覆盖集求解算法。该算法每次选择当前度最大的顶点加入覆盖集,从而降低覆盖集的规模。通过使用哈希计数方法,可在线性时间得到近似的最小顶点覆盖集。提出了一种基于最小顶点覆盖集的2-hop索引,该方法结合了最小顶点覆盖集和2-hop索引的优势,通过建立仅包含覆盖点的2-hop索引,降低了索引构建时间,索引规模以及查询处理时间。其次,提出了三种优化策略来进一步加快查询处理的速度。第一种是基于互逆拓扑序号的不可达查询优化,提升了不可达查询的处理效率。第二种是基于带环有向图的等价压缩策略,进一步减小了图的规模。第三种是基于阈值的索引优化策略,改善了非覆盖点查询效率低的问题。最后,在25个真实数据集上对提出的最小覆盖集求解算法与已有算法进行了比较。实验结果表明,本文提出的算法求解出的覆盖集规模更小,同时基于覆盖点构建索引的方法在索引构建时间,索引大小以及查询时间三个指标上的性能都优于已有的算法,并且在给定16GB内存的前提下,能支持在千万级顶点规模的带环有向图上高效处理k步可达查询。