[CS] 📕 데이터 베이스

---

📖 데이터 베이스를 사용하는 이유

데이터 베이스를 사용하기 전에는 파일 시스템을 이용하여 관리하였는데 이 경우에는 데이터 종속성, 중복성, 무결성 문제가 발생한다.

📖특징

1. 데이터의 독립성
   • 물리적 독립성 : 데이터 베이스 사이즈를 늘리거나 줄일 때 관련된 응용 프로그램을 수정할 필요가 없다.
   • 논리적 독립성 : 논리적인 구조를 가지므로 응용 프로그램의 요구를 만족시킬 수 있다.
2. 데이터의 무결성
   • 여러 경로를 통해 잘못된 데이터가 발생하는 경우를 방지하는 기능(데이터의 유효성 검사)
3. 데이터의 보안성
   • 권한이 있는 사용자들만 자원에 접근할 수 있도록 설정
4. 데이터의 일관성
   • 연관된 정보를 논리적인 구조로 관리함(어떤 데이터를 변경했을 때 나머지 데이터와 일치하지 않는 불일치성을 배제함)
5. 데이터 중복 최소화
   • 데이터를 통합 관리함으로써 자료의 중복과 데이터의 중복 문제를 해결할 수 있다.

⚡ 디스크 I/O를 줄일 수록 데이터 베이스의 성능은 좋아진다.

---

---

📖 Index

📚 인덱스란?

• 인덱스는 말 그대로 색인이다. 예를 들어 설명하면 데이터는 책의 내용이고 데이터가 저장된 레코드 주소는 인덱스 목록에 있는 페이지 번호이다.
  데이터 베이스도 마찬가지로 모든 데이터를 검색해서 찾으면 시간이 오래 걸리니까 컬럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 인덱스를 만들어둔다.
• DBMS(데이터 베이스 관리 시스템)은 항상 정렬된 상태를 유지한다. (즉, 탐색하는데는 빠르지만 값을 추가, 삭제, 수정하는 경우에는 느리다.)

📚 인덱스 자료구조

1. B-Tree
   • 일반적으로 사용되는 알고리즘으로 컬럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱한다.
2. Hash
   • 컬럼의 값으로 해시 값을 계산해서 인덱스하는 알고리즘으로 매우 빠른 검색속도를 가지고 있다. 하지만 값을 변형해서 인덱싱하므로 값의 일부만으로 검색 할 때는 hash를 사용할 수 없다.

⚡ B-tree보다 Hash가 효율적일 것 같지만 SELECT 질의의 조건에 부등호(<>)도 포함되므로 hash에서 등호(=) 연산이 아닌 부등호 연산의 경우에 문제가 발생한다.

📚 클러스터

인덱스에서 클러스터는 물리적으로 인접한 장소에 저장되어 있는 데이터들을 묶어서 저장하는 형태이다. 클러스터 인덱스는 프라이머리 키에 의해 레코드 저장 위치가 결정된다. 따라서 키를 신중하게 결정하고 사용해야한다.

📚 성능과 고려해야할 사항

인덱스를 생성하게 되면 INSERT, DELETE, UPDATE 쿼리문을 실행할 때 별도의 과정이 추가된다.
INSERT는 인덱스에 대한 데이터를 추가해야하고 DELETE는 인덱스에 존재하는 값은 삭제하지 않고 사용하지 않는다는 표시로 남게 된다. 따라서 row의 수는 그대로이므로 실제 데이터에 비해 허수 데이터가 많이 존재할 수 있다.

---

---

📖 정규화

📚 정규화란?

