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

LazyDFA based XPath query optimized algorithm over XML data stream

作　　者：张晓琳[1] 崔敏[1] 谭跃生[1] 

机构地区：[1]内蒙古科技大学信息工程学院,内蒙古包头014010

出　　处：《计算机工程与应用》2008年第28期125-127,139,共4页Computer Engineering and Applications

基　　金：国家社会科学基金No.07XTQ003;内蒙古自然科学基金No.200508010808~~

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

关 键 词：XML数据流 XPATH lazyDFA 查询优化 

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