Online View Selection for the Web

Abstract

View materialization has been shown to ameliorate the scalability problem of data-intensive web servers. However, unlike data warehouses which are off-line during updates, most web servers maintain their back-end databases online and perform updates concurrently with user accesses. In such environments, the selection of views to materialize must be performed online; both performance and data freshness should be considered. In this paper, we discuss the Online View Selection problem: select which views to materialize in order to maximize performance while maintaining freshness at acceptable levels. We define Quality of Service and Quality of Data metrics and present OVIS(theta), an adaptive algorithm for the Online View Selection problem. OVIS(theta) evolves the materialization decisions to match the constantly changing access/update patterns on the Web. The algorithm is also able to identify infeasible freshness levels, effectively avoiding saturation at the server. We performed extensive experiments under various workloads, which showed that our online algorithm comes close to the optimal off-line selection algorithm. Also UMIACS-TR-2002-25