• 관계형 데이터 베이스에서 중복을 최소화하기 위해 데이터를 구조화하는 작업이다. 구체적으로 말하면 어떠한 함수적 종속성을 만족하는지에 따라 정규형이 정의되고 그 정규형을 만족하지 못하는 릴레이션을 나누어서 만족하는 릴레이션으로 분해하는 작업이다.
• 함수적 종속성 : 속성들 간의 상호 관계로부터 유도되는 제약조건의 일종(X의 값이 Y의 값을 유일하게 결정하면 X는 Y를 함수적으로 결정한다.)
• 정규형의 조건
  • 분해의 대상인 분해 집합은 무손실 조인을 보장해야 한다.
  • 분해 집합은 함수적 종속성을 보존해야 한다.

📚 정규화의 종류

• 제 1 정규형
  • 속성의 도메인이 오직 원자 값(하나의 값)만을 포함하고, 튜플의 모든 속성이 도메인에 속하는 하나의 값을 가진다.
• 제 2 정규형
  • 제 1 정규형에 속하면서 모든 비주요 속성들이 주요 속성에 대해서 완전 함수적 종속이면 만족한다.(완전 함수적 종속 : x -> y 라고 할 때, x의 어떠한 속성이라도 제거하면 더 이상 함수적 종속성을 만족하지 않는 경우. 즉, 키가 아닌 열들이 각각 후보키에 대해 결정되는 릴레이션 형태)
• 제 3 정규형
  • 제 2 정규형에 속하면서 어떠한 비주요 속성도 기본키에 대해서 이행적으로 종속되지 않으면 만족한다.(이행 함수적 종속 : x -> y , y -> z 의 경우에 x -> z를 추론할 수 있는 관계. 즉, 비주요 속성이 비주요 속성에 의해 종속되는 경우가 없는 릴레이션 형태)
• BCNF 정규형
  • 제 3 정규형에 속하면서 3 정규형을 보완하는 정규형으로, 후보키가 여러 개인 경우 제 3 정규형을 만족시키지만 이상 현상이 발생하는 경우가 있다.
    모든 결정자(주요속성??)가 후보키 집합에 속하면 만족한다.

📚 정규화의 장점

• 데이터 베이스 변경 시 발생하는 이상 현상들을 해결할 수 있다.
  • 이상 현상
    1. 삽입 이상 : 원하지 않는 자료가 삽입, 삽입하는데 자료가 부족해 삽입x
    2. 삭제 이상 : 하나의 자료만 삭제했을 때 그 자료가 포함된 튜플 전체가 삭제됨(원하지 않는 정보 손실)
    3. 갱신 이상 : 정확하지 않거나 일부의 튜플만 갱신되어 정보가 일관성이 없어짐
• 연동된 응용 프로그램에 최소한의 영향만 미치게 만들어 응용 프로그램의 수명을 연장시킨다.

📚 단점

• 릴레이션 간의 연산(JOIN 연산)이 많아진다. 이로 인해서 응답 시간이 느려질 수 있다.(빨라질 수도, 느려질 수도 있음)

  ⚡ 대응책 : 반정규화

  • 정규화된 속성, 관계를 시스템의 성능 향상 및 개발과 단순화를 위해 통합, 분리하는 기법이다.
  • 성능이 저하될 것이 예상되는 경우 반정규화를 수행한다.(but, 과도하게 사용하면 데이터의 무결성이 깨질 수 있다. 또한 응답 시간이 늦어진다.)

---

---

📖 트랜잭션

📚 트랜잭션이란?

작업의 완전성을 보장해주는 것으로 논리적인 작업 셋을 모두 완벽하게 처리하거나 또는 처리하지 못할 경우에는 원 상태로 복구해서 작업의 일부만 적용되는 현상이 발생하지 않게 만들어주는 기능이다.

⚡ 사용자의 입장에서는 작업의 논리적 단위로 이해할 수 있고 시스템의 입장에서는 데이터들을 접근 또는 변경하는 프로그램의 단위가 된다.

📚 트랜잭션과 Lock

이 둘은 서로 비슷한 개념 같지만 사실 잠금은 동시성을 제어하기 위한 기능이고 트랜잭션은 데이터의 정합성을 보장하기 위한 기능이다.

