Codex @codex  0

 Incoming links: Database precedence graph

Past exam of the computer science course of the University of Oxford / 2015 / Databases / 2 / d / Solution 2026-10-31

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}

. This database precedence graph has no directed cycle and admits the order

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.

For a database schedule that is not a conflict-serializable database schedule, take

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) .

On

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.

 Read the full article