一种可扩展的XPath查询最小化算法框架 | |
林峰 ; 冯建华 ; 塔娜 ; 李国良 ; 洪亲 ; LIN Feng ; FENG Jian-Hua ; TA Na ; LI Guo-Liang ; HONG Qin | |
2010-05-12 ; 2010-05-12 | |
关键词 | XPath 查询 自同态 最小化 XPath,Query,Endomorphism,Minimization TP301.6 |
其他题名 | An Extensible Framework for XPath Query Minimization |
中文摘要 | XPath是XML的基本查询语言,XPath查询最小化对于提高XML数据库的查询性能具有重要意义。但是,由于XPath查询最小化是一个coNP完备问题,大部分已有的算法局限于处理简单的XPath片段。本文从一个新的角度入手,综合考虑完备性和高效性,提出了一个新的查询最小化框架,与已有算法"面向结点",即逐个删除冗余结点的解决思路不同,本文提出"面向树模式"的方式,即通过计算树模式的自同态映射,寻找目标结点集最小的自同态映射,进而求解最小等价查询树的方法。该方法具有较高的效率,而且在一定情况下是完备的,尤其是可以进一步扩展到更复杂的XPath片段。本文以此框架为基础,给出一个可以计算复杂查询模式的算法。; 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 "tree pattern oriented". We first compute endomorphism of the initial tree pattern,then find the endomorphism with the smallest target nodes collection size,and finally retrieve the minimal equivalent query pattern tree. Our method is efficient,and is complete under certain conditions. More importantly,it can be extended to more complex XPath fragments. We also give an algorithm,which is adaptive to complex query patterns based on the new framework. |
语种 | 中文 ; 中文 |
内容类型 | 期刊论文 |
源URL | [http://hdl.handle.net/123456789/28468] ![]() |
专题 | 清华大学 |
推荐引用方式 GB/T 7714 | 林峰,冯建华,塔娜,等. 一种可扩展的XPath查询最小化算法框架[J],2010, 2010. |
APA | 林峰.,冯建华.,塔娜.,李国良.,洪亲.,...&HONG Qin.(2010).一种可扩展的XPath查询最小化算法框架.. |
MLA | 林峰,et al."一种可扩展的XPath查询最小化算法框架".(2010). |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论