CSI235-Assignment 2 Solved

Task 1 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)     

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)    

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)     

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 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)      

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)      

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)      

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.

                                                                                                                                                              

 

 

 

 

             


Task 3 (6 Processing transactions at READ COMMITTED level by a snapshot isolation scheduler
 

Consider a stored PL/SQL function MAX_MIN given below.

 

CREATE OR REPLACE FUNCTION MAX_MIN ( orderkey IN NUMBER ) 

RETURN NUMBER IS  max_value NUMBER(12);  min_value NUMBER(12); 

 

BEGIN 

 SELECT MAX(L_QUANTITY * L_EXTENDEDPRICE) 

 INTO max_value 

 FROM LINEITEM 

 WHERE L_ORDERKEY = orderkey; 

 

 SELECT MIN(L_QUANTITY * L_EXTENDEDPRICE) 

 INTO min_value 

 FROM LINEITEM 

 WHERE L_ORDERKEY = orderkey; 

 

 RETURN max_value-min_value; 

END MAX_MIN; 

/ 

 

(1)      

Show a sample concurrent execution of the function at READ COMMITTED level that interleaves the operations with another transaction and such that a result returned by the function is incorrect. The operations performed by another transaction are up to you.

 

When visualizing the concurrent executions use a technique of two-dimensional diagrams presented to you during the lecture classes, for example, see a presentation 14 Transaction Processing in Oracle DBMS slide 16.

 

(2)      

Rewrite a stored function such that it can be processed at READ COMMITTED level and show how the improved function interleaves the operations with another transaction and such that a result returned by the function is always correct.

 

When visualizing the concurrent executions use a technique of two-dimensional diagrams presented to you during the lecture classes, for example, see a presentation 14 Transaction Processing in Oracle DBMS slide 16.

 

Deliverables
A file solution3.pdf with:

(1)     visualization of a sample concurrent execution of the function at READ COMMITTED level that interleaves the operations with another transaction and such that a result returned by the function is incorrect,

 

(2)     visualization of a sample concurrent execution of an improved function at READ COMMITTED level that interleaves the operations with another transaction and such that a result returned by the function is always correct.

                                                                                                                                                              

 

 

             


Task 4 (2 Deadlocks
 

Consider a stored PL/SQL function SWAP given below.

 

CREATE OR REPLACE PROCEDURE SWAP( order_key1  IN NUMBER,                                   order_key2  In NUMBER ) IS 

 

 total_price1 ORDERS.O_TOTALPRICE%TYPE;  total_price2 ORDERS.O_TOTALPRICE%TYPE; 

  

BEGIN 

 SELECT O_TOTALPRICE 

 INTO total_price1 

 FROM ORDERS 

 WHERE O_ORDERKEY = order_key1; 

 

 SELECT O_TOTALPRICE 

 INTO total_price2 

 FROM ORDERS 

 WHERE O_ORDERKEY = order_key2; 

 

 UPDATE ORDERS 

 SET O_TOTALPRICE = total_price1 

 WHERE O_ORDERKEY = order_key2; 

 

 UPDATE ORDERS 

 SET O_TOTALPRICE = total_price2 

 WHERE O_ORDERKEY = order_key1; 

 

END SWAP; 

/  

 

Show a sample concurrent execution of two transactions both processing a function SWAP, both running at READ COMMITTED level, and such that the execution leads to a deadlock.

 

When visualizing the concurrent executions use a technique of two-dimensional diagrams presented to you during the lecture classes, for example, see a presentation 14 Transaction Processing in Oracle DBMS slide 16.

 

Deliverables
A file solution4.pdf with visualization of a sample concurrent execution of two transactions both processing a function SWAP, both running at READ COMMITTED level, and such that the execution leads to a deadlock.