Genetic algorithms based approach to database vertical partition

摘要

Vertical partition clusters attributes of a relation to generate fragments suitable for subsequent allocation over a distributed platform with the goal of improving performance. Vertical partition is an optimization problem that can resort to genetic algorithms (GA). However, the performance of the classical GA application to vertical partition as well as to similar problems such as clustering and grouping suffers from two major drawbacks—redundant encoding and non-group oriented genetic operations. This paper applies the restricted growth (RG) string Ruskey (1993) constraint to manipulate the chromosomes so that redundant chromosomes are excluded during the GA process. On RG string compliant chromosomes, the group oriented crossover and mutation become realizable. We thus propose a novel approach called Group oriented Restricted Growth String GA (GRGS-GA) which incorporates the two above features. Finally, we compare the proposed approach with a rudimental RG string based approach and a classical GA based approach. The conducted experiments demonstrate a significant improvement of GRGS-GA on partition speed and result, especially for large size vertical partition problems.