3. Transaction Processing Consider schedules S1 and S2 below. S1: r2(X), r2(Z), r3(Y), w2(X), w2(Z), w3(Y), r1(Z), r3(X), w3(X), r1(X), r3(Z), w1(X), w3(Z), w1(Z) S2: r1(X), r1(Z), r2(Y), w2(Y), w1(X), r3(Y), w1(Z), r2(X), r3(X), r2(Z), w2(Z), r3(Z), w3(Y), w3(Z) (a) Apply the basic timestamp ordering (BTO) algorithm to schedules S1 and S2. Determine whether or not the algorithm allows the execution of the schedules, and discuss cascading rollback (if any). Hints: each operation takes one-time unit, and timestamp of each transaction is the time associated to its first operation. For example, timestamps of transactions T1, T2, and T3 in schedule S1 are 7, 1, and 3 (respectively). [20 marks] (b) Testing the serializability of S1 and S2 by serialization graph technique to prove that the successful execution of a schedule
under BTO will ensure the serializability of the schedule.
[15 marks] (c) Examine the recoverable characteristic of S1 and S2 and check if the schedules are cascadeless and/or strict schedules. Write an equivalent strict schedule if they are cascadeless and not a strict schedule. We assume that a transaction
will be committed or aborted right after its last operation.
[15 marks]
4. Deductive Database Consider a deductive database with the following rules: ANCESTOR(X, Y) :- PARENT(X, Y) ANCESTOR(X, Y) :- PARENT(X, Z), ANCESTOR(Z, Y) Notice that PARENT(X, Y) means that X, Y are human-beings and Y is the (biological) parent of X; ANCESTOR(X, Y) means that Y is the ancestor of X. Consider the following fact base: PARENT(john, steve), PARENT(john, olivia), PARENT(olivia, emma), PARENT(olivia, william). (a) Construct either a model theoretic interpretation or a proof theoretic interpretation of the above rules using the given
facts.