Hello friends! This is a another article about database transactions. So today we will discuss about transaction schedules in DBMS. Therefore without wasting time we will start about transaction schedule and serializability. Please go through the whole article then you can learn about it well.
Topics for today
Today we are going to discuss several sub topics under this topic. Here we discuss different transaction schedules. What is serializability schedule. What is serial and non serial schedule. How do you identify conflict serializability in transaction. What is serializability in DBMS. These things we will discuss today. What is conflict and view serializability. What do you mean by serial and serializable schedule. We will discuss this one too. Keep reading to the end. You can learn many.
Transaction schedule definition
Firstly let’s see what is transaction schedule or history meaning. Apart of schedule we can also known it as transaction history. The order of the executing operations in a transaction we can identify as a transaction schedule. There are three type of transaction schedules we have to know. What are the types of serializability. So they are serial schedule, non – serial schedule, serializable schedule. Now let’s see what are those things.
Transaction Schedule – Serial Schedule
Now we know a transaction schedule is an order that operations in a transaction is going to execute. Then what is serial? Can you build some definition from your own by looking at word serial. What is the meaning of word serial? Serial means it is linear. Not overlapping. You know in a transaction there can be starting 1 to so many operations. If those operations are executing one after another we can call it as a serial schedule. A transaction schedule where operations executes in a linear way.
Now you know what is serial schedule. Can you build the definition or idea of other two since you know what is a serial schedule. So can you? Just give a try.
Transaction Schedule – Non – Serial Schedule
A serial schedule means a schedule where operations execute in linear manner. So non means the opposite of it. What is the opposite? A Transaction schedule where operations are not executing in the linear way. They execute in mixed way. Not waiting to complete upper operation. Interleaving operations are allowed.
Serializable Schedule
Now we know what is serial schedule and what is non – serial schedule. When we think about the execution in serial schedule there we cannot find issues. Do you remember the concurrency problems that we learned earlier? Here is the article if you don’t know. Read the article and come back to this one. Concurrency issues. So When operations execute in parallel or mixed way transaction face those issues. The databases can lead to lose the inconsistency and accuracy of a database. So allowing transactions to work parallelly is good but it can cause these type of matters. Then what we can do? If we can rearrange the transaction schedule to not to have those five concurrency problems and yet make it execute as a parallelly one. So that’s what we do in serializable schedule.
We are finding a non – serial schedule and if that schedule can convert as how a serial schedule works. So that type of a schedule we call as a serializable schedule. A schedule can able to be serial. How we can identify or how we know this is a serializable schedule. The method is finding whether it’s serializability. So now we will learn about serializability.
Serializability
There are two serializability. They are,
- View serializability
- Conflict serializability
A schedule can be view serializable if the schedule is view equivalent. A schedule can be conflict serializable if the schedule is conflict equivalent. Now let’s see what is view equivalent and conflict equivalent.
View Equivalent transaction schedules
A schedule can be view equivalent if that schedule meet these three criteria.
- Initial read
- Updated read
- Final write
Initial read
Initial read of both schedules are same. Then we can say two schedules are view equivalent.
| T1 | T2 |
| R(X) | |
| W(X) |
| T1 | T2 |
| W(X) | |
| R(X) |
In yellow table the variable X is firstly reads by T1. In green table also firstly variable X is read by T1. So the first read of both the schedules are same. They have read the same variable and same transaction has done it both the table. So these two schedules are view equivalent. So they are view serializable.
Update read
In this both the transaction schedules has to update the same variable which has been read by the same transaction in the both schedules.
| T1 | T2 | T3 |
| R(A) | ||
| W(A) | ||
| R(A) |
| T1 | T2 | T3 |
| W(A) | ||
| W(A) | ||
| R(A) |
Here in yellow and green both schedules T3 read the variable A. The variable A updated by T1 in both schedule. So T3 read the updated value of A by T1. Both schedules reading value was updated by the same transaction. Now these two schedules are view equivalent.
Final write
In this scenario final write of both the schedule need to be same. Let’s look at the example.
| T1 | T2 | T3 |
| W(A) | ||
| R(A) | ||
| W(A) |
| T1 | T2 | T3 |
| R(A) | ||
| W(A) | ||
| W(A) |
Above example schedules you can see the final write operation was done by T3. So these two schedules are view equivalent since the final write operations of both schedules was done by same operations.
Now we know how schedules be view equivalent and because of that how schedules be view serializable. Now let’s see how we identify the conflict serializable.
Conflict serializability
As we discussed if a schedule is conflict equivalent we can say the schedule is conflict serializable. Then how we identify the conflict equivalent of two schedules. We have a technique for that. That is call it as the precedent graph. We are drawing a graph to identify the conflicts in a schedule. If that graph became a cyclic one we can say that the schedule has conflicts and it cannot be conflict serializable. There are conflict types we can see in a schedules. In order to draw the precedent graph firstly we have to know those things.
Conflicts in a schedule occurs with read and write operations. Actually it’s main cause is the write operations. There are conflicts in schedules with these patterns. Read – write, write – read, write – write. In read – read combination we can’t see conflicts. Because two operations in two transactions are doing read. Reading cannot do any harm to value of a variable. The concurrency issues earlier we discussed happens with those patterns.
How to draw precedent graph
Now you know what are the conflict types in a schedule. When we have the schedule we read the schedule from top to bottom and finding conflicts. When we take the first variable we find if other transaction contain a conflict operation for that variable. Then we draw a arrow from that transaction to other transaction. Let’s see a example.
| T1 | T2 | T3 |
| R(A) | ||
| R(B) | ||
| W(A) | ||
| W(B) |
Execution of precedent graphs
After see the schedule let’s learn about it. We start the drawing with top of the schedule. So first operation is R(A). Tell me what are the conflict operations for R(A). That is write A. What we want to do is see other transactions contains W(A) operation. So go from top to down. First we find the R(B) that is not a conflict. Secondly we find W(A). That’s a conflict. So we can draw T1 -> T3. Then go down. After that we find W(B). That is also not a conflict. Then we can left R(A) operation since we have identified all the conflict in the schedule for that variable.
Then after that we will move to the next variable R(B). What is the conflict operation for R(B). The answer is W(B). Find whether we can see write B operation in a schedule. Now don’t think about the upper operations. They are done. Find conflict operations in below level. T3 Have write A operation. So no conflicts for read B. Let’s move forward. The write B operation in T2 is not a conflict. Most importantly you have to keep this in mind because operations in the same operations are not make conflict. Conflicts occurs from other transactions. Read write operations for same variable in the same transaction is not a conflict.
Then we have the W(A) operation. It doesn’t have any conflicts since we can’t find R(B) below that operation. Once you have identified top to bottom all the conflicts look at the graph you have driven. If that is a cyclic one then we can say the graph is not conflict serializable. In our case we only found one conflict. Therefore this schedule is a conflict serializable schedule.
Conclusion
We have come to the end of the post. As a conclusion let’s summarize what we have learnt from this article. As a result you can improve your knowledge also. Today we discussed about transaction schedule and the serializability. What is serializability, what are the types and how to find it. I hope you have gain knowledge about those topics. Furthermore If you have doubts you can comment us and let us know. We can make a post about the questions you raised. We always there to help you.
Meanwhile if this article helps you to your education please comment to this post. Share among it friends to help another student also. We have provided many posts about database transactions please have a look them. Here is about database transaction in DBMS. Then we will meet with another interesting topic. Till then good bye!
