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
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
References
- [Aper]
- Peter M. G. Apers:
Redundant Allocation of Relations in a Communication Network.
Berkeley Workshop 1981: 245-258
- [BeCh]
- Philip A. Bernstein, Dah-Ming W. Chiu:
Using Semi-Joins to Solve Relational Queries.
J. ACM 28(1): 25-40(1981)
- [Case]
- ...
- [Chan ]
- Shi-Kuo Chang:
Data Base Decomposition in a Hierarchical Computer System.
SIGMOD Conference 1975: 48-53
- [Chang]
- Jo-Mei Chang:
A Heuristic Approach to Distributed Query Processing.
VLDB 1982: 54-61
- [ChLi]
- ...
- [Chu]
- ...
- [Codd]
- E. F. Codd:
A Relational Model of Data for Large Shared Data Banks.
Commun. ACM 13(6): 377-387(1970)
- [Date]
- ...
- [Date2]
- ...
- [DoFo]
- Lawrence W. Dowdy, Derrell V. Foster:
Comparative Models of the File Assignment Problem.
ACM Comput. Surv. 14(2): 287-313(1982)
- [Eswa]
- Kapali P. Eswaran:
Placement of Records in a File and File Allocation in a Computer.
IFIP Congress 1974: 304-307
- [FiHo]
- Marshall L. Fisher, Dorit S. Hochbaum:
Database Location in Computer Networks.
J. ACM 27(4): 718-735(1980)
- [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
- [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)
- [Grbe]
- Enrique Grapa, Geneva G. Belford:
Some Theorems to Aid in Solving the File Allocation Problem.
Commun. ACM 20(11): 878-882(1977)
- [HaCh]
- Michael Hammer, Arvola Chan:
Index Selection in a Self-Adaptive Data Base Management System.
SIGMOD Conference 1976: 1-8
- [HaNi]
- Michael Hammer, Bahram Niamir:
A Heuristic Approach to Attribute Partitioning.
SIGMOD Conference 1979: 93-101
- [HeYa]
- Alan R. Hevner, S. Bing Yao:
Query Processing in Distributed Database Systems.
IEEE Trans. Software Eng. 5(3): 177-187(1979)
- [HoSe]
- Jeffrey A. Hoffer, Dennis G. Severance:
The Use of Cluster Analysis in Physical Data Base Design.
VLDB 1975: 69-86
- [KeTY]
- Larry Kerschberg, Peter D. Ting, S. Bing Yao:
Query Optimization in Star Computer Networks.
ACM Trans. Database Syst. 7(4): 678-711(1982)
- [LamY]
- K. Lam, Clement T. Yu:
An Approximation Algorithm for a File-Allocation Problem in a Hierarchical Distributed System.
SIGMOD Conference 1980: 125-132
- [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)
- [MoLe]
- Howard L. Morgan, K. Dan Levin:
Optimal Program and Data Locations in Computer Networks.
Commun. ACM 20(5): 315-322(1977)
- [Rive]
- Ronald L. Rivest:
On Self-Organizing Sequential Search Heuristics.
Commun. ACM 19(2): 63-67(1976)
- [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)
- [Thom]
- Robert H. Thomas:
A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases.
ACM Trans. Database Syst. 4(2): 180-209(1979)
- [Ullm]
- Jeffrey D. Ullman:
Principles of Database Systems, 2nd Edition.
Computer Science Press 1982, ISBN 0-914894-36-6
- [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)
- [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
- [YLCC]
- Clement T. Yu, K. Lam, C. C. Chang, S. K. Chang:
Promising Approach to Distributed Query Processing.
Berkeley Workshop 1982: 363-390
Copyright © Tue Mar 16 02:21:57 2010
by Michael Ley (ley@uni-trier.de)