高效不确定XML复杂Twig查询处理算法  

Efficient processing algorithm for uncertain XML of complex twig pattern matching

作　　者：张晓琳[1] 韩雨童 苏龙超 刘立新[1] 

机构地区：[1]内蒙古科技大学信息工程学院,内蒙古包头014010

出　　处：《计算机工程与设计》2014年第4期1258-1263,共6页Computer Engineering and Design

基　　金：国家自然科学基金项目(61163015);内蒙古自然科学基金重点项目(2013MS0909)

摘　　要：针对目前普通XML复杂Twig查询处理算法易造成大量空间和时间浪费,且不能完全适用于不确定XML的问题,提出一种基于P-文档模型的不确定XML复杂Twig查询处理算法Prob-BooleanTwig,处理包含AND,NOT和OR复杂谓词的查询模式。算法在扩展了EDewey编码的基础上,构建路径叶子节点索引,进行自底向上的查询模式匹配,避免了对查询模式的多次扫描。理论分析和实验结果表明,Prob-BooleanTwig算法具有高效性。At present there has been much research on XML of complex Twig query processing. However, all these algorithms are not appropriate for uncertain XML, which has weaknesses of time and space efficiency. The holistic algorithm named Prob- BooleanTwig for uncertain XML based on existing p-document model is proposed to support efficient processing of complex Twig pattern queries, including an arbitrary number of logical predicates like AND, OR and NOT. Prob-BooleanTwig constructs path-leaf index based on EDewey encoding scheme and takes bottom-up approach to achieve complex Twig query processing. There is no need to scan the query mode for many times. Both analytical and experimental results show that this method is more quick and efficient.

关 键 词：不确定XML 复杂Twig查询 编码 路径索引 查询处理 

分 类 号：TP392[自动化与计算机技术—计算机应用技术]