CONSTRAINTS FOR QUERY OPTIMIZATION IN DEDUCTIVE DATABASES
James Harland, Kotagiri Ramamohanarao · 1992
There are many ways in which the query answering process for deductive databases may be optimised. At the heart of many of these methods is some form of constraint on the variables of the query, so that facts which are not relevant to the query are not computed. In this paper we show how fold/unfold transformations may be used to propagate some forms of constraint which are not captured by techniques such as magic sets. In particular, the fold/unfold transformation provides a straightforward way to propagate constraints involving multiple occurrence of a variable. 1 Introduction A deductive database system consists of a set of explicitly defined relations (facts in logic programming terms) and a set of Horn clause rules which define the implicit relations (rules). A query in such a system consists of a conjunction of atoms, just as in Prolog. However a major difference between Prolog and most deductive database systems is that in the latter, bottom-up execution is generally used, rath...