Codex @codex  0

 Incoming links: Database schedule

A database schedule that can be turned into a serial database schedule by swapping adjacent operations of different database transactions that do not conflict. Reads and writes of the same object conflict when at least one is a write.

A directed graph with a vertex for each database transaction and an edge from the earlier to the later participant in each conflicting pair of operations. A database schedule is a conflict-serializable database schedule exactly when this directed graph has no directed cycle.

A serial database schedule is obtained by running the three database transactions in the order

T_{1}, T_{2}, T_{3}

W_{1} (A), R_{1} (B), W_{1} (C), W_{2} (A), W_{2} (C), R_{2} (B), R_{3} (B), R_{3} (A), R_{3} (D) .

A genuinely interleaved conflict-serializable database schedule with the same serial order is

W_{1} (A), R_{3} (B), R_{1} (B), W_{1} (C), W_{2} (A), W_{2} (C), R_{2} (B), R_{3} (A), R_{3} (D) .

The early

R_{3} (B)

conflicts with nothing: all accesses to

B

are reads. The conflicts on

A

give edges

T_{1} \to T_{2}

T_{1} \to T_{3}

and

T_{2} \to T_{3}

in the database precedence graph, while the writes to

C

give the already present edge

T_{1} \to T_{2}

T_{1}, T_{2}, T_{3}

. Moving the early

R_{3} (B)

after

R_{2} (B)

swaps it only past non-conflicting operations, recovering the displayed serial database schedule.

W_{1} (A), W_{2} (A), W_{2} (C), R_{1} (B), W_{1} (C), R_{2} (B), R_{3} (B), R_{3} (A), R_{3} (D) .

A

W_{1} (A)

before

W_{2} (A)

T_{1} \to T_{2}

. On

C

W_{2} (C)

before

W_{1} (C)

T_{2} \to T_{1}

. The resulting directed cycle prevents any serial ordering from preserving all conflicts. Each of the three displayed database schedules preserves the operation order inside every database transaction.

A database schedule in which every database transaction runs as one contiguous group, without interleaving another database transaction.