DB

[Database System] Recovery Algorithm

Crash Recovery Recovery Algorithm은 데이터베이스의 consistency, transaction atomicity, 그리고 durability를 failure 발생 시에도 보장하기 위한 방법이다. Recovery Algorithm은 크게 두 파트로 나뉘어진다. 1. 정상 트랜잭션 처리 중에 실패로부터 복구하기 위한 조치 2. 실패가 발생한 후 데이터베이스를 consistency, transaction atomicity, 그리고 deurability를 보장하는 상태로 복구하는 조치 ARIES Algorithm for Recovery and Isoliaton Exploiting Semantics의 준말로, IBM Research에서 개발된 알고리즘이다. ARIES algorithm의..

[Database System] Database Logging

Failure Classification DBMS에서 발생할 수 있는 failure의 타입은 다음과 같다. Type1: Transaction Failure Type2: System Failure Type3: Storage Media Failures Transaction Failures 트랜잭션 실패에는 크게 두 가지 유형이 존재한다. 1. Logical Erros 논리적 에러는 트랜잭션이 내부 오류 조건(무결성 제약 조건 위반)으로 인해 완료되지 않는 상황을 의미한다. 2. Internal State Erros 내부 상태 에러는 DBMS가 active transaction을 종료해야 하는 오류 조건(ex. Deadlock)으로 인해 발생하는 상황을 말한다. 예시로 들었던 Deadlock이 발생하면, DB..

[Database System] Join Algorithm

Join Algorithms 우리는 Relational Database에서 데이터의 중복을 방지하기 위해 정규화를 수행한다. 이후, 다시 original tuple을 복구하기 위해 사용하는 것이 join operator이다 이번 파트에서는 inner equijoin algorithm을 중심적으로 살펴볼 것이며, 사실 대부분의 다른 join 알고리즘은 이 binary inner equijoin algorithm에서 파생된 것이다. 일반적으로 우리는 join을 수행할 때 더 작은 테이블을 left table(outer table)로 설정한다. Optimizer는 실제 join plan을 세우고 수행하는 과정에서 이를 자동적으로 수행한다. Query Plan 쿼리가 입력되면, operators들은 tree 형..

[Database System] B+ Tree Index

Summay Of Last Class Hash Table은 모든 DBMS에서 이용되는 중요한 data structure로, O(n)의 공간 복잡도와 O(1)의 시간 복잡도를 가진다. B+ Tree B+Tree란 self-balancing을 진행하는 정렬된 tree data로, search, sequential access, insertions, 그리고 deletions를 모두 O(logn) 에 처리한다. 이는 좀 더 일반화된 binary search tree라고 할 수 있는데, node가 둘 이상의 children을 가질 수 있기 때문이다. B+ Tree는 large blocks of data를 대상으로 한 read-wrtie에 최적화 되어있다. B+ Tree Properties B+ Tree는 다음의 ..

[Database System] Hash Table

Design Decision Database System을 설계할 때 크게 고려해야 할 점은 `Data Organizaiton`와 `Concurrency`이다. Data Organizaiton 효율적인 접근을 위해 memory/page에 어떻게 data structure를 배치할 것인지, 그리고 어떤 정보를 저장할 것인지에 대한 문제이다. Concurrency 어던 방식으로 multiple thread가 data structure에 문제를 발생시키지 않으면서 동시에 접근하게 할 수 있는지를 고려하는 문제이다. Hash Table Hash Table은 key와 value를 mapping하는 unordered associative array를 implements한다. `Hash function`을 사용해서 ..

[Database System] Database Storage2

본 포스팅은 CMU의 2022 fall database system 강의 노트를 바탕으로 작성되었습니다. What are some potential problems with the slotted page design? 앞서 살펴봤던 Slotted Paged의 경우 다음과 같은 문제점이 존재할 수 있다. 1. Fragmentation Page는 데이터 로드의 최소 단위이므로, unusable space나 empty slots가 존재하게 될 수 있다. 2. Useless DIsk I/O DBMS는 단 하나의 tuple을 Update 하기 위해 전체 page를 fetch 해야한다. 3. Random Disk I/O multiple tuple을 업데이트 하는 상황에서, 각 tuple이 모두 다른 page에 존재..

[Database System] Database Storage

본 포스팅은 CMU의 2022 fall database system 강의 노트를 바탕으로 작성되었습니다. Disk-Based Architecture DBMS은 database의 primary storage가 non-volatile disk, 즉 비휘발성 디스크에 존재한다고 가정한다. 그리고 DBMS는 이러한 비휘발성 저장공간과 휘발성 저장공간 사이에서 데이터의 움직임을 제어하는 역할을 한다. Storage Hierarchy 위 그림은 저장 장치 간의 hierarchy를 표현한 것으로, 위에 존재하는 저장 장치일수록 접근 속도가 빠르지만 가격이 비싸며 아래에 존재할 수록 접근 속도가 느리지만 가격이 싸다는 특징이 있다. 경제적인 측면, 그리고 데이터의 휘발성 측면에서 필연적으로 위와 같이 계층적으로 저장장..

[Database System] Normalization

Normalization Normalization, 즉 정규화란 관계형 데이터베이스에서 데이터의 중복을 최소화하고 데이터의 무결성과 일관성을 유지하기 위한 데이터 설계 프로세스이다. 즉 중복되는 데이터의 양을 줄여 데이터 저장공간을 절약하기 위한 메커니즘이라고 생각하면 된다. 이러한 Normalizaiton은 여러가지 단계를 가지는데, 일반적으로 1, 2, 3 정규화가 존재한다. 제 1정규화 테이블에서 칼럼에 atomic value(하나의 값)만이 존재하도록 테이블을 분리하는 것을 말한다. 1. 특정 레코드에 속한 모든 도메인이 atomic value 만으로 되어 있어야 하며 2. 모든 속성에 반복되는 그룹이 나타나지 않아야 하며 3. 기본키를 사용해서 관련 데이터의 각 집합을 고유하게 식별할 수 있어야..