论文部分内容阅读
在很多实际应用中,数据的不确定性是普遍存在的,例如传感器网络、信息抽取与数据整合系统、科学数据管理系统等。传统的关系数据库采用结构化的存储方式,不适用于不确定数据的存储和管理。XML以良好的可扩展性和自描述性,成为更适于描述不确定数据的半结构化语言,并且已经成为Internet上数据表示和交换的标准。不确定XML是研究者们提出的一种新的不确定数据表示方法,不确定XML的查询管理技术也因此成为研究的热点。由于查询不确定XML得到的每个结果都对应一个概率值,而用户通常对那些概率值较大的结果比较感兴趣,因此,不确定XML的Top-k查询技术受到了广泛的关注。目前,已提出的不确定XML的Top-k查询算法都没有涉及到连续不确定数据的处理,而在现实世界中,连续不确定数据是普遍存在的,例如温度传感器在某一时段所测得的温度服从某个高斯分布,啤酒厂某装瓶生产线在一年内的碎瓶数量服从某个高斯分布。因而,研究连续不确定XML的相关查询具有一定的现实意义。为了实现连续不确定XML的Top-k查询,首先对PEDewey编码进行扩展,用于支持连续分布类型节点的编码,然后以普通XML经典查询算法TJFast为基础,提出SPCProTJFast算法,在该算法中,对传统的归并算法进行了改进,并根据连续分布的性质设计了连续节点的过滤算法,在查询过程中结合多层过滤机制,达到了高效查询的目的。由于连续节点数量的增加以及概率下限值过小均会降低SPCProTJFast算法的查询效率,提出一种优化算法:HPCProTJFast算法,该算法首先利用概率下限值筛选出满足条件的Twig小枝,然后处理与查询相关的连续节点。由于推迟了对连续节点的访问,因此可以迅速提高概率下限值,增大了对连续节点进行过滤的可能性,从而提高了查询效率。通过具体的实验,将SPCProTJFast算法和HPCProTJFast算法同简单处理连续不确定数据的CProTJFast算法进行了对比。在实验过程中,通过改变文档的大小、k值和查询条件,分别对每种查询算法的查询时间和节点处理率进行统计分析。实验结果表明,SPCProTJFast算法和HPCProTJFast算法的执行效率明显高于CProTJFast算法,并且HPCProTJFast算法的效率更高。