Simulation for View Selection in Data Warehouse

Abstract:

On-Line Analytical Processing (OLAP) tools are frequently used in business, science and health to extract useful knowledge from 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. We apply one n Estimation of Distribution Algorithms (EDAs) to view selection under a size constraint. Our emphasis is to determine the suitability of the combination of EDAs with constraint handling to the view selection problem, compared to a widely used genetic algorithm. The EDAs are competitive with the genetic algorithm on a variety of problem instances, often finding approximate optimal solutions in a reasonable amount of time.

• Periodical: Advanced Materials Research (Volume 748)
• Pages: 1028-1032
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.748.1028
• Online since: August 2013
• Authors: Jia Chen, Hong Wei Chen, Xin Rong Hu
• Keywords: Data Warehousing, Estimation of Distribution Algorithms, OLAP, Query Optimization, View Selection

References

[1] V. Harinarayan, A. Rajaraman, and J. D. Ullman. Implementing data cubes efficiently. In Proc. SIGMOD 1996, pages 205–216, New York, NY, USA, 1996. ACM Press.

DOI: 10.1145/235968.233333

[2] Larrañaga, P. and Lozano, J.A. (2001). Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic Publisher.

[3] Wang ZQ, Zhang DX. Optimal genetic view selection algorithm under space constraint. Int'l Journal of Information Technology, 2005, 11(5): 44−51.

[4] Gorges-Schleuter, M. On the power of evolutionary optimization in the examples of ATSP and large TSP Problems. European Conference on Artificial Life. Brighton, UK, July (1997).

[5] Lin WY, Kuo IC. A genetic selection algorithm for OLAP data cubes. Knowledge and Information Systems, 2004, 6(1): 83−102.

DOI: 10.1007/s10115-003-0093-x

[6] P. Kalnis, N. Mamoulis, and D. Papadias. View selection using randomized search. J. Data Knowl. Eng., 42(1): 89–111, (2002).

DOI: 10.1016/s0169-023x(02)00045-9

[7] C. Zhang, X. Yao, and J. Yang. An evolutionary approach to materialized views selection in a datawarehouse environment. IEEE Transactions on Systems, Man and Cybernetics, Part C, 31(3): 282–294, August (2001).

DOI: 10.1109/5326.971656

[8] M. Lee and J. Hammer, Speeding upmaterialized viewselection in data warehouses using a randomized algorithm, Int. J. Cooperative Inform. Syst., vol. 10, no. 3, p.327–353, (2001).

DOI: 10.1142/s0218843001000370

[9] Yu JX. Yao X, Choi CH, Gou G. Materialized view selection as constraint evolutionary optimization. IEEE Trans. on Systems, Man and Cybernetics: Part C, 2003, 33(4): 485−467.

DOI: 10.1109/tsmcc.2003.818494

[10] H. Műhlenbein and G. Paass. From recombination of genes to the estimation of distributions I. Binary parameters. Parallel Problem Solving from Nature - PPSN IV, Berlin, pp.178-187. (1996).

DOI: 10.1007/3-540-61723-x_982

[11] A. Shukla, P. Deshpande, J.F. Naughton, and K. Ramasamy. Storage estimation for multidimensional aggregates in the presence of hierarchies. In The VLDB Journal, pages 522–531, (1996).