[CS300 #165] 정규화 — 같은 사실은 한 곳에만

컴퓨터공학 300 주제 시리즈의 165번째 글이다. 전체 지도는 여기.

한 줄 요약

정규화는 함수 종속성을 근거로 테이블을 쪼개, 하나의 사실이 정확히 한 곳에만 저장되도록 만드는 과정이다.

왜 필요한가

주문 내역을 엑셀처럼 한 장에 적었다고 하자.

주문  상품  수량  상품명    단가   고객  고객명
1001  P1    2     키보드    30000  C7    한결
1001  P2    1     마우스    15000  C7    한결
1002  P1    1     키보드    30000  C9    보람

이 표에는 세 가지 고장이 숨어 있다. 이것을 이상 현상(anomaly) 이라 부른다.

• 갱신 이상: 키보드 이름을 바꾸려면 키보드가 나온 모든 행을 고쳐야 한다. 한 행이라도 빠뜨리면 같은 상품이 두 이름을 갖는다.
• 삽입 이상: 아직 아무도 주문하지 않은 신상품은 넣을 수 없다. 주문 번호 자리가 비기 때문이다.
• 삭제 이상: 주문 1002 를 지우면 고객 보람에 대한 정보도 사라진다.

원인은 하나다. “P1 의 이름은 키보드다”라는 사실이 주문 행마다 반복 저장되어 있다. 정규화는 이 반복을 체계적으로 찾아 없애는 방법이다. E. F. Codd 가 1970년대 초에 1NF~3NF 를 정의했고, 이후 BCNF 와 더 높은 정규형이 이어졌다.

핵심 개념

함수 종속성

속성 집합 X 의 값이 정해지면 Y 의 값이 하나로 정해질 때 X → Y (X 가 Y 를 함수적으로 결정한다)라고 쓴다. 위 표에서는 다음이 성립한다.

{주문, 상품} → 수량
상품         → 상품명, 단가
주문         → 고객
고객         → 고객명

함수 종속성은 데이터를 보고 추측하는 게 아니라 업무 규칙에서 나온다. “한 주문은 한 고객의 것”이 규칙이라면 주문 → 고객이다. 지금 데이터에 우연히 맞는 규칙은 종속성이 아니다.

속성 집합 X 로부터 종속성을 따라 결정되는 모든 속성의 집합을 폐포 X⁺ 라 한다. X⁺ 가 전체 속성이면 X 는 슈퍼키이고, 그중 최소인 것이 후보키다. 위 표의 후보키는 {주문, 상품} 하나다.

정규형의 계단

정규형	조건	없애는 것
1NF	모든 값이 원자값	반복 그룹, 목록이 든 칸
2NF	1NF + 키가 아닌 속성이 후보키 전체에 종속	부분 종속
3NF	2NF + 키가 아닌 속성이 다른 키가 아닌 속성에 종속하지 않음	이행 종속
BCNF	모든 비자명 종속 X → Y 에서 X 가 슈퍼키	키가 아닌 결정자

• 부분 종속: 상품 → 상품명 은 후보키 {주문, 상품} 의 일부에만 종속한다. 2NF 위반.
• 이행 종속: 주문 → 고객 → 고객명. 고객명은 키에 직접이 아니라 고객을 거쳐 종속한다. 3NF 위반.

BCNF 는 이 모든 것을 한 문장으로 요약한다. “결정자는 모두 슈퍼키여야 한다.” 위 표에서 결정자 상품, 주문, 고객 은 모두 슈퍼키가 아니므로 위반이다.

분해

위반 종속성 X → Y 하나마다 (X, Y) 를 새 테이블로 떼어 내고 원래 테이블에서는 Y 를 지운다.

주문품목(주문, 상품, 수량)        키 {주문, 상품}
상품(상품, 상품명, 단가)          키 상품
주문(주문, 고객)                  키 주문
고객(고객, 고객명)                키 고객

이제 키보드 이름은 상품 테이블 한 행에만 있다. 신상품은 주문 없이도 넣을 수 있고, 주문을 지워도 고객은 남는다.

좋은 분해는 두 성질을 지켜야 한다.

1. 무손실 조인: 쪼갠 테이블들을 다시 조인하면 원래 표가 정확히 나온다. 공통 속성이 적어도 한쪽의 키이면 보장된다.
2. 종속성 보존: 원래의 종속성을 쪼갠 테이블 하나 안에서 검사할 수 있다.

3NF 까지는 두 성질을 모두 지키는 분해가 항상 존재한다. BCNF 는 무손실은 보장되지만 종속성 보존이 깨질 수 있다. 고전적인 예가 수강(학생, 과목, 교수) 에 “교수는 한 과목만 가르친다(교수 → 과목)”와 “학생은 과목마다 교수 한 명(학생, 과목 → 교수)”이 있는 경우다. 과목이 후보키 {학생, 과목} 의 일부라 3NF 는 만족하지만, 결정자 교수가 슈퍼키가 아니라 BCNF 는 아니다. (교수, 과목), (학생, 교수) 로 쪼개면 BCNF 가 되지만 “학생, 과목 → 교수”는 어느 테이블 하나로도 검사할 수 없게 된다. 그래서 실무 목표는 보통 3NF 이고, BCNF 는 손해가 없을 때 간다.

더 높은 정규형

4NF 는 다치 종속(한 키에 서로 독립인 목록 두 개가 붙는 경우, 예: 직원의 기술 목록과 언어 목록을 한 테이블에)을 없앤다. 5NF 는 조인 종속을 다룬다. 실무 설계에서 4NF 위반은 가끔 보이고, 5NF 는 드물다.

직접 해 보기

폐포, 후보키, BCNF 위반을 계산하는 짧은 코드다. 함수 종속성 이론이 기계적으로 계산 가능하다는 것을 보여 준다.

from itertools import combinations

def closure(attrs, fds):
    """속성 집합의 폐포 X+ 를 구한다."""
    result = set(attrs)
    changed = True
    while changed:
        changed = False
        for lhs, rhs in fds:
            if lhs <= result and not rhs <= result:
                result |= rhs
                changed = True
    return result

def candidate_keys(R, fds):
    keys = []
    for n in range(1, len(R) + 1):
        for combo in combinations(sorted(R), n):
            s = set(combo)
            if closure(s, fds) == R and not any(k <= s for k in keys):
                keys.append(s)
    return keys

def bcnf_violations(R, fds):
    return [(l, r) for l, r in fds if not r <= l and closure(l, fds) != R]

# 주문품목(주문번호, 상품코드, 수량, 상품명, 단가, 고객ID, 고객명)
R = {"주문", "상품", "수량", "상품명", "단가", "고객", "고객명"}
F = [({"주문", "상품"}, {"수량"}),
     ({"상품"}, {"상품명", "단가"}),
     ({"주문"}, {"고객"}),
     ({"고객"}, {"고객명"})]
print("후보키:", [sorted(k) for k in candidate_keys(R, F)])
for l, r in bcnf_violations(R, F):
    print("위반:", sorted(l), "->", sorted(r))

결과:

후보키: [['상품', '주문']]
위반: ['상품'] -> ['단가', '상품명']
위반: ['주문'] -> ['고객']
위반: ['고객'] -> ['고객명']

세 위반이 앞에서 손으로 찾은 것과 같다. 각각을 테이블로 떼어 내면 앞 절의 4개 테이블이 된다. 후보키 탐색은 속성 수에 대해 지수 시간이므로 이 코드는 교육용이다. 실제 설계에서는 속성이 수십 개라도 업무 규칙으로 키가 거의 정해져 있어 문제가 되지 않는다.

현업에서는

• 단가는 정말 상품에만 종속인가? 위 예에서 상품 → 단가 로 놓았지만, 현실의 주문은 “주문 시점의 가격”을 기억해야 한다. 상품 가격이 바뀌어도 지난 주문의 금액은 그대로여야 하기 때문이다. 그러면 주문품목에도 주문단가 가 있어야 하고, 이것은 중복이 아니라 다른 사실(그 주문에서의 가격)이다. 정규화의 출발점은 공식이 아니라 업무 규칙이라는 좋은 예다.
• JSON 열과 1NF: PostgreSQL 의 jsonb 처럼 한 칸에 구조를 넣는 기능이 있다. 검색·조인 대상이 아닌 부가 정보라면 편리하지만, 그 안의 값으로 자주 거르거나 다른 테이블과 맞춰야 한다면 결국 별도 테이블로 빼게 된다.
• 정규화의 비용은 조인이다. 읽기가 압도적인 화면에서 조인이 병목이 되면 일부러 중복을 들인다. 그것이 다음 글의 반정규화다. 순서가 중요하다. 먼저 정규화하고, 측정한 뒤, 근거를 가지고 되돌린다.

확인 문제

1. 갱신·삽입·삭제 이상을 각각 한 문장으로 정의하라.
2. R(A, B, C, D), F = {AB → C, B → D} 일 때 후보키는? 몇 정규형까지 만족하는가?
3. 이행 종속과 부분 종속의 차이를 예와 함께 설명하라.
4. BCNF 분해가 종속성 보존을 깨뜨릴 수 있다는 것은 실무에서 어떤 불편으로 나타나는가?

풀이

1. 갱신: 같은 사실이 여러 행에 있어 일부만 바뀌면 모순이 생긴다. 삽입: 다른 사실 없이는 어떤 사실을 넣을 수 없다. 삭제: 한 사실을 지우면 무관한 사실도 사라진다.
2. AB⁺ = {A, B, C, D} 이므로 후보키는 AB. B → D 는 키의 일부에 대한 부분 종속이라 2NF 위반이다. 1NF 까지만 만족한다.
3. 부분 종속: 키 {주문, 상품} 의 일부인 상품만으로 상품명이 정해진다. 이행 종속: 키 주문 → 고객 → 고객명 처럼 키가 아닌 속성을 거쳐 정해진다.
4. 원래 하나의 제약(학생·과목 → 교수)을 테이블 하나의 키나 UNIQUE 로 걸 수 없어, 조인을 동반한 트리거나 애플리케이션 검사로 지켜야 한다.

더 읽을거리 (References)

• E. F. Codd, “Further Normalization of the Data Base Relational Model”, in R. Rustin (ed.), Data Base Systems, Prentice-Hall, 1972.
• Abraham Silberschatz, Henry F. Korth, S. Sudarshan, Database System Concepts, 7th ed., McGraw-Hill, 2019. 7장 “Relational Database Design”
• PostgreSQL 공식 문서, Constraints
• PostgreSQL 공식 문서, JSON Types