Allocating Fragments in Distributed Databases

Authors: Syam Menon, University of Texas.

Complete Citation

• Syam Menon. Allocating Fragments in Distributed Databases. IEEE Transactions on Parallel and Distributed Systems, 16(7), 2005.

Abstract

For a distributed database system to function efficiently, the fragments of the database need to be located judiciously at various sites across the relevant communications network. The problem of allocating these fragments to the most appropriate sites is a difficult one to solve, however, with most approaches available relying on heuristic techniques. Optimal approaches are usually based on mathematical programming, and formulations available for this problem are based on the linearization of nonlinear binary integer programs and have been observed to be ineffective except on very small problems. This paper presents new integer programming formulations for the nonredundant version of the fragment allocation problem. This formulation is extended to address problems which have both storage and processing capacity constraints; the approach is observed to be particularly effective in the presence of capacity restrictions. Extensive computational tests conducted over a variety of parameter values indicate that the reformulations are very effective even on relatively large problems, thereby reducing the need for heuristic approaches.

Annotations

The authors describe a nonlinear model to optimize the placement of database fragments in a distributed system.

Considers cost contributions from:

• Data retrievals;
• Updates;
• Storage;
• Collecting fragments;
• Inter-remote-site communication.

Observations:

• Easier to handle more sites than more fragments: "it takes more time to solve a problem with 15 fragments and 10 sites than a problem with five fragments and 30 sites."
• The new approach gives better timing results, especially for large numbers of fragments.

Note that only simulation results are given, this is not based on a real distributed database.

Tags: Distributed databases, nonredundant allocation, reformulation.

Related Work

How does one fragment a database?

• D. Shin and K. Irani. Fragmenting Relations Horizontally Using a Knowledge-Based Approach.
• S. Navathe, S. Ceri, G. Weiderhold, and J. Dou. Vertical Partitioning Algorithms for Database Design.
• M. Ozsu and P. Valduriez, Principles of Distributed Database Systems.

-- JustinWozniak - 08 Aug 2007