Shamkant B. Navathe
Mingyoung Ra
Abstract
Vertical partitioning is the process of subdividing the attributes of a relation or a record type, creating fragments. Previous approaches have used an iterative binary partitioning method which is based on clustering algorithms and mathematical cost functions. In this paper, however, we propose a new vertical partitioning algorithm using a graphical technique. This algorithm starts from the attribute affinity matrix by considering it as a complete graph. Then, forming a linearly connected spanning tree, it generates all meaningful fragments simultaneously by considering a cycle as a fragment. We show its computational superiority. It provides a cleaner alternative without arbitrary objective functions and provides an improvement over our previous work on vertical partitioning.
- Bras 88 Brassard, G., and Bratley, P., Algorithmics: Theory & Practice, Prentice Hall, 1988. Google Scholar
Digital Library
- Ceri 84 Ceri, S., and Pelagatti, G., Distributed Databases: Pn'nciples and Systems, McGraw Hill, 1984. Google ScholarDigital Library
- Ceri 88 Ceri, S., Pernici, B., and Wiederhold, G., "Optimization Problems and Solution Methods in the Design of Data Distribution," Working Paper, Stanford University, 1988.Google Scholar
- Corn 87 Cornell, D., and Yu, P. S., "A Vertical Partitioning Algorithm for Relational Databases," Proc. Third International Conference on Data Engineering, Feb. 1987. Google ScholarDigital Library
- Hoff 75 Hoffer, J. A., and Severance, D. G., "The Use of Cluster Analysis in Physical Database Design," Proa First International Conference on Very Large Data Bases, 1975.Google Scholar
- McCo 72 McCormick, W. T., Schweitzer, P. J., and White, T. W., "Problem Decomposition and Data Reorganization by a Clustering Technique," Operations Research, 20, Sep. 1972.Google Scholar
- Nava 84 Navathe, S. B., Ceri, S., Wiederhold, G., and Dou, J., "Vertical Partitioning Algorithms for Database Design," ACM Trans. on Database Systems, Vol. 9, No. 4, Dec. 1984. Google ScholarDigital Library
- Nava 85 Navathe, S. B., and Ceri, S., "A Comprehensive Approach to Fragmentation and Allocation of Data in Distributed Databases," IEEE Tutorial on Distn'buted Database Management, (Larson,J.A., and Rahimi,S., eds), 1985.Google Scholar
Index Terms
- Vertical partitioning for database design: a graphical algorithm
Recommendations
Vertical partitioning algorithms for database design
This paper addresses the vertical partitioning of a set of logical records or a relation into fragments. The rationale behind vertical partitioning is to produce fragments, groups of attribute columns, that “closely match” the requirements of ...
Integrating vertical and horizontal partitioning into automated physical database design
SIGMOD '04: Proceedings of the 2004 ACM SIGMOD international conference on Management of dataIn addition to indexes and materialized views, horizontal and vertical partitioning are important aspects of physical design in a relational database system that significantly impact performance. Horizontal partitioning also provides manageability; ...
Vertical partitioning for database design: a graphical algorithm
SIGMOD '89: Proceedings of the 1989 ACM SIGMOD international conference on Management of dataVertical partitioning is the process of subdividing the attributes of a relation or a record type, creating fragments. Previous approaches have used an iterative binary partitioning method which is based on clustering algorithms and mathematical cost ...
Comments