-
Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by r(x) and w(x) respectively. Which one of them is conflict serializable?
-
- r1 (x); r2 (x); w1 (x); r3 (x); w2 (x)
- r2 (x); r1 (x); w2 (x); r3 (x); w1 (x)
- r3 (x); r2 (x); r1 (x); w2 (x); w1 (x)
- r2 (x); w2 (x); r3 (x); r1 (x); w1 (x)
- r1 (x); r2 (x); w1 (x); r3 (x); w2 (x)
Correct Option: D
rQ (x); w2 (x); r3 (x); r1 (x); w1 (x) is conflict serializable.
Conflicting Instructions : Two instructions are said to be conflicting instructions if they are performed on the same data item and atleast one of them is “write” instruction.
Serial schedule : A schedule is called a serial schedule if it consists of a sequence of instructions from various transactions, where the instructions belonging to one single transaction appear together in that schedule.
Conflict serializable schedule : A schedule is called conflict serializable if it can be transformed into a “serial schedule” using valid swap operation where valid swap denotes the swapping of any two “Nonconflicting” instructions. (a) r1 (x); r2 (x); w1 (x); r3 (x); w2 (x); is not conflict serializable because w1 (x); cannot be swapped either with r2 (x); or r3 (x).
(b) It is also not conflict serializable as w2 (x) cannot be swapped with r1 (x) or r3 (x).
(c) Same here as w2 (x) and r1(x) are conflicting.
(d) It is conflict serializable as if we swap r3 (x) with r1(x) which are Non-conflicting, we get r2 (x); w2 (x); r1 (x);
r3 (x); w3(x)
