11.1 Good Schema and Bad Schema
Bad Schema
-
관계형 스키마 : 테이블명, 속성명, 무결성 제약으로 구성
-
나쁜 테이블
- Update anomaly
- Delete anomaly
- Insert anomaly
-
Example>
mybadtable1(cID, title, deptName, credit, chairman, building, budget)

- Update anomaly
- chairman, building, budget이 deptName값에 의존적
- 학과명이 반복될 때 해당 속성값이 반복적으로 표시
- 갱신 발생 시 반복적으로 모든 값 동시에 갱신해야하는 현상
- Delete anomaly
- CS 학과가 개설하는 마지막 과목 삭제 시, 해당 과목 정보 삭제되는 것 외에도 학과 정보가 함께 삭제됨
- 과목 삭제되더라도 학과 정보는 존재해야하는데 영원히 삭제 됨
- Insert anomaly
- 새로운 학과가 창설되어 학과에 대한 정보를 데이터베이스에 입력하고자 하여도 학과가 개설하는 과목이 없으면 학과 정보를 입력 X
- 주 키가 cID이기 때문
Design Goal 설계 목표
- 주어진 관계 스키마가 좋은 스키마인지 결정
- 나쁜 스키마라면, 주어진 스키마를 다수의 다른 관계 스키마로 분해 → 분해된 각 관계 스키마는 좋은 형태 → 분해과정은 무손실 조인 분해
- 함수 종속성, 다치 종속성 → 정규화 이론
Functional Dependencies 함수 종속성
- 유효한 관계 인스턴스에 대한 제약
- 키 개념의 일반화
- 일부 속성의 값이 다른 속성의 값을 유일하게 결정하는 것을 의미
- Definition
FDs and Keys
- superkey
- 스키마 내의 모든 다른 속성들을 함수적으로 결정
- candidate key
- 슈퍼키 중에서도 최소성을 만족하는 키
- 키의 어떤 부분집합도 전체 레코드를 유일하게 식별 X
- 엔티티를 유일하게 식별할 수 있는 최소한의 속성들로 구성
Professor(pID, name, deptName, salary)
- pID : name, deptName, salary를 함수적으로 결정 → 슈퍼키이자 후보키
Use of Functional Dependencies
함수 종속성을 사용하는 방식
- 주어진 관계 인스턴스의 유효성 검사
- 특정 테이블 인스턴스가 주어진 함수 종속성을 만족하여 유효한지 여부 판단
- 적법한 테이블의 제약 조건을 명시
- 테이블 설계하고 속성 간의 함수 종속성 명시하면
- 테이블 인스턴스는 함수 종속성을 항상 만족하여야 한다.
11.2 Functional Dependency Theory
Functional Dependency Theory
- 함수 종속성 간 중복 존재 가능
- 설계 과정에 나쁜 영향을 미치는 함수 종속성 존재
→ 함수 종속성을 사용함에 있어 도움되는 이론
Trivial Functional Dependencies
- 무의미 함수 종속성
- 테이블의 모든 인스턴스에 대해 만족되는 경우 → 무의미
- ID name → ID name → name
- α ≥ β를 포함하는 슈퍼집합 → α → β 무의미
Closure of a Set of Functional Dependencies
- 함수 종속성 폐포
- 주어진 함수 종속성 집합으로부터 유추할 수 있는 모든 함수 종속성을 가진 집합
- 다른 함수 종속성으로부터 유추 가능
Armstrong’s Axioms
- 새로운 함수 종속성을 유추할 수 있는 추론 규칙
-
재귀성(reflexivity) 규칙

-
부가성(augmentaion) 규칙
- 주어진 함수 종속성에 동일한 속성을 양쪽에 추가해도 됨

-
이행성(transivity) 규칙

Amstrong’s Axioms are sound and complete
- 추론 규칙 : 건전성, 완전성 고려
- 건전성
- 새롭게 생성되는 규칙이 유효하다
- 암스트롱 공리를 이용하여 생성되는 모든 함수 종속성은 유효
- 완전성
- 모든 유효한 함수 종속성을 암스트롱 공리를 이용하여 생성 가능하다
Additional Inference Rules
- 암스트롱 공리 외 새로운 함수 종속성을 생성하는 추가 규칙
-
합성 규칙 union
왼쪽 속성이 동일하면 오른쪽 속성의 합집합을 결정하는 함수 종속성을 생성

-
분해 법칙 decomposition
왼쪽 소성이 오른쪽 소성의 일부분도 각각 결정함

-
pseudotransitivity

