7. Relational Database Design (1)

Introduction

• Relational Database Design(관계형 데이터베이스 설계)
  • 정보 요구사항에 맞는 "좋은" 관계 스키마(relation schema)의 집합을 찾는 과정
• Design Objective(설계 목표)
  • 회피 가능한 Redundancy(중복성) 없이 모든 필요한 정보를 표현(저장)할 수 있는 데이터베이스 스키마 설계
  • 데이터베이스 내의 관계(테이블) 및 각 관계의 스키마 정의
    • $R = (A, B, C, D, E)$ : 단일 관계 스키마
    • $DB = \{ R1, \dots, Rn\}$ : 데이터베이스 스키마 (관계 스키마의 집합)
• Relational database design의 Pitfall(함정)
  • 잘못된 설계는 다음을 야기할 수 있음
    • 특정 정보 표현의 불가
    • 정보의 반복
    • 정보의 손실
• Design Goals(설계 목표):
  • 속성(attribute) 간의 관계가 표현되도록 보장
  • 중복 데이터 회피
  • 데이터베이스 무결성 제약조건(integrity constraint)의 용이한 적용

Overview of Normalization

Features of Good Relational Designs

• instructor와 department 관계를 자연 조인(natural join)하여 in_dep으로 결합한다고 가정
  • 정보의 반복(중복성) 발생
  • (강사가 없는 새로운 부서를 추가할 경우) Null value(null 값) 사용 필요
• 이 관계 스키마의 Primary key(기본 키)는 무엇이 될 수 있는가?
  • (ID, dept_name): ID에 null 값이 올 수 있으므로 dept_name이 키에 포함되어야 함

Redundancy creates problems

• Anomalies(이상 현상) (by Codd)
  • Insertion anomaly(삽입 이상): 강사 없이는 새로운 부서를 추가하는 것이 불가능
    • 바람직하지 않은 null 값 사용 필요
  • Deletion anomaly(삭제 이상): 한 부서의 유일한 강사를 삭제하는 경우 (예: Music 부서의 Mozart)
    • 부서 정보를 보존하기 위해 null 값 사용 필요
    • 해당 사례를 식별하기 위한 복잡한 삭제 로직 요구
  • Update anomaly(갱신 이상): CS 부서의 예산이 변경되는 경우
    • CS 부서의 모든 중복된 레코드에 대한 갱신 필요
• 원인: 데이터 중복성
  • 단일 테이블에 여러 엔티티(entity)가 공존
• 해결책: Decomposition(분해)

Decomposition

• in_dep 스키마에서 정보 반복 문제를 피하는 유일한 방법은 스키마를 instructor와 department 두 개로 분해하는 것
  • 분해된 스키마는 이전 예제의 문제들을 가지지 않음
• 모든 분해가 좋은 것은 아님. employee(ID, name, street, city, salary)를 다음과 같이 분해한다고 가정
  • employee1(ID, name)
  • employee2(name, street, city, salary)
• 동일한 이름을 가진 두 명의 직원이 있을 때 문제 발생
  • 원본 employee 관계를 재구성할 수 없음: Lossy decomposition(손실 분해)
• 다음 슬라이드는 정보가 어떻게 손실되는지 보여줌

A Lossy Decomposition

• ID 57766인 Kim이 Perryridge에 산다는 것은 확신 가능
• (분해 후 조인 시) ID 57766인 Kim이 어디에 사는지 확신 불가능

Lossless Decomposition

• $R$을 관계 스키마라 하고, $R_1$과 $R_2$가 $R$의 분해를 형성한다고 가정
  • 즉, $R = R_1 \cup R_2$
• $R$을 두 개의 관계 스키마 $R_1 \cup R_2$로 대체함으로써 정보의 손실이 없다면, 이 분해를 Lossless decomposition(무손실 분해)이라고 함
• 공식적으로, $R$ 스키마를 가진 관계가 $r$일 때:

  $$\Pi_{R1}(r) \bowtie \Pi_{R2}(r) = r$$

