基于LSPI索引的不确定XML查询处理算法

Efficient processing algorithm for uncertain XML query processing based on LSPI index

针对目前已有XML通配符查询处理需将文档中所有元素标签读入内存中,匹配效率低的问题,提出一种新的基于LSPI(leaf sibling of path information)索引的不确定XML包含通配符和复杂谓词的查询处理算法Prob-BooleanStarTwig。算法基于有效过滤策略自底向上进行模式匹配,将通配符转换成A-D关系和层次信息约束,解决传统通配符匹配问题,避免多次扫描查询模式,提高查询速度。理论分析和实验结果表明,算法的查询效率明显优于已有的算法。

At present most algorithms are appropriate for XML wildcard twig query also load all the labels in the XML documents into memory to matching wildcards. This paper proposed the holistic algorithm named Prob-BooleanStarTwig for uncertain XML based on LSPI（leaf sibling of path information） index to support efficient processing of complex twig pattern queries including wildcards and logical predicates. The algorithm converted wildcard into A-D connection and hierarchical information constraints and solved the traditional wildcard matching problems. Prob-BooleanStarTwig was based on effective filtering strategies and a bottom-up pattern matching to avoid scaning query mode repeatedly and improved query speed. Both analytical and experimental results show that query efficiency of this method is significantly better than existing algorithms.