Count the shapes with a tiny dependency-graph checker

Simulate a modelNeeds Python

Problem

Anomalies are easier to reason about as shapes in a graph than as names. Draw one node per transaction and an edge for each dependency: ww when one transaction overwrites another's write, wr when it reads another's write, and rw (an anti-dependency) when it reads a version that another transaction then overwrites. A history is serializable if this graph has no cycle. Each famous anomaly is a cycle of a particular shape, and the number of rw edges in it decides which isolation levels can see it: snapshot isolation prevents cycles with a ww edge but not cycles made of rw edges alone.

Write a small program that takes a history as a list such as [("T1","r","x",0), ("T2","w","x",1), ...] (transaction, operation, object, version) and builds ww, wr and rw edges. Then count the cycles and the number of rw edges in each. Feed it the lost-update history, the write-skew history and a read-skew history. Check that adding the shared-row write from Write skew under Repeatable Read, and the two cures turns the write-skew cycle into one that contains a ww edge, which the SI check can see.

The script reads each version from the history itself (snapshot isolation), so a read names the version it actually returned.

The question. What cycle does each anomaly form, how many rw edges does it have, and does materializing the conflict give write skew a ww edge?

Predict

How many rw (anti-dependency) edges does the write-skew cycle have?

NoneOneTwoThree or more

Run it

1Install uv once. It fetches Python and the lab's packages for you.
Terminal
```
curl -LsSf https://astral.sh/uv/install.sh | sh
```

2Get the script. It is the whole lab: read it, then download it.

count-the-shapes-with-a-tiny.py86 linesDownload

View the code

count-the-shapes-with-a-tiny.py

# /// script
# requires-python = ">=3.10"
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""Count the shapes with a tiny dependency-graph checker.

Builds ww, wr and rw edges from a history of (transaction, op, object,
version) and finds the cycles, for the lost-update, write-skew and read-skew
histories, then for write skew with a materialized conflict.
"""
import argparse, json
from itertools import permutations

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--json", help="Also write the results to this JSON file.")
args = p.parse_args()


def edges(h):
    """Edges between transactions. Each read names the version it returned (snapshot isolation):
    wr from that version's writer; rw to whoever installed the next version of the object."""
    writers = {}                                       # (object, version) -> writer
    for t, op, x, v in h:
        if op == "w": writers[(x, v)] = t
    order = {}                                         # object -> versions in install order
    for t, op, x, v in h:
        if op == "w": order.setdefault(x, []).append(v)
    E = set()
    for x, vs in order.items():                        # ww: consecutive versions
        for a, b in zip(vs, vs[1:]):
            if writers[(x, a)] != writers[(x, b)]: E.add((writers[(x, a)], writers[(x, b)], "ww"))
    for t, op, x, v in h:
        if op != "r": continue
        if (x, v) in writers and writers[(x, v)] != t: E.add((writers[(x, v)], t, "wr"))
        vs = [0] + order.get(x, [])                    # version 0 = the initial value
        nxt = vs[vs.index(v) + 1] if v in vs and vs.index(v) + 1 < len(vs) else None
        if nxt is not None and writers[(x, nxt)] != t: E.add((t, writers[(x, nxt)], "rw"))
    return E


def cycles(E):
    """Simple cycles (as edge lists) in a small graph, each reported once."""
    nodes = sorted({a for a, _, _ in E} | {b for _, b, _ in E})
    out, seen = [], set()
    for k in range(2, len(nodes) + 1):
        for perm in permutations(nodes, k):
            if perm[0] != min(perm): continue
            path = []
            for a, b in zip(perm, perm[1:] + perm[:1]):
                es = [e for e in E if e[0] == a and e[1] == b]
                if not es: break
                path.append(es[0])
            else:
                key = frozenset(path)
                if key not in seen: seen.add(key); out.append(path)
    return out


