Using Imperialist Competitive Algorithm for Fragment Allocation in Distributed Database Design

Fragment allocation, which is considered a major issue in distributed databases, is defined as determining the data storage location in different nodes of the network so that the cost of data communication in different network routes is minimized during execution of queries. Numbers of transactions in retrieving and updating data are two major factors in this regard. Appropriate fragment allocation must be capable of balancing the transactions for retrieving and updating data in order to optimize the overall execution cost of transactions. Considering the significance of data replication in distributed databases, it can be inferred that these two factors counteract one another, since data replication, on the one hand, increases system efficiency in execution of retrieve transactions, and on the other hand, decreases execution efficiency of synchronization transactions.Fragment allocation is an NP-complete algorithm, for which various solutions have been presented in recent years. These methods, however, are far from optimal solution in terms of cost. The model used in the present study reflects the transaction behavior in distributed databases, based on which as well as the transaction information an evolutionary algorithm known as Imperialist Competitive Algorithm (ICA) was developed to find the near-optimal allocation solution.

Keywords:

Distributed database , data fragment allocation , replication , imperialist competitive algorithm (ICA)