|
|
|
This paper describes an algorithm for answering queries using views, based on inverse rules. Suppose you have a set of materialized views, V1, ..., Vn, and a query Q. The question is how to answer Q using only the extensions of the views.
Intuitively, inverse rules are datalog rules that compute tuples of the database relations from tuples of the views. A rewriting of the query using the views is simply the query itself composed with the inverse rules. The advantage of the algorithm is its modularity: it works even when the query is a recursive datalog program, and slight extensions handle functional dependencies on the database schema and the presence of binding-pattern limitations.
The disadvantage of inverse rules is that they cannot be used for efficient query evaluation in the form given by the algorithm. If we compute the query by first evaluating the inverse rules on the extensions of the views, and then evaluating the query on the resulting tuples of the database relations, we may end up undoing joins that have been performed already in the views, thereby losing one of the key advantages of using the views in the first place. This problem can be remedied by unfolding the inverse rules, but this may be relatively expensive. Another limitation of inverse rules is that they do not deal with interpreted comparison predicates.
Copyright © 1999 by the author(s). Review published with permission.