1.2 Serializability 직렬 가능

Correct Execution

•What are correct criteria of concurrent executed transactions???

•Two widely-accepted criteria

–Conflict serializable

–View serializable

Note, serial execution of transactions is always correct (why???)

 

올바른 실행

다수개의 트랜잭션을 동시에 수행할 때 올바른 트랜잭션 실행은 무엇인가를 결정하여야 한다. 트랜잭션은 다수 개의 데이터베이스 연산으로 구성이 되며, 다수개의 트랜잭션이 동시에 수행이 되면 타 트랜잭션에 속한 연산과 서로 혼합되어 수행이 될 것이며, 올바른 트랜잭션 실행에 대한 정확한 정의가 필요하다.

참고적으로 트랜잭션을 순차적으로 수행하는 직렬 방법은 항상 올바르며(correct), 이는 트랜잭션의 일치성 성질로 인하여 데이터베이스가 항상 일치하는 상태로 유지되기 때문이다. 그러나 직렬 트랜잭션 실행은 현실적으로는 운영이 불가능하며, 다만 올바른 트랜잭션 실행의 판단 기준으로 사용한다.

 

Nonserializable Execution

•There are three cases in which nonserializable execution causes problems, concurrency anomalies

 

트랜잭션을 올바르게 수행하지 못하는 경우 발생할 수 있는 현상은 오손읽기, 갱신 손실, 반복불가 읽기로 3가지이다.

1) dirty read (오손 읽기)

- T2 has seen dirty data

T1	T2
WRITE(A) ROLLBACK	READ(A) A = A + 50 WRITE(A)

오손읽기는 완료되지 않는 값(uncommitted value, dirty value)을 읽는 연산을 말한다. 상기에서 T2가 읽는 값은 아직 완료되지 않은 값이며, 만약 T1이 철회를 하면 T2 연산 또한 철회하여야 한다.

 

2) lost update (갱신 손실) 

- effect(i.e. update) of T2 is lost 

T1	T2
READ(A) A = A + 50 WRITE(A)	READ(A) A = A + 50 WRITE(A)

 갱신 손실은 T2가 쓴 값을 T1이 덮어쓰는 현상이며, 이 경우 T2의 효과는 데이터베이스에서 사라지게 된다.

 

3) unrepeatable read (반복불가 읽기)

T1	T2
READ(A) A = A + 50 WRITE(A)	READ(A) A = A + 50 WRITE(A)

반복불가 읽기는 T1이 처음에 읽는 A 값과 후에 읽은 A 값에 차이가 있게 되어, T1 관점에서는 A 값을 읽을 때마다 다른 값이 나오는 현상이다.

 

동시성 제어는 세 가지 현상을 방지하여 올바른 트랜잭션 수행에 대한 방법을 제시한다.  바르지 못한 실행으로 발생할 수 있는 현상은 오직 이 세 가지 현상뿐이며, 앞으로 전개되는 동시성 제어는 세 가지 현상을 방지하는 이론이다.

 

 

Serializability

Basic assumption

- each transaction preserves database consistency

A(possibly concurrent) schedule is serializable if it is equivalent to a serial schedule. Two different notions:

1) conflict serializability

2) view serializability

Simplified view of transactions

- ignore operations other than read and write instructions

- assume that transactions may perform arbitrary computations on data between reads and writes

- then, a simplified schedule consitsts of only reads and writes

직렬가능

스케줄이 직렬수행 스케줄 결과와 동일하면 우리는 이를 직렬가능(serializable) 스케줄이라고 한다. 스케줄에 관련되는 트랜잭션의 개수가 n개이면 가능한 직렬 스케줄은 n개의 트랜잭션을 나열하는 개수와 동일하므로 총 n!이다. 직렬 가능 스케줄은 n!의 직렬 스케줄 중에서 적어도 하나의 직렬 스케줄과 동일한 결과를 가져야 한다.

스케줄 결과의 동일함을 정의하는 방식은 충돌 직렬가능 스케줄과 뷰 직렬가능 스케줄이 있다.

 

Conflicting Instructions (충돌 연산)

