판정 포인트
트랜잭션 수가 늘어나도 보는 것은 같고, 일부 노드만의 사이클이어도 전체 스케줄은 직렬화할 수 없습니다.

스케줄 전체를 외우지 말고 충돌 관계만 간선으로 압축합니다. 그 간선이 다시 출발점으로 돌아오면 선후 제약이 서로 모순됩니다.

1. 충돌 연산만 남겨 간선을 뽑기

읽기-읽기는 제외
항목 A
R1(A) < W3(A)
T1 → T3
항목 A
W3(A) < W1(A)
T3 → T1
항목 B
W2(B) < R3(B)
T2 → T3
같은 데이터 항목에서 순서가 충돌하는 연산만 남기면, 각 간선은 누가 먼저 와야 하는지만 간단히 보여줍니다.

2. 선행 그래프로 옮겨 판정하기

고리가 보이면 종료
사이클은 T1과 T3만으로 완성 T1 A를 먼저 읽음 T3 A를 갱신 T2 B를 먼저 씀
핵심 판정

T1 → T3 → T1 이 이미 원형 제약을 만들므로, 전체 스케줄은 충돌 직렬 불가능입니다.

자주 놓치는 점

T2가 고리에 직접 들어가지 않아도 됩니다. 세 개 이상일 때는 부분 사이클 하나만 발견해도 판정이 끝납니다.

읽는 순서

충돌 추출 → 선행 그래프 작성 → 사이클 확인 순서만 지키면 됩니다. 트랜잭션 수가 많아져도, 그래프의 어느 일부에서든 고리가 생기면 하나의 직렬 순서로 펼칠 수 없습니다.