Test: Serializability & Conflict Serializability - Computer Science Engineering (CSE) MCQ

Predicate locking is the most expensive method and is generally not used in most databases.

The set of vertices in a precedence graph consists of all the transactions participating in the schedule. Precedence graph is a simple and efficient way of determining conflict serializability of the schedule.

If a schedule S can be transformed into a schedule S’ by a series of swaps of non-conflicting instructions, then S and S’ are conflict equivalent. Not all serial schedules are conflict equivalent to each other.

A Serializability order of the transactions can be obtained by finding a linear order consistent with the partial order of the precedence graph. This process is called as topological sorting.

A schedule is conflict serializable if it is conflict equivalent to a serial schedule. The concept of conflict equivalence leads to the concept.

I and J are conflicting if they are operations by different transactions on the same data item, and at least one of them is a write operation.

Concept:

Two or more actions are said to be in conflict if:

• The actions are associated with various transactions.
• A write operation is involved in at least one of the operations.
• The actions all refer to the same thing (read or write).

If the following conditions are met, the schedules S₁ and S₂ are said to be conflict-equivalent:

• The transactions in schedules S₁ and S₂ are the same (including ordering of actions within each transaction).
• In both S₁ and S₂, the order of each pair of conflicting actions is the same.

Conflict-serializable:

A schedule is said to be conflict-serializable when the schedule is conflict-equivalent to one or more serial schedules.  Conflict-serializability is that a schedule is conflict-serializable if and only if its precedence graph/serializability graph, when only committed transactions are considered, is acyclic.

There are two possible serial schedules:

• T₁ followed by T₂.
• T₂ followed by T₁.

As an initial step in both serial schedules, one of the transactions reads the value written by the other transaction. As a result, any non-serial T₁ and T₂ interleaving will not be conflict serializable.

Hence the correct answer is a schedule that is not conflict serializable.

P and Q are initialized to Zero, write operation on P and Q will be executed.
Consider any non-serial schedule like R₁(P), R₂(Q), R₁(Q), R₂(P), W₁(Q), W₂(P). R₁(P) conflicts with W₂(P) Hence T₁ must be before T₂. R₂(Q) conflicts with W₁(Q) Hence T₂ must be before T₁. There is no serial schedule that satisfies both of them hence it does not conflict with serializable.
Hence the correct answer is a schedule that is not conflict serializable.

Serial schedule is possible only when precedence graph doesn’t contain cycle. If precedence graph contains a cycle, it means schedule is not conflict serializable.
Breadth first search and Depth first search of a graph are possible even if graph contains cycle.
Topological sort in a graph will not work if graph contains a cycle.

Consider a directed acyclic graph:

 

Here Two orders possible: V₂, V₃, V₁, V₄, V₅, V₆ OR V₃, V₂, V₁, V₄, V₅, V₆.
In case of ascending order of transaction indices, two non-conflicting schedules can occur simultaneously.

S1: r1(x) r1(y) r2(x) r2(y) w2(y) w1(x)

Precedence Graph:

S2:r1(x) r2(x) r2(y) w2(y) r1(y) w1(x)

Precedence Graph:

There exists a Cycle in Precedence of S1. Hence S1 is not Conflict Serializable.

Whereas S2 is Conflict Serializable.