
Chapter 12: Performance Evaluation of Logic Programs 505
QSQR succeeds in restricting the set of relevant facts to the set of nodes
reachable from the query node even in the non-linear version of ancestor. It
does this at the cost of implementing the recursive control, which is a cost that
we do not understand at this stage. QSQI also succeeds in restricting the set of
relevant facts but performs a great deal of duplicate computation. The Magic
Sets algorithm uses the entire parent relation for the set of relevant facts and so
degenerates to Semi-Naive. APEX, for reasons explained below, also uses a
much larger set of relevant facts. So, althoug ...