겜돌이의 개발일지

개요 트랜잭션이 버퍼에는 갱신 사항을 반영했지만, 버퍼의 내용이 디스크에 기록되기 전에 고장이 발생할 수 있다. 고장이 발생하기 전에 트랜잭션이 완료 명령을 수행했다면 회복 모듈은 이 트랜잭션의 갱신 사항을 재수행(REDO)하여 트랜잭션의 갱신이 지속성을 갖도록 해야 한다. 고장이 발생하기 전에 트랜잭션이 완료 명령을 수행하지 못했다면 원자성을 보장하기 위해서 이 트랜잭션이 데이터베이스에 반영했을 가능성이 있는 갱신 사항을 취소(UNDO)해야 한다. 저장 장치의 유형 주기억 장치와 같은 휘발성 저장 장치에 들어 있는 내용은 시스템이 다운된 후에 모두 사라진다. 디스크와 같은 비휘발성 저장 장치에 들어 있는 내용은 디스크 헤드 등이 손상을 입지 않는 한, 시스템이 다운된 후에도 유지된다. 안전 저장 장치는..

개요 대부분의 DBMS들은 다수 사용자용이기 때문에, 여러 사용자들이 동시에 동일한 테이블을 접근하기도 한다. DBMS의 성능을 높이기 위해서는 여러 사용자의 질의나 프로그램들을 동시에 수행하는 것이 필수적이다. 동시성 제어 기법은 여러 사용자들이 다수의 트랜잭션들을 동시에 수행하는 환경에서 부정확한 결과를 생성할 수 있는, 트랜잭션들 간의 간섭이 생기지 않도록 한다. 종류 직렬 스케줄(Serial schedule) 여러 트랜잭션들의 집합을 한 번에 한 트랜잭션씩 차례대로 수행한다. 비직렬 스케줄(Non-serial schedule) 여러 트랜잭션들을 동시에 수행한다. 직렬 가능(Serializable) 비직렬 스케줄의 결과가 어떤 직렬 스케줄의 수행 결과와 동등할 때를 말한다. 데이터베이스 연산 Inp..

개요 분기 한정법은 백트래킹 기법과 같이 상태 공간 트리를 구축하여 문제를 해결하는 방법이다. 최적 해를 구하는 문제에 주로 사용된다. 원리 마디를 검색할 때마다, 마디가 유망한 지 여부를 결정하기 위해서 한계값(bound)을 계산한다. 한계값이 현재까지의 최적의 해보다 좋지 않으면 유망하지 않은 것이다. 이 마디는 더 이상 검색할 필요가 없다. 위 그림은 최소 등산 코스를 찾는 과정 중 하나이다. 이미 80이라는 최적의 해를 찾은 상태에서 최소 100, 200의 거리를 갖는 등산로 A, B를 조사할 필요는 없다. 즉, A와 B는 유망하지 않다. A와 B 중에서 A가 더 작은 값을 가질 수 있으므로, A 먼저 조사하는 것이 좋다. 위 그림은 반대로 최대 가치의 보물을 찾는 과정이다. 이미 180이라는 최..

개요 N-queens 문제는 N * N 체스판에 N개의 퀸을 서로 공격받지 않게 놓는 방법의 개수를 구하는 문제이다. 예시 n = 4일 때 정답의 개수를 구해보자. 먼저 각 열에는 한 개의 퀸을 놓을 수 있다. 무작정으로 놓을 수 있는 모든 경우에 수를 고려하면 다음과 같다. 총 4 * 4 * 4 * 4 = 256가지의 경우에 대해 놓을 수 있는지 각각 검사해야 한다. 하지만 (2, 1)에 퀸을 놓는 순간 조건을 만족하지 않으므로 이후 자식 노드들은 검사하지 않아도 된다. 따라서 백트래킹을 활용하면 검사해야 하는 가짓 수를 줄일 수 있다. 스도우 코드 상태공간트리 예제 코드(C++) n을 입력받아 n * n 체스판에서 n개의 퀸을 놓을 수 있는 총 방법의 개수를 출력하는 코드 1 2 3 4 5 6 7 8..

