• 들어가기에 앞서
• Good and Bad FD
• FD 찾기
  • Armstrong’s axioms(공리)
    • Reflexivity
    • Augmentation
    • Transivity
    • Additional rules
• 폐포 - Closure
  • 폐포성
• 𝐹+ (Closure of a Set of FDs)
• 𝑋+ (Closure of a Set of Attributes)
  • Closure Algorithm - 𝐹+ 찾기
• Key와 Super Key
  • 최소성
• Key와 Super Key 찾기
• FD의 최소 기저(Minimal Basis of FDs)
  • 최소 기저 만들기
• 마무리하며

들어가기에 앞서

DB 디자인 이론 - FD를 찾아보고, 어떤 것이 좋은 FD인지 판단해보자.

Good and Bad FD

FD는 함수 종속성이다. 이는 table에 전역적으로 적용된다. 즉, table 내부 column끼리 어떤 관계가 있는지 알려주는 지표의 역할로 사용될 수 있다. 따라서, table의 FD는 잘 선택해야 한다. 좋은 FD를 사용하지 않고, 정규화를 진행한다면 Bad Schema가 생성 될 것이다. 그렇다면 좋은 FD와 나쁜 FD는 어떤 것일까?

좋은 FD는 중복이 거의 없는 FD를 말한다. 예시로 A -> B라는 FD가 있다고 하자. 이 FD에 해당하는 table의 row가 중복되어 나타나지 않는다면, 좋은 FD라고 할 수 있다. 아래 그림에서, position -> phone이란 FD는 table에서 중복되어 나타나기에, 좋은 FD라고 볼 수 없다. 하지만 EmpID -> name, phone, position FD는 table에서 중복되어 나타나지 않는다. 이는 좋은 FD라고 할 수 있다.

중복된 row가 나타나면 나쁜 FD이다. 이는 데이터의 수정, 삽입, 삭제에서 문제가 발생할 수 있기 때문이다. 즉, 데이터 일관성을 해칠 수 있기에 이를 FD로 설정하여 정규화를 진행하면 안 된다.

FD 찾기

하지만 FD의 수는 매우 많다. 이 수 많은 FD중 어떻게 좋은 FD를 찾을 수 있을까?

Armstrong’s axioms(공리)

암스트롱 공리를 활용하면 주어진 FD에서 모든 가능한 종속성을 유도할 수 있다. 암스트롱 공리에는 3가지 Reflexivity , Augmentation, Transivity rule이 있다.

Reflexivity

반사성이다. 𝑋 ⊆ {𝐴1, … , 𝐴𝑚} : 𝐴1, 𝐴2, … , 𝐴𝑚 → 𝑋를 의미한다. 다시 말해, Y⊆X라면 X→Y임을 의미한다는 것이다.

예시를 들어보면 A,B,C라는 attribute set에선 A,B,C -> A도 성립하고, A,B,C -> A,C도 성립한다는 것이다.

Augmentation

증가성이다. 이는 덧셈의 등가성과 유사하다.

X -> Y면, X,Z -> Y,Z도 동일하다는 법칙이다.

Transivity

반사(이행)성이다. 이는 연쇄법칙과 유사하다.

X->Y, Y->Z면, X->Z도 성립한다는 법칙이다.

Additional rules

암스트롱 공리를 활용하면, 여러 유용한 법칙을 만들 수 있다.

• Union Rule : 𝐴 → 𝐵, 𝐴 → 𝐶면 𝐴 → (𝐵, 𝐶)
• Decomposition Rule : 𝐴 → (𝐵, 𝐶)면 𝐴 → 𝐵, 𝐴 → 𝐶
• Pseudotransivity Rule : 𝐴 → 𝐵, (𝐵, 𝐶) → 𝐷이면 (𝐴, 𝐶) → 𝐷

Pseudotransivity Rule을 증명해보자. 이산수학에서 배우는 논리학과 유사하다.

𝐴 → 𝐵면, 𝐴, 𝐶 → 𝐵, 𝐶이다. (augmentation)
(𝐵, 𝐶) → 𝐷기에, transivity rule을 적용하면 (𝐴, 𝐶) → 𝐷이다.

폐포 - Closure

closure은 폐포라고 한다. 이는 주어진 공간의 부분 집합을 포함하는 가장 작은 닫힌 집합이다.

폐포성

closure(폐포)에 대해 알아보기 이전에, 폐포성에 대해 알아보자.

폐포성은 집합의 원소와 관계가 있는 모든 원소를 폐포는 포함한다는 성질을 의미한다.

𝐹+ (Closure of a Set of FDs)

F를 우리가 아는 FD의 집합이라고 하고, 이를 폐포와 접목시켜보자.

데이터베이스의 함수 종속성(FD) 관점에서 보면, 주어진 FD 집합에서 관련이 있는 모든 FD를 포함하는 집합 𝐹+를 도출할 수 있다는 것을 의미한다. 이를 암스트롱 법칙에 연관시켜보면, 아래와 같다.

