一种改进的基于约束关系的XML查询重写算法研究

查询重写是解决数据集成、查询优化和物理层数据独立性等问题的关键技术.以往工作主要集中在关系数据模型方面.最近Michigan大学Timber研究小组提出一种全新的基于约束的XML查询重写算法.然而,该算法未考虑存在内定谓词情况下的重写问题,应用范围受到一定限制.在原算法的重写思想基础上,提出了一种基于约束的XML查询重写的改进算法.通过引入映射规则中的约束条件,消除阻碍重写的Skolem函数,从而解决内定谓词问题,增大原算法的应用范围.证明了改进算法的正确性.性能分析和测试结果表明,改进算法并不增加实质性的性能代价.

An Extended Algorithm for Constraint-Based XML Query Rewriting

Query rewriting is one of the essential issues that are closely related to data integration, query optimization, physical data independence, etc. While most of the previous work has been focused on the cases of relational model, recently the University of Michigan's Timber Project Group presented a novel algorithm for constraint-based XML query rewriting, which can operate directly on the nested structures. However, the algorithm does not consider the problem of query rewriting with built-in predicates. Therefore its scope of application is limited. In this paper, an extension of the algorithm to solve the problem of built-in predicates' presence is proposed. The extended algorithm incorporates a concept of inferred constraints within XML mapping rules and seeks any implicit assumptions with non-Skolem functions to substitute Skolem terms within the built-in predicates after translation phase. By this means, the problem can be solved and the applicability of XML query rewriting can therefore be enhanced. It is also proved that the extended algorithm can find the maximally contained rewriting over the XML schema in the presence of built-in predicates. Both performance analysis and measurement results of the extended algorithm show that it does not incur a significant increase in the cost of performance.