Part 5 of 5 · 4 min read
Exercises
Easy
Easy 1: Define a serial schedule (15 minutes)
State, in one sentence, what makes a schedule serial.
Done when: each transaction's operations running completely before the next transaction begins is correctly described.
Hint
Each transaction's operations execute completely, in order, before the next transaction's operations begin.
Easy 2: Name the precedence-graph test (15 minutes)
State what property of a precedence graph determines whether a schedule is conflict serializable.
Done when: the absence of a cycle is correctly named.
Hint
The absence of a cycle in the precedence graph.
Easy 3: Order the three schedule strictness levels (15 minutes)
Order recoverable, cascadeless, and strict from least strict to most strict.
Done when: recoverable, then cascadeless, then strict is correctly given.
Hint
Recoverable, then cascadeless, then strict.
Medium
Medium 1: Determine if a conflict exists (25 minutes)
Transaction A reads row X, and transaction B, from a different transaction, later writes row X. Determine whether this pair of operations conflicts, and why.
Done when: yes is correctly concluded, since the operations come from different transactions, access the same data item, and at least one is a write.
Hint
Yes, since they come from different transactions, touch the same data item, and at least one of the two operations is a write.
Medium 2: Build a simple precedence graph (25 minutes)
Transaction A's write to row X happens before transaction B's read of row X; transaction B's write to row Y happens before transaction A's read of row Y. Determine whether the resulting precedence graph has a cycle, and whether the schedule is conflict serializable.
Done when: a cycle (A to B and B to A) is correctly identified, with the schedule correctly concluded to not be conflict serializable.
Hint
A cycle exists (A to B and B to A), so the schedule is not conflict serializable.
Medium 3: Classify a schedule's strictness (30 minutes)
A schedule lets transaction B read a value transaction A wrote, before A has committed, but B does not commit until after A commits. Determine whether this schedule is recoverable, cascadeless, both, or neither.
Done when: the schedule is correctly classified as recoverable (the writer commits before the reader) but not cascadeless (the read happened before the writer committed).
Hint
Recoverable, since the writer commits before the reader does, but not cascadeless, since the read of the uncommitted value happened before the writer's commit.
Hard
Hard 1: Explain why a serial schedule is always conflict serializable (30 minutes)
Explain why every serial schedule is automatically conflict serializable, with no need to check a precedence graph.
Done when: the explanation correctly notes a serial schedule is trivially equivalent to itself, since conflict serializability asks whether a schedule is equivalent to some serial schedule, and a serial schedule already is one.
Hint
A serial schedule is trivially equivalent to itself, and conflict serializability is defined as being equivalent to some serial schedule, so every serial schedule automatically satisfies its own definition.
Hard 2: Explain the risk a non-cascadeless schedule introduces (35 minutes)
Explain, using an example, why a schedule that is recoverable but not cascadeless can still cause a problem if the writing transaction aborts.
Done when: the explanation correctly describes a reader having already read an uncommitted value, so if the writer then aborts, the reader's own result is now based on data that was never actually committed, potentially forcing the reader to be aborted too, cascading the failure.
Hint
The reader has already consumed a value that was never committed; if the writer aborts, the reader's result is now based on data that effectively never existed, and correctness may require aborting the reader too, which can cascade further if other transactions read from the reader in turn.
Hard 3: Connect serializability to the locking protocols ahead (40 minutes)
Explain, in general terms, why a locking protocol, covered two pages from now, would need to be specifically designed to guarantee conflict serializability, rather than simply preventing any two transactions from ever running concurrently.
Done when: the explanation correctly notes that preventing all concurrency would sacrifice the performance benefit concurrency provides, so a well-designed locking protocol instead needs to allow safe interleavings, specifically ones that remain conflict serializable, rather than forbidding concurrency outright.
Hint
Forbidding all concurrency would eliminate the performance benefit concurrency exists to provide, so a locking protocol instead aims to allow interleavings that still guarantee conflict serializability, preserving both correctness and some real degree of concurrent execution.