Ch17_Transactions

Chapter 17. Transactions

한 줄 핵심: 트랜잭션(transaction)은 “전부 되거나 전혀 안 되거나”여야 하는 작업 묶음이며, DBMS는 여기에 ACID를 보장해야 한다. 동시 실행의 올바름 기준은 직렬 가능성(serializability) — 어떤 스케줄이 직렬(serial) 스케줄과 동등하면 안전하고, 그 판정은 precedence graph가 비순환(acyclic)이냐로 한다.

이 챕터가 답하는 핵심 질문

• Q1. 트랜잭션이란 무엇이고, 왜 ACID가 필요한가?
• Q2. 트랜잭션은 어떤 상태들을 거치는가?
• Q3. 왜 트랜잭션을 동시에 실행하며, 스케줄(schedule)이란 무엇인가?
• Q4. 동시 실행이 “올바르다”는 것을 어떻게 정의하는가? (serializability)
• Q5. Conflict serializability를 어떻게 판정하는가? (precedence graph)
• Q6. View serializability는 무엇이고 conflict serializability와 어떻게 다른가?
• Q7. 트랜잭션 실패에 대비한 스케줄 조건은? (recoverable / cascadeless)
• Q8. SQL에서 트랜잭션을 어떻게 정의하고, isolation은 어떻게 구현하는가?

---

Q1. 트랜잭션이란 무엇이고, 왜 ACID가 필요한가?

A. 트랜잭션은 여러 데이터 항목을 읽고(read) 갱신하는(write) 프로그램 실행의 한 단위(unit)이며, 데이터 무결성을 위해 DBMS는 ACID(Atomicity·Consistency·Isolation·Durability)를 보장해야 한다.

비유: 계좌 A에서 B로 $50을 송금. “A에서 빼기”와 “B에 더하기”는 반드시 한 덩어리여야 한다.

1. read(A)        ← A 잔액을 읽는다
2. A := A − 50    ← 메모리에서 50 차감
3. write(A)       ← 차감된 값을 DB에 기록
4. read(B)
5. B := B + 50
6. write(B)

트랜잭션 관리가 다뤄야 할 두 가지 핵심 문제: ① 장애(failure) — HW/SW 고장, 시스템 크래시. ② 동시 실행(concurrent execution) — 여러 트랜잭션이 같은 데이터를 동시에 건드림.

ACID 속성 (송금 예제로)

속성	정의	송금 예제에서의 의미
Atomicity (원자성)	연산이 전부 반영되거나, 하나도 반영 안 되거나	3단계 후 ~ 6단계 전에 죽으면 $50 “증발”. 시스템은 부분 실행된 갱신이 DB에 남지 않도록 보장 (장애 원인은 SW/HW 모두)
Consistency (일관성)	트랜잭션을 단독으로(in isolation) 실행하면 일관성 보존	A+B 합 불변. 일관성 = ① 명시적 제약(PK, FK) ② 암묵적 제약(예: 전 계좌 잔액 합 − 대출 합 = 현금). 실행 중엔 일시적으로 비일관해도 되고, 성공 완료 시 다시 일관 (트랜잭션 로직 자체가 틀리면 비일관 발생 가능)
Isolation (고립성)	동시 실행이라도 각 트랜잭션은 다른 트랜잭션을 의식하지 못함. 중간 결과는 숨겨짐	3~6단계 사이 T2가 A,B를 읽으면 A+B가 실제보다 작은 비일관 상태를 봄. 형식: 모든 쌍 $T_i,T_j$에 대해 $T_i$ 입장에서 “$T_j$가 내 시작 전에 끝났거나 내 종료 후 시작한 것처럼” 보여야 함
Durability (지속성)	성공 완료 후 변경은 시스템 장애가 나도 보존	”송금 완료” 통지 후엔 SW/HW 장애에도 $50 이체가 사라지지 않음

Isolation 위반 시나리오

     T1                          T2
1. read(A)
2. A := A − 50
3. write(A)
             read(A), read(B), print(A+B)   ← A+B가 50 모자란 값!
4. read(B)
5. B := B + 50
6. write(B)

Isolation은 트랜잭션을 직렬로(serially, 하나씩) 실행하면 자명하게 보장된다. 하지만 동시 실행 이득이 크므로 “직렬처럼 보이게” 동시 실행하는 것이 이 장의 주제다.

---

