[Concurrency Control] 2PL ensure conflict serializability?

Proof

2PL 이 serializabizable schedule을 보장하지 못한다고 가정해보자.

precedence graph를 그려서 cycle이 생겨야한다. 

T0->T1-> ... -> Tn->T0 이라고 하자.

ai는 Ti의 lock point라고 하자.(phase 1에서 2로 넘어가는 부분)

 

2PL은 lock을 얻는 단계와 lock을 푸는 단계로 나뉜다.

 

lock

lock

lock

unlock

unlock

와 같은 방식이다.

 

Ti     Tj

R(Q)

unlock

       W(Q)

       ...

       unlock

 

와 같이 있으면 충돌연산이기 떄문에 Ti의 Q를 락 푸는 시점이 Tj의 Q를 락 푸는 시점보다 빠르다. 일반화 시키면 Ti->Tj이면 ai->aj인데 cycle이 있다고 했기 때문에 T0->T0 순서이기 때문에 a0 < a0이어야 한다. 이것은 모순이다.