[DB] 트랜잭션 스케줄 (직렬 가능성 검사)

 

직렬 가능성 검사

.

 

 

직렬 가능 스케줄인지 판단하는 것은 중요하다.

그러나 뷰 직렬 가능성을 판단하기 위한 효율적인 알고리즘은 없다고 증명되었다.

 

대부분의 병행성 제어 기법에서는 실제로 직렬성 검사를 하지 않는다.

 

대신 직렬 가능 스케줄을 보장하는 규약이나 규칙등을 개발해서

스케줄에 참여하고 있는 모든 트랜잭션들이 이 규약을 준수하게 만드는 것이다.

 

 

알고리즘은 '판독'과 '기록' 연산만 점검한다.

스케줄 S가 직렬 가능한가를 검사하기 위해서는 스케줄에 대한 '선행 그래프'를 만들어야 한다.

 

만약 구축된 선행 그래프에서 사이클이 있으면 스케줄 S는 충돌 직렬 가능이 아니고

사이클이 없으면 직렬 가능이다.

 

 

[알고리즘] 스케줄의 충돌 직렬 가능성 검사

 

1	스케줄 S에 포함된 각 트랜잭션 Ti에 대해 선행 그래프에 Ti 노드를 생성
2	S에서 Ti가 write(x)한 x의 값을 Tj가 read(x)를 수행하면 간선 (Ti -> Tj)를 삽입
3	S에서 Ti가 read(x)한 뒤에 Tj가 write(x)를 하는 경우에 간선 (Ti -> Tj)를 삽입
4	S에서 Ti가 write(x)를 한 뒤에 Tj가 바로 write(x)를 하면 간선 (Ti -> Tj)를 삽입
5	이 선행 그래프에 사이클이 없으면 충돌 직렬 가능, 있다면 직렬 불가능

 

선행 그래프에서 Ti로부터 Tj로 연결된 간선이 있을 때

Ti는 동등한 직렬 스케줄 S'에서 Tj보다 반드시 선행하게 한다.

 

이 과정을 '위상 정렬'이라 하고, 이 결과를 '위상 순서'라 한다.

 

일반적으로 선행 그래프에 사이클이 없다면 S와 동등한 직렬 스케줄을 여러 개 만들 수 있고,

사이클이 있다면 S에 동등한 직렬 스케줄을 만들 수 없다.

 

 

 

왼쪽은 사이클이 없으므로 직렬 가능하며, 오른쪽은 사이클이 있으므로 직렬 불가능하다.

 

 

 

 

 

 

 

 

* 해당 글은 '데이터베이스 시스템' 책을 참고하여 작성하였습니다. 출처: 데이터베이스 시스템 (이석호)