可达查询是图数据挖掘和管理中的重要基础操作,被广泛应用于相关领域中,例如社会网络、生物信息网络、交通网络、以及语义Web等。针对可达查询的研究已有几十年的历史,从早期的实时在线查询到现在的各种索引技术的应用,人们已经取得了非常多研究成果。给定源点和终点,可达查询的目标主要是在图中发现两个结点间的连接状态,具体可以包括判断它们之间是否存在路径、获取它们之间的最短距离以及判断它们之间的路径上的标签是否符合某种特定规律。由于这个操作是很多其它应用的重要基础,它的效率也会直接影响了其它应用的性能,所以虽然简单,可达查询仍然是图数据领域的一个研究热点。目前虽然在这方面已经出现了很多优秀的算法,但是随着信息技术的不断发展,尤其是随着大数据时代的来临,使得图数据的规模每年都呈几何级数增长,这导致目前大部分经典算法都面临着可扩展性的问题。因此,为进一步提高可达查询的效率,人们仍需要更多的关于这方面的研究。本文分析了现实世界中各类图数据的特性,从中发现有益的规律,以此为基础,将目前的可达查询相关研究成果分为三类,即无约束可达查询、距离约束查询和基于正则表达式查询,并分别针对它们各自的操作特点提出索引的创建及改进算法,具体研究工作如下：(1)利用可达主干实现无约束可达查询传统的方法都是在原图的基础之上利用所有结点创建索引,这使得这些方法的可扩展性很差,只能处理结点数量在几万以下的小规模图数据。为此本文提出了一种“可达主干”的索引框架,该方法的主要理论来源是现实世界中大多数图数据结点间的关系不是均匀分布的,即各结点间在局部范围内联系紧密,而在全局范围内联系比较松散。利用了这一发现,本文首先将原图按照社区划分的方法分成若干个小的集合,然后从每个集合中选择具有中心性质的结点,该结点与本集合内的所有其它结点都存在可达关系,利用这些结点可以建立一个能够保留原图全部拓扑信息的查询子图。这个查询子图不是最终索引,但是它的规模远远小于原图,而且结构稀疏,可以非常方便地利用其它传统的算法在该结构的基础上继续建立索引。实验结果表明,该方法与类似的高效算法相比,在保证查询效率的同时,在索引创建时间和索引规模方面明显优于其它算法。(2)利用最短路径主干和多级社区中心实现距离约束查询最短路径主干与可达主干原理基本一样,只是在创建主干的时候为边集附上权值,成为一个带权查询子图,与可达主干一样,该方法可以有效地压缩原图的规模,形成一个结构稀疏的小规模图,非常有利于利用其它算法继续在其上创建索引,实验表明该结构可以将其它算法处理的数据规模大幅度提高。但是由于可达/最短路径主干还需要借助于其它算法继续建立索引,所以当图数据规模继续增大后,该算法本身又会面临着可扩展性的问题。为此,本文还提出了另外一种索引策略,即多级社区中心标签机制,该方法的主要思想是,在为原图建立了可达/最短路径主干后,不再借助于其它算法继续建立索引,而是直接递归地使用该主干框架继续为每一级主干建立查询子图。在操作的过程中,根据每次操作结果为图中的每个结点计算标签,该多级社区中心标签可以很方便地应用于可达或距离查询,本文主要研究如何将该算法应用于目前普遍处理效率较低的无向复杂网络数据的处理,实验表明,该算法可以处理的数据规模和效率明显优于其它现存算法。(3)利用索引实现基于正则表达式查询本文对边上带有标签的图数据的可达查询操作,即所谓的基于正则表达式的查询也进行了分析和研究,为这类查询提出了两种索引结构：第一种是利用了基于广义表存储结构的压缩的宽度优先遍历邻接表,该方法首先为原图建立了一个宽度优先遍历邻接表,然后尽可能地将每个具有相同边标签的邻接结点压缩成为一个虚结点,最终形成了一个以广义表形式存储的压缩的邻接表,该结构可以保留原图的全部路径信息,所以可以实现近似常数时间的查询；第二种方法是为了解决第一种方法直接在原图上建立索引从而使得索引存储代价过大问题,该方法首先利用顶点集合覆盖的原理,通过一个“2-近似”算法生成一个近似最小顶点集合覆盖,并在它的基础上按照路径标签为原图建立一个索引,由于该方法只选择部分结点,所以索引规模得到有效压缩。实验结果表明,这两种方法与其它常用方法相比具有更高的查询效率。