• Lock : 여러 커넥션에서 동시에 동일한 자원을 요청할 경우 순서대로 한 시점에는 하나의 커넥션만 변경할 수 있게 해주는 역할
• 트랜잭션 : 논리적인 작업 셋 자체가 100% 적용되거나 아무것도 적용되지 않아야 함을 보장하는 것

📍 트랜잭션의 특성

트랜잭션은 ACID라는 4가지 특성을 만족해야 한다.

1. 원자성(Atomicity) : 트랜잭션 중간에 어떠한 문제가 발생한다면 트랜잭션에 해당하는 어떠한 작업 내용도 수행되어서는 안되며 아무런 문제가 발생되지 않았을 경우에만 모든 작업이 수행되어야 한다.

2. 일관성(Consistenct) : 트랜잭션이 완료된 다음의 상태에서도 트랜잭션이 일어나기 전의 상황과 동일하게 데이터의 일관성을 보장해야 한다.

3. 고립성(Isolation) : 각각의 트랜잭션은 서로 간섭없이 독립적으로 수행되어야 한다.

4. 지속성(Durability) : 트랜잭션이 정상적으로 종료된 다음에는 영구적으로 데이터 베이스에 작업의 결과가 저장되어야 한다.

📍 트랜잭션의 상태

• Active
  • 트랜잭션의 활동 상태
  • 트래잭션이 실행중이며 동작중인 상태를 말한다.
• Failed
  • 트랜잭션 실패 상태
  • 트랜잭션이 더 이상 정상적으로 진행 할 수 없는 상태를 말한다.
• Partially Committed
  • 트랜잭션의 Commit 명령이 도착한 상태
  • 트랜잭션이 commit 이전 sql문이 수행되고 commit만 남은 상태를 말한다.
• Committed
  • 트랜잭션 완료 상태
  • 트랜잭션이 정상적으로 완료된 상태를 말한다.
• Aborted
  • 트랙잭션 취소 상태
  • 트랜잭션이 취소되고 트랜잭션 실행 이전 데이터로 돌아간 상태를 말한다.

⚡ Partially Committed와 Committed의 차이점
Commit 요청이 들어오면 상태는 Partial Committed상태가 된다. 이후 Commit을 문제없이 수행할 수 있으면 Committed상태로 전이되고, 만약 오류가 발생하면 Failed상태가 된다.
즉, Partial Committed는 Commit요청이 들어왔을 때를 뜻하고
Committed는 Commit을 정상적으로 완료한 상태를 뜻한다.

💊 트랜잭션을 사용할 때 주의할 점
꼭 필요한 최소의 코드에만 적용하는 것이 좋다.(트랜잭션의 범위를 최소화)
그 이유는 데이터 베이스 커넥션은 개수가 제한적이다. 그런데 각 단위 프로그램이 커넥션을 소유하는 시간이 길어진다면 사용 가능한 여유 커넥션의 개수는 줄어들게 된다. 그렇게 되면 각 프로그램에서 커넥션을 가져가기 위해 기다려야 하는 상황이 발생할 수도 있다.

---

---

📖 교착상태

📚 교착상태란(deadlock)?

두 개 이상의 트랜잭션이 특정 자원의 잠금(Lock)을 획득한 채 다른 트랜잭션이 소유하고 있는 잠금을 요구하면 아무리 기다려도 상황이 바뀌지 않는 상태가 되는데 이를 뜻한다.
갱신연산(Insert, Update, Delete)를 실행하면 잠금을 획득한다.

⚡ 예시

트랜잭션 1이 테이블 B의 첫 번째 행의 잠금을 얻고 트랜잭션 2도 테이블 A의 첫 번째 행의 잠금을 얻었다고 하자.
트랜잭션을 commit하지 않은 채 서로의 첫 번째 행에 대한 잠금을 요청하면 Deadlock이 발생한다.

