A Genetic Algorithm for Database Query Optimization

Abstract

Current query optimization techniques are inadequate to support some of the emerging database applications. In this paper, we outline a database query optimization problem and describe the adaptation of a genetic algorithm to the problem. We present a method for encoding arbitrary binary trees as chromosomes and describe several crossover operators for such chromosomes. Preliminary computational comparisons with the current best--known method for query optimization indicate this to be a promising approach. In particular, the output quality and the time needed to produce such solutions is comparable to and in general better than the current method. 1 INTRODUCTION Genetic algorithms [4, 6] are becoming a widely used and accepted method for very difficult optimization problems. In this paper, we describe the implementation of a genetic algorithm (GA) for a problem in database query optimization. In order to give a careful formulation of our GA, we first give a broad outline of this parti...