• 반대로, 분해가 손실 분해인 경우는 다음과 같음:

  $$r \subset \Pi_{R1}(r) \bowtie \Pi_{R2}(r)$$

• ($\Pi_{R1}(r) \bowtie \Pi_{R2}(r) \subseteq r$는 절대 발생할 수 없음)

Example of Lossless Decomposition

• $R = (A, B, C)$를 $R_1 = (A, B)$와 $R_2 = (B, C)$로 분해
  • $\Pi_{A,B}(r) \bowtie \Pi_{B,C}(r)$

Normalization Theory

• 특정 관계 $R$이 "좋은 형태"인지, 즉 정보 반복 문제가 없는지 판단
• 관계형 데이터베이스를 설계하는 방법은 일반적으로 Normalization(정규화)으로 알려진 프로세스를 사용하는 것임
• Normalization의 목표
  • 관계 $R$이 "좋은 형태"가 아닐 경우, 이를 관계의 집합 $\{R_1, R_2, \dots, R_n\}$으로 분해
    • 각 관계는 좋은 형태(Normal form, 정규형)임
    • 분해는 무손실 분해임
• 이 이론은 다음에 기반함:
  • Functional dependencies(함수 종속성) (가장 일반적인 접근 방식)
  • Multivalued dependencies(다치 종속성) (이 수업에서는 다루지 않음)

Functional Dependencies

• 현실 세계의 데이터에는 일반적으로 다양한 Constraint(제약조건) (규칙)이 존재
• 예를 들어, 대학 데이터베이스에서 유지될 것으로 예상되는 제약조건:
  • 학생과 강사는 ID로 고유하게 식별됨
  • 각 학생과 강사는 하나의 이름만 가짐
  • 각 강사와 학생은 (주로) 하나의 부서에만 소속됨
  • 각 부서는 예산에 대해 하나의 값만 가지며, 하나의 관련된 건물만 있음
• 이러한 모든 현실 세계의 제약조건을 만족하는 관계의 인스턴스를 Legal instance(합법적 인스턴스)라 함
• 데이터베이스의 Legal instance는 모든 관계 인스턴스가 Legal instance인 경우임
• Legal relation 집합에 대한 제약조건
  • Functional Dependency (FD): 특정 속성 집합의 값이 다른 속성 집합의 값을 고유하게 결정하도록 요구
  • 함수 종속성은 Key(키) 개념의 일반화임

Functional Dependencies Definition

• $R$을 관계 스키마라 할 때
  • $\alpha \subseteq R$ 이고 $\beta \subseteq R$
• 함수 종속성

  $$\alpha \rightarrow \beta$$

  는 모든 Legal relation $r(R)$에 대해, $r$의 임의의 두 튜플(tuple) $t_1$과 $t_2$가 속성 $\alpha$에 대해 동일한 값을 가질 때마다 속성 $\beta$에 대해서도 동일한 값을 가질 경우에만 $R$에 대해 성립함
• 즉,
  • $t_1[\alpha] = t_2[\alpha] \implies t_1[\beta] = t_2[\beta]$
• 예시: 다음 인스턴스를 가진 $r(A, B)$를 고려

  A	B
  1	4
  1	5
  3	7

• 이 인스턴스에서 $B \rightarrow A$는 성립하지만 $A \rightarrow B$는 성립하지 않음

Closure of a Set of Functional Dependencies

• 함수 종속성 집합 $F$가 주어졌을 때, $F$에 의해 논리적으로 함축되는 다른 특정 함수 종속성들이 존재
  • 만약 $A \rightarrow B$이고 $B \rightarrow C$이면, $A \rightarrow C$를 추론할 수 있음
• $F$에 의해 논리적으로 함축된 모든 함수 종속성의 집합을 $F$의 Closure(폐포)라고 함
• $F$의 폐포를 $F^+$로 표기함

Keys and Functional Dependencies

