1장 연습문제

1장

1.1. ACID란?

 

Atomicity(원자성)는 all or nothing으로 트랜잭션을 구성하는 모든 연산이 수행되거나 어느 연산도 수행이 되지 않는 것.

Consistency(일치성)는 트랜잭션의 시작과 끝에서 DB의 상태와 제약사항이 같아야 하는 것.

Isolation(고립성)은 여러 트랜잭션이 동시 수행 중에 있어도 각 트랜잭션들은 다른 것들과 분리되어 서로의 상태를 알 수 없는 상태로 실행되어야 하는 것.

Durability(지속성)은 commit된 트랜잭션의 결과는 시스템 장애가 발생하여도 DB 상태에 반영되어야 하는 것.

 

1.2. UNIX 파일 시스템 관련한 문제

 

a. 파일의 생성 및 삭제, (파일에 데이터를 쓰는) 과정

step1. 파일 시스템에서는 파일 생성 시 파일에 저장소가 할당됨.

step2. index 역할을 하는 고유한 번호 i가 파일들에 주어지고 i-node를 i-list에 추가하여 관리함.

step3. 삭제 시에는 이와 반대로 i-list에 있는 i-node를 가져와 삭제하고 이 노드에 매칭되는 파일에 할당된 저장소를 삭제함.

 

b. 파일의 생성 및 삭제 과정에서의 Atomicity와 Durability

- Atomicity가 지켜지지 않으면 생성되다 말거나 삭제되다 만 파일들이 남게 되어 공간 차지 이슈가 발생하고

사용할 수 없는 파일들이 생김.

- 파일이 한번 생성 및 삭제가 되면 이것이 유지되는 즉, 저장소로서의 역할을 하기 위해서 Durability가 지켜져야 함.

 

1.3. DB 시스템이 파일 시스템보다 더 ACID property를 강조하는 이유

- DB 시스템은 유저의 데이터들을 직접 다루는 중요한 작업을 수행함.

∴ ACID를 지킴으로서(특히 Atomicity, Durability) Read/Write된 데이터들이 보존되는 것을 보장해야 함.

DB 시스템 예시 ex. 은행 DB시스템, 자리 예매 시스템 등.

 

- 반면, 파일 시스템은 직접적인 데이터를 다룬다기보다는 파일을 다루는 것이기에 ACID가 지켜지지 않아도

문제가 없음.

 

1.4. 

serial schedule(직렬 스케줄)은 한번에 하나의 트랜잭션만 수행이 되고 서로 다른 트랜잭션 간의

연산이 번갈아 일어나지 않는 스케줄임. 이는 동시에 실행되지 않는다는 조건에 의해 Deadlock이나 Stravation이 발생하지 않기에 항상 correct함.

serializable schedule(직렬가능 스케줄)은 직렬 스케줄 방식으로 하나 비직렬 스케줄 방식으로 하나

결과가 동일한 스케줄임.

 

1.5.

동시성 제어 프로토콜(직렬가능성을 보장하는 스케줄만 생성하는 프로토콜)은 충돌 직렬가능성에 기초하는데

이는 상대적으로 뷰 직렬가능성 검사보다 저렴하고(단순히 Precedence Graph(우선순위 그래프)를 그려서 Cycle 여부를 확인하면 되기 때문) 상대적으로 더 제한적이기에 충돌 직렬가능성을 강조함.

 

1.6.

디스크에 있는 데이터를 fetch해와야 하고 트랜잭션의 길이가 길다면, 디스크에서 값을 가져오는데 시간도 오래 걸리면서 트랜잭션이 끝날 때까지 다른 트랜잭션들이 기다려야 하기에 이를 동시성 제어를 통해 시간을 효율적으로 사용할 수 있음.

반면, 데이터가 메모리(메인메모리)에 있고, 트랜잭션의 길이가 짧다면 상대적으로 동시성 제어를 통해 얻어지는 효율이 작음.

 

1.7. 회복 가능 스케줄이란? 스케줄의 회복가능성이 왜 중요?

Recoverable Schedule은 T1이 쓴 데이터에 대해서 T2에서 읽는다면 T2의 commit보다 T1의 commit이 먼저 오는 스케줄임.

-> 이거 약간 Cascadeless Schedule하고 헷갈릴 수 있는데 T1의 commitdl T2의 read보다 앞에 오면 그게 Cascadeless Schedule임. Recoverable은 Cascadeless보다 범위가 넓음.

 

회복 불가능하다면 장애 발생 시 시스템에서 데이터를 아예 되돌릴 수 없을 정도로 일관되지 않을 수 있기에 문제가 됨.

 

1.8.

우선순위 그래프에 Cycle이 없기에 충돌 직렬가능 스케줄임.

순위를 보면 T1> T2> T3,T4 > T5이므로

가능한 직렬 스케줄은 

[T1, T2, T3, T4, T5]와 [T1, T2, T4, T3, T5]임.

 

1.9.

T2의 write(B)한 값을 T3에서 read(B)하기에 T3의 commit보다 T2의 commit이 앞에 있어야 함.

근데 T2의 commit이 없고 abort된게 있기에 Recoverable history가 아님.

 

1.10.

 

(a) T1 --B-->T2<--C--T3--D-->T4

(b) cycle이 없기에 충돌 직렬 가능한 스케줄임.

가능한 직렬 스케줄은

T1, T3, T2, T4

T1, T3, T4, T2

T3, T1, T2, T4

T3, T1, T4, T2

T3, T4, T1, T2

 

1.11.

(a) 우선순위 그래프는 충돌여부에 따라 화살표를 그림

T1의 write와 T2의 read 충돌

T1의 write와 T3의 write 충돌

T2의 read와 T3의 write 충돌

T3의 write와 T2의 write 충돌

-> 충돌 관계를 화살표로 그림

(b)

initial read와 final write만 고려하면 view equivalent 스케줄로 <T1, T3, T2>가 있다.

근데 이는 스케줄 내에 모든 읽기 연산이 동일한 읽기를 하느냐를 봤을 때는 T1 write값을 T2가 읽지만 

<T1, T3, T2>에서는 T3 write 값을 T2가 읽는다.

 

∴ view serializable 하지는 않다.

 

1.12.

(1) 뷰 직렬 가능이 충돌 직렬 가능을 포함하는 넓은 개념이므로 

뷰 직렬 가능이라고 해서 충돌 직렬 가능은 아니다.

 

(2) 뷰 직렬 가능 스케줄 판별은 NP-complete 문제로 인해 오래 걸림

∴ 충돌 직렬 가능 스케줄 판별은 우선순위 그래프를 사용하기에 polynomial time 내에 가능하여 이를 먼저 사용하고 

blind write를 찾는 방식을 쓴다.