Ranking Approximate Query Rewritings Based on Views

International audienceThis paper considers the problem of rewriting queries using views by means of a tolerant method. The approach proposed is based on an approximate matching between the constraints from the query and those from the views, in the case where both the query and the views contain arithmetical constraints expressed as intervals. In such a context, the answers obtained are not certain anymore but only more or less probable. An algorithm which retrieves the top-k rewritings of a given query is described. Experimentations are reported, which show that the extra cost induced by the approximate nature of the rewriting process is perfectly acceptable