Multiobjective genetic algorithms for materialized view selection in OLAP data warehouses

TLDR

OLAP systems rely on materialized views to accelerate queries, but selecting an optimal set of views is a hard multi‑objective optimization problem that balances maintenance cost and query time, requiring diverse trade‑off solutions. This study investigates whether two non‑elitist multi‑objective evolutionary algorithms can effectively solve the size‑constrained view selection problem compared to a standard greedy approach. The authors apply the MOEAs with constraint handling to generate view sets and benchmark their performance against the greedy algorithm on various problem instances. The evolutionary process converges similarly to the greedy method, and the MOEAs are competitive, often producing solutions that dominate the greedy results within a reasonable time.

Abstract

On-Line Analytical Processing (OLAP) tools are frequently used in business, science and health to extract useful knowledgefrom massive databases. An important and hard optimization problem in OLAP data warehouses is the view selection problem, consisting of selecting a set of aggregate views of the data for speeding up future query processing. A common variant of the view selection problem addressed in the literature minimizes the sum of maintenance cost and query time on the view set. Converting what is inherently an optimization problem with multiple conflicting objectives into one with a single objective ignores the need and value of a variety of solutions offering various levels of trade-off between the objectives. We apply two non-elitist multiobjective evolutionary algorithms (MOEAs) to view selection under a size constraint. Our emphasis is to determine the suitability of the combination of MOEAs with constraint handling to the view selection problem, compared to a widely used greedy algorithm. We observe that the evolutionary process mimics that of the greedy in terms of the convergence process in the population. The MOEAs are competitive with the greedy on a variety of problem instances, often finding solutions dominating it in a reasonable amount of time.