• $K$가 관계 스키마 $R$의 Superkey(슈퍼키)인 것은 $K \rightarrow R$일 때와 동치임
• $K$가 $R$의 Candidate key(후보 키)인 것은 다음 두 조건을 만족할 때와 동치임
  • $K \rightarrow R$
  • $\alpha \subset K$인 어떤 $\alpha$에 대해서도 $\alpha \rightarrow R$이 성립하지 않음
• 함수 종속성은 슈퍼키를 사용하여 표현할 수 없는 제약조건을 표현하게 해줌
• 스키마 in_dep(ID, name, salary, dept_name, building, budget)를 고려
  • 다음 함수 종속성들이 성립할 것으로 예상됨:
    • dept_name $\rightarrow$ building
    • ID $\rightarrow$ building
  • 하지만 다음은 성립하지 않을 것으로 예상됨:
    • dept_name $\rightarrow$ salary

Keys and Functional Dependencies

• 함수 종속성의 사용 목적:
  • 주어진 함수 종속성 집합 하에서 관계가 합법적인지 테스트
    • 관계 $r$이 함수 종속성 집합 $F$ 하에서 합법적이면, $r$이 $F$를 만족한다고 말함
  • 합법적 관계의 집합에 대한 제약조건 명시
    • $R$에 대한 모든 합법적 관계가 함수 종속성 집합 $F$를 만족하면, $F$가 $R$에서 성립한다고 말함
• 참고: 관계 스키마의 특정 인스턴스는, 모든 합법적 인스턴스에서 함수 종속성이 성립하지 않더라도, 우연히 해당 함수 종속성을 만족할 수 있음
  • 예를 들어, instructor의 특정 인스턴스가 우연히 name $\rightarrow$ ID를 만족할 수 있음
• 함수 종속성이 관계의 모든 인스턴스(합법적이든 아니든)에 의해 만족되면 Trivial(자명한) 함수 종속성이라 함
  • 예시:
    • ID, name $\rightarrow$ ID
    • name $\rightarrow$ name
  • 일반적으로, $\alpha \rightarrow \beta$는 $\beta \subseteq \alpha$일 때 자명함

Lossless Decomposition and Functional Dependencies

• 특정 분해가 무손실인지 보이기 위해 함수 종속성을 사용할 수 있음
• $R = (R_1, R_2)$의 경우, 스키마 $R$ 위의 모든 가능한 관계 $r$에 대해 다음을 요구

  $$r = \Pi_{R1}(r) \bowtie \Pi_{R2}(r)$$

• $R$을 $R_1$과 $R_2$로 분해하는 것이 무손실 분해이려면, $R$에서 성립하는 $F$에 대해, 다음 종속성 중 적어도 하나가 $F^+$에 속해야 함:
  • $R_1 \cap R_2 \rightarrow R_1$
  • $R_1 \cap R_2 \rightarrow R_2$
• 위의 함수 종속성들은 무손실 조인 분해를 위한 충분조건임

Example

• $R = (A, B, C)$, $F = \{A \rightarrow B, B \rightarrow C\}$
• $R_1 = (A, B), R_2 = (B, C)$는 무손실 분해임:
  • $R_1 \cap R_2 = \{B\}$이고 $B \rightarrow BC$
• $R_1 = (A, B), R_2 = (A, C)$는 무손실 분해임:
  • $R_1 \cap R_2 = \{A\}$이고 $A \rightarrow AB$
• 참고:
  • $B \rightarrow BC$는 $B \rightarrow \{B, C\}$의 축약 표기임

Dependency Preservation

• 데이터베이스가 갱신될 때마다 함수 종속성 제약조건을 테스트하는 것은 비용이 많이 들 수 있음
• 제약조건을 효율적으로 테스트할 수 있는 방식으로 데이터베이스를 설계하는 것이 유용함
• 하나의 관계만 고려하여 함수 종속성을 테스트할 수 있다면, 이 제약조건의 테스트 비용은 낮음
• 관계를 분해할 때, Cartesian Product(카티션 곱)를 수행하지 않고는 테스트가 더 이상 불가능해질 수 있음
• 함수 종속성을 강제하기 어렵게 만드는 분해는 Dependency preserving(종속성 보존)이 아니라고 함

