Vertical Partitioning Algorithms for Database Design.

@article{DBLP:journals/tods/NavatheCWD84,
  author    = {Shamkant B. Navathe and
               Stefano Ceri and
               Gio Wiederhold and
               Jinglie Dou},
  title     = {Vertical Partitioning Algorithms for Database Design},
  journal   = {ACM Trans. Database Syst.},
  volume    = {9},
  number    = {4},
  year      = {1984},
  pages     = {680-710},
  ee        = {http://doi.acm.org/10.1145/1994.2209, db/journals/tods/NavatheCWD84.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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.

Copyright © 1984 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

Jair M. Babad: A Record and File Partitioning Model. Commun. ACM 20(1): 22-31(1977) BibTeX

[2]

Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981) BibTeX

[3]

Stefano Ceri, Mauro Negri, Giuseppe Pelagatti: Horizontal Data Partitioning in Database Design. SIGMOD Conference 1982: 128-136 BibTeX

[4]

Stefano Ceri, Shamkant B. Navathe, Gio Wiederhold: Distribution Design of Logical Database Schemas. IEEE Trans. Software Eng. 9(4): 487-504(1983) BibTeX

[5]

Stefano Ceri, Giuseppe Pelagatti: Allocation of Operations in Distributed Database Access. IEEE Trans. Computers 31(2): 119-129(1982) BibTeX

[6]

Shi-Kuo Chang, Wu-Haung Cheng: A Methodology for Structured Database Decomposition. IEEE Trans. Software Eng. 6(2): 205-218(1980) BibTeX

[7]

Peter P. Chen, Jacky Akoka: Optimal Design of Distributed Information Systems. IEEE Trans. Computers 29(12): 1068-1080(1980) BibTeX

[8]

...

[9]

Mark J. Eisner, Dennis G. Severance: Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases. J. ACM 23(4): 619-635(1976) BibTeX

[10]

Marshall L. Fisher, Dorit S. Hochbaum: Database Location in Computer Networks. J. ACM 27(4): 718-735(1980) BibTeX

[11]

Michael Hammer, Bahram Niamir: A Heuristic Approach to Attribute Partitioning. SIGMOD Conference 1979: 93-101 BibTeX

[12]

...

[13]

Jeffrey A. Hoffer, Dennis G. Severance: The Use of Cluster Analysis in Physical Data Base Design. VLDB 1975: 69-86 BibTeX

[14]

Vincent Y. Lum, Sakti P. Ghosh, Mario Schkolnick, Robert W. Taylor, D. Jefferson, Stanley Y. W. Su, James P. Fry, Toby J. Teorey, B. Yao, D. S. Rund, B. Kahn, Shamkant B. Navathe, D. Smith, L. Aguilar, W. J. Barr, P. E. Jones: 1978 New Orleans Data Base Design Workshop Report. VLDB 1979: 328-339 BibTeX

[15]

Samy A. Mahmoud, J. Spruce Riordon: Optimal Allocation of Resources in Distributed Information Networks. ACM Trans. Database Syst. 1(1): 66-78(1976) BibTeX

[16]

Salvatore T. March, Dennis G. Severance: The Determination of Efficient Record Segmentations and Blocking Factors for Shared Data Files. ACM Trans. Database Syst. 2(3): 279-296(1977) BibTeX

[17]

...

[18]

Howard L. Morgan, K. Dan Levin: Optimal Program and Data Locations in Computer Networks. Commun. ACM 20(5): 315-322(1977) BibTeX

[19]

James B. Rothnie Jr., Philip A. Bernstein, Stephen Fox, Nathan Goodman, Michael Hammer, T. A. Landers, Christopher L. Reeve, David W. Shipman, Eugene Wong: Introduction to a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 1-17(1980) BibTeX

[20]

Mario Schkolnick: A Clustering Algorithm for Hierarchical Structures. ACM Trans. Database Syst. 2(1): 27-44(1977) BibTeX

[21]

Patricia G. Selinger, Michel E. Adiba: Access Path Selection in Distributed Database Management Systems. ICOD 1980: 204-215 BibTeX

[22]

...

[23]

...

[24]

R. Williams, Dean Daniels, Laura M. Haas, George Lapis, Bruce G. Lindsay, Pui Ng, Ron Obermarck, Patricia G. Selinger, Adrian Walker, Paul F. Wilms, Robert A. Yost: R*: An Overview of the Architecture. JCDKB 1982: 1-27 BibTeX

Referenced by

1. Surajit Chaudhuri, Vivek R. Narasayya: Index Merging. ICDE 1999: 296-303
2. Elzbieta Malinowski, Sharma Chakravarthy: Fragmentation Techniques for Distributing Object-Oriented Databases. ER 1997: 347-360
3. Chi-Wai Fung, Kamalakar Karlapalem, Qing Li: Cost-Driven Evaluation of Vertical Class Partitioning in Object-Oriented Databases. DASFAA 1997: 11-20
4. Salvatore T. March, Sangjyu Rho: Allocating Data and Operations to Nodes in Distributed Database Design. IEEE Trans. Knowl. Data Eng. 7(2): 305-317(1995)
5. John Shepherd, Banchong Harangsri, Hwee Ling Chen, Anne H. H. Ngu: A Two-Phase Approach to Data Allocation in Distributed Databases. DASFAA 1995: 380-387
6. Doron Rotem, Gerhard A. Schloss, Arie Segev: Data Allocation for Multi-Disk Databases. IEEE Trans. Knowl. Data Eng. 5(5): 882-887(1993)
7. Gultekin Özsoyoglu, Aladdin Hafez: Near-Optimum Storage Models for Nested Relations Based on Workload Information. IEEE Trans. Knowl. Data Eng. 5(6): 1018-1038(1993)
8. Minyoung Ra, Y.-S. Park: Data Fragmentation and Allocation for PC-Based Distributed Database Design. DASFAA 1993: 90-96
9. Michael Siegel, Edward Sciore, Sharon C. Salveter: A Method for Automatic Rule Derivation to Support Semantic Query Optimization. ACM Trans. Database Syst. 17(4): 563-600(1992)
10. Hong-Mei Chen Garcia, Olivia R. Liu Sheng: An Entity-Relationship-Based Methodology for Distributed Database Design: An Integrated Approach Towards Combined Logical and Distribution Designs. ER 1992: 178-193
11. Pedro I. Rivera-Vega, Ravi Varadarajan, Shamkant B. Navathe: Scheduling Data Redistribution in Distributed Databases. ICDE 1990: 166-173
12. Shamkant B. Navathe, Minyoung Ra: Vertical Partitioning for Database Design: A Graphical Algorithm. SIGMOD Conference 1989: 440-450
13. Peter M. G. Apers: Data Allocation in Distributed Database Systems. ACM Trans. Database Syst. 13(3): 263-304(1988)
14. Aladdin Hafez, Gultekin Özsoyoglu: The Partial Normalized Storage Model of Nested Relations. VLDB 1988: 100-111
15. Marc H. Scholl, H.-Bernhard Paul, Hans-Jörg Schek: Supporting Flat Relations by a Nested Relational Kernel. VLDB 1987: 137-146
16. Gio Wiederhold, Xiaolei Qian: Modeling Asynchrony in Distributed Databases. ICDE 1987: 246-250
17. Douglas W. Cornell, Philip S. Yu: A Vertical Partitioning Algorithm for Relational Databases. ICDE 1987: 30-35
18. Patrick Valduriez, Setrag Khoshafian, George P. Copeland: Implementation Techniques of Complex Objects. VLDB 1986: 101-110