On the expressiveness of generalization rules for XPath query relaxation

The problem of defining suitable rewriting mechanisms for XML query languages to support approximate query an-swering has received a great deal of attention in the last few years, owing to its practical impact in several scenarios. For instance, in the typical scenario of distributed XML data without a shared data scheme, accomplishing the extraction of the information of interest often requires queries to be rewritten into relaxed ones, in order to adapt them to the schemes adopted in the different sources. In this paper, rewriting systems for a wide fragment of XPath (which is the core of several languages for manipu-lating XML data) are investigated, and a general form of rewriting rules (namely, generalization rules) is considered, which subsumes the forms adopted in the most well-known rewriting systems. Specifically, the expressiveness of rewrit-ing systems based on this form of rules is characterized: on the one hand, it is shown that rewriting systems based on generalization rules are incomplete w.r.t. containment (thus, traditional rewriting mechanisms do not suffice to rewrite a query into any more general one). On the other hand, it is also shown that the expressiveness of state-of-the-art rewrit-ing systems can be improved by employing rewriting primi-tives as simple as those traditionally used, which enable any query to be relaxed into every more general one related to it via homomorphism. Copyright 2010 ACM.