Vertical partitioning algorithms for database design
- 5 December 1984
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 9 (4), 680-710
- https://doi.org/10.1145/1994.2209
Abstract
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 transactions. Vertical partitioning is applied in three contexts: a database stored on devices of a single type, a database stored in different memory levels, and a distributed database. In a two-level memory hierarchy, most transactions should be processed using the fragments in primary memory. In distributed databases, fragment allocation should maximize the amount of local transaction processing. Fragments may be nonoverlapping or overlapping. A two-phase approach for the determination of fragments is proposed; in the first phase, the design is driven by empirical objective functions which do not require specific cost information. The second phase performs cost optimization by incorporating the knowledge of a specific application environment. The algorithms presented in this paper have been implemented, and examples of their actual use are shown.Keywords
This publication has 13 references indexed in Scilit:
- Query processing in a system for distributed databases (SDD-1)ACM Transactions on Database Systems, 1981
- Reliability mechanisms for SDD-1ACM Transactions on Database Systems, 1980
- Database Location in Computer NetworksJournal of the ACM, 1980
- The determination of efficient record segmentations and blocking factors for shared data filesACM Transactions on Database Systems, 1977
- Optimal program and data locations in computer networksCommunications of the ACM, 1977
- A record and file partitioning modelCommunications of the ACM, 1977
- An integer programming formulation of computer data base design problemsInformation Sciences, 1976
- Mathematical Techniques for Efficient Record Segmentation in Large Shared DatabasesJournal of the ACM, 1976
- Optimal allocation of resources in distributed information networksACM Transactions on Database Systems, 1976
- Problem Decomposition and Data Reorganization by a Clustering TechniqueOperations Research, 1972