Constraint Propagation for Linear Recursive Rules

There are many ways in which the query answering process for deductive databases may be optimised. Many of these methods rely on applying constraints as soon as possible, to avoid the production and later rejection of facts which are not relevant to the query. This propagation of constraints is much simpler for left-linear programs than for many others. In this paper we show how to transform right-linear and mixed-linear programs into a left-linear form, to make constraint propagation more effective. Our technique generalises the magic set transformation for linear programs; the magic set transformation can only propagate constraints of the form X = a, whereas our technique can handle arbitrary goals as constraints. 1 Introduction An important issue for deductive database systems is that of query optimization. One way of performing such optimization is to reduce the number of facts generated at each stage of the computation. One way to achieve such reductions is to exploit any const..