Procedure for Computing F+
- 주어진 함수 종속성 폐포를 구하는 방법
- 암스트롱 공리를 반복적으로 적용하는 것
- 새로운 함수 종속성이 안 나올 때까지 적용
Closure of Attribute Sets
Uses of Attribute Closure
- 주어진 속성이 슈퍼키인지 검증
- 주어진 속성의 폐포를 구하여
- 주어진 테이블의 전체 속성을 가지게 되면
- 그 성은 슈퍼키
- 주어진 함수 종속성이 유효한지 검증
- 주어진 함수 종속성 “α→β”에 대하여
- 속성 α의 폐포에 β가 속하게 되면 “α→β”는 유효한 함수 종속성
- 함수 종속성의 폐포 구하여 검증하는 방식보다 쉬움
- 위 방법을 이용하여 함수 종속성의 폐포 구하기
Canonical Cover
- 정규 커버 (최소 커버)
- 사용자로부터 주어지는 함수 종속성 집합에는 중복되는 함수 종속성이 존재하기도 하고 개별 함수 종속성에도 불필요한 속성을 가지기도 한다.
- {A→B, B→C, A→CD}
- A→CD에서 A→C 유추
- A→B, B→C에서도 A→C 중복적으로 유추 가능 (필요 X)
- {A→B, B→C, AC→D}
- A→B, B→C에서 A→C 유추
- A→C에서 A→AC이므로 A→D 유추
- AC→D에서 속성 C 필요 X
- 주어진 함수 종속성과 동일한 표현력 (함수 종속성 폐포가 동일) & 가장 최소한의 속성 및 가장 적은 수의 함수 종속성을 가지는 집합 = 정규 커버
How to Get Canonical Cover
- 정규 커버 구하는 방법
- 주어진 함수 종속성에 변화가 없을 때까지 합성 법칙 적용 & 주어진 함수 종속성에 불필요한 속성 제거
- 알고리즘 복잡. 자세한 방법 생략.
- Ex> 속성 집합 R = (A,B,C) 함수적 종속성 집합 F = {A → BC, B → C, A → B, AB → C}
-
A→BC, A→B 결합 가능
F = {A→BC, B→C, AB→C}
-
AB → C : B → C만으로 결정 가능 (A 불필요)
F = {A→BC, B→C}
-
A→BC : A→B, A → C (A→B→C 전이적 관계)
F = {A→B, B→C}
⇒ Canonical Cover = {A→B, B→C}
https://mangkyu.tistory.com/110
https://code-lab1.tistory.com/48
- First Normal Form (1NF) 제1정규형
- Second Normal Form (2NF) 제2정규형
- Third Normal Form (3NF) 제3정규형
- 함수 종속성 이용하여 정의
- 실제로 많이 사용되는 정규형
- Boyce/Codd Normal Form (BCNF)
- 함수 종속성 이용하여 정의
- 실제로 많이 사용되는 정규형
- Fourth Normal Form (4NF) 제4정규형
- Fifth Normal Form (5NF) 제5정규형
- 관계형 데이터 모델 속성값
- 원자 값만 허용
- 원자값이 아닌 값 : 집합, 리스트, 백, 복합 속성
- 도메인의 모든 값이 원자값 → 제1정규형
Various Functional Dependencies
-
prime attribute (주요 속성) : 임의의 후보키에 속하는 속성
- ↔ nonprime attribute (비주요 속성)
- 주어진 테이블에 다수 개의 후보키가 존재하는 경우 최소한 하나의후보 키에 속해도 주요 속성이 됨.
-
full functional dependency (완전 함수 종속성)
- 함수 종속성 "α → β"에서 α의 부분집합 γ에 대하여
- "γ → β"이 성립하지 않으면
- "α → β"는 완전 함수 종속성

