计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (28): 125-127.DOI: 10.3778/j.issn.1002-8331.2008.28.042

• 数据库、信号与信息处理 • 上一篇    下一篇

基于LazyDFA的XPath在XML数据流上查询优化算法

张晓琳,崔 敏,谭跃生   

  1. 内蒙古科技大学 信息工程学院,内蒙古 包头 014010
  • 收稿日期:2007-11-16 修回日期:2008-01-28 出版日期:2008-10-01 发布日期:2008-10-01
  • 通讯作者: 张晓琳

LazyDFA based XPath query optimized algorithm over XML data stream

ZHANG Xiao-lin,CUI Min,TAN Yue-sheng   

  1. Information Engineering College,Inner Mongolia University of Science and Technology,Baotou,Inner Mongolia 014010,China
  • Received:2007-11-16 Revised:2008-01-28 Online:2008-10-01 Published:2008-10-01
  • Contact: ZHANG Xiao-lin

摘要: 针对XML数据流上XPath查询处理及查询优化问题,给出了一种基于lazyDFA技术的解决方案,并提出了优化算法。共享NFA状态表,通过将NFA中的状态分成共享和独享两个状态集来降低lazyDFA的内存使用量;建立状态转移表优化算法通过在lazyDFA状态结构中增加一个状态转移表,来提高lazyDFA的查询速度。实验结果表明,提出的方法能够在执行效率和空间代价方面优于传统算法。

关键词: XML数据流, XPath, lazyDFA, 查询优化

Abstract: This paper gives a solution based on lazyDFA technology and presents the optimized algorithm which aims at the XPath query processing and query optimization problem over XML data stream.Shared NFA state table,which divides the states in NFA into two sets,they are shared set and exclusive set.By this algorithm we can reduce the memory usage of lazyDFA.Another optimizational algorithm adds a state transition table in lazyDFA structure,which can improve lazyDFA query speed.The experimental results show that the method is superior to the traditional algorithms in the implementational efficiency and spacial cost.

Key words: XML data stream, XPath, lazyDFA, query optimization