[데이터베이스] Functional Dependency & 정규화

Functional Dependency

 함수 형태의 의존 관계를 나타낸다. 일반적으로 X -> Y 라고 하면 X가 Y를 결정하며, 동일한 X에 대해 반드시 동일한 Y가 대응되는 관계가 설정된다.

 마찬가지로 Relation 내의 Attribute 사이에서도 constraint 등에 의해 일종의 의존 관계가 나타날 수 있다. 예를 들어 학생의 학번(PK) 은 학생의 개인 정보를 결정한다. 이런 관계를 함수처럼 나타낸 것이 Function Dependency 이다.

• X : left-hand-side, 반드시 candidate key에 속해야 한다.
• Y : right-hand-side

 Function Dependency는 현실 세계에서 속성들에 정용되는 제약조건에 기반하여 생성된다. 특정 스키마 R 내에서 attribute 사이의 관계를 설명하는데 사용되므로, R 내의 모든 튜플 r(R) 은 FD 조건을 만족해야 한다. 또한 Key X에 기반하여 함수 관계가 결정된다.

FD 예시

• SSN -> ENAME : 주민등록번호가 이름을 결정
• PNUMBER -> {PNAME, PLOCATION} : 부서 id가 부서의 이름과 부서의 위치를 결정
• {SSN, PNUMBER}-> HOURS : 직원 id 및 부서 번호가 해당 부서에서 일한 시간을 결정

instance를 통한 Function Dependency 정의

 Function Dependency을 정의하기 위해서는 각 속성과 그들 사이의 관계의 의미를 이해해야 한다. 이때 특정 relation의 instance 들을 통해 함수 종속을 정의할 수 있다면 꽤 편할 것이다. 그러나 우리는 instance을 이용하여 FD가 존재하는지 여부를 알 수 없다. 정확히는 존재하지 않는지에 대해서는 확답할 수 있지만, 존재하는지는 확답할 수 없다.

교수	강의	교재
홍길동	자료구조	A
홍길동	알고리즘	B
김철수	데이터베이스	C
박영희	자료구조	D

 함수 종속의 정의에 따르면 X -> Y 에서 동일한 X은 반드시 동일한 Y 값을 가져야 한다. 이때 발생할 수 있는 종속 관계를 몇개만 살펴보자.

• 교수 -> 강의
  : 홍길동 교수는 자료구조 / 알고리즘 수업을 가르치므로 X 에 대해 Y가 고정되지 않는다. 따라서 함수 종속이 없다.
• 교수 -> 교재
  : 교수 -> 강의와 마찬가지로 <홍길동, A> / <홍길동, B> 가 존재하므로 함수 종속이 없다.
• 강의 -> 교재
  : <자료구조,  A> / <자료구조, D> 가 존재하므로, 함수 종속이 없다.
• 교재 -> 강의
  : 중복되는 교재 자체가 없으므로 현재 상황에서는 성립한다.

 위 예시를 보면 함수종속이 발생하지 않는 상황은 X가 동일할 때 Y가 다른 경우가 있음을 통해 보일 수 있다. 함수 종속 관계 역시 교재 -> 강의에서 가능할 것 처럼 보인다. 하지만 <김수한무, 데이터베이스 프로그래밍, C> 이라는 새로운 튜플이 삽입되는 경우 <C, 데이터베이스> 와 <C, 데이터베이스 프로그래밍> 이 존재하므로 X->Y가 성립하지 않는다. 

 따라서 instance을 이용하여 FD를 정의하려 해서는 안된다.

---

Normalization

 잘못된 설계 구조를 가진 relation을 더 작은 단위의 relation으로 쪼갬으로써 좋은 디자인으로 분해하는 프로세스. 데이터베이스에서 발생하는 중복(redundancy)을 최소화한다.

Normal Form

Key 와 Function Dependency를 사용하여 특정 relation을 정규화 했을 때 나타나는, 특정 조건을 만족하는 구조. 

