论文摘要
由于互联网技术以及新的科学／工程技术的进步,以图作为存储模式的应用数量不断地增加,如在生物信息学、社会关系学、万维网等。而由于测量方法的不准确性以及对数据测量时引入的噪声导致不确定性在图数据中普遍存在。近年来,不确定数据管理成为了数据库领域的研究热点,由于图的广泛应用,不确定图数据管理技术的研究也逐渐被重视。但是现有的图数据技术和不确定数据管理技术不能直接应用在不确定图数据上。所以如何高效处理这两者的结合体面临很大的挑战。这就要求开发新的技术以处理不确定图这种复杂的数据结构。不确定图的模式匹配查询是不确定图数据查询处理的重要组成部分,本文主要研究不确定平面图的模式匹配查询技术。首先,本文使用可能世界语义建模不确定平面图数据,在该模型的基础上定义了不确定平面图的模式匹配查询。本文首先根据可能世界语义得出计算匹配概率的直接算法,即枚举所有可能世界图(确定图),所有与查询图相匹配(确定图匹配)的可能世界图的概率之和即为不确定平面图的模式匹配概率。但可能世界图的规模是呈指数级增长的,这导致直接算法效率低下。因此提出一种“基于事件解决树”的精确算法,使查询可以避免枚举所有的可能世界图。在此方法中,本文定义成功、失败及不确定事件,建立解决树来逐层分解不确定事件以最终得到所有的成功事件,并对成功事件的概率求和来计算匹配概率。为了进一步优化算法效率,本文提出了四种优化算法,(1)基于不相交匹配/割集界算法：此方法通过不相交匹配图集和割集界计算匹配概率的紧凑边界,并通过与概率阈值的比较得出结果；(2)同构图缩减算法：此方法通过分解和合并同构图的方法来简化计算；(3)不确定事件界算法：此方法通过累加解决树中的成功事件和失败事件的概率来不断紧缩不确定事件的界,并与概率阈值相比较得出匹配结果；(4)采样算法：此方法采用蒙特卡罗理论不断模拟可能世界产生的过程,从而使查询快速的收敛。最后通过大量基于真实／合成不确定平面图的实验验证了本文提出算法的有效性。