H = {
    # T1 reads x (v0), T2 writes x (v1) and commits, T1 writes x (v2): T2's write is lost
    "lost update": [("T1", "r", "x", 0), ("T2", "r", "x", 0), ("T2", "w", "x", 1), ("T1", "w", "x", 2)],
    # both read x and y at v0, T1 writes x, T2 writes y
    "write skew": [("T1", "r", "x", 0), ("T1", "r", "y", 0), ("T2", "r", "x", 0), ("T2", "r", "y", 0),
                   ("T1", "w", "x", 1), ("T2", "w", "y", 1)],
    # T1 reads x at v0; T2 writes x and y; T1 reads y at T2's version
    "read skew": [("T1", "r", "x", 0), ("T2", "w", "x", 1), ("T2", "w", "y", 1), ("T1", "r", "y", 1)],
    # write skew plus a write by both to a shared row z (the materialized conflict)
    "write skew + shared row": [("T1", "r", "x", 0), ("T1", "r", "y", 0), ("T2", "r", "x", 0), ("T2", "r", "y", 0),
                                ("T1", "w", "z", 1), ("T2", "w", "z", 2), ("T1", "w", "x", 1), ("T2", "w", "y", 1)],
}
rows = []
for name, h in H.items():
    E = edges(h)
    for c in cycles(E):
        kinds = [k for _, _, k in c]
        rows.append({"history": name, "cycle": " → ".join(f"{a}-{k}->{b}" for a, b, k in c),
                     "rw": kinds.count("rw"), "ww": kinds.count("ww"), "wr": kinds.count("wr"),
                     "objects": len({x for t, op, x, v in h})})
        print(f"{name:<24} cycle {rows[-1]['cycle']:<34} rw={rows[-1]['rw']} ww={rows[-1]['ww']} wr={rows[-1]['wr']}")
    if not cycles(E): print(f"{name:<24} no cycle")

if args.json:
    with open(args.json, "w") as f:
        json.dump({"tables": {"cycles": rows}}, f)

3Run it in the folder you saved it to, with the defaults first. Then change a knob from the table below and run it again.
Terminal
```
uv run count-the-shapes-with-a-tiny.py
uv run count-the-shapes-with-a-tiny.py --help     # every knob
```

Our run

Cycles in each history

Cycles in each history
History	Cycle	rw	ww	wr
lost update	T1-rw->T2 → T2-ww->T1	1	1	0
write skew	T1-rw->T2 → T2-rw->T1	2	0	0
read skew	T1-rw->T2 → T2-wr->T1	1	0	1
write skew + shared row	T1-ww->T2 → T2-rw->T1	1	1	0

Reference runApple M2 · 8 cores · 8 GB

Output · uv run count-the-shapes-with-a-tiny.py

lost update              cycle T1-rw->T2 → T2-ww->T1              rw=1 ww=1 wr=0
write skew               cycle T1-rw->T2 → T2-rw->T1              rw=2 ww=0 wr=0
read skew                cycle T1-rw->T2 → T2-wr->T1              rw=1 ww=0 wr=1
write skew + shared row  cycle T1-ww->T2 → T2-rw->T1              rw=1 ww=1 wr=0

macOS 26.6.2 · Python 3.13.3 · run 2026-10-20

What we found

Each history formed one cycle of the expected shape. Lost update: 1 rw and 1 ww edge. Write skew: 2 rw edges and no ww edge, which is why snapshot isolation, looking only for write-write conflicts, lets it through. Read skew: 1 rw edge and 1 wr edge across two objects. With the shared-row write added, the write-skew cycle contained 1 ww edge, so the snapshot-isolation check can see it.

Read it

(This simple version reads the latest write and ignores snapshots, so build your histories with the version each read actually returned to reflect SI.)

Adya's phenomena (G0, G1, G-single, G2) are this classification made precise: G-single is a cycle with exactly one anti-dependency, G2 a cycle with more. They are not academic formalism; they are the output vocabulary of the only black-box isolation checker that works, and the Elle-style lab uses exactly this graph on a real database.