3.

Q: Suppose the following execution of transactions:

T1         T2

begin                
           begin
read(x)
           write(y)
           write(z)
           commit
read(y)
commit



A:

Forward validation:

begin
           begin
read(x)              readSet(T1) = {x}
           write(y)  writeSet(T2) = {y}
           write(z)  writeSet(T2) = {y,z}
	   validate  activeTMin(T2) = {T1}, activeTMax(T2) = {T2}
           commit
read(y)              readSet(T1) = {x,y}
validate             activeTMin(T1) = {T1}, activeTMax(T1) = {T1}
commit

So, writeSet(T1) == {} and readSet(T2) == {}


Validation of T2:

valid = true;
for(all txns T' from activeTMin(T2) to activeTMax(T2)) // == T1,T2
  check if(T != T' && writeSet(T2) intersects with readSet(T1))
    // Sets do not intersect, ( {y,z} U {x} == {} ), since T1 hasn't yet read y
return valid /* == true and T2 commits


Validation of T1:

valid = true;
for(all txns T' from activeTMin(T1) to activeTMax(T1)) // == T1
  check if(T != T' && writeSet(T1) intersects with readSet(T2))
    // == false, because T1 == T1
return valid // == true and T1 commits



Backward validation:

T1         T2

begin                startTMax(T1) = {T0}
           begin     startTMax(T2) = {T0}
read(x)              readSet(T1) = {x}
           write(y)  writeSet(T2) = {y}
           write(z)  writeSet(T2) = {y,z}
	   validate  finishTMax(T2) = {T2}
           commit
read(y)              readSet(T1) = {x,y}
validate             finishTMax(T1) = {T2}
commit

So, writeSet(T1) == {} and readSet(T2) == {}


Validation of T2:

valid = true;
for(all txns T' from startTMax(T2) + 1 to finishTMax(T2)) // == T1
  check if(T != T' && readSet(T2) intersects with writeSet(T1))
    // == false, because both sets are empty
return valid // == true and T2 commits

Validation of T1:

valid = true;
for(all txns T' from startTMax(T1) + 1 to finishTMax(T1)) // == T2
  check if(T != T' && readSet(T1) intersects with writeSet(T2))
    // Sets intersect, ( {y,z} U {x,y} == {y} )
    valid = false;
return valid // == false, so T1 is rolled back