Q2. 트랜잭션은 어떤 상태들을 거치는가?

A. Active → Partially committed → Committed(성공 경로) 또는 Active/Partially committed → Failed → Aborted(실패 경로)의 일생을 거친다.

상태	의미
Active	초기 상태. 명령 실행 중 머무름
Partially committed	마지막 문장 실행 직후. 디스크 반영이 아직 확정 안 된 “거의 다 됨”
Failed	정상 진행 불가를 발견한 후
Aborted	롤백 완료 → DB가 시작 전 상태로 복원. 이후 ① restart(내부 논리 오류 없을 때만) ② kill
Committed	성공적 완료 후

                ┌──────────────────┐      ┌───────────┐
         ┌────▶ │ partially        │ ───▶ │ committed │
         │      │ committed        │      └───────────┘
┌────────┐      └──────┬───────────┘
│ active │             │
└────┬───┘             ▼
     │          ┌──────────┐       ┌─────────┐
     └────────▶ │  failed  │ ────▶ │ aborted │
                └──────────┘       └─────────┘

---

Q3. 왜 트랜잭션을 동시에 실행하며, 스케줄이란 무엇인가?

A. 동시 실행은 자원 활용률↑(throughput)과 평균 응답시간↓를 주며, 그 실행 순서를 명시한 것이 스케줄(schedule)이다.

동시 실행 장점: ① 프로세서·디스크 활용률 증가 → throughput 향상(한 트랜잭션이 CPU 쓸 때 다른 건 디스크 I/O). ② 평균 응답시간 감소(짧은 트랜잭션이 긴 것 뒤에서 안 기다림).

• Concurrency control scheme = isolation 달성 메커니즘. 동시 트랜잭션 간 상호작용을 통제해 일관성 파괴를 막음 (구체적 프로토콜은 Ch18).
• Schedule = 동시 트랜잭션들의 명령이 시간순으로 어떤 순서로 실행되는지 명시한 시퀀스. ① 해당 트랜잭션들의 모든 명령을 포함 ② 각 트랜잭션 내부 명령 순서는 보존(끼워넣기만 가능). 성공 트랜잭션 마지막 = commit, 실패 = abort.

등장 트랜잭션

• $T_1$: A → B로 **$50\ast \ast 이체.$T_2$: A 잔액의 **10%**를 A → B로 이체. 초기값 A=100, B=50.

Schedule 1 (직렬, $T_1$→$T_2$): $T_1$ 후 A=50,B=100. $T_2$ 후 A=45,B=105, A+B=150 ✓.
Schedule 2 (직렬, $T_2$→$T_1$): 최종 A=40,B=110, A+B=150 ✓ (순서 달라도 직렬이면 일관성 보존).
Schedule 3 (직렬 아님, but Schedule 1과 동등): 명령이 섞여 있어도 결과가 Schedule 1과 동일, A+B=150 ✓.

Schedule 4 (일관성 깨는 동시 스케줄):

$T_1$	$T_2$	값 변화
read(A); A:=A−50		(로컬 A=50, 미기록)
	read(A)	A=100 ← T1 차감 못 봄!
	A:=A−A*0.1; write(A)	DB A=90
	read(B)	B=50
write(A)		DB A=50 ← T2 write(A) 덮어씀
read(B); B:=B+50; write(B)		DB B=100
	B:=B+temp; write(B)	DB B=60 ← T1 B갱신 덮어씀

왜 깨지는가

$T_2$가 $T_1$의 차감 전 A(=100)를 읽었고, write들이 서로 덮어썼다. read/write가 서로의 중간 상태에 끼어들었기 때문 → 최종 A=50, B=60, A+B=110 ✗ ($40 증발). 어떤 동시 스케줄이 안전한가의 기준이 필요 = 직렬 가능성.

---

Q4. 동시 실행이 “올바르다”는 것을 어떻게 정의하는가?

A. Serializable schedule = 어떤 직렬(serial) 스케줄과 동등(equivalent)한 스케줄이다. “동등”의 정의에 따라 Conflict serializability와 View serializability 두 종류가 있다.

• 기본 가정: 각 트랜잭션은 단독 실행 시 일관성을 보존한다 → 직렬 실행은 항상 일관성 보존.
• 따라서 동시 스케줄이 어떤 직렬 스케줄과 동등하다면 그 동시 스케줄도 일관성을 보존한다.