Instruction Ii and Ij of transtions Ti and Tj respectivelty, conflict if and only if there exists some item Q accessed by both Ii and Ij and at least one of these instructions is write(Q)

li = read(Q),   lj = read(Q)  Don’t conflict
li = read(Q),   lj = write(Q)  They conflict
li = write(Q),   lj = read(Q)  They conflict
li = write(Q),   lj = write(Q)  They conflict

Intuitively, a conflict between Ii and Ij forces a (logical)temporal order between them

- if Ii and Ij are consecutive in a schedule and they do not conflict, their results would remain the same even if they had been interchanged in the schedule.

 

충돌 연산 

동일한 데이터에 대한 두 개 연산 중에서 최소한 한 개 연산이 쓰기 연산이면, 두 연산은 충돌한다고 한다.

충돌 연산은 동일한 데이터에 대한 연산만을 고려한다. 동일하지 않은 데이터에 대한 연산은 전혀 고려하지 않는다.

스케줄에서 충돌연산은 연관되는 트랜잭션의 직렬 실행 순서를 결정한다. 비충돌연산은 두 연산의 순서를 스케줄에서 바꾸어도 연산효과가 동일하게 나오나, 충돌 연산은 연산 실행 순서를 바꾸면 다른 효과가 나타난다.

 

Conflict Serializable Schedule

If a schedule S can be transformed into a schedule S' by a series of swaps of non-conflicting instructions, we say that S and S' are conflict equivalent.

We say that a schedule S is conflict serializable if it is conflict equivalent to a serial schedule.

충돌 직렬가능 스케줄

스케줄에서 비충돌 연산은 서로 바꾸어도 연산효과가 동일하다. 스케줄에서 비충돌 연산을 서로 바꾸어 직렬스케줄이 된다면, 충돌 직렬가능 스케줄이라 한다.

 

Conflict Serializable Example 1

Schedule 5 can be transformed into Schedule 6, a serial schedule where T2 follows T1, by series of swaps of non-conflicting instructions

-Therefore schedule 5 is conflict serializable.

T1	T2
Read(A) Write(A) Read(B) Write(B)	Read(A) Write(A) Read(B) Write(B)

Schedule 5 (conflict serializable, 충돌 직렬가능 스케줄) 

T1	T2
Read(A) Write(A) Read(B) Write(B)	Read(A) Write(A) Read(B) Write(B)

Schedule 6 (직렬 스케줄) 

스케줄 5에서 T2의 write(A)는 T1의 read(B), write(B)와 비충돌 하므로 서로 위치를 바꿀 수 있다. 또한 T2의 read(A) 또한 T1의 read(B), write(B)와 비충돌 하므로 서로 위치를 바꿀 수 있다. 서로 위치를 바꾸면 결과적으로 스케줄 6이 나오게 되며, 스케줄 6은 직렬 스케줄이다. 이 경우 스케줄 5는 충돌 직렬가능 스케줄이다.

 

Example of a schedule that is not conflict serializable

T3	T4
Read(Q) Write(Q)	Write(Q)

We are unable to swap instructions to obtain either serial schedule <T3, T4> or <T4, T3>

충돌 직렬가능 예제 2

상기 스케줄은 비충돌 연산 상호 교환이 되지 않으므로 충돌 직렬가능 스케줄은 아니다.

Consistency가 보장되지 않는다. (충돌직렬 가능 스케줄이 아니라고 consistent하지 않다고 말할 순 없음)

 

View Serializability Definition

Let S and S´ be two schedules with the same set of transactions.  S and S´ are view equivalent if the following three conditions are met for each data item Q

–If in schedule S, transaction Ti reads the initial value of Q, then in schedule S’ also transaction Ti must read the initial value of Q

–If in schedule S transaction Ti executes read(Q), and that value was produced by transaction Tj  (if any), then in schedule S’ also transaction Ti must read the value of Q that was produced by the same write(Q) operation of transaction Tj

–The transaction (if any) that performs the final write(Q) operation in schedule S must also perform the final write(Q) operation in schedule S’

View equivalence is also based purely on reads and writes alone

 

뷰 직렬가능 정의

