A semantic approach to optimize linear datalog programs

In this work, we present a semantic query optimization approach to improve the efficiency of the evaluation of a subset of SQL:1999 recursive queries. Using datalog notation, we can state our main contribution as an algorithm that builds a program P′ equivalent to a given program P, when both are applied over a database d satisfying a set of functional dependencies. The input program P is a linear recursive datalog program. The new program P′ has less different variables and, sometimes, less atoms in rules, thus it is cheaper to evaluate. Using coral and ibm db2, P′ is empirically shown to be more efficient than the original program.This work is partially supported by Xunta de Galicia grant PGIDIT05SIN10502PR and Ministerio de Educación y Ciencia (PGE y FEDER) grants TIC2003-06593 and TIN2006-15071-C03-03.