• 2NF, 3NF, BCNF : key + relation schema 기반
• 4NF : key + multi-valued dependencies 기반
• 5NF : key + join dependencies 기반

lossless join, dependency preservation을 만족해야 한다.

 사실 4NF는 초기에 multi-valued attribute을 별개의 테이블로 미리 구분하고 시작하면 문제가 발생하지 않으므로, 일반적으로 BCNF 수준까지만 사용되지만, 4NF도 사용될 수도 있다.

Denormalization

 정규화 된 데이터(higher normal form)를 base relation(lower normal form)으로 되돌리는 행위. 데이터베이스에 저장하는 것 자체가 나중에 동일 데이터를 다시 추출해서 사용하는 것이 목적이기 때문에 denormalization을 한 결과가 반드시 none-Additive & lossless join 조건을 만족하도록 relation을 설계해야 한다.

Key

• Super Key : Key Attribute 을 포함하는 속성들의 조합.
  • 동일 Super Key를 가지는 복수의 튜플이 존재해서는 안된다 ( t1[S] != t2[S] )
  • Key Attribute가 제거되면 더 이상 Key의 역할을 수행할 수 없다.
• Candidate Key : Schema 내에서 Key 의 특성을 가지는 (Unique) 모든 속성들
  • Primary Key : 관계에 중점적으로 참여하는 키
  • Secondary Key : Primary Key가 아닌 Candidate Key 
• Prime attribute : candidate key에 포함되어 있는 attribute
• Nonprime attribute : candidate key가 아닌 attribute

---

1NF

Relation 내 모든 Attribute들은 atomic 해야 한다.

ER 모델에서는 속성의 종류를 다음과 같이 구분할 수 있었다.

• Simple Attribute : 하나의 속성으로만 구성된 attribute
• Composite Attribute : 여러개의 속성으로 구성된 attribute
• Multi-valued Attribute : 여러개의 값을 가질 수 있는 attribute
• nested Attribute : Composite + Multi-valued

 그러나 Relational Database에서 relation의 정의에 따라 모든 attribute는 하나의 속성으로만 구성되어야 하므로 모든 Attribute을 Simple Attribute로 변경해야 한다. 구체적으로는 다음과 같다.

• Composite Attribute : 내부 속성들을 각각의 attribute로 독립한다.
• Multi-valued Attribute
  
  1. 데이터를 펴고 다른 값들을 중복시켜 데이터베이스 내에 저장한다. ( flattening )
  2. 해당 속성을 별개의 relation으로 독립시킨 후 PK-FK을 통해 연결한다.

다음 예시는 도서관의 특정 서적과 관련된 데이터베이스를 나타낸 것이다.

ISBN	서적 정보
ABCDE	(책1, { 하늘도서관, 중앙도서관 })
AB123	(책2, { 우리도서관, 한아름도서관 })

위 데이터베이스에서 서적 정보는 nested attribute의 특성을 가진다. 이때 앞서 언급했듯이 relation에 저장되는 각 attribute들은 atoimic 해야하므로 '서적 정보' 라는 attribute은 single attribute 단위로 분리되어야 한다.

 서적 정보는 책의 이름과 해당 책이 비치된 도서관 정보로 구분할 수 있다. 따라서 Composite Attribute을 "제목" 및 "비치된 도서관" 이라는 칼럼으로 분리하자.

ISBN	제목	비치된 도서관
ABCDE	책1	{ 하늘도서관, 중앙도서관 }
AB123	책2	{ 우리도서관, 한아름도서관 }

 Composite Attribute을 독립시켰지만, 비치된 도서관은 여전히 single attribute가 아니다. 이때 비치된 도서관은 2가지 방식으로 처리할 수 있다.

