HW 3: Transactions

def precedence(schedule):
    edges = set()
    for (t_i, i, op_i, x) in schedule:
        for (t_j, j, op_j, y) in schedule:
            if t_i <= t_j and i != j and x == y and (op_i == 'W' or op_j == 'W'):
                edges.add((i, j))
    return edges

We loop over every pair of actions with t_i <= t_j and add an edge if they conflict on the same item.

Faster version: sort the actions first (by timestamp), then the inner loop only needs to look at later items. This halves the comparisons and lets us drop the explicit t_i <= t_j check — it’s guaranteed by the slice.

def precedence(schedule):
    edges = set()
    s = sorted(schedule)
    for k, (_, i, op_i, x) in enumerate(s):
        for (_, j, op_j, y) in s[k+1:]:
            if i != j and x == y and (op_i == 'W' or op_j == 'W'):
                edges.add((i, j))
    return edges

select distinct a.tx as i, b.tx as j
from action a, action b
where a.t <= b.t
  and a.tx != b.tx
  and a.item = b.item
  and (a.op = 'W' or b.op = 'W');

This is a self-join on action with the same conflict conditions as the Python version. select distinct removes duplicate edges (multiple conflicting pairs between the same two tx collapse to a single edge).

The “concurrent” version at the top of the homework (with tied timestamps) is serializable but not serial. To satisfy the extra constraint (unique timestamps — only one action at a time), just stagger the actions:

[(1, 1, 'R', 'A'), (2, 2, 'R', 'B'), (3, 1, 'W', 'A'), (4, 2, 'W', 'B')]

Not serial: T_1’s actions aren’t contiguous. Serializable: T_1 and T_2 touch different items, so the precedence graph is empty — equivalent to either serial order.

Consider:

The schedule violates 2PL on both tx’s, but is equivalent to the serial schedule where T₂ runs before T₁, since the R(A) action in T₁ does not conflict with anything from T₂.

locks = {}  # item -> tx holding the lock

def lock_manager(tx, op, x):
    if op in ('COMMIT', 'ROLLBACK'):
        to_release = [item for item, holder in locks.items() if holder == tx]
        for item in to_release:
            del locks[item]
        return True
    # R or W: need the lock on x
    if x not in locks:
        locks[x] = tx
        return True
    return locks[x] == tx  # True if we already hold it, False if another tx does

On COMMIT/ROLLBACK, release every lock held by this tx (strict 2PL: hold all locks until end). On R/W, acquire the lock if free; succeed silently if we already hold it; fail if another tx holds it.

First, we show that an edge i \to j in the precedence graph implies T_i unlocks an item X before T_j locks X. If there’s an edge i \to j, there must be a pair of conflicting actions a_i \in T_i and a_j \in T_j such that a_i occurs before a_j, and they act on the same DB item X. When a_i acts on X, T_i must hold a lock on X; but for a_j to act on X, T_j must have first locked X, which can only happen after T_i releases its lock. Therefore, T_i must unlock on X before T_j locks it.

Now, assume for the sake of contradiction that a schedule follows 2PL but is not serializable. Then there must be a cycle in the precedence graph. Without loss of generality suppose the cycle is 1 \to 2 \to \cdots \to k \to 1. Using the result we proved above, there exists items X_1, X_2, \ldots, X_k such that:

• T_1 unlocks X_1 before T_2 locks X_1
• T_2 unlocks X_2 before T_3 locks X_2
• …
• T_k unlocks X_k before T_1 locks X_k

According to 2PL, all unlocks must happen after all locks within the same tx, i.e., T_i unlocks X after T_i locks X' for all i. This means that we can put the events above in a strict sequential order:

U_1(X_1) < L_2(X_1) < U_2(X_2) < L_3(X_2) < \cdots < U_k(X_k) < L_1(X_k)

Where U_i(X) and L_i(X) denote the event of T_i unlocking/locking X, respectively. But this would require T_1 to lock X_k after it unlocks X_1, which violates 2PL – contradiction!

Any schedule where two transactions read the same item without writing it:

Under single-type (exclusive) locks, T₁ and T₂ cannot both hold the lock on A at the same time — one must wait. Under read/write locks, both can hold shared locks on A simultaneously (reads don’t conflict), then proceed to write their respective items B and C in parallel. The single-type scheme serializes the reads unnecessarily; the r/w scheme does not.

Starvation can happen if a tx wants to write, but some other tx’s hold a read lock, and new tx’s keep arriving locking the item for reading:

Here X(A) denotes a failed attempt to acquire an exclusive (write) lock on A, and S(A) denotes the corresponding tx is holding a shared (read) lock on A. Because read locks do not conflict, the arriving tx’s can keep getting new locks, making it impossible for the exclusive lock to succeed. Imagine you’re trying to fix a busy road: if the cars keep coming (read locks), you can’t work on the road (write lock). The solution is also similar: for roadwork, you stop letting people through once you want to start work; for transactions, block all incoming reads if you have a pending write.

Serializable, forbidden by SI — concurrent blind writes to the same item:

Non-serializable, allowed by SI:

Serializable, forbidden by WSI — a “stale read” that’s logically fine:

Non-serializable, allowed by WSI? No — WSI is sufficient for serializability.

WSI aborts T whenever last_written[x] > start_T for some x \in R_T — i.e., when a concurrent tx committed a write to something T read. The relevant “danger window” is between T’s read of x and T’s commit: a write inside that window is a real anti-dependency, while a write that lands before T reads x is harmless (T would just see the new value).

With snapshot reads, T can’t tell the difference. The check uses start_T as a conservative proxy for the read time, so any write committed during [start_T, commit_T] triggers an abort — including writes that landed before T even got around to reading x, which would have been benign.

With live reads, T reads the fresh value at the moment it asks. Now any write committed before that read is automatically reflected in what T saw, so it can’t be a conflict. The abort window shrinks from [start_T, commit_T] down to [read_time(x), commit_T], which is strictly smaller. Fewer windows → fewer false-positive aborts → better throughput.