A Materialized-View Based Technique to Optimize Progressive Queries via Dependency Analysis

Abstract

Progressive queries (PQ) are a new type of query emerging from numerous contemporary database applications, including e-commerce, social network, business intelligence, and decision support. Such a PQ is formulated in several steps via a set of inter-related step-queries (SQ). How to optimize such PQs represents a new challenge in the development of a database management system. In our previous work, we introduced a materialized-view based technique to process a special type of PQ, called monotonic linear PQs. In this paper, we present a new materialized-view based technique to efficiently process generic PQs. This technique allows an SQ in a given PQ to utilize the results of previous SQs not only from the same PQ but also from other in-process and completed PQs. Due to the storage constraint, it is impossible to retain the results of all the SQs of a completed PQ. Hence, a crucial issue is how to select popular SQs from completed PQs to keep their results as materialized views for optimizing future PQs. To tackle this issue, we introduce a multiple query dependency graph (MQDG) to capture the data source dependency relationships among SQs from multiple PQs. We then present a model to estimate the benefit of an SQ in the MQDG and discuss a procedure to choose critical SQs in the MQDG for materializing their results. The strategies for constructing the MQDG and maintaining the set of materialized views are also suggested. Experimental results demonstrate that our technique is quite promising in efficiently processing PQs.