Vertical Partitioning for Database Design: A Graphical Algorithm.

Shamkant B. Navathe, Minyoung Ra: Vertical Partitioning for Database Design: A Graphical Algorithm. SIGMOD Conference 1989: 440-450
  author    = {Shamkant B. Navathe and
               Minyoung Ra},
  editor    = {James Clifford and
               Bruce G. Lindsay and
               David Maier},
  title     = {Vertical Partitioning for Database Design: A Graphical Algorithm},
  booktitle = {Proceedings of the 1989 ACM SIGMOD International Conference on
               Management of Data, Portland, Oregon, May 31 - June 2, 1989},
  publisher = {ACM Press},
  year      = {1989},
  pages     = {440-450},
  ee        = {, db/conf/sigmod/NavatheR89.html},
  crossref  = {DBLP:conf/sigmod/89},
  bibsource = {DBLP,}


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.

Copyright © 1989 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.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

James Clifford, Bruce G. Lindsay, David Maier (Eds.): Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 - June 2, 1989. ACM Press 1989 BibTeX , SIGMOD Record 18(2), June 1989

Online Edition: ACM Digital Library


[Bras 88]
[Ceri 84]
Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
Stefano Ceri, Barbara Pernici, Gio Wiederhold: Optimization problems and solution methods in the design of data distribution. Inf. Syst. 14(3): 261-272(1989) BibTeX
[Corn 87]
Douglas W. Cornell, Philip S. Yu: A Vertical Partitioning Algorithm for Relational Databases. ICDE 1987: 30-35 BibTeX
[Hoff 75]
Jeffrey A. Hoffer, Dennis G. Severance: The Use of Cluster Analysis in Physical Data Base Design. VLDB 1975: 69-86 BibTeX
[McCo 72]
[Nava 84]
Shamkant B. Navathe, Stefano Ceri, Gio Wiederhold, Jinglie Dou: Vertical Partitioning Algorithms for Database Design. ACM Trans. Database Syst. 9(4): 680-710(1984) BibTeX
[Nava 85]

Referenced by

  1. Surajit Chaudhuri, Vivek R. Narasayya: Index Merging. ICDE 1999: 296-303
  2. Marinette Savonnet, Marie-Noëlle Terrasse, Kokou Yétongnon: FRAGTIQUE: An OO Distribution Design Methodology. DASFAA 1999: 283-290
  3. Manish Mehta, David J. DeWitt: Data Placement in Shared-Nothing Parallel Database Systems. VLDB J. 6(1): 53-72(1997)
  4. Elzbieta Malinowski, Sharma Chakravarthy: Fragmentation Techniques for Distributing Object-Oriented Databases. ER 1997: 347-360
  5. Doron Rotem, Gerhard A. Schloss, Arie Segev: Data Allocation for Multi-Disk Databases. IEEE Trans. Knowl. Data Eng. 5(5): 882-887(1993)
  6. Minyoung Ra, Y.-S. Park: Data Fragmentation and Allocation for PC-Based Distributed Database Design. DASFAA 1993: 90-96
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:39:59 2009