Abstract

With the development of databases in general and data warehouses in particular, it is now of a great importance to reduce the administration tasks of data warehouses. The materialization of views is one of the most important optimization techniques. The construction of a configuration of views optimizing the data warehouse is an NP-hard problem. On the other hand, the algorithm called extremal optimization is used to solve complex problems. In this paper, we propose a new adapted extremal optimization (AEO) for the materialized views selection problem.

References

• Bak, P., Sneppen, K.: Punctuated equilibrium and criticality in a simple model of evolution. Physical Review Letters 71(24) (1993) 4083_4086
• Bak, P., Tang, C., Wiesenfeld, K.: Self-organized criticality: An explanation of the 1/f noise. Physical Review Letters 59(4) (1987) 381_384
• S. J. Gould and N. Eldridge, Punctuated Equilibria: The Tempo and Mode of Evolution Reconsidered, Paleobiology 3, 115-151 (1977).
• S. Bocttcher and A.G. Percus, “Extremal optimization: an evolutionary local-search algorithm,” in Computational Modeling and Problem Solving in the Networked World, edited by H. M. Bhargava and N. Ye, 2003, Kluver, Boston.
• S. Bocttcher and A.G. Percus, “Extremal optimization for graph partitioning,” Physical Review E, 64(2), pp.1-13, 2001.
• S. Bocttcher and A.G. Percus, “Optimization with extremal dynamics,”complexity, 8(2), pp.57-62, 2002.
• P. Gomez-Meneses and M. Randall, “A Hybrid Extremal Optimisation Approach for the Bin Packing Problem”.
• Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA (1989).
• Boettcher, S.: Extremal optimization: Heuristics via co-evolutionary avalanches. Computing in Science and Engineering 2 (2000) 75-82.
• H.Mistry, P.Roy, S.Sudarshan, and K.Ramamritham, “Materialized view selection and maintenance using multi-query optimization,” Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, ACM Press, pp.307-318, May 2001.
• J. Darmont. Optimisation et évaluation de performance pour l’aide à la conception et à l’administration des entrepôts de données complexes. Page 6, 2007
• C. H. Choi, J. X. Yu and G. Gou, “What difference heuristic make: maintenance cost view selection revisited,” Proceedings of the third Intl. Conf. on Advances in Web-Age Information Management, Springer-Verlag.pp.313-350, Jan 2002.
• W. Y. Lin and I. C. Kuo, “A Genetic Selection algorithm for OLAP data cubes,” Knowledge and Information Systems, vol.6, pp.83-102, Feb 2004
• 14H.Gupta, “Selection of views to materialize in a data warehouse,”Proceedings of the 6th International Conference on Database Theory,Springer-Verlag,pp.98-112,January 1997
• H.Gupta and I.S.Mumick, “Selection of views to materialize under a maintenance cost constraint,” Proceedings of the 7th International Conference on Data