• Name $\rightarrow$ City, Prefecture
• City $\rightarrow$ Prefecture

Lossless decomposition with dependency preservation (무손실 분해이면서 종속성 보존)

• Name $\rightarrow$ City
• City $\rightarrow$ Prefecture
• 위 두 함수 종속성으로부터 Name $\rightarrow$ City, Prefecture가 유도
• 본래의 함수 종속성인 Name $\rightarrow$ City 와 City $\rightarrow$ Prefecture가 각각 분해된 테이블 내에서 모두 보존

Lossless decomposition but not dependency preserving (무손실 분해이지만 종속성 보존 안됨)

• Name $\rightarrow$ City
• Name $\rightarrow$ Prefecture
• 위 두 함수 종속성으로부터 Name $\rightarrow$ City, Prefecture가 유
• 하지만, 본래의 함수 종속성이었던 City $\rightarrow$ Prefecture를 검사하려면 어떻게 해야 할까?
  • 두 테이블을 Join 해야만 확인 가능
• 결론적으로, 이 분해는 종속성을 보존하지 못함

Goals for Decomposition

• 관계 스키마(relation schema) $R$과 함수 종속성(functional dependency) $F$의 집합을 $R_1, R_2, \dots, R_n$으로 분해(decompose)할 때 원하는 것
  1. 무손실 분해(Lossless decomposition)
  2. 중복 없음(No redundancy)
  3. 종속성 보존(Dependency preservation)

Normal Forms

First Normal Form

• 도메인(Domain)의 요소가 더 이상 나눌 수 없는 단위로 간주될 때, 해당 도메인은 원자적(atomic)임
• 비원자적 도메인의 예:
  • 이름 집합, 복합 속성(composite attribute)
  • CS101과 같이 부분으로 나뉠 수 있는 식별 번호
• 모든 속성의 도메인이 원자적일 때, 관계 스키마는 제1 정규형(First Normal Form, 1NF)에 있음
• 원자성은 실제로는 도메인의 요소가 어떻게 사용되는지에 대한 속성
• 학생 ID 번호: CS0012, EE1127, …
  • 학과를 찾기 위해 앞의 두 문자를 추출한다면, 도메인은 원자적이 아님
  • 그렇지 않다면, 도메인은 원자적임
• 비원자적 속성
  • 데이터베이스가 아닌 애플리케이션 프로그램에서 정보의 인코딩/디코딩으로 이어짐
  • 저장 및 쿼리 처리 복잡화
• 모든 관계는 제1 정규형에 있다고 가정

Boyce-Codd Normal Form (BCNF)

• 관계 스키마 $R$이 함수 종속성 집합 $F$에 대해 BCNF(Boyce-Codd Normal Form)에 있으려면, $F^+$에 있는 $\alpha \rightarrow \beta$ 형태($\alpha \subseteq R$이고 $\beta \subseteq R$)의 모든 함수 종속성에 대해 다음 중 적어도 하나가 성립해야 함:
  • $\alpha \rightarrow \beta$가 자명한(trivial) 함수 종속성 (즉, $\beta \subseteq \alpha$)
  • $\alpha$가 $R$의 슈퍼키(superkey) (즉, $\alpha \rightarrow R$)
• BCNF는 '확실히' 존재하는 것 외에는 함수 종속성이 없음을 보장
• BCNF가 아닌 스키마 예시: in_dep(ID, name, salary, dept_name, building, budget ) 이유:
  • dept_name → building, budget이 in_dep에서 성립
  • 하지만 dept_name은 슈퍼키가 아님
• in_dep을 instructor와 department로 분해할 때
  • instructor(ID, name, salary, dept_name)은 BCNF에 있음
  • department(dept_name, building, budget)은 BCNF에 있음
• dept_name이 슈퍼키가 아니므로, 동일한 학과명이 테이블에 반복적으로 나타날 수 있음
  • dept_name으로부터의 함수 종속성은 building과 budget도 반복적으로 나타나게 함
  • dept_name이 슈퍼키라면, 이러한 중복은 발생하지 않음

