# 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$가 반드시 성립해야 한다.

함수 종속은 속성의 집합으로 튜플을 구분하는 슈퍼 키에 비해 더 광범위한 제약 조건을 표현할 수 있게 해주며 속성 간의 관계로 구현된 제약 조건을 나타낸다. 그런데 어떤 함수 종속은 현실의 제약 조건과는 거리가 멀어 보인다.

함수 종속 $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^+$를 계산하는 절차를 알아보자.

우선 $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^+$를 계산하는 것보다 훨씬 효율적으로 계산할 수 있다.

속성 클로저 계산하기

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$가 주어졌을 때, 데이터베이스가 제 기능을 수행하기 위해서는 데이터베이스 내에서 업데이트가 이루어질 때마다 모든 함수 종속성이 지켜져야 한다.¹ 그런데 모든 종속성을 확인하는 것은 비용이 많이 들기 때문에, $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$는 불필요하다는 결론에 도달하게 된다.

캐노니컬 커버 계산하기

이제 캐노니컬 커버를 계산하는 과정에 대해 이해할 준비가 됐다. 우선 캐노니컬 커버를 엄밀하게 정의해보자.

이 정의에 근거하여 캐노니컬 커버를 계산하는 알고리즘은 아래와 같다.

우선 $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$ 관계만 확인하면 되므로 종속성 보존을 활용하면 효율적으로 검증할 수 있다.

종속성 보존 테스트

종속성 보존을 테스트하려면 위와 같은 알고리즘을 적용해야 하지만, 이 알고리즘은 $F^+$를 계산할 것을 요구하기 때문에 계산 비용이 높다. 대신 조금 더 간단한 테스트 방법이 두가지 있다.

하나는 $F$의 각 함수 의존성이 분해된 관계 중 하나에서 테스트 가능한지를 보는 것이다. 쉬운 방법이기는 하지만 언제나 먹히는 방법은 아니다. 실패하면 얄짤없이 $F^+$를 계산해야 한다.

또다른 방법은 $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.

Footnotes

1. 물론 함수 의존성이 하나라도 지켜지지 않으면 롤백rollback되어야 한다. ↩