[CS] 데이터베이스 정규화와 Heap

1. 데이터베이스 정규화

1. 정규화란?

데이터의 중복을 최소화하고, 데이터의 삽입, 수정, 삭제 과정에서 발생할 수 있는 이상 현상을 방지하기 위해 테이블을 구조적으로 분해하는 과정.

 

하나의 테이블에 여러 종류의 정보가 함께 저장되면 동일한 데이터가 여러 행에 반복될 수 있다.

예를 들어 다음과 같은 테이블이 있다고 해보자.

주문 ID	회원 ID	회원 이름	상품 ID	상품명
1	10	은콩	100	키보드
2	10	은콩	200	마우스
3	20	티모	100	키보드

 

회원 이름이나 상품명이 여러 행에서 반복된다.

 

이러한 중복은 다음과 같은 이상 현상을 발생시킬 수 있다.

• 삽입 이상(Insertion Anomaly) : 불필요한 데이터가 없으면 원하는 데이터를 추가할 수 없는 문제
• 갱신 이상(Update Anomaly) : 중복된 데이터 중 일부만 수정되어 데이터가 서로 불일치하는 문제
• 삭제 이상(Deletion Anomaly) : 특정 데이터를 삭제했는데 필요한 다른 정보까지 함께 사라지는 문제

정규화는 이러한 문제를 줄이기 위해 데이터의 종속 관계를 분석하고 테이블을 분리한다.

2. 제 1 정규형

원자성 보장
제 1정규형은 각 속성의 값이 더 이상 나눌 필요가 없는 하나의 값, 즉 원작밧을 가지도록 하는 것.

 

예를 들어 다음 테이블은 제 1정규형을 만족하지 않는다.

회원 ID	이름	전화번호
1	은콩	010-1111, 010-2222

 

하나의 전화번호 속성에 여러 개의 값이 들어가 있기 때문이다.

이를 다음과 같이 하나의 속성에 하나의 값만 저장하도록 변경할 수 있다

회원 ID	이름	전화번호
1	은콩	010-1111
1	은콩	010-2222

1NF = 하나의 속성에는 하나의 원자값만 저장한다.

 

3. 제 2 정규형

부분 함수 종속 제거
제 2정규형은 제 1정규형을 만족하면서 기본키의 일부에만 종속되는 속성, 즉 부분 함수 종속을 제거한 형태이다.

특히 기본키가 여러 칼럼에 이루어진 복합키일 때 중요하다.

 

예를 들어 다음과 같은 주문 상품 테이블이 있다고 해보자.

주문 ID	상품 ID	상품명	수량
1	100	키보드	2
1	200	마우스	1
2	100	키보드	1

 

기본키다 ( 주문 ID, 상품 ID )라고 가정해보자.

수량은 주문과 상품이 모두 결정되어야 알 수 있다.

(주문 ID, 상품 ID) → 수량

 

하지만 상품명은 상품 ID 만 알고 있어도 결정할 수 있다.

 

즉, 상품명이 복합 기본키 전체가 아니라 기본키의 일부인 상품 ID 에만 종속되어 있다.
이를 부분 함수 종속이라고 한다.

 

따라서 상품 정보를 별도의 테이블로 조회한다.

상품

상품 ID	상품명
100	키보드
200	마우스

 

주문 상품

주문 ID	상품 ID	수량
1	100	2
1	200	1
2	100	1

 

이렇게 하면 상품명이 주문마다 반복해서 저장되는 문제를 줄일 수 있다.

2NF = 복합키의 일부에만 종속되는 부분 함수 종속을 제거한다.

4. 제 3 정규형

이행 함수 종속 제거

제3정규형은 제 2정규형을 만족하면서 기본키가 아닌 속성 A가 다른 기본키가 아닌 속성 B를 결정하는 관계를 제거한 형태이다.

 

예를 들어 다음과 같은 회원 테이블이 있다고 해보자.
[표]

회원 ID	부서 ID	부서명
1	10	개발팀
2	10	개발팀
3	20	인사팀

 

다음과 같은 종속 관계가 존재한다.

회원 ID → 부서 ID
부서 ID → 부서명

 

따라서 간접적으로

회원 ID → 부서 ID → 부서명

이라는 관계가 만들어진다.

 

부서명은 기본키인 회원 ID에 직접적으로 종속된 것이 아니라 부서 ID를 통해 간접적으로 결정된다.
이를 이행 함수 종속이라고 한다.

따라서 다음과 같이 문리할 수 있다.

회원

회원 ID	부서 ID
1	10
2	10
3	20

 

부서

부서 ID	부서명
10	개발팀
20	인사팀

이제 부서명이 변경되더라도 부서 테이블의 데이터 하나만 수정하면 된다.

3NF = 기본키가 아닌 속성 사이의 이행 함수 종속을 제거한다.

2. 힙

1. 힙이란?

완전 이진 트리를 기반으로 하며, 부모 노드와 지삭 노드 사이에 일정한 대소 관계를 유지하는 자료구조이다.
힙에는 크게 두 종류가 있다.

최대 힙 (Max Heap) : 부모 노드의 값이 자식 노드의 값보다 크거나 같다. 따라서 루트 노드에는 항상 가장 큰 값이 위치한다.

최소 힙 (Min Heap) : 부모 노드의 값이 자식 노드의 값보다 작거나 같다. 따라서 루트 노드에는 항상 가장 작은 값이 위치한다.

중요한 점은 힙이 전체 데이터를 정렬된 상태로 유지하는 것이 아니다. 힙은 부모와 자식 사이의 대소 관계만 보장한다.

2. 힙의 시간 복잡도

힙의 높이는 데이터 개수가 N개 일 때 약 log N이다.

 

삽입
새로운 데이터를 완전 이진 트리의 마지막 위치에 삽입한 후 부모 노드와 비교하면서 적절한 위치까지 위로 이동한다.

이를 Heapify Up이라고 한다.

 

따라서 시간 복잡도는

O(log N)

 

삭제

최대 힙 또는 최소 힙에서는 일반적으로 루트 노드를 삭제한다.

 

루트 노드를 삭제한 뒤 마지막 노드를 루트로 이동시키고, 자식 노드와 비교하면서 적절한 위치까지 아래로 이동한다.

이를 Heapify Down이라고 한다.

 

따라서 시간 복잡도는

O(log N)

 

 

최댓값 또는 최솟값을 확인만 하는 연산(peek) 은 루트 노드를 확인하면 되므로 O(1)이다.

3. 우선순위 큐에서 힙을 사용하는 이유

일반적인 큐는 먼저 들어온 데이터가 먼저 나오는 FIFO 구조이다.

반면 우선순위 큐(Priority Queue)는 입력 순서와 관계없이 우선순위가 가장 높은 데이터를 먼저 꺼내는 자료구조이다.

 

우선순위 큐를 배열이나 연결 리스트로 구현할 수도 있지만, 삽입과 우선순위가 가장 높은 데이터의 삭제를 모두 효율적으로 처리하기 어렵다.

 

힙을 사용하면

연산	시간 복잡도
최댓값 / 최솟값 확인	O(1)
삽입	O(log N)
최댓값 / 최솟값 삭제	O(log N)

으로 처리할 수 있다.

 

따라서 삽입과 우선순위가 가장 높은 원소의 제거를 반복적으로 수행해야 하는 우선순위 큐를 효율적으로 구현하기 위해 힙을 사용한다.

 

Java의 PriorityQueue 역시 힙을 기반으로 구현되어 있으며 기본적으로 최소 힙처럼 동작한다.