Serialisable Schedules

Types of Schedules

So far we have seen two extremes of scheduling:

Serial Schedules

Execute correctly.
Maintain consistency of the database.
Inefficient in multi-user environments (because transactions have to wait until others are finished).

Concurrent Schedules

May not execute correctly.
May not guarantee consistency of the database or isolation.
Efficient in multi-user environments (if you get asked to do something, just do it!).

Concurrent schedules can be faster then serial ones by they are not always equivalent.

In a serial schedule you have to wait until one transaction is over until you can start another.

However by running two transactions simultaneously you may get erroneous results do to the interactions between the two transactions.

Concurrent schedules do not guarantee consistency or isolation.

A schedule $S$ is serialisable if there is a serial schedule $S’$ that has the same effect on $S$ on every initial database state:

Equivalent Serial Schedule $S’$
`read(X)`
`X := X + N`
`read(Y)`
`Y := Y + N`
`write(Y)`
`commit`
	`read(X)`
	`X := X + M`
	`write(X)`
	`commit`

Serialisable schedules guarantee:

Correctness and consistency because they inherit the properties of serial schedules.
Doesn’t satisfy isolation, as they can read uncommitted data.

This can be fixed.

The problem is that they are difficult to test:

Don’t depend on reads, writes, and commits, but also on the non-database operations.
Non-database operations can be complex.