ACID and Precedence Graphs

COMP207 Tutorials 2021-10-21

This tutorial relates to the questions here.

Question 1

The short hand notation would be:

\[S_a: r_1(X);w_1(X);c_1;r_2(X);w_2(X);c_2;\]

The schedule is a serial schedule as the transactions are run one after the other.

The following ACID properties are broken:

• No ACID properties are broken as there are no writes to the databases mid transaction.

Question 2

1. This breaks:
   • Atomicity as $T_1$ is not complete.
   • Maybe consistency if strong consistency is used.
   • Isolation as the transaction is not serialisable.
   • Durability breaks as $T_1$ is not complete.
2. If $T_1$ is rolled back then the database is left in an inconsistent state due to writes caused by $T_2$.
3. If we rolled both transactions back then durability is broken as we change the data committed by $T_2$.

Question 3

• $S_3$:

    graph LR
    T3 --> T1
    T2 --> T3
    T2 --> T1
  

  No cycles so it is conflict-serialisable.

• $S_4$:

    graph LR
    T3 --> T1
    T2 --> T3 & T1
    T1 --> T3
  

  There is a cycle between $T_3$ and $T_1$ so it is not conflict-serialisable.

Question 4

A transaction can’t be in conflict with itself. Therefore a cycle but be between two transactions and therefore be greater than 1.