Partial evaluation of views

Many database applications and environments, such as mediation over heterog eneous database sources and data warehousing for decision support, lead to complex queries. Queries are often nested, defined over previously defined views, and may involve unions. There are good reasons why one might want to "remove" pieces (sub-queries or sub-views) from such queries: some sub-vie ws of a query may be effectively cached from previous queries, or may be ma terialized views; some may be known to evaluate empty, by reasoning over th e integrity constraints; and some may match protected queries, which for se curity cannot be evaluated for all users. In this paper, we present a new evaluation strategy with respect to queries defined over views, which we call tuple-tagging, that allows for an effici ent "removal" of sub-views from the query. Other approaches to this are to rewrite the query so the sub-views to be removed are effectively gone, then to evaluate the rewritten query. With the tuple tagging evaluation, no rew rite of the original query is necessary. We describe formally a discounted query (a query with sub-views marked that are to be considered as removed), present the tuple tagging algorithm for evaluating discounted queries, provide an analysis of the algorithm's perfo rmance, and present some experimental results. These results strongly suppo rt the tuple-tagging algorithm both as an efficient means to effectively re move sub-views from a view query during evaluation, and as a viable optimiz ation strategy for certain applications. The experiments also suggest that rewrite techniques for this may perform worse than the evaluation of the or iginal query, and much worse than the tuple tagging approach.