Consider the Datalog program P:

T (x) e(x), T(x) a(x,y)^T(y)^b(x,z)^T(z).

1. (a) Describe, in your own words, the kind of structures that the query hT,Pi recog- nises.

2. (b) Compute the semi-naive evaluation of P for the database D with the following

   facts:

e(1) e(2) e(6) a(3, 1) a(4, 3) a(5, 3) a(7, 5) b(3, 2) b(5, 3) b(7, 6) Specify for each newly derived fact which of the rule(s) will produce it at the given

point in the derivation.