Chase of recursive queries ⋆

Abstract. In this work, we present a semantic query optimization technique 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, P ′ is empirically shown to be more efficient than the original program. Keywords: Recursive queries, Semantic Query Optimization.