Translation and Optimization of Logic Queries:
the Algebraic Approach

Stefano Ceri, Georg Gottlob, Luigi Lavazza

Abstract

This paper presents an algeraic approach to translation and optimization of logic queries. We first develop a syntax-directed translation from rukes of function-free logic programs to algebraic equations; then we show solution methods for independent equations and for systems of interdependent equations. Such solutions define the operational and fixpoint semantics of function-free logic programs and queries. We also present algebraic optimization methods for "top-down" and "bottom-up" strategies; the former are useful if no initial binding is provided with the query, while the latter are useful if some arguments of the query are bounded to constant values.