Precedence Graph

• Transaction을 node로 가지는 방향그래프
• confilct가 나면 : 먼저 실행하는 T → 나중에 접근한 T ⇒ 값을 레이블링

Conflict Serialiazbility 확인

• 싸이클이 없다. → conflict serialiable
• 사이클이 있으면 swap이 안된다.
• Cycle-detection 은 엄청 쉬운 알고리즘이다 : 시간복잡도 고려 x

Precedence Graph 그리는 법

1. 가장 먼저 T2 의 X를 보는데 밑에 아무도 X를 안쓰니깐 아무것도 안한다.
2. T1의 Y를 보는데 T2가 겹친다. 그래서 표시해준다.
3. 계속 Y가 있는지 확인한다. T4에도 있으니깐 T1→ T4 , T2→ T4
4. 만약 두개간 간다고 해도 선 두개를 그리는 것이 아니라 레이블만 추가함
5. 위에서부터 내려오면서 하나씩 확인 (다시 위로 돌아갈일 X)
6. 자기 혼자 데이터를 read write 하는 건 신경쓰지 않는다.

• T3, T2 둘중 아무거나 먼저 실행해도 된다.

Test for wiew Serializability

• 좋은 알고리즘은 없고 그냥 NP-complete 이다.
• View Serialiable 은 무조건 blind write 가 있는 것
• conflict가 아니면 확인하는데 blind write가 있는지 없는지도 확인하고 있으면 다시 확인해야한다. 없으면 그냥 아닌거