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

doi:10.3778/j.issn.1002-8331.2008.28.042

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

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

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

张晓琳,崔敏,谭跃生

内蒙古科技大学信息工程学院，内蒙古包头 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

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

摘要/Abstract

摘要： 针对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

张晓琳,崔敏,谭跃生. 基于LazyDFA的XPath在XML数据流上查询优化算法[J]. 计算机工程与应用, 2008, 44(28): 125-127.

ZHANG Xiao-lin,CUI Min,TAN Yue-sheng. LazyDFA based XPath query optimized algorithm over XML data stream[J]. Computer Engineering and Applications, 2008, 44(28): 125-127.

[1]	黄涛贻，李优，宋浩，林煜明. 大规模商品知识的组织和查询优化[J]. 计算机工程与应用, 2020, 56(21): 154-163.
[2]	王泓机，戴炳荣，李超，张绍华. 针对区块链应用的查询优化模型[J]. 计算机工程与应用, 2019, 55(22): 34-39.
[3]	刘骁，刘辉平，金澈清. 面向不确定数据流的近似ER-Topk查询处理[J]. 计算机工程与应用, 2017, 53(4): 98-105.
[4]	李文珠，廖湖声，苏航. 基于下推转换机的XML流数据处理方法[J]. 计算机工程与应用, 2016, 52(8): 49-55.
[5]	王磊. 基于BACS算法的数据库查询优化[J]. 计算机工程与应用, 2015, 51(13): 118-121.
[6]	罗鹏. 基于GM-QPSO算法的数据库查询优化[J]. 计算机工程与应用, 2014, 50(8): 103-107.
[7]	刘东. 基于多子群萤火虫算法的数据库查询优化[J]. 计算机工程与应用, 2014, 50(11): 110-114.
[8]	魏东平，朱新向，吴玉雁. 改进的XML小枝模式匹配方法[J]. 计算机工程与应用, 2013, 49(8): 125-128.
[9]	林键，刘仁义，刘南，张丰. 基于查询优化器的分布式空间查询优化方法[J]. 计算机工程与应用, 2012, 48(22): 161-165.
[10]	李希明，郑瑾. 无线传感器网络中基于关联度的多查询优化[J]. 计算机工程与应用, 2011, 47(21): 98-101.
[11]	张晓琳，崔敏，谭跃生. DTD上的lazyDFA XML数据流查询优化算法[J]. 计算机工程与应用, 2009, 45(28): 131-132.
[12]	罗永红^1,2,陈特放¹,张友生³. 网格数据的语义查询优化研究[J]. 计算机工程与应用, 2009, 45(2): 16-20.
[13]	许新华¹,胡世港¹,唐胜群²,刘华东¹. 数据库查询优化技术的历史、现状与未来[J]. 计算机工程与应用, 2009, 45(18): 156-161.
[14]	邓利¹,王新军¹,谷萌萌². 时态XML索引方法[J]. 计算机工程与应用, 2009, 45(16): 162-164.
[15]	李健,施磊,柏文阳. 自优化查询处理器的研究与实现[J]. 计算机工程与应用, 2008, 44(4): 184-186.

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

LazyDFA based XPath query optimized algorithm over XML data stream

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics