직렬가능성 :: 필넷의 블로그라이프...

직렬가능성

2007/06/20 08:22 IT 이야기/데이터베이스

○ 직렬가능성, 회복가능

개요

° 트랜잭션들의 연산들이 인터리빙되어 수행될 때 어떤 스케줄들이 정확한지 식별하는데 사용됨
° 직렬가능 스케줄에서는 어떠한 정확성도 잃지 않으면서 동시 실행의 장점을 얻을 수 있음

직렬스케줄

직렬가능

° 스케줄에 참가하는 모든 트랜잭션 T에 대해서 T에 속한 모든 연산들이 다른 트랜잭션의 연산들과 인터리빙 되지 않고 연속적으로 실행될 때 직렬스케줄이라고 함

결과동치(View Equivalence)	충돌동치(Conflict Equivalence)
° 두 개의 스케줄이 DB의 최종상태를 같게 만드는 경우 ° 스케줄 동치에 사용되어선 안됨	° 두 개의 스케줄에서 어떠한 두 개의 충돌 연산들의 순서가 동일할 경우

° n개의 트랜잭션들로 구성된 스케줄 S가 동일한 n개의 트랜잭션들로 구성된 어떤 직렬 스케줄과 동치일 경우를 의미함
※ 충돌직렬가능 - 충돌동치의 개념을 이용한 스케줄 S가 어떤 스케줄 S'과 충돌동치일 경우

선행 그래프(Precedence Graph)

° 방향그래프 - (N,E)
° Node - 스케줄 S의 트랜잭션들의 집합
° Edge - T_i → T_j

° T_i가 write_item(X) 실행 후 T_j가 read_item(X)를 실행하는 경우
° T_i가 read_item(X) 실행 후 T_j가 write_item(X)를 실행하는 경우
° T_i가 write_item(X) 실행 후 T_j가 write_item(X)를 실행하는 경우

° 스케줄 S가 직렬 가능하다는 것은 선행그래프에서 사이클이 없다는 것의 필요충분조건이다

직렬가능성 보장프로토콜

° 2 Phase Locking
° Timestamping

회복가능
(Recoverable)

° 스케줄 S내에서 어떤 트랜잭션 T에 대해서도 T가 읽은 항목에 쓰기연산을 수행한 모든 트랜잭션 T'이 완료되기전까지 T가 완료되지 않는다면 S는 회복가능(Recoverable)하다고 말함
° 회복가능한 스케줄내에서는 완료된 트랜잭션은 복귀할 필요가 없다.

'IT 이야기 > 데이터베이스' 카테고리의 다른 글

데이터웨어하우스 (0)	2007/10/12
관계대수 vs 관계해석 (0)	2007/10/05
[데이터베이스] 2007 정보시스템감리사 기출문제 복원 (0)	2007/09/05
데이터베이스 설계 (0)	2007/06/21
트랜잭션 특징 및 상태전이 (0)	2007/06/20
직렬가능성 (1)	2007/06/20