단순화 가정

• read·write 이외 연산은 무시. read/write 사이엔 로컬 버퍼에서 임의 계산을 한다고 가정. 즉 스케줄은 read/write 명령만으로 구성.

---

Q5. Conflict serializability를 어떻게 판정하는가?

A. 스케줄이 conflict serializable ⟺ precedence graph가 비순환(acyclic)이다. acyclic이면 **위상 정렬(topological sort)**로 직렬화 순서를 얻는다.

Conflicting Instructions — 충돌 명령

$T_i$의 $I_i$와 $T_j$의 $I_j$가 충돌(conflict) ⟺ 같은 항목 Q에 접근 + 둘 중 적어도 하나가 write.

$I_i$	$I_j$	충돌?
read(Q)	read(Q)	No (순서 바꿔도 무관)
read(Q)	write(Q)	Yes
write(Q)	read(Q)	Yes
write(Q)	write(Q)	Yes

• 충돌하는 두 명령 사이엔 (논리적) 시간 순서가 강제됨. 연속한 두 명령이 비충돌이면 swap해도 결과 동일.

정의

• $S$를 비충돌 연속 명령 교환(swap) 만으로 $S^{\prime }$로 변환 가능하면 conflict equivalent.
• $S$가 어떤 직렬 스케줄과 conflict equivalent하면 conflict serializable.

예시 ① Schedule 3은 conflict serializable: $T_2$의 read/write(A)와 $T_1$의 read/write(B)는 다른 데이터라 비충돌 → swap 반복으로 직렬 $⟨T_1,T_2⟩$(Schedule 6)로 변환됨.

예시 ② not conflict serializable ($T_3$: read(Q) … write(Q), $T_4$: write(Q)가 그 사이): 세 명령이 전부 충돌해 어떤 swap으로도 $⟨T_3,T_4⟩$나 $⟨T_4,T_3⟩$로 못 만듦.

Precedence Graph로 판정

• 정점 = 트랜잭션. 간선 $T_i\to T_j$: 두 트랜잭션 명령이 충돌하고, 충돌 항목을 $T_i$가 먼저 접근했을 때 (라벨에 항목명). 세 패턴: ①$T_i$ write→$T_j$ read ②$T_i$ read→$T_j$ write ③$T_i$ write→$T_j$ write.

Schedule 4의 graph: $T_1$ read(A)가 $T_2$ write(A) 앞 → $T_1\to T_2$; $T_2$ read(A)가 $T_1$ write(A) 앞 → $T_2\to T_1$. 양방향 = 사이클 → not conflict serializable (“$T_1$이 먼저이면서 동시에 $T_2$가 먼저”라는 모순).

precedence graph 그리는 법 — 한 스텝씩 (Schedule 4)

그래프를 만드는 작업은 기계적이다. 충돌하는 명령 쌍(같은 항목 + 적어도 하나 write)을 시간 순서대로 모두 찾아서, 먼저 한 쪽 → 나중 한 쪽으로 화살표를 그으면 끝이다.

스케줄을 시간순으로 펼치면 (괄호 안은 누가 무엇을):

시간 →  ① T1:read(A)  ② T2:read(A)  ③ T2:write(A)  ④ T1:write(A)
        ⑤ T1:read(B)  ⑥ T1:write(B)  ⑦ T2:read(B)  ⑧ T2:write(B)

1단계 — 충돌 쌍 찾기 (같은 항목 + 둘 중 하나라도 write):

항목	먼저 (시간)	나중 (시간)	충돌?	화살표
A	T1 read ①	T2 write ③	Yes (read↔write)	$T_1\to T_2$
A	T2 read ②	T1 write ④	Yes (read↔write)	$T_2\to T_1$
A	T2 write ③	T1 write ④	Yes (write↔write)	$T_2\to T_1$
B	T1 write ⑥	T2 read ⑦	Yes (write↔read)	$T_1\to T_2$

(T1 read(A)와 T2 read(A)는 둘 다 read라 충돌 아님 → 화살표 없음.)

2단계 — 그래프 그리기:

       ┌───── A, B ─────▶
    ( T1 )            ( T2 )
       ◀───── A ──────┘

3단계 — 사이클 검사: $T_1\to T_2\to T_1$ 로 양방향 화살표가 존재 → 사이클 O → not conflict serializable. “T1을 T2보다 먼저 놓아도, 나중에 놓아도 모순”이라 어떤 직렬 순서로도 정렬 불가.

