Basic TO Algorithm question
Two transactions T1 and T2. Initially RTS = 0 and WTS = 0 for data items X, Y
Timestamps are as follows: TS (T1)=10 and TS (T2)=20
T1
T2
TS(T1)=10
TS(T2)=20
1. A * 1 = Read(X)
A 1=A1-k
3. Write(X, A1)
1. A * 1 = Read(X)
2. A 1=A1^ * 1.01
3. Write(X, A1)
4. A^ 2 =R aad (V)
5. A 2=A2+k
6. Write(Y, A2)
4. A * 2 = Read(Y)
5. A 2=A2^ * 1.01
6. Write(Y, A2)
Discuss whether the following schedule is serializable or not? Justify your answer using Basic TO Algorithm.
To determine if the given schedule is serializable or not, we can use the Basic TO Algorithm.
The Basic TO Algorithm works by constructing a precedence graph, where each transaction is represented by a node and there is an edge between two nodes if a conflict exists between the two corresponding transactions. A schedule is serializable if and only if the precedence graph is acyclic.
Let's go step by step and identify the precedences and conflicts between the transactions:
Step 1:
- T1 reads X
- T2 reads X
No conflicts or precedences exist between T1 and T2 at this point.
Step 2:
- T1 writes X
- T2 writes X
There is a conflict between T1 and T2 since T1 writes X before T2 writes X.
Step 3:
- T1 reads X
- T2 reads X
There is a precedence between T2 (20) and T1 (10) since T2 has a higher timestamp than T1.
Step 4:
- T1 writes X
- T2 writes X
There is a conflict between T1 and T2 since T1 writes X before T2 writes X.
Step 5:
- T1 reads Y
- T2 reads Y
No conflicts or precedences exist between T1 and T2 at this point.
Step 6:
- T1 writes Y
- T2 writes Y
There is a conflict between T1 and T2 since T1 writes Y before T2 writes Y.
Based on the analysis above, we can construct the precedence graph as follows:
T1 (10) -> T2 (20)
As we can see, there is a cycle in the precedence graph, which means that the schedule is not serializable.
In conclusion, the given schedule is not serializable according to the Basic TO Algorithm.