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

• 作者: 唐世渭 杨冬青 王腾蛟 高军
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: XPath 树自动机 XML 数据流
• 年，卷（期）: 2005,（2）
• 所属期刊栏目: 数据库技术
• 页码范围: 223-232
• 页数: 10页
• 分类号: TP311
• 字数: 10198字
• 语种: 中文

摘要

如何在XML数据流上高效地执行大量的XPath查询成为数据流应用中一个迫切需要解决的关键问题.目前提出的算法或者不能完全支持XPath的常规特性,或者在算法的执行效率和空间代价上不能满足数据流应用的要求.提出了基于树自动机的XEBT机来解决这个问题.与传统方法相比,XEBT机具备如下特征:首先,XEBT机基于表达能力丰富的树自动机,无须附加中间状态,或保存中间结果,就能处理支持{[]}操作符的XPath;其次,XEBT机支持多种优化策略,包括基于DTD的XPath查询自动机的构造;在空间代价有限增加的情况下采用局部确定化减少并发执行的状态;采用自上而下和自下而上相结合的查询处理策略.实验结果表明,提出的方法能够支持复杂的XPath查询,在执行效率和空间代价方面优于传统算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	唐世渭	北京大学信息科学技术学院	103	4937	32.0	70.0
2	高军	北京大学信息科学技术学院	25	1291	16.0	25.0
3	杨冬青	北京大学信息科学技术学院	97	4962	32.0	70.0
4	王腾蛟	北京大学信息科学技术学院	60	1977	21.0	44.0