近年来,由于统计误差或噪声因素的存在,不确定图模型吸引了越来越多的研究者的注意。不确定图主要应用于对生物网络,社交网络的建模中。另一方面,作为图上的基本查询之一,子图的相似性全匹配查询广泛应用于模式识别、查找用户群、预测蛋白质结构等问题中。所谓子图的相似性全匹配查询,即为给定一个查询图,查找其在一个大的数据图中的所有的相似性匹配。研究者们设计并实现了大量的算法来查找确定图上的子图相似性全匹配,然而,对于不确定图上的子图相似性全匹配查询,并未得到足够多的重视且遇到了很大的挑战。针对上述问题,本文对面向不确定图的子图相似性全匹配问题进行研究。首先,本文考虑查询图为确定图、数据图为不确定图的情况,提出了不确定图上确定图的子图相似性全匹配查询,并针对此问题提出了基于生成树匹配的算法。此外,本文提出了一些优化算法以进一步提高算法的执行效率,例如根据顶点的标签属性及邻居节点为数据图中的顶点建立索引,基于排列组合的思想对不确定图到确定图之间相似性的计算模型进行转化等等。本文通过大量实验验证了所提算法及优化算法的有效性。其次,考虑到查询图为不确定图、数据图为确定图的情况,本文定义了确定图上不确定图的子图相似性全匹配查询,并提出了有效的算法。此外,在上个章节算法的基础上,本文提出了新的计算子图之间相似性的方法,并在此基础上利用概率限值对上述过程进行剪枝。大量实验证明了该算法的有效性。最后,本文考虑查询图及数据图均为不确定图的情况,定义了不确定图上不确定图的子图相似性全匹配问题。在总结上述两个算法的基础上,本文定义了新的计算两个不确定图之间相似性的模型,并提出了动态产生子结构,利用这些子结构进行剪枝的优化方法。实验评估了本文所提算法的高效性。总之,本文从实际应用中面向不确定图的子图相似性全匹配的典型特征和挑战出发,针对不确定图及子图相似性匹配的关键技术展开研究,如基于生成树的匹配方式、可能世界模型概念等,提供有效的面向不确定图的子图相似性全匹配查询处理方法。本文的研究工作为相关课题的开展铺平了道路。