MiniCon: A scalable algorithm for answering queries using views

The problem of answering queries using views is to find efficient methods o f answering a query using a set of previously materialized views over the d atabase, rather than accessing the database relations. The problem has rece ived significant attention because of its relevance to a wide variety of da ta management problems, such as data integration, query optimization, and t he maintenance of physical data independence. To date, the performance of p roposed algorithms has received very little attention, and in particular, t heir scale up in the presence of a large number of views is unknown. We fir st analyze two previous algorithms, the bucket algorithm and the inverse-ru les algorithm, and show their deficiencies. We then describe the MiniCon al gorithm, a novel algorithm for finding the maximally-contained rewriting of a conjunctive query using a set of conjunctive views. We present the first experimental study of algorithms for answering queries using views. The st udy shows that the MiniCon algorithm scales up well and significantly outpe rforms the previous algorithms. We describe an extension of the MiniCon alg orithm to handle comparison predicates, and show its performance experiment ally. Finally, we describe how the MiniCon algorithm can be extended to the context of query optimization.