Minimizing View Sets without Losing Query-Answering Power.

Chen Li, Mayank Bawa, and Jeffrey D. Ullman

Abstract

The problem of answering queries using views has been studied extensively, due to its relevance in a wide variety of data-management applications. In these applications, we often need to select a subset of views to maintain, due to limited resources. In this paper, we show that traditional query containment is not a good basis for deciding whether or not a view should be selected. Instead, we should minimize the view set without losing query-answering power. To formalize this notion, we first introduce the concept of ``p-containment.'' That is, a view set V is p-contained in another view set W, if W can answer all the queries that can be answered by V. We show that p-containment and the traditional query containment are not related; i.e., one does not imply the other. We then discuss how to minimize a view set while retaining its query-answering power. We develop the idea further by considering p-containment of two view sets with respect to a given set of queries, and consider their relationship in terms of maximally-contained rewritings of queries using the views.


bawa@cs.stanford.edu
06-12-2000