DB 면접대비 질문

Transaction

transaciton의 정의, 특성(ACID)

commit / rollback

state

transaction : DBMS의 상호작용 단위. transaction은 다음 4가지 성질을 가지고 있다.

• Atomicity : transction은 실행되거나, 실행되지 않거나 둘 중 하나의 상태만 가진다. 중간에 끊기지 않는다.
• Consistency : transaction의 실행 결과는 항상 일관성이 있다. (정해둔 규칙을 위배하지 않는다.)
• Isolation : transaction 사이에 다른 trasnaction이 낄 수 없다.
• Durability : DBMS가 꺼져도 수행된 transaction은 반영되어 있어야 한다.

 

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

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

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

 

active : transaction이 실행 중인 상태

failed : transaction에 오류가 발생해 중단된 상태

partially commited : 사용자의 commit 요청이 왔을 때 도착하는 상태. 아직 반영된 상태가 아니다.

commit 되면 commited로 가고, 그렇지 않으면 failed로 간다.

commited : transaction이 성공적으로 종료된 상태

aborted : rollback을 수행하고 있는 상태

 

Index

종류 2가지

B tree와 B+ tree의 차이

B+ tree의 특징 3가지, 시간복잡도

hash table과의 차이점, 각각

index를 사용할 때 장단점

clustered vs non-clustered

어떤 column을 쓰면 좋은지

종류는 hash table과 B+ tree가 있다.

 

B tree는 tree의 모든 element에 entry가 저장됨

B+ tree는 leaf node는 data page에 대한 pointer를 가지고, non leaf node는 key와 node에 대한 pointer만 가짐, leaf node들끼리 pointer를 가짐. leaf node는 data의 pointer를 가짐.

 

B+ tree의 특징

• m-way balanced tree (각 node에는 최대 m-1개의 element가 들어있고 각 node는 최대 m개의 child를 가질 수 있다)
  • balanced tree인 만큼, child의 height 차이가 1 이상 나지 않는다.
• 모든 leaf node는 doubly linked list
• space utilization이 50% 이상이어야 한다. 
  • leaf node는 $\left \lfloor \frac{n+1}{2} \right \rfloor$개의 pointer가 있어야 하고,
  • non-leaf node는 $\left \lceil \frac{n+1}{2} \right \rceil$개의 pointer가 있어야 한다.

 

hash table은 접근, 수정, 삭제가 O(1)이지만 범위가 있는 접근을 못한다. hash 함수를 사용하기 때문에 pointer가 랜덤이기 때문. 반면 B+ tree는 접근/수정/삭제가 O(logn)이지만 tree이기 때문에 range하게 접근할 수 있다.

 

• 장점 : index에 있는 정보에 대해서는 read 속도가 빨라진다.
• 단점 : insert/delete/update 속도가 느려진다. 해당 tree를 수정해야 하기 때문.
• 자주 select되고, 덜 update되는 column에 대해 쓰는 것이 좋다. + FK나 join도.
• 공통적으로 사용하는 것 - index column의 순서는 cardinality가 높은 것부터 낮은 순으로 나열하는 것이 좋다. (data의 unique 개수) 
  • cardinality가 높은 것, selectivity가 낮은 것(적은 row가 찾아짐), 조회 많은 것, 수정 적은 것

 

 clustered index는 B+ tree의 data page가 index 순서대로 정렬된 index이고, non-clustered index는 그렇지 않음.

 

Schema

schema의 정의 : DB의 구조와 제약에 대한 명세

schema의 3가지 종류

independence 2가지 종류

 schema는 data의 특정 collection의 설명을 말한다. data의 관계, 구조, 표현 방법을 표시하는 구조이다.

• external schema (view) : 각 user가 접근하는 table
• conceptual schema (logical) : 어떤 종류의 data가 저장되는지
• physical schema (physical) : data가 어떻게 저장되는지

 

independence

• physical data independence : physical structure를 바꾸어도 logical schema는 불변하는 특징
• logical data independence : logcial structure를 바꾸어도 external schema는 불변하는 특징

 

Join

join의 종류 3가지

• theta join (conditional join) R⋈$_c$S : 조건 c를 만족하는 tuple만 가져온다.
• equi join : theta join에서 조건 c가 equal로만 이뤄져 있는 theta join
• natrual join R⋈S : 모든 공통 field에 대한 equi join

 

각 연산의 I/O cost

buffer pool?

seq scan, index scan

external sort

nested loop join, blocked nested join, sort merge join, grace hash join

 

 DBMS는 disk에 있는 page를 memory에 frame으로 저장하는데, 이 공간을 buffer pool이라 한다. OS의 paging과 매우 유사하지만 조금은 다르다. (DB는 prefetch 예측하기 때문)

 

