A · Compressed recap
Directed graphs: a topological order exists iff the graph is acyclic; take vertices with no incoming edges first. Conflicts: different transactions, same item, at least one write. Precedence graph: Ti → Tj when Ti's conflicting operation comes first; CS ⇔ acyclic, serial orders = topological orders. View equivalence: same initial reads, reads-from and final writes. VS ⊇ CS; the gap needs blind writes; without blind writes VS = CS.
B · Merged rule card
6.4.1 Directed graph primer: cycles, topological order
- Directed graph: vertices, edges u → v; path; cycle; DAG = acyclic.
- Topological order exists ⇔ acyclic.
- Algorithm: repeatedly take a vertex with no incoming edge (among remaining).
- Several choices → several orders; no edges → n! orders.
6.4.2 Conflict serializability: conflicting ops, precedence graph, equivalent serial orders
- Conflict: different transactions, same item, ≥ 1 write (RW, WR, WW).
- Conflict equivalent: same order for every conflicting pair.
- Precedence graph: Ti → Tj when Ti's conflicting op is first. CS ⇔ acyclic; serial orders = topological orders.
- Count conflict-equivalent schedules by fixing conflicting pairs and counting free interleavings.
6.4.3 View serializability; blind writes; relation to conflict serializability
- View equivalent: same initial reads, same reads-from, same final writes, for every item.
- VS = view equivalent to some serial schedule. CS ⊂ VS.
- VS but not CS ⇒ blind write (write without prior read). No blind writes ⇒ VS = CS.
- Test: CS? → VS. Not CS and no blind write → not VS. Else check the three conditions against candidate serial orders.
C · Interleaved GATE-style questions
Q1 · MCQ · 1 mark(s) — Graph
Edges T1 → T2, T3 → T2. How many topological orders?
- (A) 6
- (B) 3
- (C) 1
- (D) 2
Q2 · MCQ · 2 mark(s) — CS
S = R1(A) R2(B) W1(B) W2(A). Is S conflict serializable?
- (A) Yes, as T1, T2
- (B) Yes, as T2, T1
- (C) No
- (D) Yes, both orders
Q3 · NAT · 2 mark(s) — Count
T1 = R1(A) W1(A), T2 = R2(A) W2(A). How many of the 6 schedules are conflict serializable?
Numerical answer: ________
Q4 · MCQ · 2 mark(s) — Serial order
S = R1(A) W1(A) R2(A) W2(A) R3(A) W3(A) is conflict equivalent to:
- (A) T1, T2, T3
- (B) T2, T1, T3
- (C) none
- (D) T3, T2, T1
Q5 · MCQ · 2 mark(s) — VS
S = W1(A) R2(A) W2(A) W3(A) R1(B). Which is true?
- (A) S is CS.
- (B) S is not a valid schedule.
- (C) S is neither.
- (D) S is VS but not CS.
Q6 · MSQ · 2 mark(s) — Blind writes
Which schedules contain a blind write?
- (A) R1(A) W2(A) W1(A)
- (B) R1(A) W1(A)
- (C) W1(A) R1(A)
- (D) R2(B) W2(A)
Q7 · MCQ · 1 mark(s) — Conflict
Which operation pair never produces a precedence edge?
- (A) R–W on the same item, different transactions
- (B) R–R on the same item, different transactions
- (C) W–W on the same item, different transactions
- (D) W–R on the same item, different transactions
Q8 · NAT · 2 mark(s) — Count
T1 = R1(A) W1(A) R1(B) W1(B), T2 = R2(A) W2(A) R2(B) W2(B). How many schedules are conflict equivalent to T1;T2?
Numerical answer: ________
D · Answer Vault
Reveal answers when you’re ready
Q1 Answer: (D) · 1 mark(s)
T1 and T3 in either order, then T2.
- (A) is wrong: Constrained.
- (B) is wrong: T2 must be last.
- (C) is wrong: Two choices at the start.
Re-read: Lesson 6.4.1 — Directed graph primer: cycles, topological order
Q2 Answer: (C) · 2 mark(s)
R1(A) before W2(A): T1 → T2. R2(B) before W1(B): T2 → T1. Cycle.
- (A) is wrong: T2 → T1 also exists.
- (B) is wrong: T1 → T2 also exists.
- (D) is wrong: No.
Re-read: Lesson 6.4.2 — Conflict serializability: conflicting ops, precedence graph, equivalent serial orders
Q3 Answer: 2 · 2 mark(s)
Only the two serial ones; every interleaving creates a cycle on A.
Re-read: Lesson 6.4.2 — Conflict serializability: conflicting ops, precedence graph, equivalent serial orders
Q4 Answer: (A) · 2 mark(s)
Edges T1 → T2 → T3 (and T1 → T3).
- (B) is wrong: T1 must precede T2.
- (C) is wrong: It is CS.
- (D) is wrong: Reversed.
Re-read: Lesson 6.4.2 — Conflict serializability: conflicting ops, precedence graph, equivalent serial orders
Q5 Answer: (A) · 2 mark(s)
Edges T1 → T2, T1 → T3, T2 → T3: acyclic (order T1, T2, T3).
- (B) is wrong: Valid.
- (C) is wrong: It is CS.
- (D) is wrong: It is CS.
Re-read: Lesson 6.4.3 — View serializability; blind writes; relation to conflict serializability
Q6 Answer: (A) (C) (D) · 2 mark(s)
A: W2(A) without R2(A). C: W1(A) before any read by T1. D: T2 writes A without reading A.
- (B) is wrong: T1 read A first.
Re-read: Lesson 6.4.3 — View serializability; blind writes; relation to conflict serializability
Q7 Answer: (B) · 1 mark(s)
Two reads never conflict.
- (A) is wrong: Conflict.
- (C) is wrong: Conflict.
- (D) is wrong: Conflict.
Re-read: Lesson 6.4.2 — Conflict serializability: conflicting ops, precedence graph, equivalent serial orders
Q8 Answer: 6 · 2 mark(s)
Lesson 6.4.2.
Re-read: Lesson 6.4.2 — Conflict serializability: conflicting ops, precedence graph, equivalent serial orders