DATABASE MANAGEMENT SYSTEM

SERIALIZABILITY IN DBMS

Transaction: A unit of work that is performed against a database. It is typically composed of multiple operations, such as reads and writes.

Concurrency: The simultaneous execution of multiple transactions.

Schedule: A sequence of operations from a set of transactions. A schedule is a representation of the order in which operations are executed.

Serializable Schedule: A schedule is serializable if its outcome is equivalent to the outcome of some serial execution of the transactions.

Serial Schedule

A serial schedule is one in which transactions are executed one after another without any interleaving. In other words, each transaction runs to completion before the next one begins. This type of scheduling is straightforward and inherently ensures consistency because it avoids conflicts between transactions.

Example of a Serial Schedule

Consider two transactions T1 and T2:

Non-Serial Schedule

A non-serial schedule, also known as an interleaved schedule, allows operations from different transactions to be interleaved. This means that the operations of transactions are mixed together rather than executed sequentially. While this increases concurrency and utilization of resources, it can potentially lead to conflicts and inconsistencies if not managed properly.

Example of a Non-Serial Schedule

Using the same transactions T1 and T2:

Serializability

Serializability is a key concept in database management systems (DBMS) that ensures the correctness of transactions in a concurrent environment. It guarantees that the outcome of executing multiple transactions concurrently is the same as if those transactions were executed serially, one after the other.

While non-serial schedules allow for more concurrency, they need to be managed to ensure that they are serializable. A schedule is serializable if its outcome is equivalent to some serial schedule. There are two types of Serializability: Conflict Serializability and View Serializability

 

 

Conflict Equivalent

 

Two schedules are said to be conflict equivalent when one can be transformed to another by swapping non-conflicting operations.

 

Question:

Find whether the following schedules are conflict equivalent or not.

1. Conflict Serializability

A non-serial schedule is conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations.

 

1. Construct a Precedence Graph:
   • Nodes represent transactions.
   • Directed edges represent conflicts where one transaction must precede another.
2. Check for Cycles:
   • If the graph is acyclic, the schedule is conflict-serializable.
   • If the graph is cyclic, the schedule is not conflict-serializable and we have to check for view-serializable.

 

Question: Check whether the transactions are Conflict Serializable

The nodes are T1, T2 and T3. 

Step 1: Find the edges from one node to the other.

T1:

For R(x) let's check the conflict pair W(x) which is not present in either T2 or T3. So no edge from T1 to any other transaction.
 

T3:

For R(y) the conflicting transaction is R(x), which is not in either T1 or T2.

For R(x) the conflicting transaction is W(x) which is in T1, so we draw an edge from T3 to T1.

T2:

For R(y) the conflicting transaction is  W(y) which is in T3 so we draw an edge from T2 to T3.

For R(z) the conflicting transaction is  W(z) which is in T1 so we draw an edge from T2 to T1.

T3:

For W(y) the conflicting transaction is  R(y) and W(y) which is not in T1 and T2( we see after operations only).

T2:

For W(z) the conflicting transaction is  R(z) and W(z) which is in T1  so we draw an edge from T2 to T1.

T1:For R(z), W(x) and W(z) there is no conflicting transaction.

Step 2: Draw the precedence graph

The graph does not form cycle , hence it is conflict serializable 

Step 3: Find the transaction order 

Check the indegree at any node , if indegree=0 we first place that transaction.

T2 is the node having indegree=0 , so we add that first and remove it from the graph. 

Next T3 is having indegree=0 so the next transaction will be T3 and finally T1.

T2—>T3—>T1

 

Example : Check whether the transactions are Conflict Serializable

2. View Serializability

A schedule is view serializable if it is view equivalent to a serial schedule. Two schedules are view equivalent if the following three conditions hold:

• Initial Read: For each data item, the transaction that performs the first read in both schedules must be the same.
• Update Read: For each data item, if a transaction reads the value written by another transaction in one schedule, it must read the same value in the other schedule.
• Final Write: For each data item, the transaction that performs the final write must be the same in both schedules.

 

• Two schedules are view equivalent if:
  • They read the same initial values.
  • Transactions reading the result of another transaction's write operation are the same in both schedules.
  • The final write operations on each data item are the same in both schedules.
• A schedule is view serializable if it is view equivalent to a serial schedule.

Example : Consider the following schedule. Check the Conflict serializability and View Serializability.

S1:

Solution:

To check conflict serializability, first draw the precedence graph.

 

 

From the above graph , we can see there is a loop or cycle . Hence it is not conflict serializable. So we need to find the view serializability.

 

If we swap the conflicting pair , the transaction will be : 

 

 

The Schedule will be:

S2:

 

 

Let's check both schedules by assigning some values to each transaction and see the final values. If the values are the same they are view serializable. 

 

Drawing the precedence graph of above question:

In the above question , it is view serializable.