• seq scan : $|R|_p$이다.
• index scan
  • clustered : $\left \lceil \frac{card(P)}{B} \right \rceil + 1$
  • non clustered : card(P)
• external sort : $2|R|_p \times (\left \lceil log_{B-1}\left \lceil \frac{|R|_p}{B} \right \rceil \right \rceil +  1)$
• nested loop join : $|R|_p + |R|_p \times |S|_p$
• blocked nested join : $|R|_p + \left \lceil \frac{|R|_p}{B-2} \right \rceil \times |S|_p$
• sort merge join : $|R|_p + |S|_p$
• grace hash join : $3|R|_p + 3|S|_p$

 

Query Optimizer

작동 방식

1. query를 logical operator들의 tree로 표현하고, logical equivalent rule을 적용해 tree를 바꾼다.
2. 앞서 살펴본 physical operator를 적용해 physical plan으로 바꾼다.
3. query optimizer는 plan의 실행 시간을 유추해서 best plan을 도출한다.

 

Key

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을 알아서 처리해 준다.

 

Normalization

normalization이란

anomaly

각 단계가 만족하는 조건

장단점

functional dependency가 뭔지

사용하는 목적은 redundancy를 줄여 anomaly를 막기 위함이다. 단점으로는 relation이 쪼개져 join 연산이 많아진다는 것이 있다.

 

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

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

 

• 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 : 조인 종속 제거

 

 어떤 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를 알 수 있는 관계를 말한다.

 

Integrity Constraint

정의 : 정확성, 일관성, 유효성이 유지되는 것

 

Anomaly

정의

3가지 anomaly

 

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

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

 

CAP Theroem / 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이다.

 

RDB vs NoSQL

각각의 장단점과 차이

 

Redis

특징 몇가지만 준비

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

 

빠르지만 날아갈 수 있어서 사용 시 백업에 대한 준비를 해야 한다.

빠르기 때문에 자주 조회/수정되는 leaderboard, session 등을 저장하기 좋다.

 

2 Phase Locking

사용 목적

lock의 종류 2가지

phase 종류 2가지

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

 

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

 

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

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

 

SQL 종류

3가지 - DML, DDL, DCL

 

Delete vs Truncate vs Drop

delete는 rollback 가능, data 삭제하는 명령어

truncate는 table을 제외한 전체 data를 삭제하는 명령어, rollback 불가능

drop은 table을 삭제하는 명령어, rollback 불가능

 

Prepared Statement

원리

 

RDB vs NoSQL

RDB는 정해진 schema에 따라 data를 저장하고, relation을 사용해 data를 분산시킨다. 때문에 redundancy를 줄일 수 있고, anomaly를 막을 수 있다. - 즉, consistent하다.

NoSQL은 정해진 구조가 없다.

 

RDB의 경우 consistent하지만 수정하기 어렵고, join이 많아질 경우 cost가 매우 커진다. 또한 확장도 어렵다.

NoSQL의 경우 유연하고, 확장이 쉽다. 반면 redundancy를 계속 확인해야 한다.

 

ORM

object와 relation을 매핑하는 것. 코드 레벨에서 DB에 접근하기 때문에 유지보수하기 좋다.

 

SQL 실행 순서

FROM, ON, JOIN

WHERE, GROUP BY, HAVING

SELECT

DISTINT

ORDER BY

LIMIT

 

Recovery

ARIES recovery의 가정 2가지

force ? no force ? steal ? no steal ?

write ahead logging의 방식 2가지

aries recovery algorithm의 동작 3가지

transaction의 state 5가지

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

 

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

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

 

WAL

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

 

recovery algorithm

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

 

transaction state

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

 

 

Transaction Isloation Level

4가지 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개 실행되면 이런 현상이 생긴다.
• Level 3 (Repeatable Read) : 하나의 transaction에서 조회한 record가 같음을 보장한다. 하나의 transaction이 읽은 record를 다른 transaction이 변경하지 못하게 한다.
  • 같은 transaction을 2번 실행했을 때 결과가 다른 phantom read가 발생할 수 있다. (select - insert - select의 경우)
• Level 4 (Serializable) : 한 transaction이 사용하는 record를 다른 transaction에서 접근할 수 없다.

 

 

Clustering vs Replication

정의, 장단점

clustering : 같은 저장소를 사용하되 여러 개의 DBMS를 사용하는 것. 동기 방식을 사용하기 때문에 일관성 있고, DB서버에 대한 부하 분산 가능. 그러나 저장소가 같기 때문에 lock으로 인한 병목 발생 가능.

replication : 저장소를 비동기 방식으로 사용하는 것. 일반적으로 DB는 select가 많기 때문에 insert할 수 있는 master와, master의 정보를 비동기로 저장하는 read replica를 두는 방식.