A를 먼저 쓴다. 이후 다른 트랜잭션이 A를 읽거나 쓰면 순서 제약이 생긴다.
Precedence Graph
선행 그래프로 충돌 직렬 가능성을 검증한다
같은 데이터 항목을 접근한 두 트랜잭션 중 하나 이상이 쓰기라면 충돌이다. 먼저 실행된 충돌 연산의 트랜잭션에서 나중 트랜잭션으로 간선을 그리면, 스케줄이 어떤 직렬 순서와 같은지 그래프로 확인할 수 있다.
노드
간선
무사이클
T1 → T2
T1이 쓴 A를 뒤에서 읽는다. 따라서 직렬 순서에서도 T1이 T2보다 앞서야 한다.
R1(A), W2(A)처럼 같은 항목을 만지는 연산만 비교한다. 다른 항목끼리는 간선을 만들지 않는다.
R-W, W-R, W-W는 충돌이다. R-R은 결과를 바꾸지 않으므로 선행 그래프 간선에서 제외한다.
사이클이 없으면 위상 정렬 순서가 충돌 동등한 직렬 순서가 된다.
핵심은 간선 방향이다. Ti → Tj는 “Ti가 반드시 Tj보다 앞서야 한다”는
제약이며, 이 제약들이 서로 물고 돌아오면 충돌 직렬 가능하지 않다.