DB 개념 7편 - 함수적 종속성, 정규화(1NF~BCNF)

함수적 종속성

함수적 종속성 개념

Functional dependency 함수적 종속성

어떤 스키마 R의 두 속성 집합 A, B가 존재한다.
R의 모든 튜플집합 r로부터 속성 집합 A의 속성 값이 동일한 임의의 두 튜플 t1과 t2를 선택했을 때, t1과 t2의 속성 집합 B의 속성 값도 동일하다면 이와 같은 현상을 함수적 종속성이라고 한다. 즉, A에 의해 B는 유일하게 결정된다. 이때, A가 B를 함수적으로 결정한다고 말하며, A는 결정자, B는 종속자라고 부른다.

 

R = relation
A,B = attribute set. A, B ⊆ R
r(R) = tuple set of R
t1, t2 ⊂ r

t1[A] = t2[A] → t1[B] = t2[B]

 

이와같은 함수적 종속성은 R에 여러개가 존재할 수 있고 이들의 집합을 함수적 종속성 집합이라고 부르며 기호로는 F로 표현한다.

함수적 종속성의 일반화

슈퍼키는 함수적 종속성을 일반화한 것으로 이해할 수 있다.

어떤 스키마 R의 슈퍼키 집합 K가 존재한다.
R의 모든 튜플집합 r로부터 슈퍼키 집합 K의 속성 값이 동일한(슈퍼키가 동일한) 임의의 튜플 t1과 t2_를 선택했을 때, _t1과 t2는 R의 모든 속성 값이 동일하다. 즉, R의 모든 튜플집합 r로부터 t1 = t2로 유일하게 결정된다. 이는 역이 성립한다.

 

R = relation
A,B = attribute set. A, B ⊆ R
r(R) = tuple set of R
t1, t2 ⊂ r

t1[K] = t2[K] <-> t1[R] = t2[R]

완전 함수 종속성

종속자가 기본키에만 종속되며, 기본키가 여러 속성으로 구성되는 경우, 기본키를 구성하는 모든 속성들이 기본키의 부분집합에 종속되는 경우

완전 함수적 종속성에서의 모든 결정자는 기본키 혹은 기본키의 부분집합이다.

부분 함수 종속성

릴레이션에서 종속자가 기본키가 아닌 다른 속성에 종속되거나, 기본키가 여러 속성으로 구성되는 경우에 기본키의 부분집합에 종속되는 경우

이행 함수 종속성

X → Y, Y → Z, X → Z의 종속성이 릴레이션 내에 모두 존재하는 경우.
암스트롱 공리의 전이성(transtivity)과 관련 있음.
=> 릴레이션에서 X → Y이고, Y → Z이면, X → Z가 성립한다.
문제점 : X → Z 라는 FD는 X → Y와 Y → Z만 있으면 유도해낼 수 있는 FD임.

Closure

클로저(폐포)란 FD가 주어졌을 때, 이 함수적 종속성으로부터 논리적으로 추론 가능한(암시되는) 모든 함수적 종속성을 일컫는다.
r이 함수적 종속성을 만족한다면, 클로저는 마땅히 만족한다.

 

Closure 수학적 개념
https://w.wiki/9Rir

 

함수적 종속성을 F로 표현하고, 클로저는 F⁺로 표현한다.

암스트롱 공리

암스트롱 공리 
https://w.wiki/9RjC

 

클로저를 구하기 위해 사용된다.

α, β, γ, δ는 attribute set

 

암스트롱 공리

1. β ⊆ α 이면, α → β : reflexivity(재귀성)
2. α → β 이면, γα → γβ : augmentation(증가)
3. α → β 이고 β → γ 이면, α -> γ : transitivity(전이성, 이행성)

이 공리는 sound and complete (완전한 사실인 것들에 대해서 말하고 있다.)

 

부수규칙

1. α → β 이고 α → γ 이면, α → βγ : union(합집합)
2. α → βγ 이면, α → β, α → γ : decomposition(분해)
3. α → β 이고 γβ → δ 이면, αγ → δ : pseudotransivity(의사 전이) (augmentation에 의해서)

Canonical cover

Canonical cover 캐노니컬 커버(정규 커버)
함수적 종속성 집합으로부터 의미없는 중복을 제거한 가장 간소화 된 집합을 말한다.

스키마 R에서 두 FD 집합 F와 G가 동등하다면, F ≡ G (F와 G는 동치이다) 라고 말하며, 동등의 조건은 (F⁺ = G⁺)F의 클로저와 G의 클로저가 동일한 것이다. 이때 F는 G의 cover라고 말할 수 있다. F가 다른 모든 cover들 중, 가장 간소화된 cover라면 이를 Canoncial cover라고 부른다.

FD set이 적을수록 효율적이라고 할 수 있다.

데이터베이스 정규화

데이터베이스의 중복을 최소화하도록 데이터를 구조화 하는 과정을 의미한다.

