트랜잭션 처리

1. 트랜잭션 처리의 개념

 

① 사용자 수에 따른 시스템 분류

∘데이터베이스 시스템을 분류함에 있어서 사용자 수를 기준으로 하여 시스템 분류하면, 단일사용자 시스템과 다수 사용자 시스템으로 구분할 수 있음 - 단일 사용자 시스템: 한번에 한 사람만이 그 시스템을 사용할 수 있는 시스템 . 대다수 개인용 컴퓨터 시스템 - 다수 사용자 시스템: 많은 사용자가 동시에 그 시스템을 사용할 수 있는 시스템 . 대부분의 DBMS는 다수 사용자 시스템 - 항공기 예약, 은행, 보험, 증권 등 ∘다수 사용자 시스템은 한 컴퓨터가 동시에 여러 개의 프로그램(또는 트랜잭션)을 처리하는 다중 프로그래밍 개념 때문에 여러 사용자들이 컴퓨터 시스템을 동시에 사용할 수 있음 ∘다수 사용자 DBMS에서 사용자 프로그램들이 동시에 접근하는 주된 자원은 데이터베이스에 저장되어 있는 데이터 항목이며, 사용자 프로그램들은 데이터베이스에서 지속적으로 정보를 검색하고 데이터베이스를 갱신함 [그림 1] 트랜잭션 처리의 인터리빙 형태와 병렬 처리 ∘다수 사용자의 동시 실행은 [그림 1]의 프로세스 A, B와 같은 인터리빙 방식과 프로세스 C, D와 같이 병행처리 방식이 있음 ∘인터리빙 방식은 다중 프로그래밍 개념으로 CPU가 입출력 동안 다른 프로세스를 실행하기 위해 전환하는 것을 뜻하며, 병행 처리는 CPU가 여러 개일 때를 의미함

 

② 트랜잭션의 읽기(read)와 쓰기(write) 연산

∘트랜잭션(transaction)은 데이터베이스 처리의 논리적 단위를 형성하는 실행 프로그램임 ∘트랜잭션은 하나 이상의 데이터베이스 접근 연산을 포함하며, 그 접근 연산에는 삽입, 삭제, 갱신, 검색 연산이 포함됨 ∘트랜잭션을 형성은 데이터베이스 연산을 응용 프로그램에 끼워 넣거나 고수준 질의어를 사용하여 대화식으로 기술할 수도 있음 ∘트랜잭션에는 갱신은 하지 않고 검색만 한다면 읽기전용(read-only) 트랜잭션이라고 함 ∘하나의 트랜잭션이 포함할 수 있는 기본적인 데이터베이스 접근 연산은 보통 read_item 연산과 write_item 연산을 수행함 - read_item(X): 이름이 X인 데이터베이스 항목을 프로그램 변수로 읽어 들이며, 다음과 같은 단계를 거쳐서 실행됨 ① 항목 X를 포함하는 디스크 블록의 주소를 찾음 ② 디스크 블록을 주기억장치의 버퍼로 복사함     (그 디스크 블록이 주기억장치의 버퍼에 이미 존재하는 것이 아닐 때) ③ 항목 X를 버퍼로부터 프로그램 변수 X로 복사함 - write_item(X): 프로그램 변수 X의 값을 데이터베이스 항목에 X에 기록하며 다음과 같은 단계를 거쳐 실행됨 ① 항목 X를 포함하는 디스크 블록의 주소를 찾음 ② 디스크 블록을 주기억장치의 버퍼로 복사함     (그 디스크 블록이 주기억장치의 버퍼에 이미 존재하는 것이 아닐 때 ) ③ 항목 X를 프로그램 변수 X에서 버퍼의 정확한 위치로 복사함 ④ 갱신된 블록을 디스크에 즉시 또는 나중에 디스크에 저장함 ∘일반적으로 DBMS는 주기억 장치 안에 여러 개의 버퍼를 가지며, 버퍼 교체 정책(buffer replacement policy)을 사용하여 현재 버퍼들 중에서 어떤 것을 교체할 것인가 선택함 ∘동시성 제어와 회복기법은 주로 트랜잭션에 포함되어 있는 데이터베이스 접근 명령들과 　　관계있으며, 여러 사용자들이 동시에 트랜잭션들을 수행시켜서 동일한 데이터베이스 항목에 접근하여 항목을 갱신할 가능성이 있음 [그림 2] 트랜잭션의 예

③ 동시성 제어가 필요한 이유(1)

