Serializability

Correct Execution

동시에 실행되는 트랜잭션들이 올바르기 위한 기준은 다음과 같다.

1. Conflict serializable
2. View serializable

-> 트랜잭션의 직렬 수행은 항상 correct 하다. (data consistency 를 항상 보장받는다.)

 

Nonserializable Execution

- dirty read

T2 는 dirty data 를 읽게 된다. (T1이 write 한 값을 읽게 됨)

- lost update

T2 가 A를 변경한 효과가 없어지게 된다.

- unrepeatable read

T1 이 서로 다른 A 를 읽게 된다.

 

Schedules

여러 트랜잭션을 동시에 실행하기 위해서는, 순서를 스케줄링 해야 한다.이때 schedule 이 다음과 같은 조건들을 만족해야 correct 하다.

- schedule은 트랜잭션의 모든 연산들을 포함하고 있어야한다.
- schedule의 연산 순서는 트랜잭션 내에서의 연산 순서와 동일해야한다.
- schedule 내 트랜잭션이 성공적으로 마무리되면 마지막에 commit 을, 실패했다면 abort 를 수행한다.

 

ex) T1이 A에서 B로 $50 를 이체하며, T2는 잔액의 10% 를 A에서 B로 이체한다.

 

1. serial schedule (T1 이 먼저 실행된 후에 T2가 실행됨)

2. serial schedule (T2 이 먼저 실행된 후에 T1가 실행됨)

3. not serial schedule ( 그러나 schedule 1과 동일함)

4. not correct schedule (data consistency 를 보장하지 않음)

-> 1,2,3 은 correct 한 schedule 이지만, 4은 그렇지 않다.

왜냐하면 A+B 의 합이 트랜잭션 실행 전과 후 다름으로, data consistency 가 지켜지지 않았기 때문이다.

 

Serializability

각 트랜잭션은 database consistency 를 유지한다.

어떤 schedule 이 직렬 schedule 과 동일하다면, serializable 하다.

 

Conflicting Instructions

서로 다른 트랜잭션 Ti, Tj 의 instruction Ii, Ij 가 item Q에 대해서 write하는 연산이 하나라도 있다면 conflict하다.

Ii 와 Ij 의 순서를 바꿨을 때, 스케줄의 결과가 유지된다면 conflict 하지 않다. 
그러나, write 연산은 순서를 바꾸면 항상 결과가 유지되지 않기 때문에 conflict 를 일으킨다.

 

Conflict Serializable Schedule

만약 Concurrent execution 되고 있는 스케쥴 S에서 non-conflicting instruction(비충돌 연산) 을 swap하여

Serial 스케쥴 S' 으로 만들 수 있다면 S와 S'은 conflict equivalent 하다.

 

-> 이때 스케줄 S 는 conflict serializable schedule 이다.

 

ex 1)

schedule 5에서 비충돌 연산끼리 swap 을 해서 serial schedule 6으로 만들 수 있다.

T2의 < Read(A) Write(A) > 와 T1의 < Read(B) Write(B) > 연산을 swap 하면 스케줄 6이 된다.

Write(A) 와 Write(B) 는 서로 다른 아이템에 대한 쓰기 연산이므로 비충돌 연산이 맞다.

이때 스케줄5와 스케줄6 은 Conflict equivalent 하며, 스케줄 5는 conflict serializable 하다.

 

 

ex 2)

스케줄7 에 대해서 swap 할 수 있는 비충돌 연산이 없다. 따라서 이를 serial schedule 로 만들 수 없고, 스케줄7은 conflict serializable 하지 않다.

 

 

View Serializability Definition

S와 S`이 같은 트랜잭션의 집합을 스케쥴하였을 때, S와 S'이 다음 조건을 만족하면 View equivalent 하다.

- S가 읽은 Q의 initial value 과 S`이 읽은 Q의 initial value 이 같아야한다.
- 만약 S의 T1이 T2로부터 생성된(write) Q를 read했다면, S'에서도 T1은 T2로부터 생성된 Q값을 읽어야 함
  /* 즉, S에서 Ti 가 먼저 write(Q) , Tj 가 후에 read(Q) 를 했다면 S' 에서도 이 순서를 지켜야 한다. */
- 어느 한 스케쥴이 final write를 했다면 (디스크에 저장) 다른 스케쥴 또한 final write 를 해야함

-> S가 serial schedule과 view equivalent하면 S는 view serializable하다고 한다.

 

ex)

스케줄8 (S) 은 view-serializable 하지만 conflict serializable 하지 않다.

S' 은 <T5, T6, T7> 이라고 하자.

- 초기값을 S,S' 모두 T5 에서 읽는다.

- Ti 로부터 생성한 Q를 Tj 가 읽는 연산이 없으므로 만족한다.

- final write 는 T7 에서 이루어진다.

-> S 와 S' 은 view equivalent 하다.

 

그러나 S 를 serial schedule 로 만들기 위해서 충돌 연산끼리 swap 을 해야하므로 conflict serializable 하지 않다.

 

-> 이와 같이 conflict serializable 하지 않지만 view serializable 한 스케줄은 모두 blind writes 를 가지고 있다.

blind write : 읽는 연산이 이전에 실행되지 않은 채 데이터를 쓴다.

 

 

Conflict Serializability vs View Serializability

모든 conflict serializable schedule 은 또한 view serializable 하다.

 

Other Notions of Serializability

위 스케쥴은 Conflict serializable 하지도, view serializable 하지도 않지만 <T1, T2> 와 같은 결과를 내므로 serializable 하다. -> 덧셈, 뺄셈으로 이루어진 commutable operation  때만 가능하다.

view serializable 하지 않은 이유 (S' 은 <T1,T2> 라고 가정하자)
- S 에서는 T2 에서 생성한 B를 (Write(B)) T1 에서 읽는다. (Read(B)) 
그러나 S' 에서는 T2에서 생성하기 전에 T1에서 먼저 Read(B) 를 하기 때문에 순서가 같지 않다.

 

Testing for Conflict Serializability

Precedence graph의 사이클 유무를 검사한다.

-> Ti와 Tj 가 서로 conflict 하며 Ti 가 Tj 보다 해당 데이터 아이템에 먼저 접근한다면 Ti -> Tj 의 edge를 추가한다.

ex 1)

이때 schedule10 의 precendence graph 에는 사이클이 존재하므로 이는 conflict serializable 하지 않다.

 

ex 2)

schedule11 의 경우 사이클이 존재하지 않기 때문에 conflict serializable 하다.

이 경우 T1 -> (<T2,T3> or <T3,T2>) -> T4 에 T5 는 아무 곳이나 들어갈 수 있기 때문에

2 x 5 = 10 가지의 serialization order 을 만들 수 있다.

 

사이클 검사는 N^2 또는 N+E 의 시간 복잡도로 가능 (N = 정점 수, E = 간선 수)

그래프가 비순환적이라면 topological sorting 을 통해 serializable 하게 만들 수 있음

ex) schedule11 은 T5->T1->T3->T2->T4 로 만들 수 있다.

 

Test for View Serializability

NP-complete 문제로, precedence graph 로 테스트할 수 없다.