子图查询返回图数据集合中所有包含查询图的数据图。本文从两个不同角度对子图查询进行研究。首先是频繁更新的(确定)图数据上的子图查询,然后是不确定图上的子图查询。定义了图的双分支特征图和双分支特征编码,基于特征编码提出了一种迭代式子图查询处理算法,称为基于双分支特征编码的子图查询算法。算法通过动态优化子图特征迭代顺序和限制全局迭代次数来提高候选结果集的计算效率。为了高效地完成该查询算法执行过程中的图数据过滤,设计了双分支特征编码的索引结构DBrIndex。该索引的创建不依赖于任何频繁子图挖掘方法,易于增量式维护,适合于索引频繁更新的动态图数据集合。实验结果表明:与现有同类方法相比,DBrIndex索引体积小,维护代价低,能够高效地支持子图查询处理。在查询图和数据图同时为不确定性图的前提下,提出了不确定图间的期望子图同构定义和-β子图同构匹配定义。查询图的不确定性反应了用户对查询图中各种元素(边、顶点或标号信息)存在的可能性的期望。不确定图间的期望子图同构是确定图上子图同构在概率图模型上的直接推广,不确定图间-β子图同构利用两个限制阈值来衡量查询图和数据图间的匹配质量。文章详细阐述了-β子图同构匹配的语义特点,分析了它和期望子图同构的联系和差别,设计实现-β子图同构匹配判定算法。