DB 기초 - 2

이 글은 포스텍 한욱신 교수님의 데이터베이스시스템(CSED421) 강의를 기반으로 재구성한 것입니다.

 

Key

 다음 4종류가 있다.

• Candidate Key : tuple을 unique하게 식별할 수 있는 attribute set.
  • + minimality : attribute 1개를 지우면 식별할 수 없다.
• Super Key : key의 super set
• Primary Key : candidate key 중 지정된 것.
• Foreign Key : 다른 relation을 참조하기 위해 다른 relation의 key를 가져온 것. dangling을 알아서 처리해 준다.

 

 

 

Normal Form / Normalization

 [1NF - 2NF - 3NF - BCNF - 4NF - 5NF] 순서로 더 higher하다. 사용하는 목적은 redundancy를 줄여 anomaly를 막기 위함이다. 단점으로는 relation이 쪼개져 join 연산이 많아진다는 것이 있다.

• 1NF : 모든 도메인이 atomic value일 때
• 2NF : 모든 non-key attribute가 candidate key에 fully dependent한 경우.
  • (부분적 함수 종속 제거, partial functional dependency 삭제)
  • candidate key의 일부분으로 식별할 수 없는 것.
• 3NF : 모든 functional dependency X => Y에 대해 X가 superkey이거나 Y가 prime attribute인 경우.
  • (이행적 함수 종속 제거, transivity functional dependency 삭제)
  • X => Y, Y => Z로 식별할 수 있는 정보가 없는 것.
• BCNF : 모든 functional dependency X => Y에 대해 X가 candidate key인 경우.
  • (모든 결정자 X가 후보키인 것)
• 4NF : 다치 종속 제거
• 5NF : 조인 종속 제거

 

 

Functional Dependency

 어떤 relation의 모든 tuple t$_1$, t$_2$과 어떤 field X, Y에 대해 if t$_1$[X] = t$_2$[X] then t$_1$[Y] = t$_2$[Y]인 X, Y의 관계를 functional dependency라고 한다. 말로 풀어쓰면 relation의 field X로 Y를 식별할 수 있는 관계. 더 풀어 쓰면 X를 알면 Y를 알 수 있는 관계를 말한다.

이를 사용해 redundancy를 formal한 방식으로 알아낼 수 있는데, functional dependency X => Y가 있는 경우, X가 중복되면 Y도 중복됨을 알 수 있기 때문이다.

 한편, key는 모든 attribute를 functionally determine한다.

 

 

 

Anomaly

 anomaly는 redundancy 때문에 발생하며, 다음 3가지가 있다.

• insertion anomaly : insert 시 없는 정보가 있어 삽입하지 못하는 경우. 또는 null 정보를 넣어야 한다.
• deletion anomaly : 삭제 시 원하지 않는 정보가 삭제되는 경우
• update anomaly : 중복된 여러 값들 중 하나만 수정되는 경우

 

 

 

Prepared Statement

 일반적인 SQL의 경우 parse 과정을 거치는데, prepared statement는 해당 SQL의 문법을 검사한 후 DB에 caching한다. 때문에 성능이 향상되고, SQL이 이미 caching된 상태이므로 parameter에 들어가는 값을 SQL로 인식하지 않고 parameter로 인식하므로  injection을 막을 수 있다.

 

 

 

CAP Theorem / PACELC Theorem

 Consistency, Availability, Partition Tolerance 3가지를 만족할 수 없다는 정리. 증명되었다.

• consistency : 모든 request가 최신 데이터를 받는다.
• availability : 모든 request는 정상적인 response를 받는다.
• partition tolerance : 네트워크 오류 상황이어도 정상 작동한다.

 

 PACELC theorem은 normal state, abnormal state를 구분해 설명하는 방식이다.

• partition이 존재하는 경우 (abnormal)
  • availability과 consistency는 tradeoff이다.
• partition이 존재하지 않는 경우 (normal)
  • latency와 consistency는 tradeoff이다.

 

 

 

Redis

• append only file : query를 저장하고, crash 시점부터 다시 만들어 두는 방식
• snapshot : 특정 지점을 디스크에 백업
• key-value로 이루어졌다.

 

 

 

2 Phase Locking

 transaction에 lock을 걸어서 serialization을 보장하는 concurreny 처리 방법. lcok은 resource에 대한 mutual exclusion을 위해 사용한다. lock 종류는 다음과 같다.

• Shared Lock : 해당 resource에 대해 read 연산만 가능한 lock. 따라서 한 resource에 여러 개의 shared lock이 걸릴 수 있다.
• Exclusive Lock : 해당 resource에 대해 read 연산과 write 연산 둘 다 가능한 lock. 따라서 한 resource에 하나의 exclusive lock만 걸릴 수 있다.

 

