Finding irredundant contained rewritings of tree pattern queries using views

Abstract

Contained rewriting and maximal contained rewriting of tree pattern queries using views have been studied recently for the class of tree patterns involving /, //, and []. Given query Q and view V, it has been shown that a contained rewriting of Q using V can be obtained by finding a useful embedding of Q in V. However, for the same Q and V, there may be many useful embeddings and thus many contained rewritings. Some of the useful embeddings may be redundant in that the rewritings obtained from them are contained in those obtained from other useful embeddings. Redundant useful embeddings are useless and they waste computational resource. Thus it becomes important to identify and remove them. In this paper, we show that the criteria for identifying redundant useful embeddings given in a previous work are neither sufficient nor necessary. We then present some useful observations on the containment relationship of rewritings, and based on which, a heuristic algorithm for removing redundant useful embeddings. We demonstrate the efficiency of our algorithm using examples.