A Two-Phase Approach to Data Allocation in Distributed Databases

John Shepherd, Banchong Harangsri, Hwee Ling Chen, Anne H.H. Ngu

Fourth International Conference on Database Systems for Advanced Applications (DASFAA'95),
Singapore, April 1995.

(Compressed Postscript ... 112KB)

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

Keys: Distributed databases, Data allocation

Recent Publications ... John Shepherd ... CSE ... UNSW