A Methodology for Vertically Partitioning in a Multi-Relation Database Environment
Keywords:Vertical partitioning, Database performance, Referential integrity constraints, Multi-relation databases
Vertical partitioning, in which attributes of a relation are assigned to partitions, is aimed at improving database performance. We extend previous research that is based on a single relation to multi-relation database environment, by including referential integrity constraints, access time based heuristic, and a comprehensive cost model that considers most transaction types including updates and joins. The algorithm was applied to a real-world insurance CLAIMS database. Simulation experiments were conducted and the results show a performance improvement of 36% to 65% over unpartitioned case. Application of our method for small databases resulted in partitioning schemes that are comparable to optimal.
 Baiao, F; Mattoso, M and Zaverucha, G., “A Distribution Design Methodology for Object DBMS,” Journal of Distributed and Parallel Databases, 16 (6), 2004, 45-90
 Cardenas, A.F., “Analysis and performance of inverted database structures”, Communications of the ACM 18, 5, (May 1975), 253-263.
 Ceri, S., Navathe, S., and Wiederhold, G., "Distribution Design of Logical Database Schemas", IEEE Trans. Soft. Eng. SE-9, 4, (July 1983)
 Cheng, C-H; Lee, W-K; Wong, K-F, “A Genetic Algorithm-Based Clustering Approach for Database Partitioning,” IEEE Transactions on Systems, Man, and Cybernetics, 32(3), 2002, 215-230.
 Chu, P., "A Transaction-Oriented Approach to Attribute Partitioning," Information Systems, vol. 17, no. 4, 1992, pp 329-342.
 Chu, W. W. and Ieong, I.T., "A Transaction-Based Approach to Vertical Partitioning for Relational Database Systems", IEEE Transactions on Software Engineering, 19-9, August 1993.
 Cornell, D.W. and Yu, P.S., "An Effective Approach to Vertical Partitioning for Physical Design of Relational Databases", IEEE Transactions on Software Engineering, 16-2, (Feb 1990)
 Date, C.J., An Introduction to Database Systems. Addision-Wesley Publishing Company, Sixth Edition, (1995).
 Ezeife, C.I., “Selecting and materializing horizontally partitioned warehouse views,” Data and Knowledge Engineering, 36, 2001, pp 185-210
 Elmasri, R. and Navathe S. B., Fundamentals of Database Systems, The Benjamin/ Cummings Publishing Company, Inc., Second Edition, 1994.
 Fung, C-w; Karlapalem, K. and Li, Q., “An Evaluation of Vertical Class Partitioning for Query Processing in Object-Oriented Databases,” IEEE Transactions on Knowledge and Data Engineering, 14(5), 2002, 1095-1118.
 Furtado, C; Lima, A.A.B.; Pacitti, E; Valduriez, P. and Mattoso, M., “Physical and virtual partitioning in OLAP database cluster,” 17th International Symposium on Computer Architecture and High Performance Computing, 2005, pp 143-150
 Gorla, N., “An Object-oriented database design for improved performance,” Data & Knowledge Engineering, 2001.
 Gorla, N. and Liu, C., “FHIN: an efficient storage structure and access methods for object-oriented databases,” Information and Software Technology, vol. 41, 1999, pp. 673-688.
 Hammer, M., and Niamir, B. "A Heuristic Approach to Attribute Partitioning", ACM SIGMOD International Conference on Management of Data (1979).
 Hoffer, J.A. and Severance, D.G. "The Use of Cluster Analysis In Physical Data Base Design", International Conference On Very large Databases (1975).
 Labio, W.J., Quass, D., and Adelberg, B., “Physical Database Design for Data Warehouses, IEEE Conference on Data Engineering, 1997, pp 277-288.
 Lim, S-J and Ng, Y-K, “Vertical Fragmentation and Allocation in Distributed Deductive Database Systems,” Information Systems, vol. 22, No. 1, 1997, pp 1-24.
 Mannino, M.V., Database Design, Application Development, and Administration. McGraw-Hill, Third Edition, 2007
 March, S.T. "Techniques for Structuring Database Records", ACM Computing Surveys 15, 1, 1983.
 March, S.T. and Rho, S., “Allocating Data and Operations to Nodes in Distributed Database Design,” IEEE Trans on Knowledge and Data Engineering, vol. 7, no. 2., 1995, pp 305-317.
 Navathe, S., Ceri, S., Wiederhold, G., and Dou, J. "Vertical Partitioning Algorithms for Database Design", ACM Trans. Database Syst. 9, 4 (Dec. 1984). 680-710.
 Navathe, S and Ra, M. "Vertical Partitioning for Database Design: A graphical algorithm", Proceedings of ACM SIGMOD, 1989.
 Ng, V; Gorla, N.; Law, D.M. and Chan, C.K., "Applying Genetic Algorithms in Database Partitioning,” Proceedings of the 2003 ACM Symposium on Applied Computing (SAC) 2003, pp 544-549.
 Ozsu, M. and Valduriez, P., Principles of Distributed Database Systems, Prentice Hall, 1996.
 Ramamurthy, R; Dewitt, D.J. and Su, Q., “A Case for Fractured Mirrors,” Proceedings of the 28th VLDB Conference, 2002
 Song, S.K. and Gorla, N., “A genetic Algorithm for Vertical Fragmentation and Access Path Selection,” The Computer Journal, vol. 45, no. 1, 2000, pp 81-93.
 Stonebraker, M., Aoki,P.M., Litwin, W. and Olson, M., "Mariposa: A Architecture for Distributed Data," 10th International Conference on Data Engineering, 1994, pp 54-65.
 Tamhankar, A.J. and Ram, S., “Database Fragmentation and Allocation: An Integrated Methodology and Case Study,” IEEE Trans on Systems, Man, and Cybernetics – Part A, May 1998, pp 288-305.
 Wiederhold, G., File Organization for Database Design. McGraw-Hill Company, 1987.
 Yao, S.B. "Approximating Block Accesses in Database Organizations", CACM 20, 4,1977.
 Wolfson, Ouri; Jajodia, Sushil; Huang, Yixiu, “An Adaptive Data Replication Algorithm,” ACM Transactions on Database Systems, vol. 22, no. 2, June 1997.
 Yu, P.S., Chen, M-S, Heiss, H-U, and Lee, Sukho, "On Workload Characterization of Relational Database Environments," IEEE Trans. Software Engineering, vol.18, no. 4, April 1992, pp 347-355.