基于树自动机的XPath在XML数据流上的高效执行  

Tree Automata Based Efficient XPath Evaluation over XML Data Stream

作　　者：高军[1] 杨冬青[1] 唐世渭[1] 王腾蛟[1] 

机构地区：[1]北京大学信息科学技术学院,北京100871

出　　处：《软件学报》2005年第2期223-232,共10页Journal of Software

基　　金：国家高技术研究发展计划(863);国家重点基础研究发展规划(973)~~

摘　　要：如何在 XML 数据流上高效地执行大量的 XPath 查询成为数据流应用中一个迫切需要解决的关键问题.目前提出的算法或者不能完全支持 XPath 的常规特性,或者在算法的执行效率和空间代价上不能满足数据流应用的要求.提出了基于树自动机的XEBT机来解决这个问题.与传统方法相比,XEBT机具备如下特征:首先,XEBT机基于表达能力丰富的树自动机,无须附加中间状态,或保存中间结果,就能处理支持{[]}操作符的 XPath;其次,XEBT 机支持多种优化策略,包括基于DTD的XPath查询自动机的构造;在空间代价有限增加的情况下采用局部确定化减少并发执行的状态;采用自上而下和自下而上相结合的查询处理策略.实验结果表明,提出的方法能够支持复杂的XPath 查询,在执行效率和空间代价方面优于传统算法.How to efficiently evaluate massive XPaths set over an XML stream is a fundamental problem in applications of the data stream. The current methods can not fully support the commonly used features of XPath, or can not meet the space and time requirement of the data stream applications. In this paper, a new tree automata based machine, XEBT, is proposed to solve the problem. Different from traditional ones, XEBT has the following features: First, it is based on tree automata with a powerful expressiveness, which can support Xpath {[]} without extra states or intermediate results; Second, XEBT supports many optimization strategies, including DTD based XPath tree automata construction, partial determination to reduce the concurrent states at running time with limited extra space costs, and the combination of bottom-up and top-down evaluation. Experimental results show that XEBT supports the complex Xpath and outperforms the former work in both efficiency and space cost.

关 键 词：XP 自动机 XML数据 查询 算法 执行效率 操作符 法能 局部 中间状态 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论] TP316[自动化与计算机技术—计算机科学与技术]