∎적절한 제어가 없이 동시 실행은 여러 문제점을 발생할 수 있으며, 그 문제점을 살펴보면, ∘갱신 손실 문제(lost update problem) - 두 개의 트랜잭션이 동일한 데이터베이스 항목에 접근할 때 - 두 트랜잭션의 연산들이 인터리빙된 형태로 실행이 되어 어떤 데이터베이스 항목의 값을 틀리게 만들 때 발생함 - 트랜잭션 T1과 T2가 거의 동시에 시작되고 그 연산들이 운영체제에 의해 인터리빙된다고 가정하면, T1이 변경한 X값을 데이터베이스에 기록하기 전에 T2가 X값을 읽게 되어 항목 X의 최종 값은 틀리게 됨 ∘임시 갱신 또는 오손 읽기 문제(temporary update or dirty read problem) - 하나의 트랜잭션이 데이터베이스 항목을 갱신하고 나서, 어떤 이유로 인하여 그 트랜잭션이 실패 하였을 경우 발생하는 것으로서, 실패한 트랜잭션이 갱신한 값을 원래의 값으로 되돌리기 전에 다른 트랜잭션이 그 값을 읽을 때 발생함 - T1이 항목 X를 갱신하고 나서 완료되기 전에 실패했을 때, 시스템은 X를 원래의 값으로 되돌려야 한다. 그러나 시스템이 X를 원래의 값으로 바꾸기 전에 트랜잭션 T2가 T1의 　실패로 인하여 데이터베이스에 영구히 기록되지 않을 X의 임시 값을 읽게 되면 X의 최종 결과가 틀리게 됨 ∘ 부정확한 요약 문제(incorrect summary problem) - 다른 트랜잭션들이 일부 레코드들을 갱신하는 동안 한 트랜잭션이 이 레코드들을 포함한 여러 레코드 상에서 집단함수를 계산한다고 가정하면, 집단함수는 레코드들 중 어떤 것은 갱신되기 전의 값으로, 또 어떤 것은 갱신된 이후의 값으로 계산할 것임 [그림 3] 갱신 손실 문제(lost update problem)의 예

④ 동시성 제어가 필요한 이유(2)

[그림 4] 임시 갱신 문제(temporary update problem)의 예 [그림 5] 부정확한 요약 문제(incorrect summary problem)의 예 ∘반복할 수 없는 읽기 문제 (unrepeatable read problem) - 트랜잭션 T가 수행 도중 하나의 항목을 두 번  읽을 때 각각의 읽기 연산 사이에 다른 트랜잭션 T＇가 그 항목의 값을 바꾸게 되면 T는 동일한 항목을 서로 다른 값으로 읽게 되는 경우이며, 예를 들어, 항공 예약이 실행되는 동안 어떤 고객이 여러 항공편에 대해서 남아 있는 좌석 수를 문의한 뒤 특정 항공편으로 결정하는데, 그 때 예약 트랜잭션은 해당 예약 작업을 끝내기 전에 그 항공편의 좌석 수를 한 번 더 읽게 됨

⑤ 회복이 필요한 이유

∘ DBMS는 트랜잭션의 실행 결과 다음 성질 중 한 가지를 만족하도록 보장해야 함 - 트랜잭션의 모든 연산이 성공적으로 완료되고, 그 결과가 데이터베이스에 영구적으로 기록이 됨 - 트랜잭션이 데이터베이스나 어떤 다른 트랜잭션에도 영향을 미치지 않음 ∘DBMS는 트랜잭션 T의 일부 연산만이 반영되고 나머지 연산은 반영되지 않는 그러한 상황을 허용하면 안 된다. 이러한 상황은 트랜잭션이 연산의 일부만 수행하고 연산 전체를 수행하기 전에 실패하는 경우 발생할 수 있음 ∘트랜잭션 수행 중 실패(고장)의 원인들 ① 컴퓨터 고장 또는 시스템 붕괴(system crash) - 컴퓨터 시스템에서 트랜잭션 수행도중 하드웨어나 소프트웨어에 에러 발생 가능 - 하드웨어가 고장 나면 컴퓨터 주기억장치의 내용이 모두 사라짐 ② 트랜잭션 또는 시스템 에러 - 정수 오버플로 혹은 0으로 어떤 수를 나누는 연산 등과 같이 어떤 연산의 에러 발생 - 잘못된 매개변수 값이나 논리적 프로그래밍 에러로 인하여 트랜잭션 실패 - 사용자가 수행중인 트랜잭션에 의도적으로 인터럽트 실행 예) control-C 누름 ③ 트랜잭션이 탐지한 지역적 에러 또는 예외 조건 - 트랜잭션의 수행 도중 트랜잭션을 철회(abort)해야 하는 어떤 조건이 발생할 수 있음 - 트랜잭션이 필요로 하는 데이터가 존재하지 않는 경우 - 예) 은행시스템에서 계좌에 충분한 잔액이 남아 있지 않을 경우에 그 계좌로부터 일정금액을 인출하는 트랜잭션은 철회해야 하며, 이 예외 조건은 트랜잭션 자체에 프로그램 되어 있어야 하며, 이 경우 고장으로 분류하지 않음 ④ 동시성 제어 시행 - 트랜잭션이 직렬가능성을 위반하거나, 여러 트랜잭션들이 교착상태(deadlock)에 속하게 되어 트랜잭션을 철회시키거나, 나중에 다시 시작시킬 수 있음 ⑤ 디스크 고장 - 입출력 오류 또는 디스크의 판독/기록 헤드가 파손되어서 디스크 블록들의 데이터가 손실될 수 있으며, 이런 손실은 트랜잭션의 입출력 연산이 수행되는 동안 발생함 ⑥ 물리적 문제와 재해(catastrophe) - 전원이나 에어컨의 고장, 화재, 절도, 사보타주, 과실로 인한 디스크나 테이프의 덮어쓰기, 오퍼레이터에 의한 잘못된 테이프의 적재 등이 이에 해당함 ∘고장 유형 ①,②,③,④ 발생할 때 마다 시스템은 고장을 회복하기 위해서 충분한 정보를 유지하고 있어야 하며, 고장 유형 ⑤,⑥은 자주 발생하지는 않지만 회복하기가 더 어려우므로 발생할 경우를 대비해야 함

 

