Transaction

Transaction Concept

Transaction은 data에 접근하는 program의 실행 단위

두가지 main issue

• 중간에 실패하는 경우
• 여러 transcation이 동시에 실행되는 경우

Example of Fund Transfer
계좌 A에서 B로 50$을 송금하는 transaction

read(A)
A = A - 50
write(A)
read(B)
B = B + 50
write(B)

Atomicity requirement

• 만약 transaction이 3번째 줄까지만 실행되고 6번째 줄이 실행되지 않으면, 50달러는 그냥 사라져버림. -> database inconsistent
• system은 부분적으로 실행된 transaction이 database에 영향을 끼치지 않을 것을 보장해야 함

Durability requirement

• 한번 수행된 transaction은 영원히 반영되어야 함

Consistency requirement

• 예시를 예로 들면, A, B의 총 금액은 항상 유지되어야 함
  
• In general, consistency requirements include
  -Explicit integrity (ex. primary key, foreign key)
  -Inplicit integrity (ex. sum of balance)
• transaction must see a consistent database

Isolation requirement

• transaction이 실행될 때, 다른 transaction의 연산이 영향을 끼치면 안됨

위의 4가지 원칙을 ACID Principle이라고 함

Transaction State

Active - 초기 state.
Partially committed - final statement가 실행된 뒤 state
Failed - execution이 더 이상 진행이 불가능 할 때
Aborted - transaction이 roll back되고 database는 초기 상태로 복구

• restart the transaction
• kill the transaction

Committed - transaction이 성공적으로 완료

Concurrent Execution

다수의 transaction이 동시에 실행될 수 있음
장점

• processor and disk utilization 증가
• average response time 감소

Concurrency control schemes - Isolation을 보장하기 위한 mechanism

Schedules

Schedule - concurrent한 transaction들의 instruction의 실행 순서

• transaction들의 schedule은 각 transaction들의 모든instruction을 포함해야 함
• transaction내의 instruction의 순서는 유지되어야 함

성공적으로 완료된 transaction은 마지막으로 commit instruction을 실행

완료되지 못한 transaction은 마지막으로 abort instruction을 실행

Serial Schedule

Serial schedule - transaction내의 insturction이 연속적으로 쭉 실행되는 schedule
예시

Serializable Schedule - serial schedule은 아니지만, serial schedule과 동일한 결과를 내는 schedule
예시

Serializability

기본 가정 - 각 transaction은 database consistency를 유지

serializability의 두 가지 form

• Conflict serializability
• View serializability

Conflict Serializability

두 transaction $T_i \enspace T_j$의 instruction $I_i\enspace I_j$가 있을 때, 두 instruction중 하나라도 같은 데이터 Q에대한 write가 있을 때 conflict 발생
1. $I_i=read(Q),\enspace I_j=read(Q)$ => conflict 아님
2. $I_i=read(Q),\enspace I_j=write(Q)$ => conflict
3. $I_i=write(Q),\enspace I_j=read(Q)$ => conflict
4. $I_i=write(Q),\enspace I_j=write(Q)$ => conflict

conflict가 있으면 순서가 중요해짐

conflict가 없는 instruction은 순서를 바꿔도 같은 결과를 냄

이러한 conflict가 없는 instruction들의 순서를 바꿔 serial schedule로 만들 수 있으면 그 schedule은 conflict serializable하다고 한다.
conflict serializable한 schedule의 예시

conflict serializable하지 않은 예시

View Serializability

두 같은 instruction set으로 이루어진 schedule S와 S'이 있을 때, 다음 조건을 만족하면 두 schedule은 view equivalent한 관계
1. S에서 transaction Ti가 Q를 처음 read하면, S'에서도 Ti가 Q를 처음 read해야함(각 데이터의 초기값은 같은 transaction이 read해야함)
2. S에서 Ti가 Tj에 의해 write된 데이터 Q를 read하면, S'에서의 Ti도 Tj가 write한 데이터 Q를 read해야함
3. 데이터 Q에 대한 마지막 write는 같은 transaction이 수행해야 함

어떠한 schedule이 view equvalent한 serial schedule이 존재하면 그 schedule은 view serializable함

예시)

T27의 write(Q)와 T28의 write(Q)의 순서를 바꾸면 3가지 조건을 깨지 않으면서 serial schedule로 바꿀 수 있음
안되는 예시)

