A GRASP Heuristic to Optimize the Materialization of Views in the Cloud

This article studies the problem of materializing views for a database stored in a cloud, in order to improve the response time of queries on the database under a budget limit. Views are subsets of the database, also stored in the cloud, that act like caches to accelerate the access to data. In a cloud, CPU usage and data storage have to be paid, meaning that a trade-off between speed gain and storage cost has to be found. The problem has been formulated as a mixed integer program (MIP) and identified as NP-hard. To solve the problem a GRASP heuristic is proposed. The quality and speed of this algorithm are compared with the results of a MIP solver. Numerical experiments on many randomly generated instances of the problem show that the proposed approach is able to efficiently solve large instances of the problem.