Database Partitioning in a Cluster of Processors.

@article{DBLP:journals/tods/SaccaW85,
  author    = {Domenico Sacc{\`a} and
               Gio Wiederhold},
  title     = {Database Partitioning in a Cluster of Processors},
  journal   = {ACM Trans. Database Syst.},
  volume    = {10},
  number    = {1},
  year      = {1985},
  pages     = {29-56},
  ee        = {http://doi.acm.org/10.1145/3148.3161, db/journals/tods/SaccaW85.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In a distributed database system the partitioning and allocation of the database over the processor nodes of the network can be a critical aspect of the database design effort. In this paper we develop and evaluate algorithms that perform this task in a computationally feasible manner. The network we consider is characterized by a relatively high communication bandwidth, considering the processing and input output capacities in its processors. Such a balance is typical if the processors are connected via busses or local networks. The common constraint that transactions have a specific root node no longer exists, so that there are more distribution choices. However, a poor distribution leads to less efficient computation, higher costs, and higher loads in the nodes or in the communication network so that the system may not be able to handle the required set of transactions.

Our approach is to first split the database into fragments which constitute appropriate units for allocation. The fragments to be allocated are selected based on maximal benefit criteria using a greedy heuristic. The assignment to processor nodes uses a first-fit algorithm. The complete algorithm, called GFF, is stated in a procedural form.

The complexity of the problem and of its candidate solutions are analyzed and several interesting relationships are proven. Alternate benefit metrics are considered, since the execution cost of the allocation procedure varies by orders of magnitude with the alternatives of benefit evaluation. A mixed benefit evaluation strategy is eventually proposed.

A model for evaluation is presented. Two of the strategies are experimentally evaluated, and the reported results support the discussion. The approach should be suitable for other cases where resources have to be allocated subject to resource constraints.

Copyright © 1985 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]

Peter M. G. Apers: Redundant Allocation of Relations in a Communication Network. Berkeley Workshop 1981: 245-258 BibTeX

[2]

...

[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]

...

[6]

E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX

[7]

Stephen A. Cook: The Complexity of Theorem-Proving Procedures. STOC 1971: 151-158 BibTeX

[8]

Lawrence W. Dowdy, Derrell V. Foster: Comparative Models of the File Assignment Problem. ACM Comput. Surv. 14(2): 287-313(1982) BibTeX

[9]

Kapali P. Eswaran: Placement of Records in a File and File Allocation in a Computer. IFIP Congress 1974: 304-307 BibTeX

[10]

M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX

[11]

M. R. Garey, David S. Johnson, Larry J. Stockmeyer: Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci. 1(3): 237-267(1976) BibTeX

[12]

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

[13]

...

[14]

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

[15]

John E. Hopcroft, Richard M. Karp: An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs. SIAM J. Comput. 2(4): 225-231(1973) BibTeX

[16]

Ellis Horowitz, Sartaj Sahni: Fundamentals of Computer Algorithms. Computer Science Press 1978
BibTeX

[17]

David S. Johnson: Approximation Algorithms for Combinatorial Problems. J. Comput. Syst. Sci. 9(3): 256-278(1974) BibTeX

[18]

David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham: Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SIAM J. Comput. 3(4): 299-325(1974) BibTeX

[19]

...

[20]

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

[21]

...

[22]

...

[23]

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. Chengwen Liu, Hao Chen: A Hash Partition Strategy for Distributed Query Processing. EDBT 1996: 373-387
2. 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
3. Erhard Rahm: Empirical Performance Evaluation of Concurrency and Coherency Control Protocols for Database Sharing Systems. ACM Trans. Database Syst. 18(2): 333-377(1993)
4. Rex Blankinship, Alan R. Hevner, S. Bing Yao: An Iterative Method for Distributed Database Design. VLDB 1991: 389-400
5. Peter M. G. Apers: Data Allocation in Distributed Database Systems. ACM Trans. Database Syst. 13(3): 263-304(1988)
6. Jonathan Bein, Roger King: MOBY: An Architecture for Distributed Expert Database Systems. VLDB 1987: 13-20
7. Giovanni Maria Sacco: Fragmentation: A Technique for Efficient Query Processing. ACM Trans. Database Syst. 11(2): 113-133(1986)