论文部分内容阅读
1998年2月万维网联盟发布了一种名为XML(可扩展标记语言)的数据标准。由于它是标准通用标记语言SGML的子集,又是由W3C组织发布的,因此XML正逐渐成为信息世界数据交换的标准。在Web应用中的数据存储、应用程序的配置文件、应用程序之间数据共享等凡是涉及数据存储、数据交换的领域都有XML的身影。面对多变的客观世界,数据的不确定性在加工数据的同时也要被考虑到。由于XML技术的发展以及XML自身所具有的各种优点,使用XML来存储不确定性数据已经成为当前趋势。利用XML文档来保存数据及数据的概率,这种形式的XML叫做不确定XML,针对不确定XML的查询已经成为当前研究热点。二元结构连接和整体匹配是当前小枝模式匹配领域中常使用的方法。但二元结构连接过程中的部分结果是没有意义的,这样无意义的结果对查询速度有着很大的约束。基于整体匹配的方法由于查询过程过于集中,不方便进行概率阈值过滤,无法高效地利用概率阈值过滤来提高查询效率。由于当前不确定XML小枝模式查询处理方法存在着缺陷,本文将基于序列匹配的方法应用到不确定XML查询。通过改进LCS-TRIM算法提出了基于序列的不确定XML小枝模式匹配算法PrTRIM以及H-PrTRIM。不确定XML文档与普通XML文档相比,具有额外概率信息,因此在查询同时还需要正确地处理这些概率信息。本文中PSI索引由于存储了结构信息,因此可以对互斥分布节点来进行识别。PSI索引中的内容信息可以进行实例树概率的计算,这样XML文档中存储数据的概率就可以被准确处理。PSI索引在查询中也发挥着重要的作用。不确定XML的查询结果没有必要全部保留,这是因为低概率结果对于一些实际应用没有意义。这样就可以考虑在查询中设置一个阈值来去掉部分不符合要求的结果。概率阈值是查询时给出的一个概率值,意义是要求查询结果的概率值都大于等于给出的概率阈值。本文在查询同时加入三次概率阈值过滤策略,可以确保查询结果符合概率阈值,同时又能提高查询效率。实验主要通过PrTRIM算法与H-PrTRIM算法对比来进行,包括概率阈值对查询效率的作用,算法效率比较以及文档容量对查询效率的作用三个方面,在最后对实验结果进行了相应的分析。实验结果表明针对小文档和结构简单的查询语句H-PrTRIM算法效率接近PrTRIM算法,但仍然高于PrTRIM算法。针对大文档和结构复杂的查询语句,H-PrTRIM算法效率明显高于PrTRIM算法。由此可见,针对查询大文档和结构复杂的查询语句H-PrTRIM算法更具有优势。