[Transaction] easy test Serializability

Conflict Serializability 확인 방법

Precedence graph를 그려서 아이템에 대해서 edge를 그려서 cycle이 존재하는지 파악하면 된다. cycle이 없으면 conflict serializable

precedence graph: direct graph, vertex is transaction, conflict 연산이 있으면 edge 연결

 

위 방법으로 확인하고 나서 어떤 serial schedule과 결과가 일치하는지 알 수 있을까? topological sorting을 통해 찾을 수 있다.

 

위와 같은 graph를 그렸다고 하면 T1은 T2,T3,T4보다 먼저 와야하고 T4는 T1,T2,T3보다 먼저와야 한다. 

T1-> T2 ->T3 ->T4

T1-> T3-> T2 ->T4

T1~T4만 보면 위와 같은 두 가지가 가능하고 T5는 순서에 상관없다. 따라서 10가지의 경우가 나온다.

 

 

view serializability은 easy test가 불가능하다. 따라서 휴리스틱한 방법으로 진행한다. 3번 조건만 체크한다던지 하는 식으로 휴리스틱으로 해결한다.