A Two-Phase Approach to Data Allocation in Distributed Databases
John A. Shepherd, Banchong Harangsri, Hwee Ling Chen, Anne H. H. Ngu · 1995
In this paper, we propose a two-phase approach to the problem of optimal allocation of data objects (fragments) on a network in a distributed database system. In the first phase, we perform fragment clustering 1 , in which we form groupings of fragments that tend to be accessed together. In the second phase, we use a "divide and conquer " search technique to allocate clusters to the computing nodes (sites) in the network. We show, via complexity analysis, that the combined process of clustering and data allocation takes time that is polynomial with respect to the number of objects and sites. We also show, via experimental analysis, that our approach produces solutions that are close to optimal for a wide range of fragmentations, queries and network structures. 1 Introduction Data allocation is a critical aspect of distributed database systems: a poorly-designed data allocation can lead to inefficient computation, high access costs, and high network loads [15, 16] whereas a welldesig...