> [!abstract] Introduction > 이번 글에서는 데이터베이스가 현실을 제대로 반영했는지를 판단하는 기준 중 하나인 함수 종속*Functional Dependency*에 대해 알아봅니다. # Legal Instance 데이터베이스는 현실 세계를 본떠 설계하기 때문에, 데이터베이스의 객체와 관계는 현실 세계의 여러 제약을 반영해야 한다. 관계의 인스턴스 중 현실 세계의 제약 조건을 충족하는 인스턴스를 관계의 적법한 인스턴스*Legal Instance*라 부르며, 데이터베이스의 적법한 인스턴스는 데이터베이스 내의 모든 관계 인스턴스가 적법한 경우다. 현실 세계의 제약 조건을 데이터베이스로 가져오기 위해서는 이 제약 조건이 수식으로 표현되어야 하지만, 보통 현실 세계의 제약 조건은 `모든 학생은 고유의 학번을 가진다`와 같이 문장으로 되어 있다. # Functional Dependency 여기서 등장하는 것이 바로 함수 종속*Functional Dependency*이다. 관계 스키마가 $R$인 관계 $r$과 $R$의 속성인 $\alpha, \beta$, 그리고 $r$의 인스턴스에 속하는 임의의 튜플 $t_1, t_2$에 대하여 $t_1[\alpha] = t_2[\alpha]$일 때 언제나 $t_1[\beta] = t_2[\beta]$라면 해당 인스턴스에 대하여 함수 종속 $\alpha \to \beta$가 성립한다고 말한다. 그리고 $r$의 모든 합법적인 인스턴스에서 함수 종속 $\alpha \to \beta$가 성립할 때 함수 종속 $\alpha \to \beta$가 $R$에서 유지된다고 말한다. 그리고 데이터베이스에서 속성의 이름이 한가지 의미만 가진다면, 함수 종속 $\alpha \to \beta$가 데이터베이스의 제약 조건으로 유지될 때 $\alpha \subseteq R, \beta \subseteq R$이면서 해당 데이터베이스에 존재하는 임의의 스키마 $R$에 대하여 함수 종속 $\alpha \to \beta$가 반드시 성립해야 한다. 함수 종속은 속성의 집합으로 튜플을 구분하는 슈퍼 키에 비해 더 광범위한 제약 조건을 표현할 수 있게 해주며 속성 간의 관계로 구현된 제약 조건을 나타낸다. 그런데 어떤 함수 종속은 현실의 제약 조건과는 거리가 멀어 보인다. ![[StrangeFunctionDependency.png]] 함수 종속 $room\_number \to capacity$는 정의상 성립하기는 하지만, 현실에서 강의실 번호가 같아도 건물이 다르면 강의실의 수용 인원이 다르다는 것을 우리는 알고 있다. 반면, 여기에 건물에 대한 정보까지 함께 적용한 함수 종속 $building, room\_number \to capacity$는 현실의 제약 조건을 반영하며 $classroom$의 인스턴스에서 유지될 것이다. ## Trivial Functional Dependency 모든 관계에서 유지되는 함수 종속은 자명하다*Trivial*고 말하는데, 이러한 함수 종속은 $A \to A$나 $AB \to A$와 같이 $\beta \subseteq \alpha$인 $\alpha, \beta$에 대하여 $\alpha \to \beta$의 형태로 정의된다. # Logical Implication 관계 스키마 $r(R)$에 대하여 함수 종속의 집합 가 주어졌을 때, $r(R)$에서 다른 함수 종속 $f$가 논리적으로 함축*Logically Implied*된다는 것은 $F$를 만족하는 모든 관계 인스턴스가 $f$도 만족한다는 의미다. 예를 들어, $F = \{A \to B, B \to H\}$가 주어졌을 때, 두 튜플 $t_1, t_2$에 대해 $t_1[A] = t_2[A]$라면, $A \to B$에 의해 $t_1[B] = t_2[B]$이 성립하고 $B \to H$에 의해 $t_1[H] = t_2[H]$이 성립하므로 $A \to H$가 논리적으로 함의된다. # Closure of Functional Dependencies 앞서 살펴본 경우와 같이 어떤 함수 종속들의 집합 $F$가 관계 $r$에서 유지될 때 $F$에 존재하는 함수 종속들을 연결하여 $r$에서 유지되는 다른 함수 종속을 끄집어 낼 수도 있다. $A \to B$와 $B \to C$가 유지된다면 $A \to C$도 유지될 것이다. 이렇게 암묵적으로 유지되는 함수 종속을 하나둘 $F$에 합치다 보면 $F$에서 유추할 수 있는 모든 함수 종속의 집합이 탄생한다. 이 집합을 $F$의 클로저*Closure*라 부르며, $F^+$로 표기한다. ## Armstrong's Axioms $F^+$를 체계적으로 구하기 위해서는 암스트롱 공리*Armstrong's Axioms*를 사용한다. 이 공리들은 건전하고*sound* 완전하다*complete*. 건전하다는 것은 잘못된 함수 종속을 생성하지 않는다는 의미이며, 완전하다는 것은 $F^+$의 모든 원소를 생성할 수 있다는 의미다. ### 공리 암스트롱 공리는 세가지 공리에서 출발한다. - 반사성 규칙*Reflexivity Rule*: $\beta \subseteq \alpha$이면 $\alpha \to \beta$가 성립한다. - 예를 들어 $AB \to A$면 $ABC \to BC$가 성립하는데, 이는 $A \subseteq AB$와 $BC \subseteq ABC$가 성립하기 떄문이다. - 확장 규칙*Augmentation Rule*: $\alpha \to \beta$가 성립하고 $\gamma$가 속성 집합이면 $\gamma\alpha \to \gamma\beta$가 성립한다. - 예를 들어 $A \to B$이면 $AC \to BC$가 성립한다. - 이행 규칙*Transitivity Rule*: $\alpha \to \beta$와 $\beta \to \gamma$가 성립하면 $\alpha \to \gamma$가 성립한다. - 예를 들어 $A \to B$이고 $B \to C$이면 $A \to C$가 성립한다. ### 추가 규칙 이 기본 공리를 통하여 추가할 수 있는 법칙이 세가지 더 있다. - 합집합 규칙*Union Rule*: $\alpha \to \beta$와 $\alpha \to \gamma$가 성립하면 $\alpha \to \beta\gamma$가 성립한다. - 예를 들어 $A \to B$이고 $A \to C$이면 $A \to BC$인데, 이는 - 분해 규칙*Decomposition Rule*: $\alpha \to \beta\gamma$가 성립하면 $\alpha \to \beta$와 $\alpha \to \gamma$가 성립한다. - 예를 들어 $A \to BC$이면 $A \to B$이고 $A \to C$인데, 이는 $B, C \subset BC$이기 때문에 반사성 규칙에 의해 $BC \to B$와 $BC \to C$가 성립하고, 이행 규칙에 의해 $A \to B$와 $A \to C$가 성립하기 때문이다. - 의사이행 규칙*Pseudotransitivity Rule*: $\alpha \to \beta$와 $\gamma\beta \to \delta$가 성립하면 $\alpha\gamma \to \delta$가 성립한다. - 예를 들어 $A \to B$이고 $CB \to D$이면 $AC \to D$가 성립하는데, 이는 확장 규칙에 의해 $A \to B$일 때 $AC \to BC$가 성립하고, 따라서 이행 규칙에 의해 $AC \to D$가 성립하기 때문이다. ### $F^+$ 계산하기 이제 암스트롱 공리를 이용해 $F^+$를 계산하는 절차를 알아보자. ![[AProcedureToComputeF+.png]] 우선 $F$에 반사성 규칙울 적용하여 모든 자명한 종속을 생성한 뒤 이를 집합 $F^+$에 포함시킨다. 그 다음 $F^+$가 변하지 않을 때까지 다음의 과정을 반복한다. 1. $F$와 $F$의 모든 자명한 종속에 대하여 확장 규칙을 적용한 결과를 $F^+$에 추가한다. 2. $F^+$에서 함수 종속을 2개씩 뽑아 순서쌍 $\{f_1, f_2\}$를 만들고, 이렇게 만들 수 있는 서로 다른 모든 순서쌍에 대하여 $f_1$과 $f_2$를 이행 규칙으로 결합할 수 있다면 그 결과 또한 $F^+$에 추가한다. ``` F+ = F 반사성 규칙울 적용하여 모든 자명한 종속을 생성한다. 반복: F+의 각 함수 종속 f에 대해: f에 확장 규칙 적용 결과를 F+에 추가 F+의 각 함수 종속 쌍 (f1, f2)에 대해: f1과 f2를 이행 규칙으로 결합 가능하면: 결과를 F+에 추가 F+가 더 이상 변하지 않을 때까지 ``` # Attribute Closure 속성 집합 $\alpha$의 클로저 $\alpha^+$는 함수 종속의 집합 $F$ 하에서 $\alpha$에 의해 함수적으로 결정되는 모든 속성의 집합이다. 이는 $F^+$를 계산하는 것보다 훨씬 효율적으로 계산할 수 있다. ## 속성 클로저 계산하기 ![[A+Algorithm.png]] ``` result := α 반복: F의 각 함수 종속 β → γ에 대해: 만약 β ⊆ result이면: result := result ∪ γ result가 더 이상 변하지 않을 때까지 ``` 예제를 살펴보자. $F = \{A \to B, A \to C, CG \to H, CG \to I, B \to H\}$가 주어졌을 때 속성 집합 $AG$에 대하여 속성 클로저 $(AG)^+$를 계산하면 다음과 같은 과정을 통해 계산하게 된다. 1. $result = AG$ 2. $A \to B$ 적용: $result = ABG$ 3. $A \to C$ 적용: $result = ABCG$ 4. $CG \to H$ 적용: $result = ABCGH$ 5. $CG \to I$ 적용: $result = ABCGHI$ 6. 더 이상 변화 없음 따라서 $(AG)^+ = ABCGHI$가 된다. ## 속성 클로저의 활용 이렇게 구한 속성 클로저는 슈퍼키 테스트, 함수 종속의 검증, $F^+$ 계산 등 다양한 용도로 활용한다. 1. **슈퍼키 테스트**: $\alpha$가 슈퍼키인지 확인하려면 $\alpha^+$가 $R$의 모든 속성을 포함하는지 확인한다. 2. **함수 종속의 검증**: $\alpha \to \beta$가 $F^+$에 속하는지 확인하려면 $\beta \subseteq \alpha^+$인지 확인한다. 3. **$F^+$ 계산**: 모든 $\gamma \subseteq R$에 대해 $\gamma^+$를 계산하고, 각 $S \subseteq \gamma^+$에 대해 $\gamma \to S$를 출력한다. # Canonical Cover 어떤 관계 스키마에 대하여 함수 종속의 집합 $F$가 주어졌을 때, 데이터베이스가 제 기능을 수행하기 위해서는 데이터베이스 내에서 업데이트가 이루어질 때마다 모든 함수 종속성이 지켜져야 한다.[^1] 그런데 모든 종속성을 확인하는 것은 비용이 많이 들기 때문에, $F$와 동일한 클로저를 가지지만 더 단순한 집합이 있다면 이쪽을 사용하는 것이 더 효율적이다. 이러한 집합은 실제로 존재하며, 이를 캐노니컬 커버*Canonical Cover*라 부르고 기호로는 $F_c$라고 한다. 이제 이 캐노니컬 커버를 만드는 과정을 살펴보자. ## Extraneous Attribute 우선 불필요한 속성에 대해 알아보자. 함수 종속 $\alpha \to \beta$에서 함수 종속의 한 속성 $A$가 불필요*Extraneous*하다는 것은 $A$를 제거해도 $F^+$가 변하지 않는다는 의미다. 이게 무슨 뜻인지 이해하려면 함수 종속 내에서 $A$가 자리한 위치를 기준으로 나누어 생각해 보아야 한다. ### 좌항에서의 불필요성 함수 종속의 좌항에서 어떤 속성을 제거한다는 것은 기본적으로 제약을 더욱 강하게 만든다는 것을 의미한다. 그러나 속성 $A \in \alpha$가 좌항에서 불필요하다면 $A$를 제거해도 함수 종속의 제약은 변하지 않으며, $F$는 $(F - \{\alpha \to \beta\}) \cup \{(\alpha - A) \to \beta\}$를 논리적으로 함축한다. 이를 테스트하기 위해서는 $\gamma = \alpha - \{A\}$에 대해 $\gamma^+$를 $F$ 하에서 계산하고, $\gamma^+$가 $\beta$의 모든 속성을 포함하는지 확인하면 된다. ### 우항에서의 불필요성 함수 종속의 우항에서 어떤 속성을 제거한다는 것은 기본적으로 제약을 더욱 약하게 만들어낸다는 것을 의미한다. 그러나 속성 $A \in \beta$가 우변에서 불필요하다면 $A$를 제거해도 함수 종속의 제약은 변하지 않으며, $(F - \{\alpha \to \beta\}) \cup \{\alpha \to (\beta - A)\}$가 $F$를 논리적으로 함축한다. 이를 테스트하기 위해서는 $F' = (F - \{\alpha \to \beta\}) \cup \{\alpha \to (\beta - A)\}$ 하에서 $\alpha^+$를 계산하고, $\alpha^+$가 $A$를 포함하는지 확인한다. 예를 들어 $F = \{AB \to CD, A \to E, E \to C\}$에서 $AB \to CD$의 $C$가 불필요한지 확인하려면, $F' = \{AB \to D, A \to E, E \to C\}$ 하에서 $(AB)^+$를 계산해보면 된다. 그 결과는 $ABCDE$로, 여기에 $C$가 포함되므로 $C$는 불필요하다는 결론에 도달하게 된다. ## 캐노니컬 커버 계산하기 이제 캐노니컬 커버를 계산하는 과정에 대해 이해할 준비가 됐다. 우선 캐노니컬 커버를 엄밀하게 정의해보자. > [!info] Definition > 캐노니컬 커버 $F_c$는 다음 조건을 만족한다: > 1. $F$와 $F_c$는 논리적으로 동등하다. ($F^+ = F_c^+$) > 2. $F_c$의 어떤 함수 종속도 불필요한 속성을 포함하지 않는다. > 3. $F_c$의 각 함수 종속의 좌항은 유일하다. 즉, 같은 좌항을 가진 함수 종속이 없다. 이 정의에 근거하여 캐노니컬 커버를 계산하는 알고리즘은 아래와 같다. ![[ComputingCanonicalCover.png]] 우선 $F$를 출발점으로 삼고 더이상 집합에 변동이 없을 때까지 다음의 과정을 반복한다. 1. 합집합 규칙을 사용하여 $F_c$에서 $\alpha_1 \to \beta_1$과 $\alpha_2 \to \beta_2$ 형태의 모든 종속을 $\alpha_1 \to \beta_1\beta_2$로 대체한다. 2. 불필요한 속성을 가진 함수 종속을 찾고, 있으면 해당 함수 종속에서 불필요한 속성을 제거한다. 이를 위한 테스트는 $F_c$를 기준으로 진행한다. ``` Fc := F 반복: 합집합 규칙을 사용하여 Fc에서 α1 → β1과 α1 → β2 형태의 종속을 α1 → β1β2로 결합 Fc에서 불필요한 속성을 가진 함수 종속 α → β를 찾음 (테스트는 F가 아닌 Fc를 사용) 불필요한 속성이 발견되면 α → β에서 삭제 Fc가 더 이상 변하지 않을 때까지 ``` 예를 들어 $F = \{A \to BC, B \to C, A \to B, AB \to C\}$에 대해 캐노니컬 커버를 계산하는 과정은 아래와 같다. 1. $A \to BC$와 $A \to B$를 결합하면 $A \to BC$가 된다. 2. $B \to C$가 이미 존재하기 때문에 $AB \to C$에서 $A$가 불필요하다. 3. $A \to B$와 $B \to C$를 통해 이행 규칙으로 $A \to C$를 유도할 수 있기 때문에, $A \to BC$에서 $C$가 불필요하다. 4. 그 결과, $F_c = \{A \to B, B \to C\}$이다. ## 캐노니컬 커버의 유일성 캐노니컬 커버는 유일하지 않을 수 있다. 어떤 불필요한 속성을 먼저 제거하느냐에 따라 다른 캐노니컬 커버가 생성될 수 있는데, 예를 들어 $F = \{A \to BC, B \to AC, C \to AB\}$의 경우 $F_c = \{A \to B, B \to C, C \to A\}$, $F_c = \{A \to C, C \to B, B \to A\}$ 등등 여러가지 버전의 캐노니컬 커버가 존재한다. # Dependency Preservation 데이터베이스 스키마 $R$을 $R_1, R_2, \ldots, R_n$으로 분해할 때, 각 $R_i$에 대한 $F$의 한정*restriction* $F_i$은 $F^+$에서 $R_i$의 속성만을 포함하는 모든 함수 종속의 집합이다. 이때 분해가 종속성을 보존*Dependency Preserving*한다는 것은 $F' = F_1 \cup F_2 \cup \cdots \cup F_n$의 클로저가 $F^+$와 같다는 의미다. 즉, $(F_1 \cup F_2 \cup \cdots \cup F_n)^+ = F^+$를 만족하는 분해를 종속성 보존 분해*Dependency-Preserving Decomposition*이라 부른다. 각 $F_i$의 함수 종속은 해당 $R_i$ 관계만 확인하면 되므로 종속성 보존을 활용하면 효율적으로 검증할 수 있다. ## 종속성 보존 테스트 ![[TestingForDependencyPreservation.png]] 종속성 보존을 테스트하려면 위와 같은 알고리즘을 적용해야 하지만, 이 알고리즘은 $F^+$를 계산할 것을 요구하기 때문에 계산 비용이 높다. 대신 조금 더 간단한 테스트 방법이 두가지 있다. 하나는 $F$의 각 함수 의존성이 분해된 관계 중 하나에서 테스트 가능한지를 보는 것이다. 쉬운 방법이기는 하지만 언제나 먹히는 방법은 아니다. 실패하면 얄짤없이 $F^+$를 계산해야 한다. ![[AlternativeTestForDependencyPreservation.png]] 또다른 방법은 $F^+$를 계산하지 않는 방법인데, $F$의 각 함수 종속 $\alpha \to \beta$에 대하여 위의 테스트를 적용하면 된다. # 함수 의존성의 활용 함수 의존성은 크게 두 가지 상황에서 사용하는데, 관계의 인스턴스들이 함수 종속의 집합 $F$를 만족하는지 확인하는 검증*Verification* 상황이며, 다른 하나는 합법적인 관계들의 집합에 존재하는 제약 조건을 기술하는 명세*Specification* 상황이다. 또한 만약 관계 스키마 $R$ 전체에 대하여 $F$가 충족한다면 그때는 $F$가 $R$에서 유지된다고 말한다. 함수 의존성은 정규화*Normalization* 과정에서 좋은 데이터베이스 설계를 판단하는 핵심 도구로 사용된다. --- # 출처 - Silberschatz, A., Korth, H.F. and Sudarshan, S. (2020) _Database system concepts_. Seventh edition. New York, NY: McGraw-Hill. [^1]: 물론 함수 의존성이 하나라도 지켜지지 않으면 롤백*rollback*되어야 한다.