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.