Serialisability

Serialisability is the ability of a schedule to be transformed into a serial schedule without altering the result of the operation. * Conflict Serialisability - avoid RAW / WAW hazards * View Serialisablility - fancier stuff. It's NP-Hard

Conflict

• Read and Read > No conflict
• Write and Read > Conflict
• Read and Write > Conflict
• Write and Write > Conflict

Any conflict presents an order, which must be preserved during any modification.

Conflict Serialisability

A schedule \(S\) is considered conflict serialisable if it is conflict-equivalent to, i.e. can be converted to a serial schedule \(S'\) (achieved by swapping no conflicting instructions).

Testing for Conflict Serialisability

We test for conflict serialisability by making a precedence graph. If and only if we see a circular dependency, the schedule is non-conflict-serialisable.