现实世界中复杂交互的关系通常可以通过图来表示，如生物网络、社交网络等，这些图的边上往往具有表示特征的文本标签，如生物网络中的边标签可能是化合物之间转换的反应酶种类。在现实应用中，用户可能仅对某些个体之间特定的属性关系感兴趣。标签约束的可达性查询，用于回答有向图中从给定一个顶点出发，仅经过某些特定类型的边，是否可以到达另一个顶点。具体来说，就是确定图中是否存在从给定源点s到目标顶点t的路径，并且路径上的边标签属于预定义标签集L中的标签。然而，现有方法处理标签约束的可达性查询时，存在索引规模大或者查询效率低的问题。
　　为了解决现有方法存在的问题，本文首先提出一种具有较高可达信息覆盖率的双向路径标签索引策略，其次提出基于所有顶点构建双向路径标签索引的BPLI方法，最后提出了基于部分点构建双向路径标签索引的BPLI+方法。具体来说，本文主要贡献如下：
　　首先，针对已有方法索引具有较低可达信息覆盖率的问题，提出一种双向路径标签索引策略来提升索引的可达信息覆盖率，并给出降低索引规模的两个剪枝策略及证明：1）遍历中访问到已经处理过的顶点时，不更新索引并停止该分支的遍历；2）比较当前遍历路径的路径标签与索引得到的路径标签之间的集合包含关系，决定是否更新索引与继续遍历。基于以上策略，本文提出了一种完全索引BPLI方法，该方法通过为图中所有顶点建立双向路径标签索引来记录所有顶点对之间的可达信息及标签信息，在处理查询时完全避免了图遍历操作，从而提高查询响应性能。
　　其次，针对BPLI方法索引规模大的问题，提出一种基于部分点的双向路径标签索引BPLI+方法，并提出相应的优化措施：1）顶点处理序号代替顶点自身序号，从而避免排序，有效减少了构建索引的时间；2）基于整数的32位存储索引，将索引规模降低一半；3）查询时，提出双向遍历策略减少遍历过程中访问的顶点数目，从而加速查询的处理速度。
　　最后，基于23个真实数据集进行测试，实验结果从索引大小，索引构建时间和查询响应时间三个方面验证了所提方法相对现有方法具有索引规模小、索引构建时间短且查询响应快的优势。