Consider the following set of facts for the relation parent \((X, Y),\) where
\(Y\) is the parent of \(x:\)
parent(a,aa), parent(a,ab), parent(aa,aaa), parent(aa,aab), parent(aaa,aaaa),
parent(aaa,aaab).
Consider the rules
r1: ancestor \((X, Y):-\) parent \((X, Y)\)
\(r 2:\) ancestor \((X, Y):-\) parent \((X, Z),\) ancestor \((Z, Y)\)
which define ancestor \(Y\) of \(X\) as above.
a. Show how to solve the Datalog query
ancestor \((\mathrm{aa}, \mathrm{X}) ?\)
using the naive strategy. Show your work at each step.
b. Show the same query by computing only the changes in the ancestor relation
and using that in rule 2 each time. [This question is derived from Bancilhon
and Ramakrishnan (1986).]