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

2023.06.02 - [DB] - [DB] 병행 제어 (동시 공용 문제점)

[DB] 병행 제어 (동시 공용 문제점)

 

 

트랜잭션 스케줄

.

 

 

이전 글에서의 문제들의 원인은 공용하는 충돌된 데이터를 통해

트랜잭션들 사이에 간섭이 일어나기 때문이다.

 

 

충돌이란 두 개의 연산이 각각 상이한 트랜잭션에 속하고 있으면서

동일한 데이터 아이템을 처리 대상으로 하고 있고

이때 적어도 하나의 연산은 기록 연산이 되는 경우를 말한다.

 

 

연산의 인터러빙이 허용된다면 트랜잭션들의 개개 연산들을 실행시킬 수 있는 순서는 여러가지다.

이러한 트랜잭션들의 연산들을 실행하는 순서를 그 트랜잭션들의 '스케줄'이라 한다.

 

 

직렬 가능 스케줄

.

 

 

 

위의 T1과 T2의 직렬 스케줄 예는 아래와 같이

T1을 먼저 실행하고 다음에 T2를 실행하거나

T2를 먼저 실행한 다음 T1을 실행하는 두 가지 스케줄이 있다.

 

 

 

 

스케줄에 포함된 모든 트랜잭션의 연산들을

각 소속 트랜잭션별로 모두 연속적으로 실행하는 스케줄을 '직렬 스케줄'이라 하고,

그 이외의 스케줄, 즉 인터리브 실행이 포함되어 트랜잭션들을

병행 실행시키는 스케줄을 '비직렬 스케줄'이라 한다.

 

아래는 T1과 T2의 비직렬 스케줄이다.

 

 

 

 

만일 n개의 트랜잭션에 대한 비직렬 스케줄 S가 똑같은 이 n개의 트랜잭션에 대한

어떤 직렬 스케줄S'과 동등하다고 하면 이 스케줄 S를 '직렬 가능 스케줄'이라 한다.

즉, 직렬 스케줄과 동등해서 직렬 가능한 것과 동등하지 않아 직렬 가능하지 않은 것으로 구분된다.

 

비직렬 스케줄 S가 직렬 가능하다고 하는 것은 S가 정확하다고 말하는 것과 같다.

 

 

스케줄 동등과 직렬 가능 스케줄

 

동일한 초기 상태에서 두 개의 상이한 스케줄로 생성된 데이터베이스의 최종 결과가 모두 똑같다면

이 두 스케줄은 '결과 동등'이라 한다.

 

하지만 이 방법을 다른 트랜잭션들에 적용하여 실행하면 항상 동일한 결과를 생성하는 것이 보장되지 않는다.

 

이러한 이유로 결과 동등성은 스케줄 동등성 정의에 사용되지 않는다.

 

 

충돌 동등과 충돌 직렬 가능 스케줄

 

두 스케줄이 동등하기 위해서는 두 스케줄에 의해 영향을 받는 모든 레코드들에 대한 연산들이

두 스케줄에서 모두 똑같은 순서로 이 레코드들에 적용되어야 한다.

 

만일 두 스케줄에서 충돌 연산의 순서가 같으면 이 두 스케줄은 '충돌 동등'이라 한다.

 

예로, read와 write 연산이 트랜잭션 T1과 T2에 대한 스케줄 Si에서는

read1(x), write2(x) 순서로 되어 있고,

다른 스케줄 Sj에서는 write2(x), read1(x) 순서로 되어 있다면

read1(x)로 읽혀진 값은 두 스케줄에서 다를 수 있다.

 

만일 n개의 트랜잭션에 대한 어떤 (비직렬) 스케줄 S가 같은 n개의 트랜잭션에 대한

어떤 직렬 스케줄 S'과 충돌 동등하다면 스케줄 S는 '충돌 직렬 가능 스케줄'이라 한다.

 

앞의 '비직렬 스케줄' 그림은 '충돌 직렬 가능 스케줄'이다.

 

 

스케줄에서 충돌 연산이 아닌 두 연속 연산은 그 순서를 교환하더라도 상관없다.

이것을 '비충돌 연산 교환 원리'라 한다.

이 원리를 이용하여 앞의 그림 '비직렬 스케줄'은 그림 '직렬 스케줄'로 변환시킬 수 있고,

직렬 가능 스케줄이라는 것을 알 수 있다.

 

 

 

 

 

 

 

 

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

* 참고 사이트: https://rebro.kr/164