
466 Bancilhon and Ramakrishnan
sg^(X,Y) :- p(X,XP),p(Y,YP),magic^(Y),sg^(YP,XP).
sg*(X,X) i-magic*(X).
sg^(X,X) :-magic*(X).
query.f(X) :- sg*(a,X).
The idea of the magic sets strategy was presented in Bancilhon et al.
[1986b] and the precise algorithm is described in Bancilhon et al. [1986a]. To
our knowledge, the strategy is not implemented.
Counting
and Reverse
Counting
Counting and Reverse Counting are derived from the magic sets optimization
strategy. They apply under two conditions: (i) the data is acyclic, and (ii) there
is at most one recursive rule for each predicate, and it is linear. We first
describe counting using the
*
'typical ...