2. 트랜잭션 상태와 특성

 

① 트랜잭션의 상태와 추가적인 연산

∘하나의 트랜잭션은 완전히 수행을 완료하거나 전혀 수행되지 않아야 함 ∘회복을 위한 목적으로 회복 관리자는 트랜잭션에 대한 - 트랜잭션의 시작, 읽기 또는 쓰기, 트랜잭션의 종료, 트랜잭션의 완료, 복귀 또는 철회 - 연산들이 적용된 시점을 유지해야 하며, 취소와 재수행과 같은 추가적인 연산을 필요로 하는 회복 기법도 있음 [그림 6] 트랜잭션 실행의 상태를 나타내는 상태 전이도 ∘트랜잭션 시작(BEGIN TRANSACTION): 트랜잭션 수행의 시작을 표시함 ∘읽기(READ) 또는 쓰기(WRITE): 트랜잭션의 일부로 수행되며 데이터베이스에 대하여 읽거나 쓰는 연산을 가리킴 ∘트랜잭션 종료(END TRANSACTION): 읽기, 쓰기 연산들이 끝났음을 가리키며, 트랜잭션 실행의 종착점(end limit)을 표시한다. 그러나 이 시점에서 트랜잭션으로 인한 변화들을 영구적으로 데이터베이스에 반영해야 할지, 아니면 그 트랜잭션이 동시성 제어에 관한 규칙을 위반하였거나 그 밖의 다른 이유들 때문에 철회해야 할지 확인할 필요가 있음 ∘트랜잭션 완료(COMMIT TRANSACTION): 트랜잭션이 성공적으로 실행을 마쳤음을 나타낸다. 따라서 그 트랜잭션을 실행하여 발생한 모든 갱신들이 데이터베이스에 안전하게 저장되며, 이후 취소(undo)되지 않음 ∘복귀(ROLLBACK) 또는 철회(ABORT): 트랜잭션이 성공적으로 종료되지 않았음을 나타낸다. 따라서 그 트랜잭션이 데이터베이스에 반영시킨 갱신은 반드시 취소해야 함 ∘취소(UNDO): 복귀와 비슷하지만 트랜잭션 전체가 아닌 하나의 연산에만 적용됨 ∘재수행(REDO): 완료된 트랜잭션의 모든 연산들이 데이터베이스에 성공적으로 반영되도록 보장하기 위해서, 그 트랜잭션의 일부 연산들을 재수행해야 함을 나타냄

② 시스템 로그와 트랜잭션의 완료점

∎시스템 로그 ∘트랜잭션 실패를 회복하기 위해서 시스템은 로그(log)를 유지함 - 로그를 때로는 DBMS 저널(journal)이라고도 부름 ∘로그는 데이터베이스 항목들의 값에 영향을 미치는 트랜잭션의 모든 연산들을 기록함 ∘로그는 디스크에 유지되기 때문에 디스크 오류나 재해를 제외한 어떤 유형의 고장에도 영향을　받지 않음 ∘재해로부터 로그를 보호하기 위해서 로그를 주기적으로 테이프 등에 백업해야 함 ∘연쇄복귀(cascading rollback)를 방지하는 회복 프로토콜에서는 읽기연산을 시스템 로그에 기록할 필요는 없지만, 다른 프로토콜에서는 읽기연산을 시스템 로그에 기록해야 함 ∘트랜잭션들이 중첩되지 않고 데이터베이스에 대한 모든 영구적인 변화들이 트랜잭션 내에 일어난다고 가정을 한다면, 실패한 트랜잭션으로부터 회복하는 것은 로그를 보고 회복 가능한 트랜잭션 연산들을 취소하거나 재수행할 수 있음 <시스템 로그 진행순서> ① [start_transaction, T]: 트랜잭션 T가 실행을 시작했음을 기록함 ② [write_item, T, X, old_value, new_value]: 트랜잭션 T가 데이터베이스 항목 X를 old_value에서 new_value로 변경했음을 기록함 ③ [read_item, T, X]: 트랜잭션 T가 데이터베이스 항목 X의 값을 읽었음을 기록함 ④ [commit, T]: 트랜잭션 T가 성공적으로 끝났음을 기록한다. 그리고 그 효과가 완료 (영구적으로 저장) 될 수 있음을 보장함 ⑤ [abort, T]: 트랜잭션 T가 철회되었음을 기록함 ∎트랜잭션의 완료점 ∘데이터베이스를 접근하는 모든 연산들이 성공적으로 수행되고 트랜잭션의 모든 연산들이 데이터베이스에 끼친 효과들이 로그에 저장되었을 때, 트랜잭션 T는 완료점에 도달함 ∘완료점을 지나면 트랜잭션은 완료되었다고 하며, 그 트랜잭션의 효과는 데이터베이스에 영구적으로 저장됨 ∘그 트랜잭션은 로그에 하나의 [commit, T] 레코드를 기록한다. 만일 시스템 고장이 일어나면 로그에 [start_transaction, T]레코드는 기록했지만 [commit, T] 레코드는 기록하지 않은 모든 트랜잭션 T를 거꾸로 찾는다. 회복 과정에서 이 트랜잭션들은 데이터베이스에 반영한 영향을 없애기 위해서 복귀해야 함 ∘로그에 commit 레코드를 기록한 트랜잭션은 commit 레코드 이전에 먼저 자신의 모든 쓰기 연산들을 로그에 기록해야 하며, 그 트랜잭션이 데이터베이스에 끼친 영향은 로그를 보고 재수행해야 한다. 또한 로그 파일은 반드시 디스크에 유지해야 함 ∘로그 레코드가 추가될 때마다 디스크에 직접 기록하는 대신에 로그 파일의 한 블록을 주기억장치에 유지하고 그것이 로그 레코드들로 채워질 때마다 디스크에 한 번만 기록하는 방법이 보편적으로 사용됨 ∘트랜잭션을 완료하기 전에 로그파일에 강제 쓰기(force-writing)를 함