대조: Schedule 3 (안전한 버전) — 거기선 충돌이 전부 $T_1\to T_2$ 한 방향뿐이라 그래프가 T1 ──▶ T2, 사이클 없음 → 위상정렬하면 직렬 순서 $⟨T_1,T_2⟩$가 그대로 나온다.

핵심 정리

conflict serializable ⟺ precedence graph acyclic

• 사이클 탐지: $O(n^2)$ (또는 $O(n+e)$). acyclic이면 위상 정렬로 직렬화 순서 획득 — 그래프 부분 순서와 일치하는 선형 순서 (여러 개일 수 있음).

---

Q6. View serializability는 무엇이고 conflict serializability와 어떻게 다른가?

A. View serializable은 read가 본 값과 최종 write만 따지는 더 넓은 개념이다. 모든 conflict serializable은 view serializable이지만 역은 아니고, 그 차이의 원천은 blind write다. 단 view serializability 판정은 NP-complete.

$S,S^{\prime }$가 view equivalent ⟺ 모든 항목 $Q$에 대해:

1. 초기값 읽기: $S$에서 $T_i$가 $Q$ 초기값 읽으면 $S^{\prime }$에서도 그래야 함.
2. 누가 쓴 값을 읽는가: $S$에서 $T_i$의 read(Q)가 $T_j$의 write가 만든 값을 읽으면, $S^{\prime }$에서도 같은 $T_j$의 같은 write(Q) 값을 읽어야 함.
3. 마지막 write: $S$에서 $Q$의 최종 write를 한 트랜잭션이 $S^{\prime }$에서도 최종 write를 해야 함.

• View serializable = 어떤 직렬 스케줄과 view equivalent. 모든 conflict serializable ⊂ view serializable.

view serializable이지만 conflict serializable 아닌 예 ($T_{27}$ read(Q), $T_{28}$ write(Q), $T_{27}$ write(Q), $T_{29}$ write(Q)): 직렬 $⟨T_{27},T_{28},T_{29}⟩$과 view equivalent(초기값은 $T_{27}$, 최종 write는 $T_{29}$, 중간 write는 아무도 안 읽음). 하지만 write끼리 전부 충돌해 conflict serializable 아님. 이런 스케줄엔 반드시 blind write(읽지 않고 쓰기)가 있다.

그 밖의 동등성: $T_1$/$T_5$가 A,B에 산술 연산하는 스케줄은 직렬 $⟨T_1,T_5⟩$와 결과는 같지만 conflict도 view equivalent도 아님(덧셈·뺄셈 교환성으로 우연히 일치). 판정하려면 read/write 외 산술 의미까지 분석해야 함 → 일반적으로 다루지 않음.

View serializability 판정

precedence graph 검사를 그대로 못 씀(확장은 지수 비용). 판정 문제는 NP-complete → 실무는 충분조건(sufficient condition) 만 검사하는 실용 알고리즘 사용.

---

Q7. 트랜잭션 실패에 대비한 스케줄 조건은?

A. 한 트랜잭션의 abort가 다른 트랜잭션에 미치는 영향을 막기 위해 스케줄은 recoverable(읽은 쪽이 나중에 commit)해야 하고, 가급적 cascadeless(commit된 데이터만 읽기)여야 한다.

Recoverable Schedule

• Recoverable: $T_j$가 $T_i$가 쓴 데이터를 읽었다면 commit($T_i$)가 commit($T_j$)보다 먼저.
• Not recoverable 예 (Schedule 11): $T_9$가 $T_8$의 미commit A를 읽고 $T_8$보다 먼저 commit. 이후 $T_8$이 abort하면 $T_9$는 존재하지 않게 된 값을 읽고 이미 commit까지 함 → commit은 되돌릴 수 없으므로(Durability) 복구 불가.

Cascading Rollback — 연쇄 롤백

• Cascading rollback: 트랜잭션 하나의 실패가 연쇄 롤백을 유발. $T_{10}$ abort → 그 값 읽은 $T_{11}$ 롤백 → $T_{11}$ 값 읽은 $T_{12}$ 롤백. (아무도 commit 안 했으면 이 스케줄 자체는 recoverable이지만) 상당한 작업이 무효화됨.

Cascadeless Schedule

