ACM SIGMOD Anthology VLDB dblp.uni-trier.de

File Allocation in Distributed Databases with Interaction between Files.

Clement T. Yu, M. K. Siu, K. Lam, C. H. Chen: File Allocation in Distributed Databases with Interaction between Files. VLDB 1983: 248-259
@inproceedings{DBLP:conf/vldb/YuSLC83,
  author    = {Clement T. Yu and
               M. K. Siu and
               K. Lam and
               C. H. Chen},
  editor    = {Mario Schkolnick and
               Costantino Thanos},
  title     = {File Allocation in Distributed Databases with Interaction between
               Files},
  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     = {248-259},
  ee        = {db/conf/vldb/YuSLC83.html},
  crossref  = {DBLP:conf/vldb/83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper, we re-examine the file allocation problem. Because of changing technology, the assumptions we use here are different from those of previous researchers. Specifically, the interaction of files during processing of queries is explicitly incorperated into our model and the cost of communication between two sites is dominated by the amount of data transfer and is independent of the receiving and the sending sites. We study the complexity of the file allocation problem using the new model. Unfortunateiy, the problem is NP-hard. We present an approach to three versions of the problem, thus demonstrating the flexibility of our approach. We further argue that our method provides a practical solution to the problem, because accurate solutions are obtained, the time complexity of our algorithms is much smaller than existing algorithms, the algorithm is conceptually simple, easy to implement and is adaptive to users' changing access patterns.

Copyright © 1983 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


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 ...

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[Aper]
Peter M. G. Apers: Redundant Allocation of Relations in a Communication Network. Berkeley Workshop 1981: 245-258 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BeCh]
Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Case]
...
[Chan ]
Shi-Kuo Chang: Data Base Decomposition in a Hierarchical Computer System. SIGMOD Conference 1975: 48-53 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Chang]
Jo-Mei Chang: A Heuristic Approach to Distributed Query Processing. VLDB 1982: 54-61 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ChLi]
...
[Chu]
...
[Codd]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Date]
...
[Date2]
...
[DoFo]
Lawrence W. Dowdy, Derrell V. Foster: Comparative Models of the File Assignment Problem. ACM Comput. Surv. 14(2): 287-313(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Eswa]
Kapali P. Eswaran: Placement of Records in a File and File Allocation in a Computer. IFIP Congress 1974: 304-307 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FiHo]
Marshall L. Fisher, Dorit S. Hochbaum: Database Location in Computer Networks. J. ACM 27(4): 718-735(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GaJo]
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
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ghos]
Sakti P. Ghosh: Distributing a Data Base with Logical Associations on a Computer Network for Parallel Searching. IEEE Trans. Software Eng. 2(2): 106-113(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Grbe]
Enrique Grapa, Geneva G. Belford: Some Theorems to Aid in Solving the File Allocation Problem. Commun. ACM 20(11): 878-882(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HaCh]
Michael Hammer, Arvola Chan: Index Selection in a Self-Adaptive Data Base Management System. SIGMOD Conference 1976: 1-8 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HaNi]
Michael Hammer, Bahram Niamir: A Heuristic Approach to Attribute Partitioning. SIGMOD Conference 1979: 93-101 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HeYa]
Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HoSe]
Jeffrey A. Hoffer, Dennis G. Severance: The Use of Cluster Analysis in Physical Data Base Design. VLDB 1975: 69-86 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KeTY]
Larry Kerschberg, Peter D. Ting, S. Bing Yao: Query Optimization in Star Computer Networks. ACM Trans. Database Syst. 7(4): 678-711(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LamY]
K. Lam, Clement T. Yu: An Approximation Algorithm for a File-Allocation Problem in a Hierarchical Distributed System. SIGMOD Conference 1980: 125-132 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LoPo]
...
[MaRi]
Samy A. Mahmoud, J. Spruce Riordon: Optimal Allocation of Resources in Distributed Information Networks. ACM Trans. Database Syst. 1(1): 66-78(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MoLe]
Howard L. Morgan, K. Dan Levin: Optimal Program and Data Locations in Computer Networks. Commun. ACM 20(5): 315-322(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rive]
Ronald L. Rivest: On Self-Organizing Sequential Search Heuristics. Commun. ACM 19(2): 63-67(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Salt]
...
[SDD1]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Thom]
Robert H. Thomas: A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Trans. Database Syst. 4(2): 180-209(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ullm]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[UrOI]
...
[Wah]
...
[Whit]
...
[YaDT]
S. Bing Yao, K. Sundar Das, Toby J. Teorey: A Dynamic Database Reorganization Algorithm. ACM Trans. Database Syst. 1(2): 159-174(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[YSLT]
...
[YuOz]
...
[YCTBL]
Clement T. Yu, C. C. Chang: On the Design of a Query Processing Strategy in a Distributed Database Environment. SIGMOD Conference 1983: 30-39 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[YLCC]
Clement T. Yu, K. Lam, C. C. Chang, S. K. Chang: Promising Approach to Distributed Query Processing. Berkeley Workshop 1982: 363-390 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:21:57 2010 by Michael Ley (ley@uni-trier.de)