M E T U

DEPARTMENT OF COMPUTER ENGINEERING

 

C.Eng 352 - Database Management Systems

Prof. Dr. Adnan Yazıcı

Asst. Prof. Dr. Ahmet Coşar

Asst. Semra Doğandağ

Date given       : Dec 12, 2003

Date due         : Dec 22, 2003 (A302, before 17:00)

 

HOMEWORK NO 3 - Solutions

 

1. Given the following history

H = R1(x)R2(y)R3(x)W1(x)W3(y)W2(x)

 

a) Decide whether history H is view serializable or not. Show your work.

 

T1 = R1(x)W1(x)

T2 =  R2(y)W2(x)

T3 =  R3(x)W3(y)

 

There are 6 possible serial schedules. These are : T1T2T3, T1T3T2, T2T3T1, T2T1T3, T3T2T1, T3T1T2. H is view serializable if it is view-equivalent to at least one of these serial sechedules. You should show that it is not view-equivalent to any of these serial schedules. Therefore it is not view-serializable.

 

b) Decide whether history H is conflict-serializable or not. Show all conflicting operations.

 

Conflicting operations:

 

R1(X)W2(X)

R2(Y)W3(Y)

R3(X)W1(X)

R3(X)W2(X)

W1(X)W2(X)

 

T1          T2

 

 

 


T3

 

The precedence graph is cyclic, therefore the given history is not conflict serializable.

 

 

 

 


2. Given the following history

 

R1(A)R4(A)R2(B)W1(A)W2(B)R4(B)R2(C)W2(C)R3(C)R4(C)R1(B)W3(C)W1(B)

 

a)      Show whether this execution is conflict-serializable or not. 

        Conflicting operations:
 
        R4(A)W1(A)
        W2(B)R4(B)
        W2(B)R1(B)
        W2(B)W1(B)
        R2(B)W1(B)
        R4(B)W1(B)
        R2(C)W3(C)
        W2(C)R3(C)
        W2(C)W3(C)
        W2(C)R4(C)
        R4(C)W3(C)
 
        Serialization graph:
       T1         T4  
                  
 
       T2          T3 
        
 
      There is no cycle in the precedence graph so it is conflict serializable.

       

b) Show how a Strict Two-Phase Locking will execute this history. Draw the "Wait-for Graph" to indicate the transactions waiting for others and update it as necessary during execution.

 

               A              B              C              Wait-for Graph
 
R1(A)          rl1
R4(A)          rl1 rl4 
R2(B)          rl1 rl4        rl2
W1(A)          T1 waits for T4                               T1 --> T4
W2(B)          rl1 rl4        rl2 wl2
R4(B)          rl1 rl4        T4 waits for T2                T1 --> T4 --> T2
R2(C)          rl1 rl4        rl2 wl2        rl2
W2(C)          rl1 rl4        rl2 wl2        rl2 wl2
Commit T2      rl1 rl4                                       T1 --> T4
R4(B)          rl1 rl4        rl4
R3(C)          rl1 rl4        rl4            rl3
R4(C)          rl1 rl4        rl4            rl3 rl4
Commit T4      rl1                            rl3            T1
W1(A)          rl1 wl1                        rl3
R1(B)          rl1 wl1        rl1            rl3
W3(C)          rl1 wl1        rl1            rl3 wl3
Commit T3      rl1 wl1        rl1            
W1(B)          rl1 wl1        rl1 wl1
Commit T1

 

 

Result: R1(A)R4(A)R2(B)W2(B)R2(C)W2(C)R4(B)R3(C)R4(C)W1(A)R1(B)W3(C)W1(B)

 

 

 

 

 

 

 

 

 

 

 

 

 

b)      Show how a Strict Timestamp Ordering will execute this history. Show all the details.

 

TS(T1)=1

TS(T4)=2

TS(T2)=3

TS(T3)=4

 

 

ReadTS_A

WriteTS_A

ReadTS_B

WriteTS_B

ReadTS_C

WriteTS_C

 

0

0

0

0

0

0

R1(A)

1

0

0

0

0

0

R4(A)

2

0

0

0

0

0

R2(B)

2

0

3

0

0

0

W1(A)

Abort and rollback T1 because ReadTS_A > TS(T1)

 

 
W2(B)

2

0

3

3

0

0

 
R4(B)

Abort T4 because WriteTS_B > TS(T4)

 
R2(C)

2

0

3

3

3

0

W2(C)

2

0

3

3

3

0

 
Commit T2

2

0

3

3

3

3

 
R3(C)

2

0

3

3

4

3

 
R4(C)

                   T1 and T4 are aborted

 
R1(B)
 
W3(C)

2

0

3

3

4

4

 
Commit T3

2

0

3

3

4

4

 
W1(B)

T1 is aborted

 
               
T1 and T4 are aborted and will be added to the system later with new time stamps.

 

1