스케줄 S에 속한 각 트랜잭션의 읽기 연산에 대하여 S' 스케줄에서 동일한 값을 읽고, 스케줄 S의 마지막 쓰기 연산이 S' 스케줄의 마지막 쓰기 연산과 동일하면, 스케줄 S'는 뷰 직렬가능 스케줄이라고 한다.

 

View Serializability Example

Below is a schedule which is view-serializable but not conflict serializable

T5	T6	T7
Read(Q) Write(Q)	Write(Q)	Write(Q)

Schedule 8

What serial schedule is the above equivalent to?

–view equivalent to <T5, T6, T7>

Every view serializable schedule that is not conflict serializable has blind writes (writing data without prior reading)

스케줄 8은 충돌연산만으로 구성되어 있어 비충돌 연산 위치 바꿈에 의하여 직렬 스케줄로 변환이 가능한 충돌 직렬가능 스케줄은 아니다.

그러나 스케줄 8은 직렬스케줄 <T5, T6, T7>와 효과가 동일한 뷰 직렬가능 스케줄이다. T5 읽기 연산에서 보는 데이터 Q는 직렬 스케줄 <T5, T6, T7>의 T5 읽기 연산이 보는 데이터 값과 동일하며, 스케줄 8의 데이터 Q에 대한 마지막 쓰기 연산은 T7의 쓰기 연산인데 <T5, T6, T7>의 T7 쓰기 연산과 동일하기 때문이다.

충돌 직렬가능하지 않은 뷰 직렬가능 스케줄은 blind write를 포함한다. 

 

Conflict Serializability vs. View Serializability

A schedule S is view serializable if it is view equivalent to a serial schedule

Every conflict serializable schedule is also view serializable

 

 

충돌 직렬가능 스케줄 ⊂ 뷰 직렬가능 스케줄

현실적으로는 DBMS 시스템은 충돌 직렬가능성 스케줄과 뷰 직렬가능성 스케줄의 일부분만을 지원하고 있다.

 

Other Notions of Serializability

 

The schedule below produces same outcome as the serial schedule <T1, T2>,  yet is not conflict equivalent or view equivalent to it

T1	T2
Read(A) A := A – 50 Write(A) Read(B) B := B+50 Write(B)	Read(B) B := B – 10 Write(B) Read(A) A := A + 10 Write(A)

- Not conflict serializable

- Not view serializable

- But the same as <T1, T2>

- Commutable operators only !!!

Determining such equivalence requires analysis of operations other than read and write

다른 직렬가능 스케줄

해당당 스케줄은 충돌 직렬가능 스케줄이 아니다(트랜잭션 중간에 나오는 데이터 B에 대한 연산들을 swap할 수 없음).  뷰 직렬가능 스케줄을 판단하기 위해서는 두 개 트랜잭션의 모든 직렬 스케줄(즉, <T1, T2>, <T2, T1>)과 뷰 동등성(view equivalence) 여부를 판단하여야 한다. <T1, T2> 직렬 스케줄과 비교하면 데이터 B에 대한 최종 쓰기가 주어진 스케줄에서는 T1이며, <T1, T2> 에서는 T2가 되어 뷰 동등성이 성립되지 않는다.  유사한 이유로 주어진 스케줄은 <T2, T1> 직렬 스케줄과 뷰 동등성이 성립되지 않으므로, 주어진 스케줄은 뷰 직렬가능하지 않다.

그러나 해당 스케줄은 직렬 스케줄 <T1, T2>와 동일한 결과를 보인다. 해당 스케줄은 트랜잭션의 모든 연산이 더하기, 빼기이며, 이러한 연산은 상호 교환(commutable)이 된다는 특징이 있어, 직렬 스케줄 <T1, T2>와 동일한 결과를 보인다.  만약 우리가 트랜잭션에서 수행하는 모든 연산을 미리 알 수 있으면, 상기와 같은 분석을 통하여 좀 더 많은 직렬가능 스케줄을 데이터베이스 시스템에서 수행 할 수 있으나, 이는 현실적으로는 불가능하다. 실제 상황에서는 사용자 트랜잭션내에서 수행하는 연산이 사전에 데이터베이스 시스템에 알려질 수 없다.