13. serialize schedule

n개의 transaction으로 구성된 스케줄이 있을 때,

그 스케줄이 동일한 transaction으로 구성된 임의의 

serial 스케줄하고 equivalent하면,

그 스케줄은 serializable 하다.

 

여기서 equivalent는 '동등한'뜻을 가지고, 똑같다란 의미가 아닌 동격이란 의미로 봐야 함

 

Result equivalent

결과의 동등.

 

스케줄 S와 S`의 DB에서의 최종 결과가 같을 때,

 

이 두 스케줄을 equivalent하다고 본다.

다만 연산 과정에서 지금 예시처럼 안 맞는 문제가 발생해,

적절한 방법은 아니다.

 

아무튼 100 넣으면 결과는 같음

 

이처럼 연산에 위 예시처럼 '100이 들어가는 가정하에' 란 가정(assumption)이 들어가면 안 되고,

양쪽 연산이 동일하게 적용돼야

equivalent한 스케줄이라 볼 수 있다.

 

Conflict equivalent

 

2개의 스케줄에서, 충돌(Conflict) 되는 연산의  순서가 동일하다.

read 연산만 있으면 상관 없지만,

write 연산이 들어가면, 그 스케줄은 Conflict하다고 본다.

 

그렇기에, write연산을 조정함으로써, recorable하게 만들 수 있다면,

이 스케줄은 Serializable하다고 본다.

동등한 스케줄

 

위의 예시에선 Y읽고 쓰는 부분을 T2연산 후에 적용해도 문제가 없기 때문에,

serailizable하다.

 

반면 다음 예를 보자.

 

3번째 행에서 conflict가 발생하지만,

write_item(X)를 위로 올리자니, T2의 read_item(X)와 충돌이 일어나고,

밑으로 가자니, T2의 write_item과 충돌이 발생한다.

이렇게 이도저도 못하는 상황인 경우 Nonserializable하다고 한다.

 

 

Conflict Serialize 테스트

지금이야 트랜젝션이 간단하니, 오류를 찾거나, 교정하기가 쉽지만,

규모가 커지면 이렇게 하는건 많은 비용이 든다.

게다가 선형 탐색을 해야 하기 때문에, 한 트랜젝션당 T(n)만큼의 시간 복잡도가 발생한다.

 

그렇기에 DBMS는 디자인 프로토콜을 정하고,

그 기준에 충족한다면, Serializable Schedule로 본다.

 

프로토콜 종류에는 여러 가지가 있다.

1. Locking

2. Timestamps

3. Multiversion CC Protocols

4. Optimistic protocols

 

View equivalence

서로 똑같은 read연산을 할 때, 같은 값이 나오면 Serializable하다고 본다.

즉, schedule이 끝날 때, DB엔 동일한 데이터가 남고 동일한 View가 보여지면 된다.

 

위에서의 Conflict equivalence에 비해 느슨하다.

 

예시를 보자.

아무튼 serialiable

read연산 뒤에, 각 트랜젝션에서 무작위 write가 발생하지만,

아무튼 r1(X)값은 동일하므로, Serializable하다.

r1(X);w1(X);w2(X);w3(X);

 

Constratin write assumption

위의 예시에서, writing을 하기 전에, read연산을 하지 않은 경우,

이 write를 blind write라고 한다.

위의 serialize 식 r1(X);w1(X);w2(X);w3(X); 에서, w2(X)와 w3(X)가 blind write이다.

 

이 제약을 적용시키면, 모든 쓰기 연산 전엔 read를 해줘야 한다.

 

SQL에서의 Isolation level

SQL에선 Transaction 처리를 위한 여러 지원을 해주는데,

그 중 하나가 Isolation level이다.

 

 

Dirty Read : commit : 안 된 데이터를 다른 트렌젝션이 접근하는 것에 대한 허용

Nonrepeatable Read : 한 트랜젝션에서 같은 쿼리를 두번 실행할 때, 그 사이 다른 트렌젝션이 값을 수정함으로써, 두 쿼리의 결과가 다른 비일관성의 허용

Phantom :  일정 범위의 레코드를 여러 번 읽을 때, 첫 번째 쿼리에 없던 결과가 두 번째 쿼리에선 나오는 현상

즉, 트렌젝션 도중 새로운 레코드 삽입에 대한 허용

Ex) 출석을 부르는데, 출석 지나친 애가 들어오는 경우 이걸 인정할지