不确定图数据查询处理关键技术的研究

近年来，人们针对化合物、蛋白质等具有复杂结构的图数据的管理技术开展了很多研究工作。目前的大多数研究工作都假设图数据是准确无误的。但是，大量实际应用中的图数据往往并不准确，含有噪音、错误和不确定信息。这使得上述研究成果难以得到有效地应用。如何有效地存储和索引大量不确定图数据，以高效地支持各种复杂的查询与检索，是数据库领域面临的一个新的挑战性问题。因此，本课题从数据库的角度，研究不确定图数据库查询处理关键理论和技术，包括不确定图数据模型、不确定图数据的存储与索引方法、不确定图数据的基本操作算法以及不确定图数据查询与优化处理算法，并研制相应的不确定图数据查询处理系统原型，验证课题所提出方法的正确性和有效性。本项研究将提出一系列有关不确定图数据查询处理的理论、技术和方法，取得国际一流研究成果，具有重要学术意义。上述研究成果在化学、生物信息学和复杂社会网络等实际领域具有广阔的应用前景。

如何高效地存储和索引大量不确定图数据以支持各种复杂的查询是数据库领域面临的挑战性问题。针对图数据的存储和索引问题，本课题设计了基于双分支特征编码的索引和基于频繁闭图的索引结构。双分支特征编码是由图的短路径及路径两侧端点的邻接点标签的散列向量构成。基于双分支特征编码的索引具有创建速度快和维护代价低的特点，适合于索引频繁更新的图数据。基于频繁闭图特征的索引采用数据挖掘获得的频繁子图特征来构造。通过选择适当的闭图特征集合构造的索引能够高效的支持数据操作和查询处理过程中的候选数据集的获取。针对基本的图数据操作算法，本课题研究了基于索引的子图匹配和图包含操作算法。基于双分支特征的子图匹配操作算法首先计算查询图的最小双分支特征覆盖。应用查询图的最小覆盖特征和部分随机选择的双分支特征迭代查询双分支特征索引来获得候选结果集。基于频繁闭图索引的图包含操作算法在遍历索引树的同时将索引闭图特征与查询图进行子图同构增量验证，有效地减小了操作算法的代价。本课题研究了不确定图上的复杂查询处理算法。针对基于概率阈值距离阈值的可达性查询，提出了基于优化分类树的自适应双向遍历随机抽样算法来处理查询。基于概率阈值的不确定图匹配查询处理算法通过模式图简化方法消除查询图模式中的冗余信息，再根据节点可达概率上下界的估计值来过滤候选结果。从而减少模式图匹配过程的代价。课题组还研究了不确定图数据上的频繁图模式挖掘问题。提出了基于近似算法的不确定频繁子图挖掘算法和基于随机游走的K极大频繁子模式挖掘算法。这些频繁子图模式挖掘算法获得的结果有助于构造基于频繁子图特征的不确定图数据索引。