首页 | 本学科首页   官方微博 | 高级检索  
     

一种基于DTD的XPath逻辑优化方法
引用本文:高军,杨冬青,唐世渭,王腾蛟.一种基于DTD的XPath逻辑优化方法[J].软件学报,2004,15(12):1860-1868.
作者姓名:高军  杨冬青  唐世渭  王腾蛟
作者单位:北京大学,信息科学技术学院,北京,100871
基金项目:Supported bythe 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))
摘    要:Xpath成为XML数据查询的基本机制.Xpath中表达节点之间的祖孙关系的‘//'和任意匹配字符的‘*'等非确定操作符,增强了Xpath表达方式的灵活性,但同时引入了Xpath处理的复杂性.如何利用DTD减少Xpath中的不确定操作符,从而提高Xpath的执行效率成为一个基本的研究问题.传统方法主要侧重于特定受限Xpath的确定化重写.利用树自动机在一个框架中表达Xpath和DTD,提出了一种新的Xpath树自动机和DTD树自动机的乘积运算,并证明了乘积的结果就是基于DTD的Xpath优化形式,在多项式时间内基于代价获取了Xpath的优化结果.实验数据表明,基于提出的Xpath的逻辑优化方法,能够有效地提高Xpath执行器的执行效率.

关 键 词:Xpath  DTD  树自动机  重写  优化
收稿时间:2003/9/12 0:00:00
修稿时间:3/2/2004 12:00:00 AM

XPath Logical Optimization Based on DTD
GAO Jun,YANG Dong-Qing,TANG Shi-Wei and WANG Teng-Jiao.XPath Logical Optimization Based on DTD[J].Journal of Software,2004,15(12):1860-1868.
Authors:GAO Jun  YANG Dong-Qing  TANG Shi-Wei and WANG Teng-Jiao
Abstract:XPath becomes the basic mechanism for XML query. The non-deterministic operators in XPath, such as //?denoting ancestor-descendant relationship and *?denoting wildcards in XPath, greatly enhance the flexibility of XPath, but at the same time, introduce the complexity in XPath evaluation. How to explore DTD to reduce non-deterministic operators in XPath in order to improve the efficiency of XPath processing becomes a fundamental problem. The existing work focus on the limited fragment of XPath or DTD. This paper employs tree automata to express XPath and DTD in a unified framework, proposes a novel production operation on tree automata for XPath and tree automata for DTD, proves that the result of production equals to the optimized form of XPath in the presence of DTD, and generates the optimized XPath in a polynomial time based on the generation cost. The experimental result demonstrate that logical optimization on XPath can lead to the increase of efficiency on the existing XPath evaluator.
Keywords:XPath  DTD  tree automata  rewrite  optimization
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号