近年来,图模型得到越来越多的重视,它不仅可以应用到路网及社交网络中,还可以应用到各种生物网络中。作为图上的基本查询之一,可达性查询得到了广泛的研究。可达性查询也是子图同构的图形查询的一个基本构成部分,因此可能会被频繁调用以处理大量数据和复杂查询,对它的有效支持就显得尤为重要。然而,由于统计误差等原因,图数据往往具有不确定性,且随着图中包含的信息越来越丰富,各式各样的标签图应需产生。在这些图上的一个基础研究问题是基于标签限制的可达性查询(LCR),即查询任意两点间路径满足标签集限制的可达概率。针对不确定标签图,传统的可达性查询技术不再适用。针对上面提出的问题,本文对不确定图上基于标签限制的可达性查询技术进行了研究。首先,针对概率图的不确定性,本文形式化定义了不确定图上基于标签和距离限制的可达性问题,接着提出了一种基于子路径的高效的剪枝方法,根据子路径和距离阈值的特性,通过分支路径过滤的剪枝方法,大幅度减少了子路径处理个数。最后给出了抽样方法包括Random Walk、不等概率抽样和DC树抽样方法。其次,针对标签集为有序限制的情况下,对上面的问题进行改进,定义了不确定图上有序标签限制的可达性查询问题,由此提出了一个迭代算法,即使用路径索引及有效的剪枝方法定位含有有序标签的边,接着用这些边构造新的子路径,连接成完整路径并记录,再使用蒙特卡罗采样方法对所有路径的概率和进行估计,并给出了Bonferroni和Chung-Erdos不等式界和路径/割界。最后,实验通过比其他方法验证了本文所提出的算法在高效性和准确性上的优越性,同时检验了各种剪枝优化方法的效率。总之,本文从越来越接近实际应用的不确定图上基于标签限制的可达性查询的典型特征和挑战出发,针对不确定图上的路径标签的关键技术展开研究,如基于子路径、路径索引的数据结构的标签查询技术,预处理技术、分支路径过滤技术和拓扑顺序剪枝技术等,从而提供高效健壮的不确定图上基于标签限制的查询处理方法。本文的研究工作所采用的算法思想和剪枝更新策略将为相关课题的开展打下了坚实的基础。