**Preliminaries**

· Read Chapter 6, Sections 1 –
3.

**Prob lems**

1. A transaction is *strict two-phase locked
*if it is two-phase locked and it holds all of its write

a) For each of the fo

b) If not, what about strict
two-phase locking?

c) If not, what about ordinary
two-phase locking?

d) If not, is the history
serializable?

For (a) – (c), add lock operations to the history to
demonstrate your point. For (d) draw the serialization graph for the history.

In each history, changes from the previous history
are noted in boldface.

H_{1} = w_{0}[x,y,z] c_{0} r_{1}[x] r_{1}[y]
w_{1}[y] r_{2}[x] w_{2}[z] r_{1}[y] c_{2}
w_{1}[z] c_{1}

_{ }

H_{2} = w_{0}[x,y,z] c_{0} r_{1}[x]
r_{1}[y] w_{1}[y] r_{2}[x] w_{2}[z] r_{1}[y]
w_{1}[z] **c _{2}** c

H_{3 }= w_{0}[x,y,z] c_{0} r_{1}[x]
r_{1}[y] w_{1}[y] **r _{2}[y]**
w

_{ }

H_{4 }= w_{0}[x,y,z] c_{0} r_{1}[x]
r_{1}[y] w_{1}[y] **r _{2}[x]**

_{ }

H_{5 }= w_{0}[x,y,z] c_{0} r_{1}[x]
r_{1}[y] w_{1}[y] **r _{3}[z]**
r

2. Suppose each transaction is
a sequential program with no internal concurrency (i.e., no multi-threading).
Consider the following three transactions:

T_{1} = r_{1}[x,y] w_{1}[x] _{ }T_{2} = r_{2}[x] w_{2}[z] T_{3} = r_{3}[z] r_{3}[y]
w_{3}[y]

a) Suppose the data manager is
using two-phase locking, as in Section 6.1.4 of the textbook or slide 24 of the
lecture slides. Suppose it receives the transactions’ reads and writes in the
following sequence (i.e., the operations may execute in a different order than
this):

r_{1}[x,y]
r_{2}[x] w_{1}[x] _{ }w_{2}[z]
r_{3}[z] r_{3}[y] w_{3}[y]

The
transactions also submitted commit operations but the commits are not shown in
the above sequence. Add each transaction’s commit operation to the earliest
spot in the sequence where the data manager could have received that commit.

b) Answer the same question for
this sequence (the difference is highlighted in bold):

r_{1}[x,y]
r_{2}[x] w_{1}[x] _{ }**r _{3}[z] w_{2}[z]** r