④ 트랜잭션의 성질

∘트랜잭션은 다음의 ACID 성질을 가져야 하며, 이 성질은 DBMS의 동시성 제어와 회복 기법을 통하여 유지됨 - 원자성(Atomicity): 한 트랜잭션은 하나의 원자적 수행 단위이며, 트랜잭션은 완전히 수행되거나 전혀 수행되지 않아야 함 - 일관성 유지 (Consistency preservation): 트랜잭션을 완전히 실행하면 데이터베이스를 하나의 일관된 상태에서 또 다른 일관된 상태로 바꿔야 함 - 고립성(Isolation). 하나의 트랜잭션은 다른 트랜잭션들과는 독립적으로 실행되는 것처럼 보여야 한다. 즉 하나의 트랜잭션의 실행은 동시에 실행 중인 다른 트랜잭션의 간섭을 받아서는 안 됨 - 지속성(Durability) 또는 영속성(permanency): 일단 한 트랜잭션이 데이터베이스를 변경시키고 그 변경이 완료되면 그 변경은 이후의 어떠한 고장에도 손실되지 않아야 함 ∘원자성을 보장하기 위해서는 한 트랜잭션을 끝까지 수행해야 한다. 원자성을 보장하는 것은 DBMS의 트랜잭션 회복 서브시스템의 역할임 ∘일관성유지 성질은 데이터베이스 프로그램을 작성하는 프로그래머나 무결성 제약조건을 시행하는 DBMS 모듈의 책임임 ∘동시성 제어 방법이 고립성을 지켜줌 ∘지속성을 보장하는 것은 회복 기법의 책임임 ∘고립성 등급(level of isolation) - 0 등급 : 상위등급의 트랜잭션이 오손읽기(dirty-read)한 것을 덮어쓰지 않음 - 1 등급 : 갱신 손실(lost update)이 없음 - 2 등급 : 갱신 손실과 오손 읽기가 없음 - 3 등급 : 등급 2의 성질을 모두 가지며, 이외에도 반복 읽기 성질을 가짐

※ 원자성의 예

∘은행 시스템 계좌 이체 트랜잭션의 예를 살펴보면, 계좌 A는 잔고가 1000만원, 계좌 B는 잔고가 3000만원 만약 계좌 A의 100만원을 계좌 B로 이체한다고 가정함 T : Begin_Trans           Read(A)           A := A - 100만원           Write(A)           ◀--           Read(B)           B := B + 100만원           Write(B)      End_Trans ∘정상적인 결과는 계좌 A는 900만원, 계좌 B는 3100만원이 되어야 하지만, Write(A)를 수행한 직 후 오류가 났을 경우에 원자성의 특성을 고려치 않는다면, 결과는 계좌 A는 900만원, 계좌 B는 3000만원이 되어서 결국 100만원은 상실되는 모순이 생길 수 있음 ∘트랜잭션의 실행에서부터 종료할 때까지 한 단위로 해서 일관성 있게 해 주는 것이 원자성의 특성이며, 원자성을 지원하는 연산은 commit(완료), rollback(복귀)이 있음

 

3. 스케줄의 회복 가능성

 

① 트랜잭션들의 스케줄(히스토리)