Decomposing a Schema into BCNF

• $R$을 BCNF에 있지 않은 스키마라고 가정
• $\alpha \rightarrow \beta$를 BCNF 위반을 야기하는 함수 종속성(FD)이라고 가정
  • 즉, $\alpha$는 $R$의 슈퍼키가 아님
• $R$을 두 개의 스키마로 분해:
  • $(\alpha \cup \beta)$
    • $\alpha$와 $\beta$만을 가지는 다른 관계를 생성
    • $\alpha \rightarrow \beta$이지만, 이 관계에서 $\alpha$는 슈퍼키이므로 BCNF를 위반하지 않음
  • $(R - (\beta - \alpha))$
    • 원래 스키마에서 $\beta$를 제거하고 $\alpha$는 유지
    • 이 스키마에는 더 이상 $\alpha \rightarrow \beta$가 존재하지 않음
• in_dep 예시에서, dept_name → building, budget이 BCNF를 위반
  • $\alpha = \text{dept\_name}$
  • $\beta = \text{building, budget}$
• 따라서, in_dep은 다음과 같이 분해됨
  • $(\alpha \cup \beta) = (\text{dept\_name, building, budget})$
  • $(R - (\beta - \alpha)) = (\text{ID, name, salary, dept\_name})$

Example

• $R = (A, B, C)$, $F = \{A \rightarrow B, B \rightarrow C\}$, $F^+ = \{A \rightarrow B, B \rightarrow C, A \rightarrow C\}$
• $R$은 BCNF에 있지 않음, 왜냐하면 $B \rightarrow C$이지만 $B$는 슈퍼키가 아니기 때문
• $R_1 = (A, B), R_2 = (B, C)$
  • 무손실-조인 분해: $R_1 \cap R_2 = \{B\}$이고 $B \rightarrow BC$ (자명한 종속성이므로 실제로는 $B \rightarrow B$만 확인)
  • 종속성 보존: $A \rightarrow B$는 $R_1$에, $B \rightarrow C$는 $R_2$에 있으므로, $R_1 \Join R_2$를 수행하지 않고도 $A \rightarrow C$를 테스트할 수 있음
  • $A \rightarrow C$는 $A \rightarrow B$와 $B \rightarrow C$에 의해 보장됨 (즉, 명시적 테스트 불필요)
• $R_1 = (A, B), R_2 = (A, C)$
  • 무손실-조인 분해: $R_1 \cap R_2 = \{A\}$이고 $A \rightarrow AB$ (자명한 종속성이므로 실제로는 $A \rightarrow A$만 확인)
  • 종속성을 보존하지 않음
  • $A \rightarrow B$는 $R_1$에, $A \rightarrow C$는 $R_2$에 있음
  • 하지만 $R_1 \Join R_2$를 계산하지 않고는 $B \rightarrow C$를 확인할 수 없음

BCNF and Dependency Preservation

• BCNF와 종속성 보존을 모두 달성하는 것이 항상 가능한 것은 아님
• 스키마 예시: dept_advisor(student_ID, instructor_ID, dept_name) 함수 종속성:
  • instructor_ID → dept_name
  • student_ID, dept_name → instructor_ID
• 위 스키마는 한 학생이 서로 다른 학과에 여러 명의 지도교수를 가질 수 있다고 가정
• dept_advisor는 instructor_ID가 슈퍼키가 아니므로 BCNF에 있지 않음
• dept_advisor의 어떤 분해도 student_ID, dept_name → instructor_ID를 보존하지 못함
• 따라서, 이 분해는 종속성을 보존하지 않음

Third Normal Form: Motivation

• 다음과 같은 일부 상황 존재
  • BCNF가 종속성을 보존하지 않음
  • 업데이트 시 함수 종속성 위반에 대한 효율적인 검사가 중요
• 해결책: 제3 정규형(Third Normal Form, 3NF)이라는 더 약한 정규형 정의
  • 일부 중복 허용
  • 하지만 조인(join)을 계산하지 않고 개별 관계에서 함수 종속성을 검사 가능
