Data Allocation in Distributed Database Systems.

@article{DBLP:journals/tods/Apers88,
  author    = {Peter M. G. Apers},
  title     = {Data Allocation in Distributed Database Systems},
  journal   = {ACM Trans. Database Syst.},
  volume    = {13},
  number    = {3},
  year      = {1988},
  pages     = {263-304},
  ee        = {http://doi.acm.org/10.1145/44498.45063, db/journals/tods/Apers88.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The problem of allocating the data of a database to the sites of a communication network is investigated. This problem deviates from the well-known file allocation problem in several aspects. First, the objects to be allocated are not known a priori; second, these objects are accessed by schedules that contain transmissions between objects to produce the result. A model that makes it possible to compare the cost of allocations is presented, the cost can be computed for different cost functions and for processing schedules produced by arbitrary query processing algorithms.

For minimizing the total transmission cost, a method is proposed to determine the fragments to be allocated from the relations in the conceptual schema and the queries and updates executed by the users.

For the same cost function, the complexity of the data allocation problem is investigated. Methods for obtaining optimal and heuristic solutions under various ways of computing the cost of an allocation are presented and compared.

Two different approaches to the allocation management problem are presented and their merits are discussed.

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

Michel E. Adiba, Jean-Claude Chupin, Robert Demolombe, Georges Gardarin, Jean Le Bihan: Issues in Distributed Data Base Management Systems: A Technical Overview. VLDB 1978: 89-110 BibTeX

[2]

Michel E. Adiba, Bruce G. Lindsay: Database Snapshots. VLDB 1980: 86-91 BibTeX

[3]

Michel E. Adiba: Derived Relations: A Unified Mechanism for Views, Snapshots, and Distributed Data. VLDB 1981: 293-305 BibTeX

[4]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX

[5]

...

[6]

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

[7]

Peter M. G. Apers: Centralized or Decentralized Data Allocation. DDSS 1981: 101-116 BibTeX

[8]

...

[9]

Peter M. G. Apers, Alan R. Hevner, S. Bing Yao: Optimization Algorithms for Distributed Queries. IEEE Trans. Software Eng. 9(1): 57-68(1983) BibTeX

[10]

...

[11]

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

[12]

...

[13]

Stefano Ceri, Giancarlo Martella, Giuseppe Pelagatti: Optimal File Allocation for a Distributed Data Base on a Network of Minicomputers. ICOD 1980: 216-237 BibTeX

[14]

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

[15]

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

[16]

Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
BibTeX

[17]

...

[18]

...

[19]

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

[20]

Robert S. Epstein, Michael Stonebraker, Eugene Wong: Distributed Query Processing in a Relational Data Base System. SIGMOD Conference 1978: 169-180 BibTeX

[21]

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

[22]

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

[23]

Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979) BibTeX

[24]

...

[25]

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

[26]

...

[27]

...

[28]

...

[29]

...

[30]

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

[31]

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

[32]

...

[33]

...

[34]

...

[35]

...

[36]

...

[37]

James B. Rothnie Jr., Nathan Goodman: A Survey of Research and Development in Distributed Database Management. VLDB 1977: 48-62 BibTeX

[38]

Domenico Saccà, Gio Wiederhold: Database Partitioning in a Cluster of Processors. ACM Trans. Database Syst. 10(1): 29-56(1985) BibTeX

[39]

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

[40]

K. C. Toth, Samy A. Mahmoud, J. Spruce Riordon: Query Processing Strategies in a Distributed Database Architecture. DDSS 1981: 117-134 BibTeX

[41]

Benjamin W. Wah, Yao-Nan Lien: Design of Distributed Databases on Local Computer Systems with a Multiaccess Network. IEEE Trans. Software Eng. 11(7): 606-619(1985) BibTeX

[42]

Eugene Wong: Retrieving Dispersed Data from SDD-1: A System for Distributed Databases. Berkeley Workshop 1977: 217-235 BibTeX

[43]

Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984) BibTeX

[44]

Clement T. Yu, K. Lam, C. C. Chang, S. K. Chang: Promising Approach to Distributed Query Processing. Berkeley Workshop 1982: 363-390 BibTeX

Referenced by

1. 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)
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. Anna Brunstrom, Scott T. Leutenegger, Rahul Simha: Experimental Evaluation of Dynamic Data Allocation Strategies in A Distributed Database with Changing Workloads. CIKM 1995: 395-402
4. Mukesh K. Mohania, Nandlal L. Sarda: Some Issues in Design of Distributed Deductive Databases. VLDB 1994: 60-71
5. Minyoung Ra, Y.-S. Park: Data Fragmentation and Allocation for PC-Based Distributed Database Design. DASFAA 1993: 90-96
6. 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
7. Sudha Ram, Roy E. Marsten: A Model for Database Allocation Incorporating a Concurrency Control Mechanism. IEEE Trans. Knowl. Data Eng. 3(3): 389-395(1991)
8. Rex Blankinship, Alan R. Hevner, S. Bing Yao: An Iterative Method for Distributed Database Design. VLDB 1991: 389-400
9. Clement T. Yu, C. H. Chen: Adaptive Information System Design: One Query at a Time. SIGMOD Conference 1985: 280-290