基于PSB编码的小枝模式匹配算法

Twig Pattern Matching Algorithm Based on PSB Encoding

XML已经成为Internet上数据表示和交换的标准,因此,在XML查询处理过程中如何有效地找出满足条件的查询路径表达式是非常关键的。目前,在区间编码的基础上已经提出了许多小枝模式匹配算法来实现XML路径表达式的查询。在PSB编码的基础上提出了一种新的小枝模式匹配算法PSBDirect。与现有的算法相比,该算法可以直接跳过一些不需要参与连接的结点,在一定程度上提高了查询处理效率。

XML is becoming the de facto standard for data represent and exchange over the Internet,so efficiently finding all occurrences of a twig pattern is a core operation of XML query processing.Recently,a large number of holistic twig join algorithms based on region coding have been proposed to find the XML path expression.In this paper,we propose a novel algorithm,named PSBDirect,based on the PSB coding.Compared with the previous algorithm,this algorithm can skip some nodes which do not need to take part in connection,to some extent,it can improve the efficiency of processing query.