• Cascadeless: $T_j$가 $T_i$가 쓴 데이터를 읽으려면 commit($T_i$)가 read($T_j$)보다 먼저 (= commit된 데이터만 읽기). 모든 cascadeless는 recoverable.

두 조건 비교

조건	요구사항	강도
Recoverable	$T_i$ write→$T_j$ read이면 commit($T_i$) < commit($T_j$)	약함 (더티 리드 허용, commit 순서만)
Cascadeless	$T_i$ write→$T_j$ read이면 commit($T_i$) < read($T_j$)	강함 (더티 리드 금지) → recoverable 자동 보장

Concurrency Control의 목표

DBMS는 모든 스케줄이 **conflict/view serializable + recoverable(가급적 cascadeless)**이 되도록 보장해야 한다.

• “한 번에 하나만” 정책은 직렬 스케줄(자명하게 recoverable/cascadeless)이지만 동시성이 형편없음.
• 실행이 끝난 뒤 serializability를 검사하는 건 너무 늦다! → 프로토콜은 precedence graph를 실시간 검사하는 대신 non-serializable 스케줄이 아예 안 생기도록 규율(discipline)을 강제. 프로토콜마다 동시성 ↔ 오버헤드 트레이드오프. serializability 이론은 “왜 이 프로토콜이 올바른가”를 이해하는 도구.

Weak levels of consistency: 일부 응용은 serializable 아닌 약한 일관성을 택함 (예: 대략적 총잔액 읽기, 질의 최적화용 근사 통계). 본질은 정확도 ↔ 성능 트레이드오프.

---

Q8. SQL에서 트랜잭션을 어떻게 정의하고, isolation은 어떻게 구현하는가?

A. SQL 트랜잭션은 암묵적으로 시작되고 COMMIT/ROLLBACK WORK로 끝나며, isolation 구현 기법은 Locking·Timestamps·Multiple versions 세 갈래다(상세는 Ch18).

Transaction Definition in SQL

• 트랜잭션은 암묵적 시작(BEGIN 없이). COMMIT WORK(commit 후 새 트랜잭션 시작), ROLLBACK WORK(abort).
• 대부분 DBMS는 모든 SQL 문이 성공 시 암묵 commit(autocommit). 끌 수 있음 — 예: JDBC connection.setAutoCommit(false);

제약 검사 지연(deferred constraint checking): 자기 참조 FK 등은 commit 시점으로 검사를 미룰 수 있다.

PRAGMA foreign_keys = ON;
create table person2 (
  ID char(10) primary key, name char(40), mother char(10), father char(10),
  foreign key (father) references person2 DEFERRABLE INITIALLY DEFERRED);
BEGIN TRANSACTION;
insert into person2 values ('me_id','me','mymother_id','myfather_id');
insert into person2 values ('myfather_id','myfather','mygrandma_id',null);
COMMIT;

첫 insert 시점엔 myfather_id가 없어 FK 위반이지만, DEFERRABLE INITIALLY DEFERRED 덕에 COMMIT 시점에 한꺼번에 검사 → 통과.

Implementation of Isolation Levels

기법	아이디어	설계 쟁점
Locking	데이터에 잠금을 걸어 접근 통제	DB 전체 vs 항목별 lock / 얼마나 오래 / shared(공유) vs exclusive(배타)
Timestamps	트랜잭션 시작 시 timestamp 부여, 항목마다 read TS + write TS 저장	순서 어긋난(out of order) 접근 탐지
Multiple versions	항목의 여러 버전 유지	트랜잭션이 DB “snapshot” 을 읽도록 허용

---

한눈에 보는 개념 지도

트랜잭션 = 프로그램 실행 단위 (read/write 묶음)
    ├─ ACID 보장 (Q1) — Atomicity/Durability→장애복구, Isolation→동시실행
    ├─ 동시 실행의 올바름 = Serializability (Q4)
    │    ├─ Conflict serializable (Q5) ⟺ precedence graph acyclic
    │    │      └─ acyclic이면 topological sort로 직렬 순서
    │    └─ View serializable (Q6) ⊃ conflict serializable, NP-complete, blind write가 차이
    ├─ 장애 대비 (Q7): cascadeless ⊂ recoverable
    └─ 목표: serializable + recoverable(+cascadeless)을 "실행 전에"
       강제하는 concurrency control protocol (→ Ch18)