半结构化数据查询重写

查询重写是数据库研究的一个基本问题，它和查询优化，数据仓库，信息集成，语义缓存等问题紧密相关，目前Internet上存在海量的半结构化数据，在信息集成过程中产生了大量半结构化视图，如何利用物化半结构化视图来重写用户查询，减少响应时间成为研究热点问题，上述问题本质上是NP问题，提出了一种半结构化查询重写的新方法，该方法在保证算法正确性和完备性的基础上，利用半结构化数据特点和查询子目标之间的关系，减少了指数空间的查询重写候选方案生成，理论分析表明，它极大地降低了算法的代价。

QUERY REWRITING FOR SEMI-STRUCTURED DATA

Query rewriting is a basic problem in database research. It is closely related to the query optimizing, datawarehousing, data integrating, semantic caching, etc. At present, the data on the Internet is mostly the semi structured data , and data integration produces a lot of semi structured data views. Thus how to use semi structured views to rewrite the query so as to shorten the respond time receives more attention. And this problem is essentially an NP problem. Here a novel query rewriting approach is put forward. Compared with the traditional approaches, this approach prunes the exponential results of query rewriting plan space by using the knowledge of characteristic of semi structured data and the relation between the subgoals in the query, while the soundness and completeness of algorithm are maintained. Theoretical analysis proves that the approach greatly reduces the cost of algorithm.