DBMS Menu

Serializability in DBMS



Schedule is an order of multiple transactions executing in concurrent environment.

Serial Schedule: The schedule in which the transactions execute one after the other is called serial schedule. It is consistent in nature.

For example: Consider following two transactions T1 and T2.


   T1     |    T2
----------|----------
Read(A)   |
Write(A)  |  
Read(B)   |	 
Write(B)  |  
          |  Read(A)
          |  Write(A)
          |  Read(B)
          |  Write(B)

All the operations of transaction T1 on data items A and then B executes and then in transaction T2 all the operations on data items A and B execute.

Non Serial Schedule: The schedule in which operations present within the transaction are intermixed. This may lead to conflicts in the result or inconsistency in the resultant data.

For example- Consider following two transactions,


   T1     |    T2
----------|----------
Read(A)   |
Write(A)  |  
          |  Read(A)
          |  Write(B)
Read(A)   |	 
Write(B)  |
          |  Read(B)
          |  Write(B)

The above transaction is said to be non serial which result in inconsistency or conflicts in the data.

What is serializability? How it is tested?

Serializability is the property that ensures that the concurrent execution of a set of transactions produces the same result as if these transactions were executed one after the other without any overlapping, i.e., serially.

Why is Serializability Important?

In a database system, for performance optimization, multiple transactions often run concurrently. While concurrency improves performance, it can introduce several data inconsistency problems if not managed properly. Serializability ensures that even when transactions are executed concurrently, the database remains consistent, producing a result that's equivalent to a serial execution of these transactions.

Testing for serializability in DBMS

Testing for serializability in a DBMS involves verifying if the interleaved execution of transactions maintains the consistency of the database. The most common way to test for serializability is using a precedence graph (also known as a serializability graph or conflict graph).

Types of Serializability

  1. Conflict Serializability
  2. View Serializability

Conflict Serializability

Conflict serializability is a form of serializability where the order of non-conflicting operations is not significant. It determines if the concurrent execution of several transactions is equivalent to some serial execution of those transactions.

Two operations are said to be in conflict if:

  • They belong to different transactions.
  • They access the same data item.
  • At least one of them is a write operation.
Examples of non-conflicting operations 

   T1     |    T2
----------|----------
Read(A)   |  Read(A)
Read(A)   |  Read(B)
Write(B)  |  Read(A)
Read(B)   |  Write(A)
Write(A)  |  Write(B)
Examples of conflicting operations 

   T1     |    T2
----------|----------
Read(A)   |  Write(A)
Write(A)  |  Read(A)
Write(A)  |  Write(A)

A schedule is conflict serializable if it can be transformed into a serial schedule (i.e., a schedule with no overlapping transactions) by swapping non-conflicting operations. If it is not possible to transform a given schedule to any serial schedule using swaps of non-conflicting operations, then the schedule is not conflict serializable.


To determine if S is conflict serializable:

Precedence Graph (Serialization Graph): Create a graph where:

Nodes represent transactions.

Draw an edge from \( T_i \) to \( T_j \) if an operation in \( T_i \) precedes and conflicts with an operation in \( T_j \).

For the given example:


   T1     |    T2
----------|----------
Read(A)   |  
          |  Read(A)
Write(A)  |  
          |  Read(B)
          |  Write(B)

\( R1(A) \) conflicts with W1(A), so there's an edge from T1 to T1, but this is ignored because they´re from the same transaction.
R2(A) conflicts with W1(A), so there's an edge from T2 to T1.
No other conflicting pairs.
The graph has nodes T1 and T2 with an edge from T2 to T1. There are no cycles in this graph.

Decision: Since the precedence graph doesn't have any cycles,Cycle is a path using which we can start from one node and reach to the same node. the schedule S is conflict serializable. The equivalent serial schedules, based on the graph, would be T2 followed by T1.

View Serializability

View Serializability is one of the types of serializability in DBMS that ensures the consistency of a database schedule. Unlike conflict serializability, which cares about the order of conflicting operations, view serializability only cares about the final outcome. That is, two schedules are view equivalent if they have:

  • Initial Read: The same set of initial reads (i.e., a read by a transaction with no preceding write by another transaction on the same data item).
  • Updated Read: For any other writes on a data item in between, if a transaction \(T_j\) reads the result of a write by transaction \(T_i\) in one schedule, then \(T_j\) should read the result of a write by \(T_i\) in the other schedule as well.
  • Final Write: The same set of final writes (i.e., a write by a transaction with no subsequent writes by another transaction on the same data item).

Let's understand view serializability with an example:

Consider two transactions \(T_1\) and \(T_2\):

Schedule 1(S1):


| Transaction T1      | Transaction T2      |
|---------------------|---------------------|
| Write(A)            |                     |
|                     | Read(A)             |
|                     | Write(B)            |
| Read(B)             |                     |
| Write(B)            |                     |
| Commit              | Commit              |

Schedule 2(S2):


| Transaction T1      | Transaction T2      |
|---------------------|---------------------|
|                     | Read(A)             |
| Write(A)            |                     |
|                     | Write(A)            |
| Read(B)             |                     |
| Write(B)            |                     |
| Commit              | Commit              |
​

Here,

  1. Both S1 and S2 have the same initial read of A by \(T_2\).
  2. Both S1 and S2 have the final write of A by \(T_2\).
  3. For intermediate writes/reads, in S1, \(T_2\) reads the value of A after \(T_1\) has written to it. Similarly, in S2, \(T_2\) reads A which can be viewed as if it read the value after \(T_1\) (even though in actual sequence \(T_2\) read it before \(T_1\) wrote it). The important aspect is the view or effect is equivalent.
  4. B is read and then written by \(T_1\) in both schedules.

Considering the above conditions, S1 and S2 are view equivalent. Thus, if S1 is serializable, S2 is also view serializable.

Next Topic :Recoverability in DBMS