ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Database Partitioning in a Cluster of Processors.

Domenico Saccà, Gio Wiederhold: Database Partitioning in a Cluster of Processors. VLDB 1983: 242-247
@inproceedings{DBLP:conf/vldb/SaccaW83,
  author    = {Domenico Sacc{\`a} and
               Gio Wiederhold},
  editor    = {Mario Schkolnick and
               Costantino Thanos},
  title     = {Database Partitioning in a Cluster of Processors},
  booktitle = {9th International Conference on Very Large Data Bases, October
               31 - November 2, 1983, Florence, Italy, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1983},
  isbn      = {0-934613-15-X},
  pages     = {242-247},
  ee        = {db/conf/vldb/SaccaW83.html},
  crossref  = {DBLP:conf/vldb/83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

In a distributed database system the partitioning and allocation of the database over the processor nodes of the network is a critical aspect of database design effort. A poor distribution can lead to higher loads and hence higher costs in the nodes or in the communication network, so that the system cannot handle the required set of transactions.

We consider here a system where multiple processors are clustered at one location in order to increase the system`s processing capability. The local network used in such a system has typically a high communication bandwith but any single processor will have inadequate processing and input-output capacity to deal with the transaction load. We develop and evaluate algorithms which perform in a computationally feasible manner the design steps of partitioning and allocation of a database to the processors.

More precisely, we investigate the optimal non-redundant partitioning and allocation of a database to a number of processors nodes. Given is a set of source relations of the database and their attributes and a set of transactions which are to be executed during some period of interest. A transaction performs operations on some subset of the database. The initial network node, associated with every transaction, is not prespecified, but to be signed as part of the design.

This problem differs from the problem in destributed systems where the processors are remote from each other and, presumably, close to their users. In those systems a transaction enters a known, local processor node, and the final response is issued from that node as well. The unclustered model with local transactions has been treated previously in the literature, for instance in [Ap82] and [CNW81].

We model the content of the database as a collection of relations. The given conceptual relations may be too large to be effectively assigned to single processors. We will consider initially how the relations can be fragmented, and will then allicate those fragments to the processor nodes. The possibility that files may be fragmented is not considered in treatments of the file allocation problem, as surveyed for instance in [DoFo82].

Once the database is put into operation each transaction will access some subset of the tuples and the attributes of each original relation. In order to complete transactions which do not find their data on the same processor, a scheduling algorithm is invoked which optimizes the processing over the netword. We do not investigate this scheduling algorithm itself, but simply assume that it exists, and that we can use it in order to obtain the costs for the execution of a given transaction over a proposed database allocation for some specified but fictitious processor network.

In this presentation the following section will formulate our problem precisely. In Sec. 3 we show the intrinsic complexity of the problem, present the heuristic greedy with first-fit algorithms we propose, and prove statements about their behavior. The conclusions we draw from this work are presented in Sec. 4. Further background material, proofs, conjectures on the feasibility of the solutions, design algorithms, and evaluations can be found in [SW83].

Printed Edition

Mario Schkolnick, Costantino Thanos (Eds.): 9th International Conference on Very Large Data Bases, October 31 - November 2, 1983, Florence, Italy, Proceedings. Morgan Kaufmann 1983, ISBN 0-934613-15-X
Contents BibTeX

References

[Ap82]
...
[Casey72]
...
[Chu68]
...
[Co71]
Stephen A. Cook: The Complexity of Theorem-Proving Procedures. STOC 1971: 151-158 BibTeX
[CNW81]
...
[CODD80]
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
[DoFo82]
Lawrence W. Dowdy, Derrell V. Foster: Comparative Models of the File Assignment Problem. ACM Comput. Surv. 14(2): 287-313(1982) BibTeX
[JDUGG73]
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
[GJ79]
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
[GJS76]
M. R. Garey, David S. Johnson, Larry J. Stockmeyer: Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci. 1(3): 237-267(1976) BibTeX
[J74]
David S. Johnson: Approximation Algorithms for Combinatorial Problems. J. Comput. Syst. Sci. 9(3): 256-278(1974) BibTeX
[Kn79]
...
[MoLe77]
Howard L. Morgan, K. Dan Levin: Optimal Program and Data Locations in Computer Networks. Commun. ACM 20(5): 315-322(1977) BibTeX
[SW83]
...
[W83]
...
[WSA81]
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. Douglas W. Cornell, Philip S. Yu: Site Assignment for Relations and Join Operations in the Distributed Transaction Processing Environment. ICDE 1988: 100-108
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:19 2009