Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC-SA. Authors must sign a non-exclusive distribution agreement after article acceptance.
A Methodology for Vertically Partitioning in a Multi-Relation Database Environment
Keywords:
Vertical partitioning, Database performance, Referential integrity constraints, Multi-relation databasesAbstract
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.
Downloads
Download data is not yet available.
References
[1] Ailamaki, A; Dewitt, D.J.; Hill, M.D. and Skounakis, M.,“Weaving Relations for Cache Performance,” Proceedings of the 27th VLDB Conference, 2001
[2] 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
[3] Cardenas, A.F., “Analysis and performance of inverted database structures”, Communications of the ACM 18, 5, (May 1975), 253-263.
[4] Ceri, S., Navathe, S., and Wiederhold, G., "Distribution Design of Logical Database Schemas", IEEE Trans. Soft. Eng. SE-9, 4, (July 1983)
[5] 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.
[6] Chu, P., "A Transaction-Oriented Approach to Attribute Partitioning," Information Systems, vol. 17, no. 4, 1992, pp 329-342.
[7] 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.
[8] 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)
[9] Date, C.J., An Introduction to Database Systems. Addision-Wesley Publishing Company, Sixth Edition, (1995).
[10] Ezeife, C.I., “Selecting and materializing horizontally partitioned warehouse views,” Data and Knowledge Engineering, 36, 2001, pp 185-210
[11] Elmasri, R. and Navathe S. B., Fundamentals of Database Systems, The Benjamin/ Cummings Publishing Company, Inc., Second Edition, 1994.
[12] 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.
[13] 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
[14] Gorla, N., “An Object-oriented database design for improved performance,” Data & Knowledge Engineering, 2001.
[15] 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.
[16] Hammer, M., and Niamir, B. "A Heuristic Approach to Attribute Partitioning", ACM SIGMOD International Conference on Management of Data (1979).
[17] Hoffer, J.A. and Severance, D.G. "The Use of Cluster Analysis In Physical Data Base Design", International Conference On Very large Databases (1975).
[18] Labio, W.J., Quass, D., and Adelberg, B., “Physical Database Design for Data Warehouses, IEEE Conference on Data Engineering, 1997, pp 277-288.
[19] 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.
[20] Mannino, M.V., Database Design, Application Development, and Administration. McGraw-Hill, Third Edition, 2007
[21] March, S.T. "Techniques for Structuring Database Records", ACM Computing Surveys 15, 1, 1983.
[22] 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.
[23] 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.
[24] Navathe, S and Ra, M. "Vertical Partitioning for Database Design: A graphical algorithm", Proceedings of ACM SIGMOD, 1989.
[25] 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.
[26] Ozsu, M. and Valduriez, P., Principles of Distributed Database Systems, Prentice Hall, 1996.
[27] Ramamurthy, R; Dewitt, D.J. and Su, Q., “A Case for Fractured Mirrors,” Proceedings of the 28th VLDB Conference, 2002
[28] 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.
[29] 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.
[30] 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.
[31] Wiederhold, G., File Organization for Database Design. McGraw-Hill Company, 1987.
[32] Yao, S.B. "Approximating Block Accesses in Database Organizations", CACM 20, 4,1977.
[33] Wolfson, Ouri; Jajodia, Sushil; Huang, Yixiu, “An Adaptive Data Replication Algorithm,” ACM Transactions on Database Systems, vol. 22, no. 2, June 1997.
[34] 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.
[2] 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
[3] Cardenas, A.F., “Analysis and performance of inverted database structures”, Communications of the ACM 18, 5, (May 1975), 253-263.
[4] Ceri, S., Navathe, S., and Wiederhold, G., "Distribution Design of Logical Database Schemas", IEEE Trans. Soft. Eng. SE-9, 4, (July 1983)
[5] 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.
[6] Chu, P., "A Transaction-Oriented Approach to Attribute Partitioning," Information Systems, vol. 17, no. 4, 1992, pp 329-342.
[7] 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.
[8] 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)
[9] Date, C.J., An Introduction to Database Systems. Addision-Wesley Publishing Company, Sixth Edition, (1995).
[10] Ezeife, C.I., “Selecting and materializing horizontally partitioned warehouse views,” Data and Knowledge Engineering, 36, 2001, pp 185-210
[11] Elmasri, R. and Navathe S. B., Fundamentals of Database Systems, The Benjamin/ Cummings Publishing Company, Inc., Second Edition, 1994.
[12] 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.
[13] 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
[14] Gorla, N., “An Object-oriented database design for improved performance,” Data & Knowledge Engineering, 2001.
[15] 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.
[16] Hammer, M., and Niamir, B. "A Heuristic Approach to Attribute Partitioning", ACM SIGMOD International Conference on Management of Data (1979).
[17] Hoffer, J.A. and Severance, D.G. "The Use of Cluster Analysis In Physical Data Base Design", International Conference On Very large Databases (1975).
[18] Labio, W.J., Quass, D., and Adelberg, B., “Physical Database Design for Data Warehouses, IEEE Conference on Data Engineering, 1997, pp 277-288.
[19] 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.
[20] Mannino, M.V., Database Design, Application Development, and Administration. McGraw-Hill, Third Edition, 2007
[21] March, S.T. "Techniques for Structuring Database Records", ACM Computing Surveys 15, 1, 1983.
[22] 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.
[23] 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.
[24] Navathe, S and Ra, M. "Vertical Partitioning for Database Design: A graphical algorithm", Proceedings of ACM SIGMOD, 1989.
[25] 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.
[26] Ozsu, M. and Valduriez, P., Principles of Distributed Database Systems, Prentice Hall, 1996.
[27] Ramamurthy, R; Dewitt, D.J. and Su, Q., “A Case for Fractured Mirrors,” Proceedings of the 28th VLDB Conference, 2002
[28] 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.
[29] 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.
[30] 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.
[31] Wiederhold, G., File Organization for Database Design. McGraw-Hill Company, 1987.
[32] Yao, S.B. "Approximating Block Accesses in Database Organizations", CACM 20, 4,1977.
[33] Wolfson, Ouri; Jajodia, Sushil; Huang, Yixiu, “An Adaptive Data Replication Algorithm,” ACM Transactions on Database Systems, vol. 22, no. 2, June 1997.
[34] 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.
Downloads
Published
2007-10-01
Issue
Section
Original Articles
License
How to Cite
[1]
“A Methodology for Vertically Partitioning in a Multi-Relation Database Environment”, JCS&T, vol. 7, no. 03, pp. p. 217–227, Oct. 2007, Accessed: Jan. 14, 2026. [Online]. Available: https://journal.info.unlp.edu.ar/JCST/article/view/774