∘트랜잭션들이 인터리빙 방식으로 동시에 수행될 때 여러 트랜잭션들이 가진 연산들의 실행 순서를 스케줄(또는 히스토리)이라 함 ∘트랜잭션의 스케줄: - n개의 트랜잭션 T1, T2, ..., Tn의 스케줄(히스토리) S는 이들 트랜잭션들의 연산들을 순서화한 것임 - 여기서 스케줄 S에 참여하는 각 트랜잭션 Ti에 대해서 Ti의 연산들이 Ti내에서와 동일한 순서로 스케줄 S에 나타나야 함 ∘충돌(conflict): - 하나의 스케줄에 포함된 두 개의 연산이 아래의 세 가지 조건들을 모두 만족하면 충돌(conflict)한다고 말함 : ① 그 연산들은 서로 다른 트랜잭션에 속함 ② 그 연산들은 동일한 항목 X에 접근함 ③ 그 연산들 중 최소한 하나는 write_item(X)이 있음 ∘완전한 스케줄(complete schedule) : n개의 트랜잭션 T1, T2, ..., Tn에 대한 스케줄 S가 다음과 같은 조건을 만족하면 완전한 스케줄이라고 함 ① S 내의 연산들은 T1, T2, ..., Tn내의 연산들이며, 각 트랜잭션의 마지막 연산으로서 완료나 철회 연산을 포함함 ② 트랜잭션 Ti의 연산들의 어떠한 쌍에 대해서도 S내에서 그 연산들이 나타나는 순서는 Ti내에서 그 연산들이 나타나는 순서와 동일함 ③ 충돌하는 어떠한 두 개의 연산에 대해서도 그들 중 하나는 반드시 나머지 하나보다 스케줄에서 먼저 나타나야 함 ∘위의 조건③은 두 개의 충돌하지 않는 연산들 중 어떤 연산이 먼저 스케줄에 나타나야 하는지 정의하지 않으므로, 스케줄은 n개의 트랜잭션에 포함된 연산들의 부분순서로 정의됨 ∘그러나 충돌되는 연산들의 어떠한 쌍에 대해서도(조건③),동일한 트랜잭션에 속하는 연산들의 어떠한 쌍에 대해서도(조건②), 반드시 전체 순서가 스케줄에 명시되어야 함 ∘조건① 은 단지 트랜잭션의 모든 연산들이 반드시 완전한 스케줄 안에 나타나야 한다는 것을 의미함 ∘모든 트랜잭션은 완료되거나 철회되므로 완전한 스케줄은 진행 중인 트랜잭션을 스캐줄의 끝에 포함하지 않음 ∘트랜잭션 처리 시스템에서 새로운 트랜잭션들이 계속해서 시스템으로 들어오기 때문에 완전한 스케줄들을 만나기는 어려움 ∘완료 연산 Ci가 스케줄 S에 있는 트랜잭션 Ti들에 속한 연산들만을 포함함

② 회복가능성을 근거로 한 스케줄의 특성화

∘회복 가능한 스케줄 (recoverable schedule) - 트랜잭션 T가 완료되었다면 절대 복귀(rollback)될 필요가 없다는 기준을 두고, 이 기준을 만족하는 스케줄을 회복 가능한 스케줄이라 함 ∘회복가능(recoverable) - 만약 스케줄 S내의 어떤 트랜잭션 T에 대해서도 T가 읽은 항목에 쓰기연산을 수행한 모든 트랜잭션 T’이 완료되기 전까지 T가 완료되지 않는다면 S가 회복가능하다고 함 - 회복 가능한 스케줄 내에서는 어떠한 완료된 트랜잭션도 복귀할 필요가 없음 ∘연쇄 복귀(cascading rollback) 또는 연쇄 철회(cascading abort) - 완료되지 않은 트랜잭션이 실패한 트랜잭션으로부터 항목을 읽어옴으로써 발생하는 것으로 하나의 트랜잭션 철회가 다른 트랜잭션의 철회로 이어지는 현상이 발생함 [예] Se : r1(X); w1(X); r2(X); r1(Y); w2(X); w1(Y); a1; a2 . r: read_item, w: write_item, c: commit, a: abort의 기호를 나타냄 . 트랜잭션 T2는 항목 X를 T1으로부터 읽었고, 그 후 T1이 철회되었기 때문에 T2를 복귀해야 함 - 많은 트랜잭션들이 연쇄복귀 될 수 있기 때문에 연쇄복귀는 시간을 많이 소비함 ∘연쇄복귀방지 - 스케줄내의 모든 트랜잭션들이 오직 완료된 트랜잭션들이 쓴(갱신) 항목만을 읽는다면 그 스케줄은 연쇄복귀를 방지한다고 말함 ∘엄격한 스케줄(strict schedule) - 마지막으로 X에 쓰기연산을 한 트랜잭션이 완료되거나 철회되기 전까지 다른 트랜잭션이 X를 읽지도 쓰지도 못함 - 회복과정 : 철회된 쓰기연산이 적용되기 전에 X가 가지고 있던 이전 값(before image, BFIM)으로 복귀함 ∘스케줄들을 ①회복가능성, ②연쇄 복귀의 방지, ③엄격함이라는 관점에 따라 특성화하였으며, 스케줄들이 가진 특성들은 번호가 높아짐에 따라 더 엄중한 조건임을 알 수 있다. 그러므로 조건 ②는 조건 ①을 암시하고 조건 ③은 조건 ②와 ① 모두를 암시한다. 따라서 모든 엄격한 스케줄들은 연속적인 철회가 필요 없으며, 모든 연속적인 철회가 필요 없는 스케줄들은 회복 가능함

 

 

