1.3 How to Test Serializability

Testing for Conflict Serializability

Consider a schedule with transactions T1, T2, ..., Tn

Precedence graph

–A direct graph where the vertices are the transactions

–We draw an arc from Ti to Tj if the two transactions conflict, and Ti accesses the data item on which the conflict arises earlier

–We may label the arc by the item that is accessed

 

Precedence Graph Example 1

 

 

 

 

 

 

 

 

 

스케줄에 대한 선행 그래프를 작성한 예제이다. 선행 그래프에 사이클이 있으므로 해당 스케줄은 충돌 직렬가능 스케줄이 아니다.

Precedence Graph Example 2

schedule 11

선행 그래프에 대한 우리의 관심은 사이클 존재 여부이므로, 중복되는 엣지는 그래프 작성 시에 표기하지 않아도 된다.

스케줄에 의한 선행 그래프에는 사이클이 없으므로 해당 스케줄은 충돌 직렬가능 스케줄이다.

Cycle detection in precedence graphs is cheap

A schedule is conflict serializable if and only if its precedence graph is acyclic

Cycle-detection algorithms exist which take order n2 (or n+e) time complexity, where n is the number of vertices and e is the number of edges

If precedence graph is acyclic, the serializability order can be obtained by a topological sorting of the graph

 

–A linear order consistent with the partial order of the graph

–For example, a serializability order for Schedule 11 would be
T5 -> T1 -> T3 -> T2 -> T4

–There are actually 10 serialization orders!!!

선행 그래프는 방향성 그래프이며, 방향성 그래프에서 사이클 존재 여부 판별은 간단하고 저렴한 연산이다.

위상 정렬(topological sort)은 부분 순서를 가지는 노드(트랜잭션)에 대하여 부분 순서를 만족하면서 전체 노드를 정렬하는 방식이다. 스케줄 11 선행 그래프에는 총 5개의 노드가 있으며 노드 간에는 부분 순서가 결정되어 있다. 스케줄 11 선행 그래프에 대하여 위상 정렬을 하면 T2, T3 간에는 순서가 없으므로 2개 정렬이 나오고 또한 T5는 다른 노드와 순서가 없으므로 5가지 정렬이 가능하므로 총 10개의 위상정렬이 가능하다.

  - T1 T2 T3 T4 T5     - T1 T2 T3 T5 T4

  - T1 T2 T5 T3 T4   - T1 T5 T2 T3 T4

  - T5 T1 T2 T3 T4   - T1 T3 T2 T4 T5

  - T1 T3 T2 T5 T4   - T1 T3 T5 T2 T4

  - T1 T5 T3 T2 T4   - T5 T1 T3 T2 T4

 

<T1,T2,T3,T4> T5  => T5가 1,2,3,4의 전후로 들어갈 경우 5가지

<T1,T3,T2,T4> 5  => T5가 1,2,3,4의 전후로 들어갈 경우 5가지

총 10가지 직렬 스케줄