Distributed database design—Optimization vs feasibility

摘要

This paper is concerned with the problem of optimal assignment of data to sites in a distributed relational database. It is shown that in general the optimal allocation will require exponential time in terms of the input. Several heuristic algorithms that can be applied to various constraints and which provide feasible, near optimal results, as well as a model that determines the “best” assignment for a given input out of several optimal and near optimal assignments have been developed. The model is shown to be efficient, to require polynomial time, to be practical in terms of feasible inputs and to achieve assignments with near minimal global and local costs.