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 로 테스트할 수 없다.
'DB' 카테고리의 다른 글
Deadlock (0) | 2022.04.20 |
---|---|
Multiple Granularity Locking (0) | 2022.04.20 |
Lock-based Protocols (0) | 2022.04.20 |
Recoverability (0) | 2022.04.19 |
Transaction (0) | 2022.04.19 |
댓글