| 一种可扩展的XPath查询最小化算法框架 |
| |
| 引用本文： | 林峰,冯建华,塔娜,李国良,洪亲.一种可扩展的XPath查询最小化算法框架[J].计算机科学,2008,35(3):58-60. |
| |
| 作者姓名： | 林峰 冯建华 塔娜 李国良 洪亲 |
| |
| 作者单位： | 1. 清华大学计算机科学与技术系,北京,100084
2. 福建师范大学物理与光电信息科技学院,福州,350007 |
| |
| 摘 要： | XPath是XML的基本查询语言,XPath查询最小化对于提高XML数据库的查询性能具有重要意义.但是,由于XPath查询最小化是一个coNP完备问题,大部分已有的算法局限于处理简单的XPath片段.本文从一个新的角度入手,综合考虑完备性和高效性,提出了一个新的查询最小化框架,与已有算法"面向结点",即逐个删除冗余结点的解决思路不同,本文提出"面向树模式"的方式,即通过计算树模式的自同态映射,寻找目标结点集最小的自同态映射,进而求解最小等价查询树的方法.该方法具有较高的效率,而且在--Z..情况下是完备的,尤其是可以进一步扩展到更复杂的XPath片段.本文以此框架为基础,给出一个可以计算复杂查询模式的算法.
|
| 关 键 词： | XPath 查询 自同态 最小化 |
An Extensible Framework for XPath Query Minimization |
| |
| LIN Feng,FENG Jian-Hua,TA Na,LI Guo-Liang,HONG Qin.An Extensible Framework for XPath Query Minimization[J].Computer Science,2008,35(3):58-60. |
| |
| Authors: | LIN Feng FENG Jian-Hua TA Na LI Guo-Liang HONG Qin |
| |
| Affiliation: | LIN Feng1 FENG Jian-Hua1 TA Na1 LI Guo-Liang1 HONG Qin2(Department of Computer Science , Technlogy,Tsinghua University,Beijing 100084)1(School of Physics , OptoElectronics Technology,Fujian Normal University,Fuzhou 350007)2 |
| |
| Abstract: | XPath is a standard language for XML queries,and XPath query minimization is very important for improving the performance of XML queries. However,XPath query minimization is a coNP-complete problem,and most previous algorithms are restricted to simple XPath fragments. We study the problem from a novel perspective,and present an efficient and extensible framework of query minimization. Traditional methods,which are node oriented,always delete redundant node one by one,however we present an alternative way of... |
| |
| Keywords: | XPath Query Endomorphism Minimization |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
|
