Automata theory for database theoreticians

Abstract

The author describes three applications of automata theory to the optimization of database logic programs. The first application is to the analysis of predicate emptiness, the second application is to termination, and the third application is to boundedness. These examples range from the easy to the difficult. The three sections have similar structures. The author first describes the necessary automata-theoretic notions for automata on words. This is then generalized to automata on trees. Finally, the application to the analysis of Datalog programs is described.