Linearization-based query optimization in datalog
Dongxing Tang · 1997
Datalog, a query language, is a version of Prolog suitable for database systems. It has been shown that linear datalog programs are easier to evaluate than nonlinear datalog programs. In this work, we first consider the possibility and hardness of some special linearizations of a subclass of datalog programs, called n-linear sirups for arbitrary n. We then study the possibility of qualitatively approximating a nonlinearizable datalog predicate using a linear datalog program. Finally, we consider bow to simplify a datalog program under a set of functional dependencies (fd's). In particular, given a linear sirup and a set of fd's over EDB predicates, we study how to make the recursion in the linear sirup less intensive.