论文部分内容阅读
传统的数据库管理只处理确定的信息,现在越来越多的数据库应用包含了非确定的信息。XML文档以其自描述性,跨平台交换性等特点,已经成为网络上数据存储和数据交换的标准。互联网上越来越多的结构化或者半结构化的数据采用了XML格式存储和交换,对XML数据的查询处理及其文档过滤的研究显得日益重要。最近,基于XML模型来描述不确定数据越来越引起了大家的兴趣。在概率XML文档的相关查询方法中,传统的查询处理方法是基于possible worlds的,其不足之处主要是,在查询的时候不得不遍历整个XML文档得到每一个possible world,然后在每个possible world上进行查询。鉴于Holistic Twig查询处理方法可以做到一遍扫描原文档即可得到查询处理的所有中间结果,本文改进了传统的Holistic Twig查询方法并将其运用到概率XML的查询中,利用概率标签流来进行查询匹配。应用于概率XML文档中的Holistic Twig算法被称为概率Holistic Twig查询处理算法。概率XML文档相对于普通XML文档,其数据的存在具有一定的概率,利用概率Holistic Twig算法在概率XML文档中进行查询处理的时候,需要对文档中的数据节点编码进行相应的改进。改进后的概率节点编码使得p-TwigStack算法成功地运用于概率XML文档的查询处理,得到了查询所需要的所有的中间结果。另外,由于概率XML文档中数据存在的概率特性,使得查询处理得到的中间结果和最终结果都具有一定的存在概率,低概率的结果无法满足查询要求,为了提高算法的查询效率,本文在算法运行的过程中加入了相应的过滤操作。过滤操作主要包括中间结果生成过程中的过滤和最终结果生成过程中的过滤。在文章的最后,对相关查询处理算法做了比较,主要包括概率Holistic Twig查询处理算法与possible worlds算法相比较的效率分析、概率Holistic Twig算法查询处理的过程中,概率过滤操作对整个算法效率的影响分析等,并且对比较结果给出相应的分析。