
Chapter 12: Performance Evaluation of Logic Programs 477
V
=
V
h'^r = h
R
- h'
R9
and
Analysis
of the Query
Evaluation
Strategies
In this section, we analyze the performance of each strategy on the set of
sample queries.
Query
Form Ancestor.Μ
Rl a(X,Y):-p(X,Y).
R2 a(X,Y):-p(X,Z),a(Z,Y).
R3 query(X) :- a(john,X).
Naive
Evaluation
We begin the computation of the answer by firing Rl
(Step 1). The number of successful firings is the number of arcs in ρ (which is
the number of arcs of length 1 in the transitive closure of p). There are no suc-
cessful firings of R2 at this step since the relation α is empty. At the next step,
we fire Rl again, and