Evolutionary Algorithms for Allocating Data in Distributed Database Systems |
| |
Authors: | Ishfaq Ahmad Kamalakar Karlapalem Yu-Kwong Kwok Siu-Kai So |
| |
Affiliation: | (1) Department of Computer Science, The Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong, People's Republic of China;(2) Department of Electrical and Electronic Engineering, The University of Hong Kong, Pokfulam Road, Hong Kong, People's Republic of China |
| |
Abstract: | A major cost in executing queries in a distributed database system is the data transfer cost incurred in transferring relations (fragments) accessed by a query from different sites to the site where the query is initiated. The objective of a data allocation algorithm is to determine an assignment of fragments at different sites so as to minimize the total data transfer cost incurred in executing a set of queries. This is equivalent to minimizing the average query execution time, which is of primary importance in a wide class of distributed conventional as well as multimedia database systems. The data allocation problem, however, is NP-complete, and thus requires fast heuristics to generate efficient solutions. Furthermore, the optimal allocation of database objects highly depends on the query execution strategy employed by a distributed database system, and the given query execution strategy usually assumes an allocation of the fragments. We develop a site-independent fragment dependency graph representation to model the dependencies among the fragments accessed by a query, and use it to formulate and tackle data allocation problems for distributed database systems based on query-site and move-small query execution strategies. We have designed and evaluated evolutionary algorithms for data allocation for distributed database systems. |
| |
Keywords: | data allocation distributed database systems query processing optimal allocation mean field annealing genetic algorithm simulated evolution neighborhood search |
本文献已被 SpringerLink 等数据库收录! |
|