Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Schedules and serialisability

Schedules and serialisability: how to decide whether interleaved transaction executions are correct (equivalent to some serial order), how to test that (conflict / precedence graph), and how recoverability, cascading aborts and strictness relate.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Database engines interleave transactions to improve concurrency. Engineers use schedules and serialisability to check that an interleaving is "correct" (it preserves consistency as if transactions ran one after another). Also, recoverability and strictness govern abort behavior and crash-recovery safety in implementations (locking, MVCC, etc.).

Key ideas

  • Serial schedule: a schedule in which transactions execute one after another with no interleaving. Example: all operations of T1 then all of T2.

  • Serializable schedule: a (possibly interleaved) schedule S is serializable if its effect on the database is the same as the effect of some serial schedule of the same transactions.

  • Conflict (on the same data item X): two operations conflict if they are by different transactions and at least one is a write. Thus the pairs that conflict are: (read, write), (write, read), (write, write) on the same item.

  • Conflict-equivalence: two schedules are conflict-equivalent if one can be transformed into the other by swapping adjacent non-conflicting operations (swapping only preserves the internal order of each transaction). A schedule is conflict-serializable if it is conflict-equivalent to some serial schedule.

  • Construction used in many proofs: swapping adjacent non-conflicting operations does not change the effect of the schedule on any item.

  • Precedence (conflict) graph: directed graph G = (V, E). V = {transactions in S}. There is a directed edge Ti -> Tj if an operation of Ti occurs before and conflicts with an operation of Tj on the same data item in S. (Label each edge optionally with the data item and conflict type.)

    • How to draw (diagram to draw in exam): draw one node for each transaction Ti (label nodes T1, T2, ...). For every pair of conflicting operations op from Ti then op' from Tj on same item, draw an arrow Ti -> Tj. If multiple conflicts exist, you may annotate with the items.
  • Theorem (exact statement universities expect):

    • A schedule S is conflict-serializable iff the precedence graph of S is acyclic.

    • Assumptions: schedules contain only reads/writes (and commit/abort) and conflicts defined as above.

    • Proof sketch (two directions, step-by-step):

      1. If S is conflict-serializable, then precedence graph is acyclic.
        • If S is conflict-equivalent to a serial schedule with order Tα1, Tα2, ..., then any edge Ti -> Tj in the precedence graph means Ti has a conflicting op before Tj's op in S, so in any conflict-equivalent serial schedule Ti must appear before Tj. Thus edges respect serial order; impossible to have a cycle.
      2. If precedence graph is acyclic, then S is conflict-serializable.
        • Take a topological order of the acyclic graph, say Ti1, Ti2, ..., Tin. Show we can transform S by repeatedly swapping adjacent non-conflicting operations to obtain the serial schedule in that topological order: because there is no edge from later transaction to earlier one, each time we can move all operations of the earliest-in-topological-order transaction leftwards past non-conflicting operations until its operations are contiguous and first. Remove that transaction and repeat. Each swap moves non-conflicting adjacent operations and so preserves conflict-equivalence. After n steps we reach the serial schedule. Therefore S is conflict-serializable.
  • View serializability (brief): a more general notion. S is view-equivalent to a serial schedule if the reads-from and final-writes are preserved: (1) for every read of X by Ti, it reads the value written by the same transaction Tj in both schedules (treat the initial value as written by a special T0), and (2) for each data item X, the transaction that performs the final write on X is the same in both. Every conflict-serializable schedule is view-serializable, but not vice versa. Deciding view-serializability is NP-complete in general, whereas conflict-serializability can be tested in polynomial time via the acyclicity of the precedence graph.

  • Recoverable schedule: a schedule is recoverable if whenever Ti reads X from Tj (i.e., Ti reads the value of X last written by Tj), Ti commits only after Tj commits. This avoids committing based on uncommitted data that might later be rolled back.

  • Cascadeless schedule (avoids cascading aborts): a schedule is cascadeless if no transaction reads uncommitted data (i.e., every read reads only values written by committed transactions). Cascadeless implies recoverable.

  • Strict schedule: no other transaction may read or write a data item X that has been written by an uncommitted transaction (a transaction may, of course, access its own uncommitted writes). Equivalent formal statement: if Tj wrote X and has not yet committed, then no other Ti may read or write X. Strict implies cascadeless (and hence recoverable). Many systems implement strict two-phase locking to achieve this.

  • Relationship summary (implications): strict => cascadeless => recoverable (all implications are one-way).

Formulas

r_i(X) — transaction Ti reads item X (no units).

