[DB/1-2.Serializability(직렬성)]

2️⃣ Serializability

---

Correct Execution

Two widely accepted criteria

• Conflict serializable
• View serializable

→ 두 개 중 하나만이라도 만족하면 correct execution

(* serial execution of transaction is always correct)

---

Nonserializable Execution

비순차적인 연산의 문제점

 

1. dirty read

: Rollback으로 인해 A는 처음 상태로 → T2의 A는 잘못된 값을 읽고 있는 것임

 

2. lost update

: Effect (update) of T2 is lost

최종적으로는 T1에서 A+50한 값이 write됨 (T2연산이 사라짐 → lost update)

 

 

3. unrepeatable read

: 한 transaction에서 update한 내용이 없으면 read한 데이터가 같아야 함. 근데 T2의 연산으로 인해 T1에서 read한 데이터가 변함

 

⇒ “Serializable”하게 schedule하면 항상 Correct(Consistent)한 결과

 

---

 

Schedules (Histories)

: A sequence of instructions that specify the chronological order in which instructions of concurrent transactions are executed

 

Schedule 1 && Schedule 2

: 직렬 스케줄

 

Schedule : T1 → T2 // T2 → T1

serial schedule ⇒ consistent한 결과

 

트랜잭션 전, 후 A+B의 값 변화 x

Schedule 3

: not a serial schedule, but it is equivalent to Schedule 1

트랜잭션 전, 후 A+B의 값 변화 x

 

Schedule 4

: 올바른 스케줄 X

트랜잭션 수행 후, A+B 값 변화 O

 

---

Serializability

Serial Schedule의 결과와 동일 → Serializable Schedule

(Transaction 수 n개일 때 Serializable schedule은 n!의 결과 중 적어도 하나와 결과 동일해야)

 

동일함을 판단하는 기준?

• Conflict Serializability
• View Serializability

---

Conflicting Instructions

충돌연산

• Instructions  and $I_j$ of transactions $T_i$ and $T_j$ respectively, conflict if and only if there exists some item Q accessed by both $I_i$ and $I_j$ , and at least one of these instructions is write(Q)
  • 동일한 데이터에 대한 두 개 연산 중에서 최소한 한 개의 연산이 write이면 두 개의 연산은 충돌
  • 충돌 연산을 고려할 때, 동일한 데이터에 대한 연산을 고려
   

 

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

∴ non-conflict 연산 순서를 바꾸어서 serial schedule과 결과 동일하면 Conflict Serializable Schedule (consist 보장)

T1	T2
r(A)
	r(B)

T1	T2
r(A)
	r(A)

두 경우 다 non conflict 연산 -> 순서를 바꿀 수 있음

 

Conflict Serializability Example 1

• 스케줄 5의 T2의 w(A)는 T1의 r(B), w(B)랑 비충돌 → 순서 교환 가능
• 스케줄 5의 T2의 r(A)는 T1의 r(B), w(B)랑 비충돌 → 순서 교환 가능

→ 결과적으로 스케줄 6(serial schedule)과 같은 스케줄이 나오게 됨.

∴ 스케줄 5는 conflict serializable schedule

 

Conflict Serializability Example 2

• r(Q), w(Q)는 충돌 → 순서 교환 불가능
• <T3, T4> 또는 <T4, T3>의 serial schedule로 교환 불가능

⇒ schedule 7 is not conflict serializable

---

View Serializability Definition

뷰 직렬 가능 스케줄의 정의 (다음 3개를 모두 만족해야.)

• 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(Q)를 했다면 (디스크에 저장) 다른 스케쥴 또한 final write(Q) 를 해야함
• View equivalence is also based purely on reads and writes alone

 

View Serializability Example

• S’을 <T5, T6, T7>이라고 가정
• View Serializable한가?
  1. 초기값을 모두 T5에서 읽음 → O
  2. Ti 로부터 생성한 Q를 Tj 가 읽는 연산이 없음 → O
  3. final write는 둘 다 T7에서 함 → O
  ⇒ S’ <T5, T6, T7>은 View Serializable Schedule이다.
• Conflict Serializable한가?
  • serial하게 바꾸려면 T5의 w(Q), T6의 w(Q)의 순서를 바꿔야.
  • 이 두 개를 교환하는 것은 충돌연산이므로 충돌 직렬가능 스케줄은 아님

⇒ Schedule 8 is view-serializable but not conflict serializable.

 

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

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

 

---

Conflict Serializability vs. View Serializability

 

Other Notions of Serializability

• not conflict serializable
• not view serializable → final write 동일 X
• but the same as <T1, T2>
• Commutable operators only !!

덧셈, 뺄셈 연산은 상호 교환이 되기 때문에 직렬 스케줄과 동일한 결과를 보임