7. Relational Database Design (1)

Introduction

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

Overview of Normalization

Features of Good Relational Designs

• instructor와 department relation을 natural join하여 in_dep으로 결합한다고 가정
  • 정보의 반복(redundancy) 발생
  • (강사가 없는 새로운 부서를 추가할 경우) Null value(null값) 사용 필요
• 이 relation schema의 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 부서의 모든 중복된 레코드에 대한 갱신 필요
• 원인: 데이터 redundancy
  • 단일 테이블에 여러 엔티티가 공존
• 해결책: Decomposition(분해)

Decomposition

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

A Lossy Decomposition

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

Lossless Decomposition

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

  $$\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r) = r$$

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

  $$r \subset \Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)$$

• ($\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r) \subset r$는 절대 발생할 수 없음)

Example of Lossless Decomposition

• $r$

  $A$	$B$	$C$
  $\alpha$	1	A
  $\beta$	2	B

• $\Pi_{A,B}(r)$

  $A$	$B$
  $\alpha$	1
  $\beta$	2

• $\Pi_{B,C}(r)$

  $B$	$C$
  1	A
  2	B

• $\Pi_{A,B}(r) \bowtie \Pi_{B,C}(r)$

  $A$	$B$	$C$
  $\alpha$	1	A
  $\beta$	2	B

Normalization Theory

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

Functional Dependencies

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

Functional Dependencies Definition

• $R$을 relation schema라 할 때
  • $\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$가 relation schema $R$의 superkey인 것은 $K \rightarrow R$일 때와 동치임.
• $K$가 $R$의 candidate key인 것은 다음 두 조건을 만족할 때와 동치임.
  • $K \rightarrow R$
  • $\alpha \subset K$인 어떤 $\alpha$에 대해서도 $\alpha \rightarrow R$이 성립하지 않음.
• 함수 종속성은 superkey를 사용하여 표현할 수 없는 제약조건을 표현하게 해줌
• Schema in_dep(ID, name, salary, dept_name, building, budget)를 고려
  • 주로 다음 함수 종속성들이 성립할 것으로 기대함.
    • dept_name $\rightarrow$ building
    • ID $\rightarrow$ building
  • 하지만 다음은 성립하지 않을 것으로 기대함.
    • dept_name $\rightarrow$ salary

Keys and Functional Dependencies

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

Lossless Decomposition and Functional Dependencies

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

  $$r = \Pi_{R_1}(r) \bowtie \Pi_{R_2}(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$
• 위의 함수 종속성들은 무손실 join 분해를 위한 충분조건임.

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

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

• Name $\rightarrow$ City, Prefecture
• City $\rightarrow$ Prefecture
• Lossless decomposition이면서 dependency preservation

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

Lossless decomposition이지만 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

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

Boyce-Codd Normal Form (BCNF)

• Relation schema $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가 아닌 schema 예시 in_dep(ID, name, salary, dept_name, building, budget ) 이유
  • dept_name → building, budget이 in_dep에서 성립
  • 하지만 dept_name은 superkey가 아님
• in_dep을 instructor와 department로 분해할 때
  • instructor(ID, name, salary, dept_name)은 BCNF에 있음.
  • department(dept_name, building, budget)은 BCNF에 있음.
• dept_name이 superkey가 아니므로, 동일한 학과명이 테이블에 반복적으로 나타날 수 있음.
  • dept_name으로부터의 함수 종속성은 building과 budget도 반복적으로 나타나게 함.
  • dept_name이 superkey라면, 이러한 중복은 발생하지 않음.

Decomposing a Schema into BCNF

• $R$을 BCNF에 있지 않은 schema라고 가정
• $\alpha \rightarrow \beta$를 BCNF 위반을 야기하는 함수 종속성(FD)이라고 가정
  • 즉, $\alpha$는 $R$의 superkey가 아님
• $R$을 두 개의 schema로 분해
  • $(\alpha \cup \beta)$
    • $\alpha$와 $\beta$만을 가지는 다른 relation를 생성
    • $\alpha \rightarrow \beta$이지만, 이 relation에서 $\alpha$는 superkey이므로 BCNF를 위반하지 않음.
  • $(R - (\beta - \alpha))$
    • 원래 schema에서 $\beta$를 제거하고 $\alpha$는 유지
    • 이 schema에는 더 이상 $\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$는 superkey가 아니기 때문
• $R_1 = (A, B), R_2 = (B, C)$
  • 무손실-join 분해: $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)$
  • 무손실-join 분해: $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와 종속성 보존을 모두 달성하는 것이 항상 가능한 것은 아님
• Schema 예시
  • dept_advisor(student_ID, instructor_ID, dept_name)
• 함수 종속성
  • instructor_ID → dept_name
  • student_ID, dept_name → instructor_ID
• 위 schema는 한 학생이 서로 다른 학과에 여러 명의 지도교수를 가질 수 있다고 가정
• dept_advisor는 instructor_ID가 superkey가 아니므로 BCNF에 있지 않음.
• dept_advisor의 어떤 분해도 student_ID, dept_name → instructor_ID를 보존하지 못함.
• 따라서, 이 분해는 종속성을 보존하지 않음.

Third Normal Form: Motivation

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

Third Normal Form

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

3NF Example

• Schema 예시
  • 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은 superkey
  • instructor_ID → dept_name이지만 instructor_ID는 superkey가 아님. 하지만,
  • $\{\text{dept\_name}\} - \{\text{instructor\_ID}\} = \{\text{dept\_name}\}$이고
  • dept_name은 후보 키에 포함됨

Redundancy in 3NF

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

Goals of Normalization: Revisited

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

How good is BCNF?

• 충분히 정규화되지 않은 것처럼 보이는 BCNF 데이터베이스 schema 존재
• 한 명의 교수가 여러 개의 전화번호와 여러 명의 자녀를 가질 수 있는 relation inst_info(ID, child_name, phone)를 고려
• inst_info의 인스턴스
• 이 relation은 자명하지 않은 함수 종속성이 없으므로 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)과 같은 더 높은 정규형의 필요성을 시사