###
DOI:
Journal of Software:2004.15(12):1860-1868

一种基于DTD的XPath逻辑优化方法
高军,杨冬青,唐世渭,王腾蛟
(北京大学,信息科学技术学院,北京,100871)
XPath Logical Optimization Based on DTD
GAO Jun,YANG Dong-Qing,TANG Shi-Wei,WANG Teng-Jiao
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3073   Download 3411
Received:September 12, 2003    Revised:March 02, 2004
> 中文摘要: Xpath成为XML数据查询的基本机制.Xpath中表达节点之间的祖孙关系的‘//'和任意匹配字符的‘*'等非确定操作符,增强了Xpath表达方式的灵活性,但同时引入了Xpath处理的复杂性.如何利用DTD减少Xpath中的不确定操作符,从而提高Xpath的执行效率成为一个基本的研究问题.传统方法主要侧重于特定受限Xpath的确定化重写.利用树自动机在一个框架中表达Xpath和DTD,提出了一种新的Xpath树自动机和DTD树自动机的乘积运算,并证明了乘积的结果就是基于DTD的Xpath优化形式,在多项式时间内基于代价获取了Xpath的优化结果.实验数据表明,基于提出的Xpath的逻辑优化方法,能够有效地提高Xpath执行器的执行效率.
中文关键词: Xpath  DTD  树自动机  重写  优化
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
文章编号:     中图分类号:    文献标志码:
基金项目: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)) 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))
Foundation items:
Reference text:

高军,杨冬青,唐世渭,王腾蛟.一种基于DTD的XPath逻辑优化方法.软件学报,2004,15(12):1860-1868

GAO Jun,YANG Dong-Qing,TANG Shi-Wei,WANG Teng-Jiao.XPath Logical Optimization Based on DTD.Journal of Software,2004,15(12):1860-1868