摘要
XPath成为XML数据查询的基本机制.XPath中表达节点之间的祖孙关系的//和任意匹配字符的*等非确定操作符,增强了XPath表达方式的灵活性,但同时引入了XPath处理的复杂性.如何利用DTD减少XPath中的不确定操作符,从而提高XPath的执行效率成为一个基本的研究问题.传统方法主要侧重于特定受限XPath的确定化重写.利用树自动机在一个框架中表达XPath和DTD,提出了一种新的XPath树自动机和DTD树自动机的乘积运算,并证明了乘积的结果就是基于DTD的XPath优化形式,在多项式时间内基于代价获取了XPath的优化结果.实验数据表明,基于提出的XPath的逻辑优化方法,能够有效地提高目前XPath执行器的执行效率.
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.
出处
《软件学报》
EI
CSCD
北大核心
2004年第12期1860-1868,共9页
Journal of Software
基金
国家高技术研究发展计划(863)
国家重点基础研究发展规划(973)~~
关键词
XPATH
DTD
树自动机
重写
优化
Algorithms
Automata theory
Computational complexity
Optimization
Query languages
Trees (mathematics)
