For this homework, I went through it completely myself several weeks ago, it will require 1 hour or so to enumerate all the possible schedules and verify them one by one to see whether it is a recoverable schedule, cascadeless schedule or strick schedule. I would suggest you to go through at least 25 schedules if 56 schedules are too many.

Given 2 transactions with number of operations n1 and n2 respectively, the number

of possible schedules is: (n1 + n2)! / (n1! * n2!), where ! is the

factorial function. In this case, i.e. this problem, and n1 = 5 and n2 = 3, so the number of possible

schedules is:

(5+3)! / (5! * 3!) = 8*7*6*5*4*3*2*1/ 5*4*3*2*1*3*2*1 = 56.

Why? It is simple, IF YOU KNOW, SUPPOSED TO KNOW, HOW TO PICK 5 POSITIONS FROM 8 POSITIONS. In case you need some refresh of this knowledge, here is a link I find for you: http://mathforum.org/library/drmath/view/56106.html

Below are four possible schedules of the 56 possible schedules, and the type of each schedule:

S 1 : r 1 (X); w 1 (X); r 1 (Y); w 1 (Y); C 1 ; r 2 (X); w 2 (X); C 2 ; strict (and hence cascadeless)

S 2 : r 1 (X); w 1 (X); r 1 (Y); w 1 (Y); r 2 (X); C 1 ; w 2 (X); C 2 ; recoverable

S 3 : r 1 (X); w 1 (X); r 1 (Y); w 1 (Y); r 2 (X); w 2 (X); C 1 ; C 2 ; recoverable

S 4 : r 1 (X); w 1 (X); r 1 (Y); w 1 (Y); r 2 (X); w 2 (X); C 2 ; C 1 ; non-recoverable

..

You will list all of the rest and point out what type of schedule each of them should be of.

S 21 : r 1 (X); r 2 (X); w 1 (X); r 1 (Y); w 1 (Y); C 1 ; w 2 (X); C 2 ; strict (and hence

cascadeless)

Why it is a strict schedule? Let us take a look at the definition for strict schedule.

A strict schedule is a schedule in which transactions can neither read nor write an item x until the last transaction that wrote X has committed ( or aborted).

To verify, we need to check all read and all wirte operations.

r1(x) is good, because before r1(x), no write to x from other transactions, here the only other transactions is transaction 2, has been made at all. So no need check whether transaction 2 has committed or not by that moment.

r2(x) is good, because before that, no write to x from other transactions, here only transaction 1, has been made. … same argument

w1(x) is good, Notice that although W2(x) writes to X, it did not get chance to write at this moment. So w1(X) is good.

r1(Y) is good, Y is only used by transaction 1.

w1(Y) is good.

W2(X) is good, this is interesting. before that, W1(X) also wrote to X and from transaction 1, but C1 committed already.

S 22 : r 1 (X); r 2 (X); w 1 (X); r 1 (Y); w 1 (Y); w 2 (X); C 1 ; C 2 ; cascadeless

Here is the definition for cascadeless: A schedule is said to be cascadeless, if every transaction in the schedule reads only items that were written by commited (or aborted) transactions.

Let me elaborate the concept using this example.

Based on the definition, we need to check all read operations. For each read operation, we need to see whether before that read is made, is there any uncommitted written to the same data item made by other transactions. If no, that read is good. Otherwise, bad.

In otherwords, If a transaction Ti read something, make sure either that if x has been written by another transaction Tj (different from Ti, showing two different transactions) before X is read by Ti, the transaction Tj has committed or no other transaction has written to X at all!

In this case, r1(x) does NOT violate the definition of cascadeless, because when transaction 1 reads x, x was not written by transaction 2. So that is fine.

r2(x) is also good for the same reason. Pay attention here, although x will be changed by transaction 1, and transaction 1 has not been committed, when r2(x) is made, that change will happen after r2(x). So r2(x) reads x written by committed transactions, because before r2(x), transaction 1 does not write to x.

How about r1(y), it is about y, that is certainly fine. So, every transaction in the schedule reads only items (we just verify all reads) that written by committed transactions.

S 50 : r 2 (X); r 1 (X); w 2 (X); C 2 ; w 1 (X); r 1 (Y); w 1 (Y); C 1 ; cascadeless

How about this one, which we had some concern in the class. Here is my justification for the conclusion.

go through all reads.

How about r2(x)? I would say r2(x) is fine, because we need to see read only items that were writeen by committed transactions. First of all, before r2(x) any written to x? No. so that is fine.

How about r1(x) ? same argument applies. that is fine.

How about r1(Y)? certainly fine.

So, if any read, it has read item that were written only by committed transactions. so it is cascadeless.

Make sure you understand the above elaboration, before you work on your homework. If you are not certain about the explanation, come to see me or email me as early as possible. You do not want to solve the problem in wrong ways.

Dear All,



the hints for 17.16 I put on the website are correct.

S50 is cascadeless. Please read my explanation, which I just added.



This part of content is theoretical, so you just try your best to work out homework and understand them. It might not be immediately useful for a programmer, but it trains your theorectial thinking. Just take it as a kind of intelligent game.  Do you best, submit your solution and we will discuss the solution together later.



You might forget the details shortly after the summer for how to solve this kind problems again, in my opinion, that is fine. But when you learn it, make sure you can do it accurately.



Go through a topic in details now, you will remember the big picture in the future, and most of cases, that might be all you need to remember and you can easily pick it up when you have to use them. However, if you stay with big picture now when you learn it, you will remember not even the big picture in the future. You do not even know where you can find the content to pick it up.



For a database related job interview, espeically for DBA or advanced db programming, knowing some concepts about transaction control, concurrent control and recovery will always be useful.



regards,

Sen Zhang

Dear all,

I just added more detailed explanation about the hints.

Make sure you understand my hints and explanation before you proceed. So, use your time efficiently.



Concentrate on the hints and 17.16, you should get it done with 1 hour.



For 17.14 and 17.15, if you have any concern, let me know. Or you just come up whatever you can, they are NOT supposed to be difficult. If you are giving out too involved solution, that might be wrong. We will discuss the solution to 14 and 15 together anyway. You should spend more than 10 minutes on 14 and 15 if you concentrate.







regards,

Sen Zhang

In both S 21 and S 50, neither T1 nor T2 reads an item that was written by
the other transaction.
The definition of strict is:
a transaction does not read nor write an item (say X) until
the transaction that last wrote the item X has committed. In S21:
S 21 : r 1 (X); r 2 (X); w 1 (X); r 1 (Y); w 1 (Y); C 1 ; w 2 (X); C 2 ;
                                            ^ ^
We need to go through every read and write operations.

For example, T2 writes X after the transaction that last wrote X (T1) has committed, so
it is strict

However, in S50:
S 50 : r 2 (X); r 1 (X); w 2 (X); C 2 ; w 1 (X); r 1 (Y); w 1 (Y); C 1
                                           ^                     ^
T2 writes X and then T1 writes X before T2 has committed, so it is not strict.

the definition of cascadeless is: A transaction does not
read an item X until the transaction that last wrote X has committed.
Since neither T1 nor T2 read an item that was previously written by the other,
S50 does not violate and is cascadeless.