개요 0-1 배낭 문제는 n개의 물건에 대해 최대 가치가 되도록 담는 알고리즘이다. 시간복잡도 분석 각각의 물건은 넣는다 / 넣지 않는다의 2개의 경우가 있으므로 단순히 시간 복잡도를 계산하면 O(2^n)이다. Dynamic Programming으로 해결 i > 0이고 w > 0일 때, 전체 무게가 w를 넘지 않도록 i번째까지의 항목 중에서 얻어진 최고 이익을 P[i][W]라고 하면 P[i][W]는 다음과 같이 구할 수 있다. 이 알고리즘의 시간복잡도는 이다. W = 10이고, 품목이 다음과 같을 때의 0-1 배낭 문제 예시 문제점 불필요한 항을 계산한다. (위 그림에서 P[3][8]과 P[3][9]를 구할 필요는 없다.) 위 그림의 경우 총 n(4) * W(10)의 40번의 비교가 필요하다. 아래와 같..

개요 허프만 코드란 최적 이진 코드를 만드는 알고리즘 중 하나이다. Fixed-length binary code 코드의 길이가 고정적이다. ex) a : 00, b : 01, c : 11 등 문제점 : 자주 나타나는 코드의 길이도 고정이므로 낭비가 생긴다. Variable-length binary code 코드의 길이가 가변적이다. ex) a : 10, b: 0, c : 11 등 자주 나타나는 코드의 길이를 줄일 수 있다. 문제점 : 위의 예시에서 d를 00으로 표기하는 방법을 추가하면 00이 d인지, bb인지 구별할 수 없어진다. optimal binary code (최적 이진 코드) 주어진 파일에 있는 문자들을 이진코드로 표현하는데 필요한 비트의 개수가 최소가 되는 코드이다. Prefix code 한..

개요 다익스트라 알고리즘은 가중치가 있는 방향성 그래프에서, 한 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 문제이다. 알고리즘의 단계는 다음과 같다. 1. F는 공집합으로 둔다. 2. Y(최단 경로가 확정된 집합)에는 시작 정점 v1을 포함해 {v1}으로 둔다. 3. 최종해답을 얻을 때까지 다음 과정을 반복한다. (a) 선정 절차 / 적정성 점검 : V-Y에 속한 정점 중에서, v1에서 Y에 속한 정점만을 거쳐서 최단 경로가 되는 v를 선정한다. (b) v를 F에 추가한다. (c) v에서 F로 이어지는 최단경로 상의 이음선을 F에 추가한다. (d) 해답 점검 : Y = V가 되면 T = (V, F)가 최단경로를 나타내는 그래프가 된다. 예시 초기화 : v1에서 v2~v5까지의 최단 거리를..

시스템 카탈로그 개요 데이터베이스의 객체(사용자, 릴레이션, 뷰, 인덱스, 권한 등)와 구조들에 대한 모든 데이터를 포함한다. 메타데이터라고도 한다. 메타데이터는 데이터에 대한 데이터라는 의미이다. 시스템 카탈로그는 사용자 및 질의 최적화 모듈 등 DBMS 자신의 구성요소에 의해서 결정된다. 시스템 카탈로그는 관계 DBMS마다 표준화되어 있지 않아서 관계 DBMS마다 서로 다른 형태로 시스템 카탈로그 기능을 제공한다. 시스템 카탈로그는 데이터 사전(data dictionary) 또는 시스템 테이블이라고도 부른다. 질의 처리에서의 시스템 카탈로그 SELECT 문이 문법적으로 정확한가를 검사한다. SELECT 문에서 참조하는 EMPLOYEE 릴레이션이 데이터베이스에 존재하는가를 검사한다. EMPLOYEE 릴..

뷰의 개요 ANSI/SPARC 3단계 아키텍처에서 외뷰 뷰는 특정 사용자가 보는 데이터베이스 구조를 의미했다. 관계 데이터베이스에서의 뷰는 한 사용자의 전체 외뷰 뷰 대신에 하나의 가상 릴레이션을 의미한다. 뷰는 기존의 기본 릴레이션에 대한 SELECT문의 형태로 정의된다. 사용자는 여러 개의 릴레이션과 뷰를 사용할 수 있다. 뷰는 릴레이션으로부터 데이터를 검색하거나 갱신할 수 있는 동적인 창의 역할을 한다. 스냅샷 스냅샷이란, 어느 시점에 SELECT문의 결과를 기본 릴레이션의 형태로 저장해 놓은 것이다. 스냅샷은 사진을 찍은 것과 같아서 스냅샷을 정의하는 시점의 기본 릴레이션의 내용이 스냅샷에 반영된다. 어떤 시점의 조직체의 현황, 예를 들어 몇년 몇월 시점에 근무하던 사원들의 정보, 재고 정보 등이..