• BCNF에 대한 3NF의 장점
  • 항상 3NF로의 무손실, 종속성 보존 분해가 존재
• 3NF의 단점
  • 데이터 항목 간의 의미 있는 관계 일부를 표현하기 위해 null 값을 사용해야 할 수 있음
  • 정보 반복의 문제가 있음

Third Normal Form

• 관계 스키마 $R$이 제3 정규형(3NF)에 있으려면, $F^+$의 모든 $\alpha \rightarrow \beta$에 대해 다음 중 적어도 하나가 성립해야 함:
  • $\alpha \rightarrow \beta$가 자명한 함수 종속성 (즉, $\beta \subseteq \alpha$)
  • $\alpha$가 $R$의 슈퍼키
  • $\beta - \alpha$에 있는 각 속성 $A$가 $R$의 후보 키(candidate key)에 포함됨 (참고: 각 속성은 다른 후보 키에 있을 수 있음)
• 관계가 BCNF에 있으면, 3NF에도 있음
  • BCNF에서는 위의 첫 두 조건 중 하나가 반드시 성립하기 때문
• 세 번째 조건은 종속성 보존을 보장하기 위해 BCNF를 최소한으로 완화한 것

3NF Example

• 스키마 예시: dept_advisor(student_ID, instructor_ID, dept_name) 함수 종속성:
  • instructor_ID → dept_name
  • student_ID, dept_name → instructor_ID
• 두 후보 키 = {student_ID, dept_name}, {student_ID, instructor_ID}
• 앞서 dept_advisor는 BCNF에 있지 않음을 확인했음
• 그러나 $R$은 3NF에 있음
  • student_ID, dept_name은 슈퍼키
  • instructor_ID → dept_name이지만 instructor_ID는 슈퍼키가 아님. 하지만,
  • $\{\text{dept\_name}\} - \{\text{instructor\_ID}\} = \{\text{dept\_name}\}$이고
  • dept_name은 후보 키에 포함됨

Redundancy in 3NF

• 3NF에 있지만 BCNF에는 없는 아래 스키마 $R$을 고려
• $R = (J, K, L)$
• $F = \{JK \rightarrow L, L \rightarrow K\}$, 두 후보 키: $JK$와 $JL$
• 그리고 인스턴스 테이블:
• 테이블의 문제점은 무엇인가?
  • 정보의 반복 ($l_1, k_1$)
  • null 값 사용 필요 (예: $J$에 해당하는 값이 없는 관계 $l_2, k_2$를 표현하기 위해)

Goals of Normalization: revisited

• $R$을 함수 종속성 집합 $F$를 가진 관계 스키마라고 가정
• 관계 스키마 $R$이 "좋은" 형태인지 결정
• 관계 스키마 $R$이 "좋은" 형태가 아닌 경우, 다음과 같은 관계 스키마 집합 $\{R_1, R_2, \dots, R_n\}$으로 분해할 필요가 있음:
  • 각 관계 스키마는 좋은 형태임
  • 분해는 무손실 분해임
  • 가급적 분해는 종속성을 보존해야 함

How good is BCNF?

• 충분히 정규화되지 않은 것처럼 보이는 BCNF 데이터베이스 스키마 존재
• 한 명의 교수가 여러 개의 전화번호와 여러 명의 자녀를 가질 수 있는 관계 inst_info(ID, child_name, phone)를 고려
• inst_info의 인스턴스
• 이 관계는 자명하지 않은 함수 종속성이 없으므로 BCNF에 있음
• 삽입 이상(Insertion anomaly): ID 99999에 전화번호 981-992-3443을 추가하려면 두 개의 튜플을 추가해야 함 (99999, David, 981-992-3443), (99999, William, 981-992-3443)

Higher Normal Forms

• inst_info를 다음과 같이 분해하는 것이 더 좋음:
  • inst_child:
  • inst_phone:
• 이는 다치 종속성(Multivalued Dependency)에 기반한 제4 정규형(4NF)과 같은 더 높은 정규형의 필요성을 시사