4. 직렬 가능성으로 스케줄의 특성화

 

① 직렬, 비직렬, 충돌 직렬가능 스케줄(1)

∘직렬 스케줄(serial schedule) - 스케줄에 참가하는 각 트랜잭션 T에 대해서 T에 속한 모든 연산들이 다른 트랜잭션의 연산들과 인터리빙되지 않고 연속적으로 실행될 때 직렬 스케줄이라고 함 ∘스케줄의 직렬가능 - n개 트랜잭션들로 구성된 스케줄 S가 동일한 n개의 트랜잭션들로 구성된 어떤 직렬 스케줄과 동치일 경우를 의미함 ∘결과 동치(result equivalence) - 두 개의 스케줄이 데이터베이스의 최종 상태를 동일하게 만드는 경우이며, 결과 동치만으로 스케줄의 동치를 정의하는데 사용해서는 안 됨 ∘충돌 동치 - 두 스케줄에서 어떠한 두 개의 충돌 연산들의 순서도 동일할 경우 [그림 7] 트랜잭션 T1과 T2에 관련된 직렬 및 비직렬 스케줄의 예 ∘[그림 7]의 스케줄 A와 B는 직렬 스케줄(serial schedule) - 스케줄 A는 T1이 실행된 다음 T2가 실행되고, B는 T2가 실행된 다음 T1가 실행됨 ∘[그림 7]의 스케줄 C와 D는 비직렬 스케줄(nonserial schedule) 　- 스케줄 C와 D는 두 트랜잭션에 속한 연산들이 인터리빙되기 때문에 비직렬 스케줄 임

 

② 직렬, 비직렬, 충돌 직렬가능 스케줄(2)

∘직렬 스케줄의 문제점은 연산들의 동시성과 인터리빙을 제한하는 것이며, 직렬 스케줄에서 어떤 트랜잭션이 입출력 연산이 끝나기를 기다리게 되면, 다른 트랜잭션이 중앙처리장치를 사용하지 못하도록 하기 때문에 중요한 자원인 중앙처리장치를 낭비하게 됨 ∘n개의 트랜잭션으로 구성된 스케줄 S가 동일한 n개의 트랜잭션으로 구성된 직렬 스케줄과 동치(equivalence)이면 그 스케줄은 직렬 가능함 ∘n개의 트랜잭션으로 만들 수 있는 직렬 스케줄의 개수는 n!이고 비직렬 스케줄의 개수는 이보다 훨씬 더 많음 ∘만약 두 개의 스케줄이 데이터베이스의 최종 상태를 동일하게 만든다면 그 두 개의 스케줄을 결과 동치(result equivalence)라고 함 - 두 개의 스케줄이 우연히 마지막 상태를 같게 만들 수도 있음 - 예) S1: read_item(X); x:=X+10; write_item(X); S2: read_item(X); x:=X*1.1; write_item(X); . X의 초기값이 100이라면 결과 동치가 되지만, 일반적으로는 결과 동치가 아님 ∘스케줄의 동치를 정의하기 위해서는 일반적으로 충돌 동치와 뷰 동치 두 방법이 있음 ∘만약 두 스케줄에서 어떠한 두 개의 충돌연산의 순서도 동일하다면 두 스케줄은 충돌동치　　 (conflict equivalence)라고 함 ∘충돌 동치의 개념을 이용해서 스케줄 S가 어떤 직렬 스케줄 S’과 (충돌) 동치이면 충돌 직렬가능(conflict serializable)하다고 정의하며, 이 경우 S에서 충돌이 아닌 연산들을 직렬 스케줄 S’과 동치가 될 때까지 재배열할 수 있음 ∘[그림 7]의 스케줄 D는 직렬스케줄 A와 동치임 - 두 스케줄에서 T2의 read_item(X)는 T1이 기록한 X 값을 읽고, read_item(Y) 연산은 데이터베이스의 초기값을 읽음 - 양쪽 스케줄에서 T1은 항목 Y를 갱신하는 마지막 트랜잭션이고 T2는 항목 X를 갱신하는 마지막 트랜잭션임 - A가 직렬스케줄이고 D가 A와 동치이기 때문에 D는 직렬가능 스케줄임 ∘[그림 7]의 스케줄 C는 두개의 직렬 스케줄 A와 B의 어떤 것과도 동치가 아니다. - 스케줄 A에서 T2의 read_item(X) 연산은 T1이 기록한 값을 읽지만 스케줄 C에서는 X의 초기값을 읽기 때문에 동치가 되기 위한 규칙1을 위반하므로 스케줄C는 스케줄 A와 동치가 되지 않음

 

③ 스케줄의 충돌 직렬 가능성 테스트(1)

