Right-, left- and multi-linear rule transformations that maintain context information
David B. Kemp, Kotagiri Ramamohanarao, Zoltán Somogyi · 1990
We present an algorithm that takes recursive rules, predicates and queries belonging to a particular class and transforms them into rules, predicates and queries that allow efficient bottom-up computation of answers. This work extends the work presented in "Efficient evaluation of right-, left-, and multi-linear rules " by J. Naughton, R. Ramakrishnan, Y. Sagiv, and J. Ullman. Our transformation can handle calls whose input arguments are not manifest constants but are computed by other calls in the query, and it can handle predicates containing pseudo-left-linear rules together with right-linear and/or multi-linear rules. The first of those properties allows us to apply our algorithm effectively to calls to predicates that occur in the bodies of rules as well as in queries. Experimental results indicate that our algorithm can achieve considerable speedups over previous methods. 1 Introduction The past several years have seen great advances in the field of deductive databases. Much o...