Schedules Read operations can be done in parallel while read/write and write/write have to be done according to the specified order Example: T=(R(X), R(y),Z=X+y, w(z,Cj R(X) and r(y) can be done in parallel but W(z)must follow(x) /R(y) R(X)R(y) W(z Ime Department of Computer Science and Engineering, HKUST 16
Department of Computer Science and Engineering, HKUST 16 Read operations can be done in parallel while read/write and write/write have to be done according to the specified order Example: T = { R(x), R(y), z = x+y, W(z), C } R(x) and R(y) can be done in parallel but W(z) must follow R(x)/R(y) R(x),R(y) W(z) C Time Schedules
Representation of a Schedule The schedule for a transaction T can be represented by a DAG(Directed Acyclic Graph) R(X) W(z R(y) Order along the time axis No particular ordering Department of Computer Science and Engineering, HKUST 17
Department of Computer Science and Engineering, HKUST 17 The schedule for a transaction T can be represented by a DAG (Directed Acyclic Graph) R(x) R(y) W(z) C Representation of a Schedule Order along the time axis No particular ordering
Serializability Theory For every transaction T, we have a set of operations executed by the transaction, like R(x), W(x),C a For each transaction these operations are executed in some order according to a schedule The serializability theory defines the correctness of a schedule and provides a mechanism for testing the correctness Department of Computer Science and Engineering, HKUST 18
Department of Computer Science and Engineering, HKUST 18 Serializability Theory • For every transaction T, we have a set of operations executed by the transaction, like R(x), W(x), C, A • For each transaction these operations are executed in some order according to a schedule • The serializability theory defines the correctness of a schedule and provides a mechanism for testing the correctness
Serializability Theory( Cont Two operations in a set of transactions are conflicting if they both operate on the same data item and at least one of them is a Given Ti and Ti the following pairs contain conflicting opreations R(x),W(×) W(),WiX) Conflicting operations among transactions must be ordered R(x) precedes w(×),orW」(x) precedes r(x) W (X) precedes W,(x),or W, (x)precedes W; (X) Department of Computer Science and Engineering, HKUST 19
Department of Computer Science and Engineering, HKUST 19 • Two operations in a set of transactions are conflicting if they both operate on the same data item and at least one of them is a write • Given Ti and Tj , the following pairs contain conflicting opreations – Ri (x), Wj (x) – Wi (x), Wj (x) • Conflicting operations among transactions must be ordered – Ri (x) precedes Wj (x), or Wj (x) precedes Ri (x) – Wi (x) precedes Wj (x), or Wj (x) precedes Wi (x) Serializability Theory (Cont.)
Example 1 T1:{R1(x),X=x+1,W1(x),C1} T2:{R2(x),x=x+1,W2(x),C2} Conflicting operations between T, and t, {(R1(x),W2(x),(R2(x)W1(x),(W1(x),W2(x))} Note that this is Not a precedence We need to order these conflicting operations, e.g. graph(introduced next) TI RI(X) R2(x)→>W1(x) W2(x)→>W1(x) R2(X) W2(X) A Schedule Department of Computer Science and Engineering, HKUST 20
Department of Computer Science and Engineering, HKUST 20 T1 : {R1 (x), x = x+1, W1 (x), C1} T2 : {R2 (x), x = x+1, W2 (x), C2} Conflicting operations between T1 and T2 : { (R1 (x), W2 (x)) , (R2 (x), W1 (x)) , (W1 (x), W2 (x)) } We need to order these conflicting operations, e.g., Example 1 R1 (x) → W2 (x) R2 (x) → W1 (x) W2 (x) → W1 (x) T1 R1 (X) W1 (X) R2 (X) W2 (X) C2 C1 T2 A Schedule Note that this is NOT a precedence graph (introduced next)