2 phase locking

 lock만으로는 deadlock이 발생할 수도 있기 때문에 strict 2 phase lock을 사용한다. locking phase와 unlocking phase 2단계로 나뉜다. 

• locking phase : lock 연산만 수행할 수 있는 단계
• unlocking phase : unlock 연산만 수행할 수 있는 단계. unlock은 transaction이 완전히 끝난 후에 실행한다.

 

 

 

Isolation Level

 non consistent data를 허용하는 수준.

• Level 1 (Read Uncommited) : 아직 commit되지 않은 record나, transaction이 처리중인 record을 다른 transaction에서 접근할 수 있음. 이 경우 consistent하지 않다.
  • commit되지 않은 data를 보는 dirty read가 발생할 수 있다.
• Level 2 (Read Commited) : commit된 transaction의 결과만 조회할 수 있다.
  • 하나의 transaction에 같은 query가 2개 이상 있을 때, 다른 결과가 나오는 non repeatable read가 발생할 수 있다. query 실행 시점 사이에 다른 transaction이 2개 실행되면 이런 현상이 생긴다. (insert - update - insert의 경우)
• Level 3 (Repeatable Read) : 하나의 transaction에서 조회한 record가 같음을 보장한다. 하나의 transaction이 읽은 record를 다른 transaction이 변경하지 못하게 한다.
  • MVCC를 사용해 transaction에서 사용하는 record들의 version을 관리한다. 때문에 select transaction 실행 중 다른 transaction이 update를 하더라도 MVCC가 저장하고 있는 record를 넘겨주며, 이 때문에 읽는 값은 같다.
  • 그러나 MVCC는 update는 versioning을 하지 않기 때문에, 같은 transaction을 2번 실행했을 때 결과가 다른 phantom read가 발생할 수 있다. (select - insert - select의 경우)
• Level 4 (Serializable) : 한 transaction이 사용하는 record를 다른 transaction에서 접근할 수 없다.

 

 

 

ARIES Recovery

 ARIES recovery의 가정 : strict 2 phase locking, WAL (write ahead logging)

• DB에 접근하기 전 lock, transaction 끝난 후 unlock하는 것을 말한다.

 

 

Force / Steal

• Force: transaction commit 후 바로 disk에 쓰는 방식
• No Force : transaction commit 후 바로 disk에 쓰지 않는 방식
• Steal: transaction 완료 여부에 상관없이 data를 disk에 기록하는 방식
• No Steal: transaction uncommit 상태에서 data를 disk에 기록하지 않는 방식

 

ARIES recovery의 경우 Force + No Steal 방식으로, 어렵지만 빠르다.

 

 

Commit, Rollback

 commit은 모든 작업이 정상적으로 수행되었다는 명령이며, 실 DB에 반영하게 된다.

 rollback은 crash가 난 경우, 해당 transaction의 변경을 취소하는 과정이다. 직전 commit까지만 복구한다.

 이를 통해 consistency를 보장할 수 있다.

 

 

WAL

• disk에 update하기 전에 log를 작성한다. undo를 위해 사용하며, disk에 update한 후 crash가 나면 undo할 수 없기 때문이다.
• transaciton이 commit되기 전에 모든 작업 내용을 log에 기록해야 한다. redo를 위해 사용하며, 해당 transaction이  commit되었음을 보장한다.

 

 

ARIES recovery algorithm

 strict 2 phase lock을 사용하고 있기 때문에 data에 대한 접근은 걱정하지 않아도 된다.

• analysis : REDO 시작위치 결정 (checkpoint : transaction이 모두 disk에 쓰인 시점), crash 위치 결정
• redo : analysis에서 결정한 위치부터 crash 직전까지 redo 수행.
• undo : log를 역순으로 읽으면서 uncommit transaction까지 undo. (최근 commit까지)

 

 

Transaction State

 크게 5가지 종류가 있다.

• active : transaction이 실행 중인 상태
• failed : transaction에 오류가 발생해 중단된 상태
• partially commited : 사용자의 commit 요청이 왔을 때 도착하는 상태. 아직 반영된 상태가 아니다. commit 되면 commited로 가고, 그렇지 않으면 failed로 간다.
• commited : transaction이 성공적으로 종료된 상태
• aborted : rollback을 수행하고 있는 상태

 

 

 

 

잘못된 내용이나 오탈자에 대한 지적, 질문 등은 언제나 환영합니다.