ISBN	제목	비치된 도서관
ABCDE	책1	하늘도서관
ABCDE	책1	중앙도서관
AB123	책2	우리도서관
AB123	책2	한아름도서관

 첫번째 방법은 Flattening 하는 것이다. '비치된 도서관' 에 저장되어 있었던 값들을 각각 분리한 후, 다른 요소들을 중복시켜 데이터 베이스에 저장한다. 중복 데이터가 발생하여 anomaly가 발생할 수 있다는 문제점이 여전히 존재한다.

ISBN	제목
ABCDE	책1
AB123	책2

(Multi-Valued Attribute가 분리된 테이블)

ISBN	비치된 도서관
ABCDE	하늘도서관
ABCDE	중앙도서관
AB123	우리도서관
AB123	한아름도서관

( 분리되어 표현된 Multi-Valued Attribute)

 두번째 방법은 Multi-valued Attribute을 다른 테이블로 분리시키고, PK-FK 관계를 이용하여 연결하는 것이다. 첫번째 방법과는 달리 anomaly가 발생하지 않는다는 장점이 있다. 거의 모든 상황에서 이 방법이 더 좋다.

---

2NF

모든 Non Prime Attribute 들은 반드시 Candidate Key에 대한 완전 함수종속(FD) 관계를 가져야 한다.

Full Functional Dependency

 Y -> Z 의 함수 종속이 존재할 때 Y 내의 어떤 속성을 제거하게 되면 Z을 결정할 수 없는 상태를 의미한다. 즉, Y가 Z을 결정하기 위한 최소 조건인 경우 이를 완전 함수종속이라고 한다.

해당 조건을 만족하지 못하는 경우 Y에서 어떤 속성을 제거하더라도 Z을 결정할 수 있는 상태가 된다. 이러한 경우 partial Dependency가 존재한다고 말한다.

 예를 들어 Y = AB 라고 생각해보자. 이 경우 AB -> Z라고 나타낼 수 있다. 이때 B를 제거하더라도  A가 Z을 결정할 수 있다면, Y와 Z 사이에는 partial Dependency 가 존재한다. 만약 A가 Single Attribute인 경우, A는 Z을 결정하기 위한 최소 조건이 되므로, A->Z은 Full Functional Dependency가 된다.

 요점은 Y에서 특정한 Attribute을 제거했을 때 관계가 성립하는지 여부라고 볼 수 있다.

 구체적인 예시를 들어보자. 특정 학생이 특정 강의를 수강했는지 여부를 알기 위해서는 학번과 강의 번호의 조합이 필요하다. 만약 둘 중 하나만 존재하지 않더라도 학생 속은 강의를 특정할 수 없어 수강 여부를 검사할 수 없다.

 반면 학생의 이름은 학번과 강의번호를 모두 요구하지 않는다. 당연하지만 학생의 이름은 학번만 있더라도 충분히 조회할 수 있다. 이 경우 {학번, 강의번호} 의 조합은 학생의 이름을 특정하기 위한 최소 조합이 아니므로 partial Dependency를 가진다. 따라서 이를 분리하여 나타내야 한다.

학번#

학생 이름

강의번호#

강의 이름

수강 여부

 위 relation에서 학번과 강의번호는 Candidate Key에 속한다. 이들을 제 2 정규화에 맞도록 분리하면 다음과 같다.

학번#

강의번호#

강의 이름

수강 여부

학번 -> 학생 이름을 분리한다. Key Attribute인 학번은 테이블에 남고, 학생이름은 제거된다.

학번#

강의번호#

수강 여부

강의번호 -> 강의 이름을 분리한다. Key Attribute인 강의번호는 테이블에 남고, 강의 이름은 제거된다.

결과적으로 구분된 relation은 다음과 같이 나타난다.

학번#

학생 이름

학번#

강의번호#

수강여부

강의번호#