Other Notions of Serializabilty

conflict equivalent, view equivalent 둘 다 성립하지 않는 schedule일지라도, serial schedule로 바꿨을 때, 같은 결과를 낼 수도 있음

즉 conflict, view serializable하지 않으면 serializable이 안된다? -> no

Testing for Serializability

Test for conflict serializability

Precedence Graph - vertex가 transaction인 direct graph

두 transaction $T_i$, $T_j$가 서로 conflict이고 $T_i$가 conflicting data에 $T_j$보다 먼저 접근하면 $T_i$에서 $T_j$로 간선을 그린다.
예시)

precedence graph가 acyclic이면 conflict serializable

cycle detection algorithm = $O(n^2)$

graph가 acyclic하면, topological sort(한 방향으로 쭉 정렬)해 serial한 order로 만들 수 있다.

Test for view serializability

precedence graph로 못찾아

view serializability를 확인하는 문제는 NP-complete 문제임

하지만 단지 몇몇 충분 조건을 확인하는 것으로 view serializability 확인 가능 (조건을 만족하면 view serializable이라고 확신 가능, 하지만 만족하지 않는다고 view serializable이 아니라고는 확신할 수 없다)

Conflict VS View

DBMS에서는 conflict serializability를 더 많이 사용

하지만, conflict serializability는 serializable한 schedule 중 일부(conflict가 없는)만 가려낼 수 있음

view serializability를 test하는 것은 매우 힘듦 매우 제한된 형태만 concurrency control하는데 사용됨

Recoverable schedule

transaction의 failure를 다른 concurrent한 transaction에 알릴 필요가 있음

Recoverable schdule
$T_j$가 $T_i$가 마지막으로 write한 data를 read하면, $T_i$가 $T_j$보다 먼저 commit 해야 함

안되는 예시)

만약 T8이 abort되면, T9는 inconsistent한 data를 읽게 됨
그러므로, database는 schedule들이 recoverable함을 보장해야 함

Cascading Rollback

하나의 transaction이 rollback되면 얘랑 연관된 transaction들이 전부 rollback됨

T10이 rollback되면 T11, T12도 rollback 됨

Cascadeless Schedule

commit된 데이터만 read하면 cascade rollback이 일어 날 일이 없음

cascadeless하면 recoverable함

Concurrency control

DBMS는 conflict or view serializable하고 recoverable and cascadeless하게 scheduling해야 함

DBMS는 높은 concurrency를 제공해야 함

Weak Levels of Consistenct

몇몇 application(OLAP)는 weak level of consistency로 동작함. (not serializable한 schedule 허용)

• 정확성 대신 성능을 우선하기 위해

Online Transaction Processing - OLTP

• DB의 정확성이 중요
• 실제 DB를 수정하는 transaction
• 짧고 간단한 transaction
• transaction은 DB의 일부만 access

Online Analytic Processing - OLAP

• 복잡한 query
• transaction은 DB를 광범위하게 access
• Data가 up-to-date일 필요 없음
• DB의 내용을 분석하여 정보 제공

Phenomena caused by Concurrent Transaction

Dirty read

• transaction이 다른 concurrent uncommitted transaction이 write한 data를 read

Nonrepeatable read

• 같은 data를 읽었는데 값이 달라짐 (다른 transaction이 값을 변경)

Phantom read

• 같은 data를 읽었는데 없던 값이 생김 (다른 transaction이 값을 변경)

Serialization anomaly

• 일련의 transaction들을 수행한 결과가 다른 순서대로 수행 했을 때 다른 결과가 나오는 현상

Phantom phenomenon

T1
select ID, name from instructor where salary > 90000

T2
insert into instructor values('11111', 'James', 'Marketing', 100000)

T1이 실행되는 도중에 T2가 실행되면 원래 T1이 시작했을 때 의도한 결과와 다른 결과가 나옴 (새로 insert한 결과가 추가될 수 있음)
이는 tuple수준의 lock으로는 예방 불가

Transaction Isolation in SQL-92

Serializable - default
Repeatable read - commit된 record만 read 가능

• 같은 데이터에 대한 반복된 read는 같은 결과를 내야 함
• transaction이 serializable하지 않을 수 있음

Read committed - commit된 record만 read 가능

• read의 결과가 다를 수 있음

Read uncommitted - uncommitted record도 read 가능