- β는 α 전체(α의 참부분 집합(proper subset)이 아닌)에 대하여 의존적인 함수 종속성을 완전 함수 종속성이라고 한다.
-
partial functional dependency (부분 함수 종속성)
- "α→ β"에서 α의 부분집합 γ만 가지고도 β 결정가능
- "α → β" 외에도 "γ → β" (γ는 α의 참부분 집합)가 성립
-
transitive functional dependency (이행 함수 종속성)
- 암스트롱 공리의 이행 규칙을 이용하여 생성되는 함수 종속성
- "α → β“ "β → γ“가 존재하는 경우
- α는 γ를 이행적으로 결정 (또는 γ는 α에 이행적으로 의존적)
- 제1정규형 중에서 모든 비주요 속성이 모든 후보키에 완전 의존적
R(SSN, pNumber, hours, eName, pName, pLocation)
SSN pNumber -> hours
SSN -> eName
pNumber -> pName pLocation
- R의 후보키 = (SSN, pNumber)
- 비주요속성 eName : 후보키에 부분적으로 의존 → SSN에는 완전 의존하지만 pNumber에는 의존 X
- R은 제2정규형이 아니다!
R1(SSN, pNumber, hours)
R2(SSN, eName)
R3(pNumber, pName, pLocation)
- 모든 비주요 속성이 후보키에 완전 의존 → 제2정규형이다
- 제2정규형 중에서 비주요속성이 모든 후보키에 이행적으로 의존적이 아닌 경우 = 모든 의미 있는 함수 종속성 "α → β"에서 α가 슈퍼 키이거나 β가 주요 속성인 경우
myEmpDept(SSN, Ename, Bdate, Addr, D
SSN -> Ename Bdate Addr D
D
- 비주요속성 Dname : D#을 거처 SSN에 의존적 (이행적으로 의존) → 제3정규형(X), 제2정규형(O)
ED1(SSN, Ename, Bdate, Addr, D
ED2(D
→ 제3규형 (O)
- 모든 의미 있는 함수 종속성 "α → β"에서 α가 슈퍼키인 경우
- 제3정규형 정의에서 α가 슈퍼키가 아닌 경우 β가 주요 속성인 경우를 삭제한 것
MovieStudio(title, year, length, filmType, studioName, studioAddr)
title year -> length filmType studioName
studioName -> studioAddr
- studioName 슈퍼키도, studioAddr이 주요 속성도 아님
- 제3규형 (X), 제2정규형(O)
MovieStudio1(title, year, length, filmType, studioName)
MovieStudio2(studioName, studioAddr)
→ BCNF
- 모든 binary relations(속성이 두 개인 테이블)은 BCNF이다.
- 더이상 분해 불가능
- 분해과정에서 binary relations 나오면 더이상 정규화 진행할 필요 X
- 관련 함수 종속성이 없는 경우
- (A, B) 가 후보키
- 의미있는 함수 종속성이 없으므로 BCNF
- A→B 성립, B→A 성립 X
- 후보키 = A
- 함수 종속성 왼쪽이 슈퍼키이므로 BCNF
- A→B 성립, B→A 성립
- 후보키 = (A,B)
- 함수 종속성 왼쪽이 슈퍼키이므로 BCNF

Practice
-
후보키 구하기
→ 테이블의 모든 속성을 결정하는 최소 속성 집합
-
주요 속성과 비주요 속성 구하기
→ 주요 속성 : 후보키를 구성하는 속성
-
주어진 스키마에 대한 정규형 판별하기
R(A, B, C, D, E, F)
A -> CD
B -> EF
- 후보키 : AB
- 주요 속성 : A, B 비주요 속성 : C, D, E, F
→ 1NF
- 나쁜 스키마의 전형적 사례, ACD/BEF 전혀 관련 X
R(A, B, C, D, E)
AB -> CDE
C -> D
- 후보키 : AB
- 주요 속성 : A, B 비주요 속성 : C, D, E
→ 2NF
- 갱신 이상 : 속성 D = 속성 C에만 의존적 → 속성 D값이 반복되면 속성 C값도 반복 입력 이상 : 속성 AB값이 없으면 속성 C에만 의존적인 속성 D값을 테이블에 입력할 수 없음 삭제 이상 : 속성 C에 대한 마지막 터플이 삭제되면 속성 D값도 삭제됨
→ 비주요속성간의 함수 종속성은 피해야하는 사항이다!
R(A, B, C, D, E)
A -> BC
C -> DE
- 후보키 : A
- 주요 속성 : A 비주요 속성 : B,C,D,E
→ 2NF
R(A, B, C, D, E)
AB -> CDE
D -> B
- 후보키 : AB, AD
- 주요 속성 : A, B, D 비주요 속성 : C, E
→ 3NF
R(A, B, C, D, E)
A -> BCDE
D -> A
- 후보키 : A, D
- 주요속성 : A, D 비주요속성 : B, C, E
→ BCNF : 모든 함수 종속성 왼쪽 부분이 후보키
R(A, B, C, D, E)
A -> BCDE
→ BCNF
11.4 Decomposition and Design
Goals of Normalization (Revised)
- F : 주어진 함수 종속성의 집합
- 정규화 목표
-
주어진 R이 좋은 스키마인지 결정
-
좋은 스키마가 아니면 분해 연산 통해 다수개의 작은 관계형 스키마로 변형
→ 분해과정 : 무손실 조인 분해 (lossless join decomposition)
→ 함수 종속성을 보존하는 분해이면 더 좋음
Lossy Decomposition

- 분해 및 조인 연산 과정에서 부가적으로 터플 생성
- spurious 터플 생성 → 손실 조인 분해
Lossless-Join Decomposition
- R = (A, B, C) → R1 = (A, B) and R2 = (B, C)

- 분해된 테이블의 공통 속성(B)이 분해된 테이블 중 적어도 하나(R2)에서 주키 → 두개의 테이블로 분해할 때, 무손실 조인 분해 만족
Dependency Preservation
- 함수 종속성 보존
- R → R1, … Rn으로 분리 주어진 함수 종속성 F의 폐포 중 Ri에 속하는 속성만을 가진 함수 종속성 = Fi
- 분해가 함수 종속성 보전하는 방법
- Fi의 합집합의 폐포 : 원래 주어진 함수 종속성의 폐포와 동일
- 함수 종속성이 보전되지 않는 분해면 함수 종속성 확인을 위해 자연조인연산 필요 → 시간 자원 소모
Decomposition
R = (A, B, C)
F = {A -> B, B -> C}
- 함수 종속성이 보존되는 무손실 조인 분해
R1 = (A, B), R2 = (B, C)
- 공통속성(B)이 R2 테이블에서 속성 모두를 결정 → 무손실 조인 분해
- 주어진 함수 종속성을 분해가 된 테이블에서 쉽게 확인 A→B (R1), B→C(R2) : 함수 종속성 보존
- 함수 종속성이 보존되지 않는 무손실 조인 분해
R1 = (A, B), R2 = (A, C)
- 공통속성(A)이 R1 테이블에서 속성 모두를 결정 → 무손실 조인 분해
- B→C 함수 종속성 확인을 위해 자연조인연산 필요 → 함수 종속성 보존 X
Testing for BCNF
- 주어진 함수 종속성의 최소 커버를 구한 후 각 함수 종속성에 대해 슈퍼키 여부 확인
- 최소 커버를 구하는 것 : 복잡한 계산 요구하는 어려운 작업
- 주어진 함수 종속성만을 가지고 슈퍼키 여부 결정 → 슈퍼 키 여부를 위반하지 않는다면 함수 종속성의 폐포에 속하는 함수 종속성도 슈퍼키 여부 위반 X
- 하지만 분해된 테이블에 대한 BCNF 테스트는 주어진 함수 종속성만 검사하면 X
- R = (A, B, C, D, E), F = {A→B, BC→D}
- R1 = (A,B), R2 = (A, C, D, E)
- R2에서 AC→D 종속성 새롭게 발견 → R2에 대해 별도로 BCNF 검증 필요
- 분해가 된 작은 테이블 Ri에 대한 BCNF 테스트
- Ri에 속하는 속성만으로 구성된 모든 함수 종속성 구하여 슈퍼 키 여부 확인
- 속성의 폐포를 활용
- Ri에 속하는 속성의 모든 서브셋 속성 α에 대해 속성의 폐포 구하기
- 구한 속성 폐포가 Ri의 모든 속성을 가지고 있는 경우 → α가 슈퍼키인 경우이므로 BCNF 조건 만족
- 구한 속성 폐포에 α를 제외한 속성 없으면 : α → α인 경우 → 무의미한 함수 종속성이므로 BCNF 만족
BCNF and Dependency Preservation
- 하나의 테이블에 적용되는 함수 종속성 확인 수월 두개 이상의 테이블에 적용되는 함수 종속성은 확인하기에 비쌈 → 자연 조인 연산 수행 필요
- 주어진 모든 함수 종속성 확인을 위해 분해된 각각의 테이블에만 속하는 함수 중 속성을 확인하여도 충분한 경우를 만족하는 성질 = 함수 종속성 보존
- BCNF 정규형을 구하기 위해 테이블을 분해하는 경우 함수 종속성을 보존하지 못하는 경우 존재 이 경우 사용자는 함수 종속성을 보존하면서 그 대신 BCNF보다 하위 정규형인 제3정규형 사용할 수 있음
R = (J, K, L)
F = {JK -> L, L -> K}
R1(L, K), R2(L, J)
- JK→ L 확인을 위해 조인 필요 : 함수 종속성 보존되지 않는 분해
-
BCNF 정규형 : 함수 종속성을 보존하는 분해 지원 X
→ 함수 종속성에 효과적인 검증이 중요한 응용 : 제3정규형 사용
-
테이블 내 값 중복성에 의한 이상 존재
-
함수 종속성이 항상 보존되는 분해가 가능
→ 모든 함수 종속성은 하나의 테이블 내에서 검증 가능
-
중복 존재
R = (J, K, L)
F = {JK -> L, L -> K}
-
redundancy
- 제3정규형 : 테이블 내 발생할 수 있는 중복 줄이고 디비 설계 최적화하기 위한 정규화 과정 → 여전히 중복 존재할 수 있음
- 어떤 L값에 대해 J값이 없는 경우, NULL 사용 → NULL : 디비 설계 시 여전히 발생할 수 있는 문제점, 추가적인 정규화 과정 필요

- -해결법 : 보다 높은 정규형으로 더 분해 → BCNF (더 엄격한 정규형)
Testing for 3NF
- 주어진 함수 종속성 검증 → 폐포에 속하는 모든 함수 종속성에 대한 검증 필요 X
- 왼쪽이 슈퍼키가 아니면 오른쪽 속성이 주요속성인지 확인
- 후보키 구하기
- 전체 속성의 서브셋에 대해 속성의 폐포 구하기
- 비싼 연산
BCNF vs. 3NF
- 3NF로 분해 가능
- 어떤 관계도 손실없이 분해 가능
- 분해과정에서 함수적 종속성 보존
- 중복을 줄이기 위한 좋은 정규화 제공 → 어떤 경우에는 여전히 중복이 존재할 수 있음
- BCNF로 분해 가능
- 어떤 관계도 손실없이 분해 가능
- 모든 함수적 종속성이 보존되지 않을 수 있음 → 다시 복구하기 위한 추가적인 조치 필요
- 각 함수적 종속성 : 후보키에 의해서만 결정
Database Design
- 설계 목표
- 함수 종속성을 직접적으로 명시하는 방법 X
- assertion 기능을 이용해 함수 종속성 표현 가능
- 사용 DBS에서는 assertion 기능 지원 X
- ER 데이터모델로 설계된 데이터베이스
- 더이상 정규화 과정 필요 X
- 키가 아닌 속성이 다른 속성을 결정하는 함수 종속성이 존재할 수 있으나 드물게 나타난다. → 대부분의 관계성 집합으로부터 생성되는 테이블은 두 개의 속성만 가지기 때문
- 성능을 위한 역정규화
- 주어진 테이블이 좋은 성질을 가지도록 작은 테이블로 분해하는 과정 → 관련 있는 정보 검색을 위해 조인 연산 필요 → 성능을 위해 역정규화
- 역정규화가 요구되는 상황 → 데이터 중복에 의한 이상현상보다 DB 성능이 더 중요할 경우
- 역정규화가 적합하지 않을 때 : 실체화된 뷰 (materialized view) 사용
- 뷰 테이블이 소속 터플을 항상 구체적으로 소유
- 질의를 수행하기 위해 추가적인 조인 연산 필요 X
11.5 Multivalued Dependencies
Multivalued Dependencies Example
-
다치 종속성
profChild(ID, childName)
profPhone(ID, phoneNumber)
professor(ID, childName, phoneNumber)
-
의미있는 함수 종속성이 없으므로 BCNF
-
anomaly 현상 발생

-
한 개의 테이블에 두 개의 1:N 관계 존재
-
두 개의 1:N 관계 간에는 연관관계 X
→ 두 개의 다치 종속성 존재
Multivalued Dependencies(MVDs)
- 다치 종속성 정의 : 속성의 부분집합 α 및 β에 대하여 “α →→ β”이 성립하려면 α와 β 부분이 동일한 두 개의 터플 t1, t2에 대하여 5가지 조건을 만족하여야 한다.

- Y값 하나에 대해 다수개의 W값이 관련되는 현상
- 함수 종속성 만족 → 다치 종속성 만족
Multivalued Dependency Theory
-
보완(complementation) 규칙

-
부가(augmentation) 규칙

-
이행(transitivity) 규칙

- 다치 종속성 “α →→ β”가 무의미한 경우
- α가 β를 포함
- α와 β의 합집합이 해당 테이블의 모든 속성
- 관계형 스키마가 제4정규형이 되려면
- 의미 있는 다치 종속성 “α →→ β”가 성립
- α가 슈퍼 키
- 주어진 스키마에 의미 있는 다치 종속성이 없으면 당연히 제4정규형이다.
Star(name, street, city, title, year)
name ->-> street city
Star1(name, street, city)
Star2(name, title, year)
- name →→ street name name →→ title year
- 두 개의 다치 종속성이 분해된 각 테이블에서는 의미 없는 다치 종속성 → 분해된 테이블 모두는 제4정규형