一种可扩展的XPath查询最小化算法框架  

An Extensible Framework for XPath Query Minimization

作　　者：林峰[1] 冯建华[1] 塔娜[1] 李国良[1] 洪亲 

机构地区：[1]清华大学计算机科学与技术系,北京100084 [2]福建师范大学物理与光电信息科技学院,福州350007

出　　处：《计算机科学》2008年第3期58-60,64,共4页Computer Science

基　　金：福建省科技计划项目的资助,资助号:2006F501050079

摘　　要：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.

关 键 词：XPATH 查询 自同态 最小化 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论] TP311.51[自动化与计算机技术—计算机科学与技术]