∘스케줄 S의 충돌 직렬가능성 테스트 알고리즘 ① 스케쥴 S에 참가하는 각 트랜잭션 Ti에 대해 선행 그래프에서 Ti라는 레이블을 가진 노드 생성 ② 스케줄 S에서 Ti가 write_item(X)를 실행한 후에 Tj가 read_item(X)를 실행하는 경우마다 선행 그래프에 간선 (Ti Tj) 생성 ③ 스케줄 S에서 Ti가 read_item(X)를 실행한 후에 Tj가 write_item(X)를 실행하는 경우마다 선행 그래프에 간선 (Ti Tj) 생성 ④ 스케줄 S에서 Ti가 write_item(X)를 실행한 후에 Tj가 write_item(X)를 실행하는 경우마다 선행 그래프에 간선 (Ti Tj) 생성 ⑤ 선행 그래프에 사이클이 없으면 스케줄 S는 직렬 가능하고, 스케줄 S가 직렬 가능하면 선행 그래프 사이클은 없음(스케줄 S가 직렬 가능한 것은 선행 그래프에 사이클이 없다는 것의 필요충분조건임) ∘선행 그래프에 존재하는 모든 간선에 대해 위상 정렬(topological sorting, 그래프의 노드들을 배열하는 과정)함으로써 얻어짐 [그림 8] 충돌 직렬 가능성 테스트 선행 그래프 ∘일반적으로 S에 대한 선행 그래프에 사이클이 없으면 여러 개의 직렬 스케줄이 S와 동치가 될 수 있으며, 반면에 선행 그래프에 사이클이 존재하면 동치인 직렬 스케줄을 생성할 수 없음을 나타냄

④ 스케줄의 충돌 직렬 가능성 테스트(2)

∘직렬 가능성을 테스트하는 예를 [그림 9] 세 개의 트랜잭션 예 T1, T2, T3의 read, write 연산 [그림 10] 스케줄 E [그림 11] 스케줄 F

 

⑤ 스케줄의 충돌 직렬 가능성 테스트(3)

[그림 12] 스케줄 E에 대한 선행 그래프 [그림 13] 스케줄 F에 대한 선행 그래프 [그림 14] 동치인 직렬 스케줄을 두 개 가지는 선행 그래프

⑥ 직렬가능성의 용도와 뷰 동치, 뷰 직렬가능성

∎직렬가능성의 용도 ∘직렬가능한 스케줄에서는 어떠한 정확성도 잃지 않으면서 동시 실행의 장점을 얻을 수 있으나 현실적으로 스케줄의 직렬가능성을 테스트하는 것은 매우 어려움 ∘동시에 실행되는 트랜잭션들의 연산이 어떻게 인터리빙되는가는 일반적으로 운영체제의 스케줄러가 결정함 ∘운영체제는 시스템 부하, 트랜잭션이 시작된 시간 트랜잭션의 우선순위와 같은 요소들을 사용하여 어떤 스케줄내의 연산들의 순서를 정한다. 따라서 직렬 가능성을 보장하기 위한 스케줄의 연산들이 어떻게 인터리빙될 것인가를 미리 결정하는 것은 어려움 ∘직렬가능성의 이론을 사용하여 프로토콜이나 규칙들의 집합을 찾는 것인데, 이런 프로트콜과 규칙들의 집합을 모든 트랜잭션들이 지키거나 DBMS의 동시성 제어 서브시스템이 시행되면 트랜잭션들이 참여한 모든 스케줄의 직렬가능성을 보장하는 것임 ∘트랜잭션들이 시스템으로 들어올 때 한 스케줄이 언제 시작하고 언제 끝나는가를 결정하는 것이 어려운 문제점이 있음 ∘직렬가능성을 보장하는 몇 가지 동시성 제어 프로토콜 - 2단계 로킹(twp-phase licking)방법 : 동시에 실행되는 트랜잭션들이 서로 간섭하는 것을 방지하기 위해 데이터 항목에 로크를 거는 것에 바탕을 둠 - 타임스탬프 순서화(timestamp ordering) 방법 : 각 트랜잭션이 유일한 타임스탬프를 할당 받고, 어떠한 충돌 연산들도 트랜잭션이 가진 타임스탬프의 순서대로 실행되도록 보장하는 것임 ∎뷰 동치와 뷰 직렬가능성 ∘동시성 제어에 영향을 미치는 또 다른 요소는 한 개의 항목이 데이터베이스에서 얼마 만큼에 해당하는가를 나타내는 데이터 항목의 단위크기(granularity)임 ∘ 아래 세 가지 조건이 만족하면 두 스케줄 S와 S'는 뷰 동치 임 ① 동일한 트랜잭션들의 집합이 S와 S’에 참여하고, S와 S’은 그 트랜잭션들이 가진 연산들과 동일한 연산들을 포함 ② S에 속한 Ti의 임의의 ri(X)연산에 대해서, 그 읽기 연산이 Tj에 속한 연산 wj(X)가 기록한 X 값 (또는 스케줄이 시작되기 전에 X가 가지고 있던 원래의 값)을 읽은 연산이라면 S’에 속한 Ti의 ri(X) 연산이 읽는 X 값에 대해서도 동일한 조건이 만족되어야 함 ③ 만약 S에서 Tk의 wk(Y)연산이 항목 Y를 마지막으로 기록하는 연산이라면 S’에서도 Tk의 wk(Y) 연산이 항목 Y를 마지막으로 기록하는 연산이어야 함 ∘뷰동치의 바탕이 되는 아이디어는 두 개의 스케줄상에서 각 트랜잭션의 읽기연산이 동일한 쓰기연산의 결과를 읽는다면, 각 트랜잭션의 쓰기연산들은 동일한 결과를 내야 함 ∘조건 ③은 데이터베이스의 상태가 양쪽 스케줄의 끝에서 동일하게 되도록 각 데이터 항목에 대해 마지막으로 수행되는 쓰기 연산이 양쪽 스케줄에서 같도록 보장함 ∘만약 스케줄 S가 어떤 직렬스케줄과 뷰 동치이면 뷰 직렬가능하다고 하며, 만약 제약된 쓰기 가정이라고 알려진 조건이 스케줄상의 모든 트랜잭션에서 성립하면 충돌직렬 가능성의 조건과 뷰 직렬가능성의 정의는 유사함 ∘충돌 직렬 가능한 스케줄은 뷰 직렬 가능하지만 그 역은 성립하지 않으며, 뷰 직렬가능성을 검사하는 문제는 NP-완전(NP-complete)이기 때문에 이 문제를 해결하기 위한 효율적인 알고리즘을 찾는 것은 매우 어려움

 