잘못된 설계

다음의 3가지 문제를 야기한다

1. 정보 중복
   같은 데이터가 여러 개의 테이블에서 중복되어 나타난다. 중복은 이상현상을 야기한다.
2. 정보 표현 능력 부족
   어떤 테이블에 데이터를 삽입할 때, 데이터에 비해 테이블의 속성이 필요 이상으로 많을 수 있다.
3. 정보 유실
   한 테이블을 속성을 의도적으로 중복시켜 두 개의 테이블로 분할했을 때, 두 테이블을 다시 합치는데 원상복구가 되지 않는 경우, 이를 손실 분해라고 한다.

정보 중복, 정보 표현 능력 부족은 테이블을 적절히 분할하지 않을 경우 발생한다.
정보 유실은 테이블을 잘 못 분할할 때 발생한다.

Anomaly 이상현상

이상현상은 데이터베이스에서 나타나는 중복으로 인해 삽입, 삭제, 갱신에서 발생하는 부작용을 말한다. 중복도가 높을수록 이상현상이 발생하기 쉬워지며 전체적인 무결성이 저하된다.

 

정규화의 목표

1. 무손실 조인-분해
2. 3NF 이상
3. 종속성 유지 분해

무손실 조인-분해

Lossless join decomposition

정보 유실이 없는 분해를 무손실 조인-분해라고 한다. 

다음의 조건을 만족하면 무손실 조인-분해가 보장된다.

 

R이 R1과 R2로 분해될 때,(R = R1 ∪ R2, F⁺ = R의 FD 클로저)
R1 ∩ R2 -> R1 ⊂ F⁺ 또는 R1 ∩ R2 → R2 ⊂ F⁺

이는 다시 말해 R로부터 분해된 두 릴레이션의 교집합이 두 릴레이션 중 적어도 하나의 슈퍼키로 사용된다는 말이다.

 

종속성 유지 분해

R = R1 ∪ R2 ∪ R3 ∪ R4 ∪ ... ∪ Rn
F = R의 FD 집합
F1 ~ Fn = R1 ~ Rn의 FD 집합
F' = F1 ∪ F2 ∪ F3 ∪ ... ∪ Fn

종속성 유지분해려면, F'으로부터 F내의 모든 FD들을 복원할 수 있어야한다.
일반적으로 F' != F 이다.

1NF

모든 속성의 도메인은 원자값이어야 한다.

속성의 도메인이 { 이름, 학번 } 인 경우, 1NF가 아님.

속성을 이름, 학번 각각으로 분리해준다.

2NF

1NF를 만족하고, 부분 함수 종속성을 제거한 정규형이다.

⇒ 기본키 이외의 결정자에 종속되는 경우를 제거하기 위해서 릴레이션을 분리한다.

1NF를 만족하는 테이블의 기본키가 단일키라면, 2NF가 성립

3NF

2NF까지의 조건을 만족하고, 이행 함수 종속성을 제거한 정규형이다.

F = { A → B, B → C, A → C } 에서 A → C는 나머지 두 FD로부터 유도해낼 수 있기 때문에,

A → C를 제거하기 위해 릴레이션을 분리한다.

 

3NF는 이렇게 설명할 수도 있다.

다음의 조건을 만족할 때, R은 3NF

 

💡 ∀α → β (α, β ⊆ R)에 대해서, 다음 조건 중 적어도 하나를 만족

1. 사소한 FD만 존재 ⇒ β ⊆ α
   사소한 FD 예시: A→A, AB→A, ABC→ABC
2. 모든 결정자(α)가 후보키
3. β - α 내의 각 attribute는 R의 후보키 내에 포함된다.(완화조건)

3NF의 단점

1. 정보 표현 능력 부족 = Null value를 야기하지 않고 정보를 넣을 수가 없다.
2. 정보 중복 발생

BCNF

BCNF는 Boyce-Codd Normal Form의 약어로 3NF보다 조금 더 강화된 정규형이기 때문에 3.5NF라고 불리기도 한다.

3NF까지의 조건을 만족하며, 사실상 attribute 간의 종속성이 없는(사소한 FD만 존재) 정규형이다.

다음의 조건을 만족할 때, R은 BCNF

 

💡 ∀α→β (α, β ⊆ R)에 대해서, 다음 조건 중 적어도 하나를 만족

1. 사소한 FD만 존재 ⇒ β ⊆ α
   사소한 FD 예시: A→A, AB→A, ABC→ABC
2. 모든 결정자(α)가 후보키

 

종속성 유지 분해 관점에서의 3NF와 BCNF

※ 모든 BCNF가 종속성 유지분해는 아니다.

 

BCNF이면서 종속성 유지 분해가 아닌 것보다, 정보 중복이 일어나면서(3NF) 종속성 유지 분해가 되는 것이 좋다.
=> 종속성유지 분해의 이점이 절대적이므로, 중복을 감수한다.