Concurrent executions of database transactions

Consider the database transactions listed below.
T1 T2 T3
read(x) read(y) read(z)
write(y,x+1) write(x,y+1) write(x,z+1)
commit commit write(y,z+2)
commit
Assume that the initial values of the persistent data items x, y, and z are the following.
x = 1, y = 2, and z= 3.
(1) ( 2 marks)
Show a sample concurrent execution of the transactions T1, T2, and T3 that is
nonconflict serializable and that is view serializable.

Prove, that the execution is nonconflict serializable and that it is view serializable.

When visualizing the concurrent executions use a technique of two-dimensional
diagrams presented to you during the lecture classes, for example, see a presentation
10 Introduction to Transaction Processing (1), slide 9.

(2) (2 marks)
Show a sample concurrent execution of the transactions T1, T2, and T3 that is conflict
serializable and that is not order-preserving conflict serializable.

Prove, that the execution is conflict serializable and that it is not order-preserving
conflict serializable.

When visualizing the concurrent executions use a technique of two-dimensional
diagrams presented to you during the lecture classes, for example, see a presentation
10 Introduction to Transaction Processing (1), slide 9.

(3) (2 marks)
Show a sample concurrent execution of the transactions T1, T2, and T3 that is
recoverable and that is not strict.

Prove, that the execution is recoverable and that it is not strict.

When visualizing the concurrent executions use a technique of two-dimensional
diagrams presented to you during the lecture classes, for example, see a presentation
10 Introduction to Transaction Processing (1), slide 9.

Deliverables
A file solution1.pdf with:
(1) a visualization of a sample concurrent execution of the transactions T1, T2, and T3
that is nonconflict serializable and that is view serializable and a proof that the
execution is nonconflict serializable and that it is view serializable.

(2) visualization of a sample concurrent execution of the transactions T1, T2, and T3
that is conflict serializable and that is not order-preserving conflict serializable and a
proof that the execution is conflict serializable and that it is not order-preserving
conflict serializable.

(3) visualization of a sample concurrent execution of the transactions T1, T2, and T3
that is recoverable and that is not strict and a proof that the execution is recoverable
and that it is not strict.






Task 2 (6 marks)
Serialization graph testing, 2PL, and Timestamp ordering scheduler

Consider a concurrent execution of database transactions T1, T2, and T3 such that the
execution is not controlled by any scheduler.

T1 T2 T3
read(x)
write(x,x+1)
read(y)
write(x,y+1)
read(z)
write(x,z+1)
read(z)
write(z,x+2)

(1) (2 marks)
Assume, that the transactions attempt to interleave their operations in the same way as
in the execution above. Show a sample concurrent execution of the transactions T1,
T2, and T3 that is controlled by serialization graph testing scheduler.

Draw a conflict serialization graph.

When visualizing the concurrent executions use a technique of two-dimensional
diagrams presented to you during the lecture classes, for example, see a presentation
10 Introduction to Transaction Processing (1), slide 9.

(2) (2 marks)
Assume, that the transactions attempt to interleave their operations in the same way as
in the execution above. Show a sample concurrent execution of the transactions T1,
T2, and T3 that is controlled by 2PL scheduler.

Assume, that to simplify the problem we use only a general concept of a lock and we
do not distinguish between shared locks and exclusive locks.

When visualizing the concurrent executions use a technique of two-dimensional
diagrams presented to you during the lecture classes, for example, see a presentation
10 Introduction to Transaction Processing (1), slide 9.

(3) (2 marks)
Assume, that the transactions attempt to interleave their operations in the same way as
in the execution above. Show a sample concurrent execution of the transactions T1,
T2, and T3 that is controlled by timestamp ordering scheduler.

When visualizing the concurrent executions use a technique of two-dimensional
diagrams presented to you during the lecture classes, for example, see a presentation
10 Introduction to Transaction Processing (1), slide 9.

Show the data items accessed by the transactions together with the timestamps left by
the transactions on the data items.

Deliverables
A file solution2.pdf with:
(1) visualization of a sample concurrent execution of the transactions T1, T2, and T3 that
is controlled by serialization graph testing scheduler and a conflict serialization graph,

(2) visualization of a sample concurrent execution of the transactions T1, T2, and T3 that
is controlled by 2PL scheduler,

(3) visualization of a sample concurrent execution of the transactions T1, T2, and T3 that
is controlled by timestamp ordering scheduler.