5. SQL의 트랜잭션 지원

 

① SQL 트랜잭션(1)

∘SQL 트랜잭션은 작업의 논리적인 단위이며 원자성이 보장되며, 하나의 SQL문은 오류없이 실행을 완성하든지 혹은 실패하여 데이터베이스를 수정하지 않은 상태로 두든지 간에 관계없이 항상 원자적 수행단위로 간주됨 ∘SQL에는 명시적인 Begin_Transaction 문이 없으며, 트랜잭션은 특정한 SQL 문을 만났을 때 묵시적으로 시작함 ∘모든 트랜잭션은 명시적인 종료(end) 문을 가져야 함 ∘명시적인 종료 문에는 COMMIT 혹은 ROLLBACK이 있음 ∘모든 트랜잭션들은 속성을 가지고 있으며, 이러한 속성들은 SQL에서 SET TRANSACTION 문으로 명시됨 ∘속성들에는 접근 모드(access mode), 진단 영역 크기(diagnostic area size), 고립성 등급(isolation level)이 있음 ∘접근 모드는 READ ONLY 혹은 READ WRITE로 명시할 수 있음 - READ ONLY : 데이터 검색만이 가능하며, 고립성 등급을 READ UNCOMMITTED로 명시한다면 접근 모드는 READ ONLY로 됨 - READ WRITE : 수정, 삽입, 삭제, 생성 명령을 실행할 수 있으며, 고립성 등급을 READ UNCOMMITTED로 명시하지 않는 한 접근 모드의 디폴트(default)는 READ WRITE임 ∘진단 영역 크기 : DIAGNOSTIC SIZE n - 정수 값 n을 지정하며 이는 진단 영역에서 동시에 유지할 수 있는 조건들의 개수를 나타냄 - 이러한 조건들은 사용자에게 가장 최근에 실행한 SQL문에 대하여 반환정보(즉, 오류 혹은 예외)를 제공함

② SQL 트랜잭션(2)

∘고립성 등급 옵션 : ISOLATION LEVEL <isolation>문을 사용하여 명시되며, - <isolation>은 다음과 같은 값이 될 수 있음          . READ UNCOMMITTED          . READ COMMITTED          . REPEATABLE READ          . SERIALIZABLE - 디폴트 고립성 등급은 SERIALIZABLE이며, 몇몇 시스템에서는 READ COMMITTED를 디폴트 고립성 등급으로 사용하고 있음 ∘고립성 등급으로 실행한다면 문제들 다음 세 가지 위반 중에 하나 이상이 발생 가능함 - 오손 읽기(dirty read) - 반복할 수 없는 읽기(nonrepeatable read)    - 팬텀(phantom) 현상 ∘예제 SQL 트랜잭션          EXEC SQL WHENEVER SQLERROR GOTO UNDO;          EXEC SEQ SET TRANSACTION                  READ WRITE                  DIAGNOSTIC SIZE 5                  ISOLATION LEVEL SERIALIZABLE;          EXEC SQL INSERT INTO EMPLOYEE(FNAME, LNAME, SSN, DNO, SALARY)                  VALUES('Robert', 'Smith', 991004321, 2, 35000);          EXEC SQL UPDATE EMPLYEE                  SET SALARY = SALARY * 1.1 WHERE DNO = 2;          EXEC SQL COMMIT;          GOTO THE_END;          UNDO: EXEC SQL ROLLBACK;          THE_END: ...; - 새로운 행에 EMPLOYEE 테이블에 삽입하고, 부서번호 2번의 모든 종업원의 급여를 10% 상향조정하는 작업이며, 이 SQL문 중에 어떤 문이라도 오류가 발생하면, 전체 트랜잭션이 복귀됨