Review

This paper tackles an important, and previously unexplored problem: how to translate query predicates (constraints) as expressed against an integrated view into constraints that can be executed at the data source. The predicates may be complex boolean expressions, and there may be dependencies among terms; that is, a term may be translated differently depending on what other terms are present. The authors propose a framework in which users supply rules for mapping sets of conjunctive constraints; given these rules, and a query, their algorithm(s) can then produce an appropriate translation that minimally subsumes the original query. The translation provided by the most sophisticated algorithm has some nice properties in terms of execution time and compactness of the result as well. A facility such as presented here would make a nice addition to a mediator toolkit, or, for a system such as Garlic, as further support for wrapper writers.

(As an aside, my only complaint about the paper is that it misrepresents Garlic; Garlic does NOT process queries in CNF necessarily, and Garlic will not violate constraint dependencies when generating plans -- it pushes the complete set of relevant predicates to the wrapper, and lets the wrapper decide how to translate them. However, Garlic provides no support to the wrapper in doing that translation, so a system such as the authors propose would definitely be helpful)