• Soundness (타당성): Armstrong 법칙으로 도출된 모든 FD는 원래 주어진 FD 집합에서 유효합니다.
• Completeness (완전성): Armstrong 법칙을 반복적으로 적용하면 주어진 FD 집합으로부터 도출 가능한 모든 FD를 얻을 수 있습니다.

이는 함수 종속 관계를 분석하여, 데이터의 중복을 제거하는데 사용된다. 즉 정규화에 사용된다.

𝑋+ (Closure of a Set of Attributes)

이는 attribute에 대한 것이다. 어떤 attribute의 집합 𝑋에 FD를 적용시켜, 그와 관련 있는 모든 𝑋+를 찾을 수 있음을 의미한다.

즉, 𝑋와 FD에 의해 유도되는 모든 attribute의 집합이 𝑋+이다. 이를 반복적으로 사용하면, 모든 𝑋+를 찾을 수 있다. 이를 통해 찾은 𝑋+의 부분집합 𝑌 ⊆ 𝑋+에 대해, 𝑋 -> 𝑌 라는 FD를 추출할 수 있다.

FD name->color에 의해, {name}의 closure은 {name, color}로 유도된다.

Closure Algorithm - 𝐹+ 찾기

예시를 통한 Closure Algorithm 알아보기

아래 예시를 통해 얻은 FD들은 쪼개서, 최소 기저(basis, 선형 대수에서 말하는 기저와 동일함.)로 만들어야 한다.

X+를 통한 새로운 FD 유도 - Closure Algorithm

Key와 Super Key

위에서 attribute set의 closure을 찾았다. 이를 통해 우린 table의 모든 속성을 알 수 있는 key를 찾아야 한다.

attribute의 set 중, FD를 사용하여 table의 모든 attribute를 만들 수 있는 attribute의 set을 superkey라고 한다. 이 중 최소성을 만족하는 superkey를 key라고 한다. 다시 말해, 데이터(row, tuple)을 고유하게 식별할 수 있는 속성들의 집합을 superkey라고 하고, 그 중 최소성을 만족하는 속성들의 집합을 key라고 한다.

최소성

최소성이란 어떤 집합에서 어떤 단 하나의 원소만 제거하더라도, 현재 성질을 잃는 것을 의미한다.

이를 Database 디자인 이론에 접목시키면, 어떤 superkey에서 어떤 attribute를 제거하면 더 이상 superkey가 아니게 되어버리는 attribute의 set을 key라고 한다. 아래는 key와 superkey의 차이점을 표로 나타낸 것이다.

Key와 Super Key 찾기

𝑋+를 찾은 다음, 𝑋+가 모든 attribute라면 𝑋는 superkey이다. 만약 𝑋의 부분 집합에 superkey가 없으면, 𝑋는 key이자 superkey이다. 즉, key를 찾기 위해선, superkey를 찾아야 한다.

아래 예시를 보자. 이를 통해 superkey를 통해 key를 찾을 수 있다.

## ex1

Table(A,B,C,D)
set of FDs F : {(A,C) -> B,  C -> D}
key는?

1. {A,C}+ = {A,B,C,D}이다. 즉, {A,C}는 superkey다.
2. {A,C} 집합에서, A를 뺀 {C}는 superkey가 아니다. 반대로 C를 뻰 {A}는 superkey가 아니다.
3. 따라서, {A,C}는 superkey이면서 key이다.

## ex2
Table(A,B,C)

F : {(A,B) -> C, (A,C) -> B}
key는?

1. {A,B}+ = {A,C}+ = {A,B,C}이다. 즉, {A,B}, {A,C}는 superkey이다.
2. 두 superkey를 구성하는 어떤 하나의 attribute라도 빠지면, attribute set은 superkey를 유지할 수 없다.
3. 따라서 {A,B}, {A,C}는 superkey이면서, key이다. 

FD의 최소 기저(Minimal Basis of FDs)

위에서 찾은 FD들을 최소 기저로 만들어야 한다고 했다. 중복되는 FD들은 bad FD이므로, 이를 최소한으로 만들고, 이의 결과를 최소 기저라고 한다. 즉, 핵심적인 FD들만 남긴다는 것이다. 이 최소 기저의 closure는 𝐹+와 동일해야 한다.

FD의 집합 S가 𝐹의 최소 기저가 되려면 아래 조건을 만족해야 한다.

• S의 closure과 𝐹의 closure이 같아야 한다. 즉, S+ = 𝐹+이다.
• S의 모든 FD들의 우변은 하나의 attribute여야 한다.
• S의 하나의 attribute를 제외하면, 더 이상 𝐹+가 아니다. 즉, 최소성을 만족한다.
• S의 원소 F에 대해 좌측 원소가 최소성을 만족해야 한다.

최소 기저 만들기

최소 기저를 만들기 위해 1. 좌변 나누기, 2. 우변 정리 3. 중복 삭제와 같은 알고리즘을 거친다.

아래 예시를 살펴보자.

FD 최소 기저 만들기

마무리하며

FD에 대해 알아보았다. attribute의 closure를 통해 key와 superkey를 찾을 수 있다. 또한, FD의 closure를 통해 최소 기저를 찾을 수 있다. 이를 통해 DB 정규화를 진행할 수 있다.