Filtering techniques for rewriting XPath queries using views

In this paper, we propose several filtering techniques for rewriting XPath queries using views. The work is motivated by scenarios dealing with large quantities of queries and views, such as semantic query caching and data integration. Considerable rewriting computation could be saved if we manage to efficiently discover that, given a query Q and a view V, there does not exist a rewriting for Q using V. In contrast to O(|Q||V|) (O(|Q||V|2)) time complexity to compute an equivalent rewriting (contained rewriting) for XP {/,//,[] } , we devise linear algorithms running in O(|Q|) to filter queries for both equivalent rewriting and contained rewriting. Our filtering algorithms can be extended to support queries and views in XP {/,//,[],* } , where the equivalent (or contained) rewriting existence problem is still coNP-hard.