主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
高军,杨冬青,唐世渭,王腾蛟.基于树自动机的XPath在XML数据流上的高效执行.软件学报,2005,16(2):223-232
基于树自动机的XPath在XML数据流上的高效执行
Tree Automata Based Efficient XPath Evaluation over XML Data Stream
投稿时间:2003-08-27  修订日期:2004-05-08
DOI:
中文关键词:  XPath  树自动机  XML  数据流
英文关键词:XPath  tree automata  XML  data stream
基金项目:Supported by the National High-Tech Research and Development Plan of China under Grant No.2002AA4Z3440 (国家高技术研究发展计划(863)); the National Grand Fundamental Research 973 Program of China under Grant No.G1999032705 (国家重点基础研究发展规划(973)
作者单位
高军 北京大学,信息科学技术学院,北京,100871 
杨冬青 北京大学,信息科学技术学院,北京,100871 
唐世渭 北京大学,信息科学技术学院,北京,100871 
王腾蛟 北京大学,信息科学技术学院,北京,100871 
摘要点击次数: 4393
全文下载次数: 3636
中文摘要:
      如何在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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利