Serializability ensures that a schedule (i.e., the sequence of read/write operations) of multiple concurrent transactions is equivalent to some serial execution of those transactions.
- Serial Schedule: Schedule that does not interleave the actions of different transactions.
- Equivalent Schedules: For any database state, the effect of executing the first schedule is identical to the effect of executing the second schedule.
- Serializable Schedule: A serializable schedule is a schedule that is equivalent to any serial execution of the transactions. Different serial executions can produce different results, but all are considered “correct”.
Conflict Serializability
Conflict Equivalence
- They involve the same operations from the same transactions.
- Every pair of conflicting operations (read-write, write-read, write-write on the same data item) is ordered the same way in both schedules.
Conflict Serializable Schedule
A schedule is conflict serializable if it can be rearranged (through swapping non-conflicting operations) into a serial schedule (one where transactions are executed one after another, with no overlap) that is conflict equivalent to it.
Essentially, if you can reorder a schedule without changing the outcome of conflicting operations, and achieve a serial order of transactions, the original schedule is conflict serializable.
Conflict, but serializable, so make it serializable.
View Serializability
It includes schedules that are not conflict serializable, but still result in a database state, that can be achieved by some serial execution of transactions.
Dependency Graph
- Algorithms to detect conflict serializability
- A schedule is conflict serializable iff its dependency graph is acyclic.
