论文部分内容阅读
近年来，随着数据管理技术的飞速发展，人们对数据的认知也在逐渐发生变化，研究者们突破对传统数据的理想化定义，认识到不确定性是数据的固有属性。随着计算机技术的不断发展，一种结构灵活的可扩展标记语言XML逐渐成为了数据存储和信息传递的事实标准，在Internet中扮演着越来越重要的角色。XML凭借其自身半结构化、自描述性等特点突破传统关系数据模型对数据模式的严格约束，更适用于对不确定性数据的描述。不确定XML管理技术越来越受到研究者们的关注。目前大多数不确定XML查询是基于结构匹配和内容查询，在现实世界中不确定XML查询语义往往是比较复杂的，查询模式不仅是简单的Twig查询，还有可能包括逻辑谓词、通配符等来表达更丰富的查询内容。因此，如何处理不确定XML复杂Twig查询成为亟待解决的问题。首先，通过大量分析总结，针对目前已有的XML复杂Twig查询处理算法并不适用于处理不确定XML复杂Twig查询，且查询效率较低等问题。提出针对包含逻辑谓词AND、OR和NOT的复杂Twig查询匹配算法Prob-BooleanTwig，算法在REDewey编码的基础上，采用路径索引聚集存储具有相同路径的节点编码，加快叶子路径匹配速度；查询过程中仅需遍历一次查询模式，并根据谓词类型采取不同的匹配方式，有效提高了查询效率。其次，针对不确定XML复杂Twig查询中通配符匹配以及需要处理大量中间结果的问题，提出一种优化算法Prob-Boolean StarTwig，算法在原有路径索引的基础上设计LSPI索引，索引中增加兄弟节点标签来提高AND和OR节点的匹配速度；提出路径匹配有限状态自动机，算法只需对查询模式中的叶子节点进行路径匹配，通过路径匹配有限状态自动机将通配符匹配问题转化成结构匹配和层次约束问题进行处理；算法采用概率阈值、层次信息和路径信息三层过滤的自底向上匹配策略，有效的过滤无用中间结果，减少算法在时间和空间上的消耗。通过大量实验测试算法性能，控制变量主要包括文档大小，概率阈值和查询用例，实验在经典DBLP数据集上随机插入分布节点，并且以算法查询响应时间作为评价因子。理论分析和实验测试证明，Prob-BooleanTwig算法和Prob-BooleanStarTwig算法在执行效率上明显高于已有算法。