Database Storage & Design Chapter 20 Homework Introduction Transaction Processing Concepts And Theory Introduction Transaction Processing Concepts

Unlock access to all the studying documents.

View Full Document

Chapter 20: Introduction to Transaction Processing Concepts and Theory

CHAPTER 20: INTRODUCTION TO TRANSACTION PROCESSING CONCEPTS and

THEORY

Answers to Selected Exercises

20.14 – Change transaction T 2 in Figure 21.2b to read:

read_item(X);

X:= X+M;

if X > 90 then exit

else write_item(X);

Discuss the final result of the different schedules in Figure 21.3 (a) and (b), where M = 2 and

N = 2, with respect to the following questions. Does adding the above condition change the

final outcome? Does the outcome obey the implied consistency rule (that the capacity of X is

90)?

20.15 – Repeat Exercise 21.14 adding a check in T 1 so that Y does not exceed 90.

Answer:

T1 T2

write_item(X);

read_item(Y);

if X > 90 then exit

else write_item(X);

The above condition does not change the final outcome unless the initial value of X > 88 or

20.16 – Add the operation commit at the end of each of the transactions T 1 and T 2 from

Figure 21.2; then list all possible schedules for the modified transactions.

Determine which of the schedules are recoverable, which are cascadeless, and which are

strict.

Chapter 20: Introduction to Transaction Processing Concepts and Theory

write_item(X); write_item(X);

read_item(Y); commit T 2

In general, given m transactions with number of operations n1, n2, …, nm, the number of

possible schedules is: (n1 + n2 + … + nm)! / (n1! * n2! * … * nm!), where ! is the factorial

function. In our case, m =2 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.

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

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

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

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

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

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

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

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

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

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)

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

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

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

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

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

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

Chapter 20: Introduction to Transaction Processing Concepts and Theory

cascadeless)

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

cascadeless)

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

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

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

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

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

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

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

20.17 – List all possible schedules for transactions T 1 and T 2 from figure 21.2, and

determine which are conflict serializable (correct) and which are not.

Answer:

T 1 T 2

read_item(X); read_item(X);

X := X – N X := X + M;

The transactions can be written as follows using shorthand notation:

T 1 : r 1 (X); w 1 (X); r 1 (Y); w 1 (Y);

T 2 : r 2 (X); w 2 (X);

In this case, m =2 and n1 = 4 and n2 = 2, so the number of possible schedules is:

(4+2)! / (4! * 2!) = 6*5*4*3*2*1/ 4*3*2*1*2*1 = 15.

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

Chapter 20: Introduction to Transaction Processing Concepts and Theory

S 7 : r 1 (X); r 2 (X); w 1 (X); r 1 (Y); w 1 (Y); w 2 (X); not (conflict) serializable

S 8 : r 1 (X); r 2 (X); w 1 (X); r 1 (Y); w 2 (X); w 1 (Y); not (conflict) serializable

S 9 : r 1 (X); r 2 (X); w 1 (X); w 2 (X); r 1 (Y); w 1 (Y); not (conflict) serializable

20.18 – How many serial schedules exist for the three transactions in Figure 21.8 (a)? What

are they? What is the total number of possible schedules?

20.19 – No solution provided.

20.20 – Why is an explicit transaction end statement needed in SQL but not an explicit begin

statement?

20.21 Describe situations where each of the different isolation levels would be useful for

transaction processing.

Chapter 20: Introduction to Transaction Processing Concepts and Theory

Isolation level Repeatable Read: This isolation level is similar to Serializable except

Phantom problem may occur here. Thus, in record locking (finer granularity), this isolation

Isolation level Read Committed: In this isolation level a transaction may see two different

Isolation level Read Uncommitted: In this isolation level a transaction does not either apply

20.22 – Which of the following schedules is (conflict) serializable? For each serializable

schedule, determine the equivalent serial schedules.

(a) r1 (X); r3 (X); w1(X); r2(X); w3(X)

(b) r1 (X); r3 (X); w3(X); w1(X); r2(X)

(d) r3 (X); r2 (X); r1(X); w3(X); w1(X)

T1).

(a) This schedule is not serializable because T1 reads X (r1(X)) before T3 but T3 reads X

(r3(X)) before T1 writes X (w1(X)), where X is a common data item. The operation

r2(X) of T2 does not affect the schedule at all so its position in the schedule is irrelevant. In a

20.23 – Consider the three transactions T1, T2, and T3, and the schedules S1 and S2 given

below. Draw the serializibility (precedence) graphs for S1 and S2 and state whether each

schedule is serializable or not. If a schedule is serializable, write down the equivalent serial

schedule(s).

T1: r1(x); r1(z); w1(x)

T2: r2(z); r2(y); w2(z); w2(y)

T3: r3(x); r3(y); w3(y)

S1: r1(x); r2(z); r1(x); r3(x); r3(y); w1(x); w3(y); r2(y); w2(z); w2(y)

S2: r1(x); r2(z); r3(x); r1(z); r2(y); r3(y); w1(x); w2(z); w3(y); w2(y)

Answer:

Schedule S1: It is a serializable schedule because

• T1 only reads X (r1(X)), which is not modified either by T2 or T3,

Schedule is not a serializable schedule because

• T2 reads Y (r2(Y)), which is then read and modified by T3 (w3(Y))

• T3 reads Y (r3(Y)), which then modified before T2 modifies Y (w2(Y))

20.24 – Consider schedules S3, S4, and S5 below. Determine whether each schedule is

strict, cascadeless, recoverable, or nonrecoverable. (Determine the strictest recoverability

condition that each schedule satisfies.)

Chapter 20: Introduction to Transaction Processing Concepts and Theory

S3: r1(x); r2(z); r1(z); r3(x); r3(y); w1(x); c1; w3(y); c3; r2(y); w2(z); w2(y);c2

S4: r1(x); r2(z); r1(z); r3(x); r3(y); w1(x); w3(y); r2(y); w2(z); w2(y); c1; c2; c3;

S5: r1(x); r2(z); r3(x); r1(z); r2(y); r3(y); w1(x); w2(z); w3(y); w2(y); c3; c2;

Answer:

Strict schedule: A schedule is strict if it satisfies the following conditions:

2. Tj writes a data item X after Ti has written to X and Ti is terminated (aborted or

committed)

Schedule S3 is not strict because T3 reads X (r3(X)) before T1 has written to X (w1(X))

but T3 commits after T1. In a strict schedule T3 must read X after C1.

Schedule S4 is not cascadeless because T3 reads X (r3(X)) before T1 commits.

Schedule S5 is not cascadeless because T3 reads X (r3(X)) before T1 commits or T2

reads

Y (r2(Y)) before T3 commits.

Tj commits after Ti if Tj has read any data item written by Ti.

NOTE: Ci > Cj means Ci happens before Cj. Ai denotes abort Ti. To test if a schedule is

recoverable one has to include abort operations. Thus in testing the recoverability abort

T3 wrote X (w3(Y)) and T2 committed but T3 rolled back. Thus, T2 used non- existent value

of Y. If C1>C3>A3, then S3 is recoverable because roll back of T2 does not affect T1 and

not recoverable because T3 will restore the value of Y which was not read by T2. Strictest