w_i(X) — transaction Ti writes item X.

c_i, a_i — Ti commits or aborts respectively.

Edge: Ti -> Tj in precedence graph means there exist operations op in Ti and op' in Tj on same item X, op occurs before op' in schedule, and op and op' conflict (i.e., at least one is a write).

Conflict-serializable(S) ⇔ precedence_graph(S) is acyclic — applies under the conflict definition above.

strict ⇒ cascadeless ⇒ recoverable — relation among schedule classes.

Worked examples

Example 1 — detect conflict-serializability (typical exam question)

Question (model): Given transactions T1 and T2 and schedule S with operations in order:

  1. r1(A)
  2. w2(A)
  3. r2(B)
  4. w1(B)
  5. c1
  6. c2

Decide if S is conflict-serializable. If yes, give an equivalent serial order; if no, show why.

Answer (model steps):

  1. List conflicting pairs (different transactions, same item, one write):
    • r1(A) and w2(A): r1(A) occurs before w2(A) on A and (read, write) conflict ⇒ edge T1 -> T2.
    • r2(B) and w1(B): r2(B) occurs before w1(B) on B and (read, write) conflict ⇒ edge T2 -> T1.
  2. Build precedence graph: nodes {T1, T2}. Edges: T1 -> T2 and T2 -> T1. This is a cycle.
  3. Since the precedence graph has a cycle, by the theorem S is NOT conflict-serializable.

Conclude: S is not conflict-serializable; no serial order is conflict-equivalent to S.

Example 2 — recoverability and strictness (typical theory question)

Question (model): Consider schedule S:

  1. w1(X)
  2. r2(X)
  3. a1
  4. c2

Is S recoverable? Does it cause cascading aborts? Is it strict?

Answer (model steps):

  1. Interpretation: T1 writes X (uncommitted), then T2 reads X, then T1 aborts, then T2 commits.
  2. Recoverable? No — T2 committed after reading a value written by T1, but T1 later aborted. Recoverable schedules require that if Ti reads from Tj, Ti must commit only after Tj commits. Here T2 committed before T1 committed (T1 aborted), so not recoverable.
  3. Cascading aborts? Yes — because T2 read uncommitted data from T1 and when T1 aborts, T2 must be aborted too to restore consistency (a cascading abort). So schedule causes cascading aborts.
  4. Strict? No — T2 read a value written by an uncommitted T1; strict forbids reads or writes of items written by uncommitted transactions. So not strict.

Remark: If T2 had read only committed values, the schedule would be cascadeless; if additionally no one wrote uncommitted values that others touch, schedule can be strict (example: use exclusive locks until commit).

Common mistakes

  • Forgetting that read/read on the same item do not conflict.

  • In recoverability questions, students forget to consider the commit times: a read from an uncommitted write is allowed but makes schedule non-cascadeless; commit order determines recoverability.

  • Mixing up definitions: strict means neither read nor write on an item allowed if it was written by an uncommitted transaction; cascadeless forbids only reading uncommitted writes.

For your exam

Types of questions you will get:

  • Definitions and short notes: define serializability, conflict vs view, precedence graph, recoverable/cascadeless/strict.
  • Diagrams: draw precedence graph and explain edges; the diagram must label nodes with transaction names and edges with the item causing the edge (if asked).
  • Derivations and proofs: show theorem "acyclic precedence graph ⇔ conflict-serializable" — include the swap argument and topological sort argument.
  • Problem solving: given a schedule, list all conflicts, draw graph, decide conflict-serializable and give equivalent serial order if it exists; classify schedule as recoverable/cascadeless/strict.

What a full-marks answer includes:

  • Precise definitions with bold names (serial, serializable, conflict, precedence graph).
  • Correct conflict list and correctly directed edges (explicitly state the conflicting pairs and why they conflict).
  • A clear precedence graph (drawn or described) and correct cyclic/acyclic conclusion.
  • For proofs, both directions: show acyclic implies can reorder to serial and conflict-serializable implies acyclic.
  • For recoverability/strictness: list reads-from relationships and commit times and state classification with reasoning.

Quick check

  1. Define a conflict between operations.
  2. How do you construct the precedence graph for a schedule? (short steps)
  3. State the relationship among strict, cascadeless and recoverable schedules.

Answers: 1) Two operations conflict if they are by different transactions, on the same item, and at least one is a write. 2) Create a node per transaction; for every pair of conflicting operations op in Ti before op' in Tj on same item, draw Ti -> Tj. 3) strict ⇒ cascadeless ⇒ recoverable.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?