Query Optimization Based on the Automata Theory

The query optimization problem has been widely addressed in Relational Database Management Systems (RDBMS). Many strategies have been implemented to solve this problem including deterministic algorithms, randomized algorithms, meta-heuristic algorithms and hybrid approaches. This book provides a literature review that includes solutions to the join-ordering problem using simulated annealing, genetic algorithms and ant colony optimization. Such methodologies deeply depend on the correct configuration of various input parameters. This book also introduces a new meta-heuristic approach based on the automata theory adapted to solve the join-ordering problem. The proposed method requires only a single input parameter that facilitates its usage respect to other methods. The algorithm was embedded into PostgreSQL and compared with the genetic competitor using random and star database schemas.