利用自动机高效处理XML路径表达式查询

Efficiently Processing XML Path Queries Using Automata

在XML查询处理中,应用于绝大多数XML查询语言中的路径表达式在定位和查询XML数据和数据的结构关系方面具有极强的表达能力,并且由于XML数据的半结构化性,使得XML路径表达式查询的查询处理技术的研究与传统的数据库查询处理技术相比有着全新的特点和挑战.一些目前已有的查询处理技术可以用来处理路径表达式,但是查询处理中产生的大量中间结果导致了这些方法应用在大规模XML文档和复杂的路径表达式查询中时查询效率急剧下降.文中利用自动机技术设计了一个处理XML路径表达式查询的高效方法——SAM.SAM的基本思想是将路径表达式查询转化成一个与之完全等价的自动机,然后将其与从XML文档中抽象出来的模式路径相匹配.文中同时也给出了基于SAM方法的针对路径表达式中"//"操作符计算的有效解决方案.实验证明:SAM是一种非常有效的查询方法,在计算大数据量复杂路径表达式查询时具有非常高的效率,是一种实用的XML路径表达式查询方法.

In XML query processing, path expressions applied in most XML query languages have a powerful ability in locating and querying XML data as well as structural relationships. Due to the semi-structured feature of XML data, the query processing techniques of XML path expression query has new characteristics and challenges compared to traditional database query processing techniques. So far, some techniques have been proposed for processing path queries. However, when they are applied to large scale of XML documents and complicated path expressions, their performance degrade dramatically. This paper proposes a high efficient XML path expression query processing method——SAM based on the automata technique. Its basic idea is transforming a path expression query to an equivalent automata and matching the automata with the schema paths abstracting from the XML document. This paper also presents an approach to computing the ＂＂ operation based on the SAM method. The experimental results show that SAM is an efficient and practical method for computing complicated path expression queries on large scale XML documents.