전공/데이터베이스 (21) 썸네일형 리스트형 [데이터베이스] 질의 처리와 최적화 - (1) 질의 처리 단계(Query Processing Procedure) 1. parsing과 translation: parser는 사용자가 작성한 질의의 문법이 맞는지 확인하고, 질의를 parse tree로 변환한다. 그 후 parse tree는 관계 대수 표현식으로 변환된다. 2. optimization: 먼저, 하나의 관계 대수식에 대해 동등한 관계 대수식을 가지는 많은 수의 질의 평가 계획(query execution plan)을 생성된다. 그 후, 각 질의 평가 계획을 구성하고 있는 relational operation들이 수행되었을 때 result size를 통계적으로 추정한다. 이때, 딕셔너리 데이터베이스에 저장되어 있는 통계적 수치들을 이용해서 result size를 추정하게 된다. (튜플의 개수.. [데이터베이스] 동시성 제어 - (2) 교착 상태 처리 - 잠금 기반 규약의 단점 아래의 스케줄을 살펴보면, lock-S(B)는 T4가 T3가 B에 대한 lock을 해제하기를 기다리도록 하고, lock-X(A)는 T3이 T4가 A에 대한 lock을 해제하기를 기다리도록 한다. 따라서 T3와 T4는 더 이상 진행되지 못하고 무한히 기다리는 교착 상태(dead lock)에 빠지게 된다. 또한 잠금 기반 규약은 기아(starvation) 현상이 발생할 수 있다. 이는 aging 기법을 사용해서 해결할 수 있다. - 교착 상태 예방 교착 상태를 예방하는 한 가지 방법으로 timeout-based schemes가 있다. 이는 lock을 요청한 트랜잭션이 일정한 시간 동안 기다리다가, 그 시간 안에 lock을 얻지 못하면 스스로 롤백해서 다시 시작하는 .. [데이터베이스] 동시성 제어 - (1) 동시성 문제 1. lost update problem: 두 트랜잭션이 같은 데이터 항목에 동시에 접근해 데이터 항목의 값을 갱신할 때, 두 트랜잭션 모두 정상적으로 실행됐음에도 불구하고 한 트랜잭션이 갱신한 값이 사라지는 문제가 발생한다. 2. uncommitted dependency: 한 트랜잭션 T1이 데이터 항목 X의 값을 갱신한 후,다른 트랜잭션 T2가 변경된 X의 값을 읽었을 때 트랜잭션 T1이 롤백되면, 저장된 X와 트랜잭션 T2가 읽은 X의 값이 일치하지 않는 문제가 발생한다. 3. inconsistent analysis problem: 한 트랜잭션의 실행 중에 다른 트랜잭션이 실행될 때, 데이터베이스의 일관성이 깨지는 문제가 발생할 수 있다. 잠금 기반의 규약(Lock-Based Proto.. [데이터베이스] 복구 시스템 - (3) 복구 알고리즘 - 트랜잭션 롤백 트랜잭션 롤백은 시스템 failure 후 복구 과정이 아닌 정상적인 상황에서 발생한다. 트랜잭션 $T_{i}$의 롤백은 다음과 같이 수행된다. 1. 로그를 역방향으로 스캔한다. $T_{i}$의 로그 레코드 를 만나면, 데이터 항목 $X_{j}$에 값 $V_{1}$을 기록하고, undo 작업에 대한 로그 레코드 를 기록한다. 이때, 이런 로그 레코드를 보상 로그 레코드(compensation log record)라고 부른다. 2. 를 만나면 역방향 탐색을 중단한다. 그리고 로그 레코드를 로그에 기록한다. - 시스템 failure 후의 복구 두 가지 단계를 거쳐 복구가 이루어진다. redo 단계: 마지막 검사점부터 순방향으로 로그를 탐색하며 모든 트랜잭션의 갱신 작업을 red.. [데이터베이스] 복구 시스템 - (2) 복구와 원자성(Recovery and Atomicity) failure에도 불구하고 원자성을 보장하기 위해서, 데이터베이스를 변경하기 전에 먼저 안정 저장 장치(stable storage)에 데이터베이스 변경과 관련된 정보를 기록해야 한다. 그중 가장 널리 사용하는 방법은 로그 기반 복구(log-based recovery)이다. - 로그 기반 복구(log-based recovery) 로그(log)는 안정 저장 장치에 유지되고, 연속된 로그 레코드(log record)로 구성되며, 데이터베이스의 모든 갱신 작업을 기록한다. 트랜잭션 $T_{i}$가 시작할 때, 로그 레코드 가 써진다(write). 트랜잭션 $T_{i}$가 write(X) 연산을 실행하기 전에, 로그 레코드 가 써진다. ($V_{1}$: 쓰.. [데이터베이스] 복구 시스템 - (1) 실패 분류(Failure Classification) 1. 트랜잭션 실패(transaction failure): 트랜잭션 실패를 유발하는 두 가지 원인이 있다. 논리적 오류: 잘못된 입력, 데이터 부재, 오버플로, 자원의 한계 초과 등 internal error로 인해 트랜잭션이 완료할 수 없는 상태를 의미한다. 시스템 오류: deadlock과 같은 error condition에 의해 데이터베이스 시스템이 트랜잭션을 종료해야 하는 상태를 의미한다. 2. 시스템 장애(system crash): 파워 고장이나 하드웨어 혹은 소프트웨어 오류로 인해 시스템이 정지되고 휘발성 저장 장치의 내용이 손실되고 트랜잭션 처리가 중단되는 상태를 의미한다. 이때, 시스템 장애가 발생해도 비휘발성 저장 장치의 내용은 손상되지.. [데이터베이스] 트랜잭션 - (2) 복구 가능한 스케줄(Recoverable Schedule) 복구 가능한 스케줄(recoverable schedule)이란 모든 트랜잭션 쌍 $T_{i}$와 $T_{j}$에 대해, $T_{i}$가 이전에 기록한 데이터 항목을 $T_{j}$가 읽었다면 $T_{i}$의 commit 연산이 $T_{j}$의 commit 연산보다 먼저 발생하는 스케줄을 말한다. 다음은 복구 불가능한 스케줄의 예시이다. 비연쇄적인 스케줄(Cascadeless Schedules) 하나의 트랜잭션의 취소로 인해 다른 트랜잭션들이 롤백되는 현상을 연쇄적 롤백(cascading rollback)이라고 한다. 이는 많은 양의 작업이 취소되기 때문에 비효율적인 방법이다. 따라서, 연쇄적 롤백이 발생하지 않도록 스케줄에 제한을 주어야 하는데, .. [데이터베이스] 트랜잭션 - (1) 트랜잭션(transaction) 개념 트랜잭션(transaction)은 다양한 데이터 항목에 접근하고 갱신하는 프로그램 수행의 단위이다. 데이터 무결성을 보존하기 위해서 데이터베이스 시스템은 다음과 같은 트랜잭션 성질을 보장해야 한다. 1. 원자성(atomicity): 트랜잭션의 모든 연산이 정상적으로 수행되거나 아니면 어떠한 연산도 수행되지 않은 원래 상태가 되도록 해야 한다. -> 복구 시스템(recovery system) 2. 일관성(consistency): 고립 상태에서 트랙잭션 수행이 데이터베이스의 일관성을 보존해야 한다. 3. 고립성(isolation): 여러 트랜잭션이 동시에 수행되더라도, 각 트랜잭션은 다른 트랙잭션이 동시에 수행되고 있는지를 알지 못하는 것과 같아야 한다. -> 동시성 제.. 이전 1 2 3 다음