📍 교착상태의 빈도를 낮추는 방법

• 트랜잭션을 자주 커밋한다.
• 정해진 순서대로 테이블에 접근한다.
• 읽기 잠금 획득(SELECT ~ FOR UPDATE)의 사용을 피한다.
• 테이블 단위의 잠금을 획득해 갱신을 직렬화 하면 동시성은 떨어지지만 교착상태를 피할 수 있다.

📍 교착상태 방지 프로토콜

• 타임아웃 기반 알고리즘
  • 트랜잭션 Ti 실행 시, 타임아웃 기간(timeout interval)을 설정
  • Ti사 lock 획득을 위해 대기할 경우, 타임아웃 기간 동안만 대기
  • 타임아웃 기간이 지나면 Ti를 철회하고 롤백
  • 장점
    • 알고리즘이 간단하다.
    • 일정 시간 후 교착상태를 일으키는 트랜잭션이 무조건 취소되므로 교착상태가 해결된다.
  • 단점
    • 최적의 타임아웃 기간을 설정하는 것이 어렵다.
    • 기아 현상이 자주 발생한다.
      ⚡ 기아(starvation) : 동일한 트랜잭션이 계속 롤백되는 현상
• 타임스탬프(TimeStamp) TS를 이용하는 방법
  • 먼저 시작한 트랜잭션이 어떤 것인지에 따라 대기하거나 롤백시킨다.
  • 기아를 방지하기 위해서 재시작되는 트랜잭션의 시작 타임스탬프는 오리지널 타임스탬프를 사용
    • Ti의 오리지널 시작 타임스탬프를 TS(Ti)라고 할 때, Ti가 재시작되면 시작 타임스탬프를 TS(Ti)로 부여하는 방식
• Wait-Die 방식
  • 다른 트랜잭션이 데이터를 점유하고 있을 때 기다리거나(Wait) 포기(Die)하는 방식이다.
  • 트랜잭션 Ti가 Tj에 의해 로킹된 데이터를 요청할 때
    • Ti가 먼저 들어온 트랜잭션이라면 대기(Wait)
    • Ti가 나중에 들어온 트랜잭션이라면 포기(Die)하고, 나중에 재시작하여 다시 요청
      • 재시작 될 때, Ti의 시작 타임스탬프는 오리지널 시작 타임스탬프 값인 TS(Ti)로 부여한다.
• Wound-Wait 방식
  • 다른 트랜잭션이 데이터를 점유하고 있을 때, 빼앗거나(Wound) 기다리는(Wait) 방식이다.
  • 트랜잭션 Ti가 Tj에 의해 로킹된 데이터를 요청할 때
    • Ti가 먼저 들어온 트랜잭션이라면 데이터를 선점(Wound)
    • Tj는 철회시키고, 나중에 재시작
      • 재시작 될 때, Ti의 시작 타임스탬프는 오리지널 시작 타임스탬프 값인 TS(Ti)로 부여한다.
    • Ti가 나중에 들어온 트랜잭션이라면 대기(Wait)

⚡ Wound-Wait 방식이 Wait-Die 방식에 비해 일반적으로 roll-back 횟수가 적다.

📍 교착상태 탐지 프로토콜

• 대기 그래프를 작성하여 교착 발생 여부를 확인한다.
• 그래프를 그렸을 때, 순환구조(cycle)이 생성되면 교착상태가 발생하는 것
  ⚡ 해결방안
  • 희생할 트랜잭션 선정(victim) : 진행률, 시작시간, 연산량 등을 고려하여 최소비용 트랜잭션을 선정한다.
  • 희생할 트랜잭션을 완전하게 롤백 : 이 때, 기아가 발생할 수 있다.
  • 기아 발생을 줄이기 위해, 롤백 횟수를 기록하여 희생 트랜잭션 선정시 비용 계산에 포함시킨다.

---

참고자료 : Tech Interview