Une heuristique GRASP pour optimiser la matérialisation de vues dans le nuage

Cet article étudie le problème de matérialiser des vues pour une base de données stockée dans un nuage, dans le but d'améliorer le temps de réponse de requêtes sur la base de données sous une contrainte de budget. Les vues sont des sous-ensembles de la base de données, également stockées dans le nuage, qui agissent comme des caches pour accélérer l'accès aux données. Dans un nuage, l'utilisation d'unités de calcul et le stockage de données sont facturées, signifiant qu'un compromis entre le gain en vitesse et le coût de stockage doit être trouvé. Le problème a été formulé comme un programme en nombres entiers mixte (MIP) et identifié comme NP-difficile. Pour résoudre le problème, une heuristique GRASP est proposée. La qualité et la vitesse de cet algorithme sont comparées avec les résultats d'un solveur MIP. Des expérimentations numériques sur plusieurs instances du problème générées aléatoirement montrent que l'approche proposée permet de résoudre efficacement de larges instances du problème.