강의 이름

 분리 방식을 요약하면 다음과 같다.

 R(A#,B#,C,D) 에서 B#->C 가 Full FD을 구성하면 R1(A#,B,D) 및 R2(B#, C)로 구분한다(A#B# -> C 에 대해 partial dependency가 존재하므로) . 이때 R1의 B는 Foreign Key로 남는다. 

 2NF에서 판정할 때, left hand side에는 Candidate Key만 올 수 있으며, Candidate Key에 대한 함수 종속 여부를 검사한다. 따라서 relation 내에 Candidate Key가 하나만 존재하면 자연스럽게 2NF을 만족한다.

---

3NF

2NF & Non Prime Attribute에 대해 Candidate Key의 Transitive Functional Dependency가 나타나면 안된다.

위 조건을 모든 Key에 대해 확장하면, X -> A에 대해 3NF이면 모든 relation이 다음 조건 중 하나는 만족한다.

• X 는 Super Key이다.
• A는 Prime Attribute이다.

 위 조건에 따르면 Key가 아닌 속성은 Key가 아닌 속성을 결정할 수 없다. 관계에서 왼쪽 또는 오른쪽은 반드시 key 속성이 나타나야 한다.

Transitive Functional Dependency

 X->Y 이고, Y->Z 이면 X->Z가 성립한다. 이때 X->Y->Z 꼴로 함수 종속이 나타나면, 이를 이항 함수 종속이라고 한다. 현재 관계에서 Y 가 candidate key가 아닌 경우에만 문제가 발생한다. 즉, Key가 아닌 속성이 Key가 아닌 Z을 결정하는 경우 문제가 발생한다.

 위 그림에서 { E_id , Ename, Dnumber, Dname, Dlocation } 은 반드시 2NF을 만족한다. Key가 하나밖에 없는 경우 모든 non-prime attribute들은 Primary Key에 대한 완전함수종속 관계를 가지기 때문이다.

 이때 구체적으로 attribute 사이의 관계를 따지면 Primary Key E_id 는 부서 정보를 담고 있는 Dnumber을 결정하고, Dnumber은 Dname 및 Dlocation 을 결정한다. 따라서 위 그림의 relation은 Transitive Functional Dependency 을 가진다. 이때, Dnumber은 Prime Attribute가 아니므로 3NF을 위반한다.

따라서 Dnumber이 결정하는 Dname 및 Dlocation을 원래 relation에서 분리하여 Dnumber을 Primary Key로 한 테이블을 생성하고, 원래 테이블의 Dnumber은 Foreign Key로 둬야 한다.

분리 방법을 요약하면 다음과 같다.

R(A#, B, C, D) 에서 C->D 인 경우, R1(A#, B, C) 및 R2(C#, D) 로 분리한다. 이때 R1에서의 C는 Foreign Key가 된다.

---

BCNF

BCNF는 3NF의 조건 2개 중 후자 (A는 Prime Attribute) 조건을 배제한 구조를 가진다. 

3NF에서는 A->B# 인 경우는 따로 수정하지 않았다. 따라서 다음과 같은 것이 가능했다.

 

3NF의 정의에 따르면 Non-Prime Attribute는 Non-Prime Attribute을 결정하면 안된다. 위 예시의 경우 A#B ->C 이고, C -> B 이지만 B는 A#과 합쳐 하나의 Key를 구성하므로 Prime Attribute가 된다. 따라서  Non-Prime Attribute가 Non-Prime Attribute을 결정하는 상황이 아니므로  3NF을 만족한다.

BCNF에서는 이런 상황도 배제하기를 원한다. 따라서 C를 Primary Key로 하여 C->B 관계를 분리한다.

 따라서 relation 내의 모든 요소는 Super Key 에 의해 결정된다. 그런데, 문제점이 하나 존재한다. 맨 처음 데이터베이스 설계자가 A#B -> C 관계를 지정해둔 것은 다 의미가 있기 때문일텐데, 위 테이블은 natural join을 하더라도 해당 관계가 복구되지 않는다. 즉, A#B -> C 관계는 증발한다.

 사실 이렇게 손실된 관계는 데이터베이스 측면에서 되살릴 수 없다. 따라서 더 상위 레벨인 어플리케이션 수준에서 반드시 A#B -> C 관계를 되살려 원래 가지고 있던 의미를 복구해줘야 한다.

 일반적으로 3NF 까지는 필수적으로 relation을 쪼개줘야 하지만 BCNF은 선택적이다. BCNF은 변환 과정에서 원래 relation에 있던 종속 관계를 잃으며, 새로운 테이블을 구성으로 인해 join이 추가되기 때문이다. 사실 BCNF 자체도 흔히 발생하는 상황이 아니기도 해서 BCNF 구조는 건너 뛰기도 한다.

---

4NF

 4NF은 multi-valued dependency와 관련된 정규형이다. 1NF에서 Multi-valued를 처음부터 독립적인 relation으로 분리한 경우 4NF을 위반하지 않지만, flattening을 통해 해소했다면 데이터의 중복으로 인한 anomaly가 발생하여 4NF을 위반하게 된다. 사실 그냥 relation으로 분리하면 그만이라 4NF을 볼 일이 많지는 않지만 한번 알아보자.

• X->>Y 는 X가 Y를 다치결정함을 의미한다. ( Y는 Multi-valued ).
  • 다치 종속은 1 : N 관계 A:B와 A:C 가 동일한 테이블에 작성되어 R(A, B, C) 꼴로 나타나는 경우 발생한다.
  • A->> B | C 꼴로 나타낼 수 있다.
• Trivial MVD : X->>Y 에 대해 다음 조건 중 하나를 만족하는 경우 Multi valued dependency는 사소하다.
  1. Y ⊆ X 인 경우 ( Y가 X의 부분집합인 경우 )
  2. X υ Y = R 인 경우 ( R(X, Y) 에서 X -> Y 인 경우 )

relation R에 대해 모든 가능한 함수 종속( F⁺ )의 X->>Y 에 대해 X가 R의 Super key이면 4NF을 만족한다.

 R(X, Y, Z) 가 있을 때 X->>Y 이고 X->>Z 이면 X->>Y|Z 이므로 다치 종속이 있다. 이때 X가 각각의 다치 결정에 대해 super key라는 것은 Y 및 Z가 멋대로 flattening 된 것이 아니라 X의 값에 따라 유일하게 값이 결정된다는 의미같다. 대부분의 상황에서는 다치 종속을 없애라는 표현이면 충분해 보인다.

X	Y	Z
x	y1	z1
x	y1	z2
x	y2	z1
x	y2	z2

 위 표에서는 X->>Y, X->>Z이므로 X는 Y와 Z에 대한 다치 종속을 가진다. 이때 Y와 Z가 X을 super key로 하여 결정되는 것은 아무리 봐도 아니므로 X->>Y 및 X->>Z을 각각의 테이블로 분리하자.

X	Y
x	y1
x	y2

X	Z
x	z1
x	z2

자세한 내용은 위키피디아나 여타 서적을 뒤져보자. 

https://en.wikipedia.org/wiki/Multivalued_dependency

---

5NF

* (π_R1(r), π_R2(r), ..., π_Rn(r) ) = r

 relation r을 각각 작은 단위로 decomposition한 후 natural join 한 결과가 원래 relation과 같은 경우 5NF을 만족한다. 보통 관계 없는 조인이 단일 relation에 속한 경우 발생한다. 각각을 독립적 관계로 구성하면 해소된다고 한다.

https://itwiki.kr/w/%EB%8D%B0%EC%9D%B4%ED%84%B0%EB%B2%A0%EC%9D%B4%EC%8A%A4_%EC%A0%9C5%EC%A0%95%EA%B7%9C%ED%98%95

 

---

• 2NF : Partial Dependency 제거
• 3NF : transitive Dependency 제거
• 4NF : Multi-valued Dependency 제거

 참고할만한 유튜브 영상

https://www.youtube.com/watch?v=xoTyrdT9SZI&list=PLLGlmW7jT-nTr1ory9o2MgsOmmx2w8FB3