| 摘要: |
| Xpath成为XML数据查询的基本机制.Xpath中表达节点之间的祖孙关系的‘//'和任意匹配字符的‘*'等非确定操作符,增强了Xpath表达方式的灵活性,但同时引入了Xpath处理的复杂性.如何利用DTD减少Xpath中的不确定操作符,从而提高Xpath的执行效率成为一个基本的研究问题.传统方法主要侧重于特定受限Xpath的确定化重写.利用树自动机在一个框架中表达Xpath和DTD,提出了一种新的Xpath树自动机和DTD树自动机的乘积运算,并证明了乘积的结果就是基于DTD的Xpath优化形式,在多项式时间内基于代价获取了Xpath的优化结果.实验数据表明,基于提出的Xpath的逻辑优化方法,能够有效地提高Xpath执行器的执行效率. |
| 关键词: Xpath DTD 树自动机 重写 优化 |
| DOI： |
| 分类号: |
| 基金项目: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 Logical Optimization Based on DTD |
|
GAO Jun,YANG Dong-Qing,TANG Shi-Wei,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. |
| Key words: XPath DTD tree automata rewrite optimization |
