A Generalized Approach to Optimization of Relational Data Warehouses Using Hybrid Greedy and Genetic Algorithms

Published in Volume XIX, 2009, pages 25-55

Authors: G. Velinov, M. Kon Popovska, and D. Gligoroski

Abstract

As far as we know, in the open scientific literature, there is no generalized framework for the optimization of relational data warehouses which includes view and index selection and vertical view fragmentation. In this paper we are offering such a framework. We propose a formalized multidimensional model, based on relational schemas, which provides complete vertical view fragmentation and presents an approach of the transformation of a fragmented snowflake schema to a defragmented star schema through the process of denormalization.

Full Text (PDF)

References

[1] K. Aouiche, J. Darmont, O. Boussaid, F. Bentayeb. Automatic Selection of Bitmap Join Indexes in Data Warehouses. Proc. of the 7th International Conference on Data Warehousing and Knowledge Discovery, DAWAK 05. Copenhagen, Denmark, pp. 64-73, 2005.

[2] K. Aouiche, P. Jouve, J. Darmont. Clustering-Based Materialized View Selection in Data Warehouses, Proc. of the 10th East-European Conference on Advances in Databases and Information Systems, ADBIS’06. Thessaloniki, Greece, pp. 81-95, 2006.

[3] L. Bellatreche, K. Boukhalfa. An Evolutionary Approach to Schema Partitioning Selection in a Data Warehouse. Proc. of the 7th International Conference on Data Warehousing and Knowledge Discovery, DAWAK’05, Copenhagen, Denmark, pp. 115-125, 2005.

[4] L. Bellatreche, M. Schneider, H. Lorinquer, M. Mohania. Bringing Together Partitioning, Materialized Views and Indexes to Optimize Performance of Relational Data Warehouses. Proc. of the 6th International Conference on Data Warehousing and Knowledge Discovery DAWAK’04, Zaragoza, Spain, pp. 15-25, 2004.

[5] G.K.Y. Chan, Q. Li, L. Feng. Optimized Design of Materialized Views in a Real-Life Data Warehousing Environment. International Journal of Information Technology, vol. 7, no. 1, pp. 30-54, 2001.

[6] R. Chirkova, Y.A. Halevy, D. Suciu. A formal perspective on the view selection problem. Proc. of the 27th International Conference on Very Large Data Bases VLDB’02, Hong Kong, China, pp. 216 – 237, 2002.

[7] R. Elmasri, S.B. Navathe. Fundamentals of Database Systems. Fourth Edition, Addison-Wesley Publishing Company Inc., 2003.

[8] H. Gupta, V. Harinarayan, A. Rajaraman, J.D. Ullman. Index Selection for OLAP. International Conference on Data Engineering ICDE, Birmingham, England, 1997.

[9] H. Gupta, S. Mumich. Selection of Views to Materialize Under a Maintenance Cost Constraint. Proc. of the 7th International Conference on Database Theory, ICDT’99, Jerusalem, Israel, pp. 453-470, 1999.

[10] M. Golfarelli, V. Maniezzo, S. Rizzi. Materialization of fragmented views in multidimensional databases. Data & Knowledge Engineering, Volume 49, Issue 3, pp. 325-351, 2004.

[11] M.Golfarelli, S.Rizzi, E.Saltarelli. Index Selection Techniques In Data Warehouse Systems. Proc. of the International Workshop on Design and Management of Data Warehouses DMDW’02, Toronto, pp.33-42, 2002.

[12] M. Golub. Improving the Efficiency of Parallel Genetic Algorithms. Ph.D. thesis, Zagreb University, Croatia, 2001.

[13] H. Gupta, Selection And Maintenance of Views in a Data Warehouse, Ph.D. dissertation, Stanford University, USA, 1999.

[14] J. Kratica, I. Ljubic, D. Tosic. A Genetic Algorithm for the Index Selection Problem. Proc. of the Applications of Evolutionary Computing: EvoWorkshops 2003, Essex, UK, pp. 280-290, 2003.

[15] Y. Kotidis, N. Roussopoulos. DynaMat: A Dynamic View Management System for Data Warehouses. Proc. of the ACM SIGMOD International Conference on Management of Data, Philadelphia, Pennsylvania, USA, 1999.

[16] M. Lee, J. Hammer, Speeding Up Warehouse Physical Design Using A Randomized Algorithm, Proc. of the International Workshop on Design and Management of Data Warehouses DMDW’99, Heidelberg, pp.1- 9,1999.

[17] A. Tsois, N. Karayannidis, T. Sellis, D. Theodoratos. Cost-based optimization of aggregation star queries on hierarchically clustered data warehouses. Proc. of the International Workshop on Design and Management of Data Warehouses DMDW’02, Toronto, Canada, pp. 62-71, 2002.

[18] P. Vassiliadis, Formal Foundations for Multidimensional Databases (extended version). NTUA Technical Report, 1998.

[19] G. Velinov, M. Kon-Popovska, D. Gligoroski. Vertical Fragmentation in Relational Data Warehouses. Proc. of the ROSYCS 2006, Database Theory and Practice in the context of (Semantic) Web Technologies, Iasi, Romania, pp. 109-122, 2006.

[20] G. Velinov, M. Kon-Popovska, D. Gligoroski. Optimization of Relational Data Warehouses. Proc. of the 4th European Conference on Intelligent Systems and Technologies, ECIT2006, Iasi, Romania, 2006.

[21] G. Velinov, D. Gligoroski, M. Kon-Popovska. Recessive Bits in Genetic Algorithm for Some Optimization Problems in Relational Data Warehouses. Proc. of the Third International Bulgarian-Turkish Conference – Computer Science’06, Istanbul, Turkey, pp. 101-106, 2006.

[22] G. Velinov, D. Gligoroski, M. Kon-Popovska, Hybrid Greedy and Genetic Algorithms for Optimization of Relational Data Warehouses, Proc. of the 25th IASTED International Multi-Conference: Artificial intelligence and applications, Innsbruck, Austria, pp. 470-475, 2007.

[23] J.X. Yu, X. Yao, C. Choi, G. Gou. Materialized Views Selection as Constrained Evolutionary Optimization. IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews, Volume 33, No. 4, pp. 458-468, 2003.

[24] C.Zhang, X. Yao, J. Yang. An Evolutionary Approach to Materijalized Views Selection in a Data Warehouse Environment, IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews, Volume 31, No. 3, pp. 282-294, 2001.

Bibtex

@article{sacscuza:velinov2009agatoordwuhgaga,
  title={A Generalized Approach to Optimization of Relational Data Warehouses Using Hybrid Greedy and Genetic Algorithms},
  author={G. Velinov and M. Kon Popovska and D. Gligoroski},
  journal={Scientific Annals of Computer Science},
  volume={19},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2009},
  pages={25--55},
  publisher={``A.I. Cuza'' University Press}
}