Similar articles

Abstract: Compression is an intuitive way to boost the performance of a database system. However, compared with other physical database design techniques, compression consumes large amount of CPU power. There is a trade-off between the reduction of disk access and the overhead of CPU processing. Automatic design and adaptive administration of database systems are widely demanded, and the automatic selection of compression schema to compromise the trade-off is very important. In this paper, we present a model with novel techniques to integrate a rapidly convergent agent-based evolution framework, i.e. the SWAF (SWarm Algorithm Framework), into adaptive attribute compression for relational database. The model evolutionally consults statistics of CPU load and IO bandwidth to select compression schemas considering both aspects of the trade-off. We have implemented a prototype model on Oscar RDBMS with experiments highlighting the correctness and efficiency of our techniques.

[1] Agrawal, S., Chaudhuri, S., Narasayya, V., 2000. Automated Selection of Materialized Views and Indexes for SQL Databases. 26th International Conference on Very Large Databases. Morgan Kaufmann, Cairo, p.496-505.

[2] Agrawal, S., Chaudhuri, S., Das, A., Narasayya, V., 2003. Automating Layout of Relational Databases. 19th International Conference on Data Engineering. IEEE Computer Society, Bangalore, p.607-618.

[3] Agrawal, S., Chaudhuri, S., Kollar, L., Marathe, A., Narasayya, V., Syamala, M., 2004a. Database Tuning Advisor for Microsoft SQL Server 2005. 30th International Conference on Very Large Databases. Morgan Kaufmann, Toronto, p.1110-1121.

[4] Agrawal, S., Narasayya, V., Yang, B., 2004b. Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design. ACM SIGMOD International Conference on Management of Data. ACM, Paris, p.359-370.

[5] Bäck, T., 1997. Evolutionary computation: comments on the history and current state. IEEE Transactions on Evolutionary Computation, 1(1):3-17.

[6] Brown, K.P., Mehta, M., Carey, N.J., Livny, M., 1994. Towards Automated Performance Tuning for Complex Workloads. 20th International Conference on Very Large Databases. Morgan Kaufmann, Santiago de Chile, p.72-84.

[7] Bruni, P., Naidoo, R., 1998. DB2 for OS/390 and Data Compression. IBM Redbook.

[8] Chaudhuri, S., Weikum, G., 2000. Rethinking Database System Architecture: Towards a Self-tuning RISC-style Database System. 26th International Conference on Very Large Databases. Morgan Kaufmann, Cairo, p.1-10.

[9] Chen, Z.Y., 2002. Building Compressed Database Systems. Ph.D Dissertation, Cornell University.

[10] Chen, Z.Y., Gehrke, J., Korn, F., 2001. Query Optimization in Compressed Database Systems. ACM SIGMOD International Conference on Management of Data. ACM, Santa Barbara, p.271-282.

[11] Clerc, M., Kennedy, J., 2002. The particle swarm—explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6(1):58-73.

[12] Cormack, G.V., 1985. Data compression on a database system. Communications of ACM, 28(12):1336-1342.

[13] Dorigo, M., Gambardella, L.M., 1997. Ant colonies for the traveling salesman problem. Biosystems, 43(2):73-81.

[14] Dorigo, M., Maniezzo, V., Colorni, A., 1996. The ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Csybernetics, Part B, 26(1):29-41.

[15] Dorigo, M., Gianni, D.C., Gambardella, L.M., 1999. Ant algorithms for discrete optimization. Artificial Life, 5(2):137-172.

[16] Goldstein, J., Ramakrishnan, R., Shaft, U., 1998. Compressing Relations and Indexes. 14th International Conference on Data Engineering. IEEE Computer Society, Orlando, p.370-379.

[17] Graefe, G., Shapiro, L.D., 1991. Data Compression and Database Performance. Symposium on Applied Computing. IEEE Computer Society, Kansas, p.22-27.

[18] Gray, J., Reuter, A., 1993. Transaction Processing: Concepts and Techniques. Morgan Kaufmann.

[19] Hoque, A.S.M.L., McGregor, D.R., Wilson, J., 2002. Database Compression Using an Offline Dictionary Method. 2nd International Conference on Advance in Information Systems. Springer-Verlag Heidelberg, Izmir, p.11-20.

[20] Jeffrey, A.H., Mary, P., Fred, R.M., 2002. Modern Database Management (6th Ed.). Prentice Hall.

[21] Kennedy, J., Eberhart, R., 1995. Particle Swarm Optimization. International Conference on Neural Network. Institute of Electrical and Electronics Engineers, Perth, p.1942-1948.

[22] Oracle, 2002. Table Compression in Oracle9i Release2. Oracle Technical White Paper. Available at http://www.oracle.com/technology/products/bi/pdf/o9ir2_compression_twp.pdf on 21st Feb., 2006.

[23] Roth, M.A., van Horn, M.J., 1993. Database compression. ACM SIGMOD Record, 22(3):31-39.

[24] Severance, D., 1983. A practitioner’s guide to data base compression. Information Systems, 8(1):51-62.

[25] Steve, R., 1993. Automating Physical Database Design. Ph.D Dissertation, Department of Computer Science of the Graduate School of Arts and Sciences, New York University.

[26] Steve, A.F., 1998. Foundations of Social Evolution. Princeton University Press.

[27] Storn, R., Price, K., 1997. Differential evolution―a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4):341-359.

[28] TPC, 2002. TPC Benchmark W (Web Commerce) Specification (Version 1.8). Transaction Processing Performance Council. Available at http://tpc.org/tpcw/spec/tpcw_V1.8.pdf on 21st Feb., 2006.

[29] TPC, 2005. TPC Benchmark C Standard Specification (Revision 5.6). Transaction Processing Performance Council. Available at http://tpc.org/tpcc/spec/tpcc_current.pdf on 21st Feb., 2006.

[30] Xie, X.F., Zhang, W.J., 2004. SWAF: Swarm Algorithm Framework for Numerical Optimization. In: Deb, K., Poli, R., Banzhaf, W., et al. (Eds.), Genetic and Evolutionary Computation Conference. Springer-Verlag Heidelberg, Seattle, p.238-250.

[31] Yu, X.J., Yao, X., Choi, C.H., Gou, G., 2003. Materialized view selection as constrained evolutionary optimization. IEEE Transaction on System, Man and Cybernetics, Part C, 33(4):458-467.

[32] Zhang, W.J., Xie, X.F., 2003. DEPSO: Hybrid Particle Swarm with Differential Evolution Operator. IEEE International Conference on Systems, Man and Cybernetics. IEEE Computer Society, Washington D.C., p.3816-3821.

[33] Zhang, C., Yao, X., Yang, J., 2001. An evolutionary approach to materialized view selection in a data warehouse environment. IEEE Transaction on System, Man and Cybernetics, Part C, 31(3):282-294.

[34] Zilio, D.C., Zuzarte, C., Lightstone, S., et al., 2004. Recommending Materialized Views and Indexes with IBM DB2 Design Advisor. International Conference on Autonomic Computing. New York, p.180-188.