Introduction

이번 글에서는 데이터베이스가 현실을 제대로 반영했는지를 판단하는 기준 중 하나인 함수 종속Functional Dependency에 대해 알아봅니다.

## Legal Instance

데이터베이스는 현실 세계를 본떠 설계하기 때문에, 데이터베이스의 객체와 관계는 현실 세계의 여러 제약을 반영해야 한다. 관계의 인스턴스 중 현실 세계의 제약 조건을 충족하는 인스턴스를 관계의 적법한 인스턴스Legal Instance라 부르며, 데이터베이스의 적법한 인스턴스는 데이터베이스 내의 모든 관계 인스턴스가 적법한 경우다. 현실 세계의 제약 조건을 데이터베이스로 가져오기 위해서는 이 제약 조건이 수식으로 표현되어야 하지만, 보통 현실 세계의 제약 조건은 모든 학생은 고유의 학번을 가진다와 같이 문장으로 되어 있다.

Functional Dependency

여기서 등장하는 것이 바로 함수 종속Functional Dependency이다. 관계 스키마가 RR인 관계 rr과 RR의 속성인 α,β\alpha, \beta, 그리고 rr의 인스턴스에 속하는 임의의 튜플 t1,t2t_1, t_2에 대하여 t1[α]=t2[α]t_1[\alpha] = t_2[\alpha]일 때 언제나 t1[β]=t2[β]t_1[\beta] = t_2[\beta]라면 해당 인스턴스에 대하여 함수 종속 α→β\alpha \to \beta가 성립한다고 말한다. 그리고 rr의 모든 합법적인 인스턴스에서 함수 종속 α→β\alpha \to \beta가 성립할 때 함수 종속 α→β\alpha \to \beta가 RR에서 유지된다고 말한다. 그리고 데이터베이스에서 속성의 이름이 한 가지 의미만 가진다면, 함수 종속 α→β\alpha \to \beta가 데이터베이스의 제약 조건으로 유지될 때 α⊆R,β⊆R\alpha \subseteq R, \beta \subseteq R이면서 해당 데이터베이스에 존재하는 임의의 스키마 RR에 대하여 함수 종속 α→β\alpha \to \beta가 반드시 성립해야 한다.

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

buildingroom_numbercapacity
Packard101500
Painter51410
Taylor312870
Watson10030
Watson12050

함수 종속 room_number→capacityroom\_number \to capacity는 정의상 성립하기는 하지만, 현실에서 강의실 번호가 같아도 건물이 다르면 강의실의 수용 인원이 다르다는 것을 우리는 알고 있다. 반면, 여기에 건물에 대한 정보까지 함께 적용한 함수 종속 building,room_number→capacitybuilding, room\_number \to capacity는 현실의 제약 조건을 반영하며 classroomclassroom의 인스턴스에서 유지될 것이다.

Trivial Functional Dependency

모든 관계에서 유지되는 함수 종속은 자명하다Trivial고 말하는데, 이러한 함수 종속은 A→AA \to A나 AB→AAB \to A와 같이 β⊆α\beta \subseteq \alpha인 α,β\alpha, \beta에 대하여 α→β\alpha \to \beta의 형태로 정의된다.

Logical Implication

관계 스키마 r(R)r(R)에 대하여 함수 종속의 집합 FF가 주어졌을 때, r(R)r(R)에서 다른 함수 종속 ff가 논리적으로 함축Logically Implied된다는 것은 FF를 만족하는 모든 관계 인스턴스가 ff도 만족한다는 의미다.

예를 들어, F={A→B,B→H}F = \{A \to B, B \to H\}가 주어졌을 때, 두 튜플 t1,t2t_1, t_2에 대해 t1[A]=t2[A]t_1[A] = t_2[A]라면, A→BA \to B에 의해 t1[B]=t2[B]t_1[B] = t_2[B]이 성립하고 B→HB \to H에 의해 t1[H]=t2[H]t_1[H] = t_2[H]이 성립하므로 A→HA \to H가 논리적으로 함의된다.

Closure of Functional Dependencies

앞서 살펴본 경우와 같이 어떤 함수 종속들의 집합 FF가 관계 rr에서 유지될 때 FF에 존재하는 함수 종속들을 연결하여 rr에서 유지되는 다른 함수 종속을 끄집어 낼 수도 있다. A→BA \to B와 B→CB \to C가 유지된다면 A→CA \to C도 유지될 것이다. 이렇게 암묵적으로 유지되는 함수 종속을 하나둘 FF에 합치다 보면 FF에서 유추할 수 있는 모든 함수 종속의 집합이 탄생한다. 이 집합을 FF의 클로저Closure라 부르며, F+F^+로 표기한다.

Armstrong's Axioms

F+F^+를 체계적으로 구하기 위해서는 암스트롱 공리Armstrong's Axioms를 사용한다. 이 공리들은 건전하고sound 완전하다complete. 건전하다는 것은 잘못된 함수 종속을 생성하지 않는다는 의미이며, 완전하다는 것은 F+F^+의 모든 원소를 생성할 수 있다는 의미다.

공리

암스트롱 공리는 세 가지 공리에서 출발한다.

  • 반사성 규칙Reflexivity Rule: β⊆α\beta \subseteq \alpha이면 α→β\alpha \to \beta가 성립한다.
    • 예를 들어 AB→AAB \to A면 ABC→BCABC \to BC가 성립하는데, 이는 A⊆ABA \subseteq AB와 BC⊆ABCBC \subseteq ABC가 성립하기 때문이다.
  • 확장 규칙Augmentation Rule: α→β\alpha \to \beta가 성립하고 γ\gamma가 속성 집합이면 γα→γβ\gamma\alpha \to \gamma\beta가 성립한다.
    • 예를 들어 A→BA \to B이면 AC→BCAC \to BC가 성립한다.
  • 이행 규칙Transitivity Rule: α→β\alpha \to \beta와 β→γ\beta \to \gamma가 성립하면 α→γ\alpha \to \gamma가 성립한다.
    • 예를 들어 A→BA \to B이고 B→CB \to C이면 A→CA \to C가 성립한다.

추가 규칙

이 기본 공리를 통하여 추가할 수 있는 법칙이 세 가지 더 있다.

  • 합집합 규칙Union Rule: α→β\alpha \to \beta와 α→γ\alpha \to \gamma가 성립하면 α→βγ\alpha \to \beta\gamma가 성립한다.
    • 예를 들어 A→BA \to B이고 A→CA \to C이면 A→BCA \to BC가 성립한다. A→CA \to C에 확장 규칙을 적용하면 A→ACA \to AC이고, A→BA \to B에 확장 규칙을 적용하면 AC→BCAC \to BC이므로, 이행 규칙에 의해 A→BCA \to BC가 된다.
  • 분해 규칙Decomposition Rule: α→βγ\alpha \to \beta\gamma가 성립하면 α→β\alpha \to \beta와 α→γ\alpha \to \gamma가 성립한다.
    • 예를 들어 A→BCA \to BC이면 A→BA \to B이고 A→CA \to C인데, 이는 B,C⊂BCB, C \subset BC이기 때문에 반사성 규칙에 의해 BC→BBC \to B와 BC→CBC \to C가 성립하고, 이행 규칙에 의해 A→BA \to B와 A→CA \to C가 성립하기 때문이다.
  • 의사이행 규칙Pseudotransitivity Rule: α→β\alpha \to \beta와 γβ→δ\gamma\beta \to \delta가 성립하면 αγ→δ\alpha\gamma \to \delta가 성립한다. - 예를 들어 A→BA \to B이고 CB→DCB \to D이면 AC→DAC \to D가 성립하는데, 이는 확장 규칙에 의해 A→BA \to B일 때 AC→BCAC \to BC가 성립하고, 따라서 이행 규칙에 의해 AC→DAC \to D가 성립하기 때문이다.

F+F^+ 계산하기

이제 암스트롱 공리를 이용해 F+F^+를 계산하는 절차를 알아보자.

우선 FF에 반사성 규칙을 적용하여 모든 자명한 종속을 생성한 뒤 이를 집합 F+F^+에 포함시킨다. 그 다음 F+F^+가 변하지 않을 때까지 다음의 과정을 반복한다.

  1. FF와 FF의 모든 자명한 종속에 대하여 확장 규칙을 적용한 결과를 F+F^+에 추가한다.
  2. F+F^+에서 함수 종속을 2개씩 뽑아 순서쌍 {f1,f2}\{f_1, f_2\}를 만들고, 이렇게 만들 수 있는 서로 다른 모든 순서쌍에 대하여 f1f_1과 f2f_2를 이행 규칙으로 결합할 수 있다면 그 결과 또한 F+F^+에 추가한다.
F+←F반사성 규칙을 적용하여 모든 자명한 종속을 생성repeatfor each f∈F+ dof에 확장 규칙 적용결과를 F+에 추가for each (f1,f2)∈F+×F+ doif f1과 f2를 이행 규칙으로 결합 가능 then결과를 F+에 추가until F+가 더 이상 변하지 않을 때까지\begin{aligned} & F^+ \leftarrow F \\ & \text{반사성 규칙을 적용하여 모든 자명한 종속을 생성} \\ & \textbf{repeat} \\ & \quad \textbf{for each } f \in F^+ \textbf{ do} \\ & \qquad f\text{에 확장 규칙 적용} \\ & \qquad \text{결과를 } F^+\text{에 추가} \\ & \quad \textbf{for each } (f_1, f_2) \in F^+ \times F^+ \textbf{ do} \\ & \qquad \textbf{if } f_1\text{과 } f_2\text{를 이행 규칙으로 결합 가능} \textbf{ then} \\ & \qquad \quad \text{결과를 } F^+\text{에 추가} \\ & \textbf{until } F^+ \text{가 더 이상 변하지 않을 때까지} \end{aligned}

Attribute Closure

속성 집합 α\alpha의 클로저 α+\alpha^+는 함수 종속의 집합 FF 하에서 α\alpha에 의해 함수적으로 결정되는 모든 속성의 집합이다. 이는 F+F^+를 계산하는 것보다 훨씬 효율적으로 계산할 수 있다.

속성 클로저 계산하기

result←αrepeatfor each (β→γ)∈F doif β⊆result thenresult←result∪γuntil result가 더 이상 변하지 않을 때까지\begin{aligned} & result \leftarrow \alpha \\ & \textbf{repeat} \\ & \quad \textbf{for each } (\beta \to \gamma) \in F \textbf{ do} \\ & \qquad \textbf{if } \beta \subseteq result \textbf{ then} \\ & \qquad \quad result \leftarrow result \cup \gamma \\ & \textbf{until } result \text{가 더 이상 변하지 않을 때까지} \end{aligned}

예제를 살펴보자. F={A→B,A→C,CG→H,CG→I,B→H}F = \{A \to B, A \to C, CG \to H, CG \to I, B \to H\}가 주어졌을 때 속성 집합 AGAG에 대하여 속성 클로저 (AG)+(AG)^+를 계산하면 다음과 같은 과정을 통해 계산하게 된다.

  1. result=AGresult = AG
  2. A→BA \to B 적용: result=ABGresult = ABG
  3. A→CA \to C 적용: result=ABCGresult = ABCG
  4. CG→HCG \to H 적용: result=ABCGHresult = ABCGH
  5. CG→ICG \to I 적용: result=ABCGHIresult = ABCGHI
  6. 더 이상 변화 없음

따라서 (AG)+=ABCGHI(AG)^+ = ABCGHI가 된다.

속성 클로저의 활용

이렇게 구한 속성 클로저는 슈퍼키 테스트, 함수 종속의 검증, F+F^+ 계산 등 다양한 용도로 활용한다.

  1. 슈퍼키 테스트: α\alpha가 슈퍼키인지 확인하려면 α+\alpha^+가 RR의 모든 속성을 포함하는지 확인한다.
  2. 함수 종속의 검증: α→β\alpha \to \beta가 F+F^+에 속하는지 확인하려면 β⊆α+\beta \subseteq \alpha^+인지 확인한다.
  3. F+F^+ 계산: 모든 γ⊆R\gamma \subseteq R에 대해 γ+\gamma^+를 계산하고, 각 S⊆γ+S \subseteq \gamma^+에 대해 γ→S\gamma \to S를 출력한다.

Canonical Cover

어떤 관계 스키마에 대하여 함수 종속의 집합 FF가 주어졌을 때, 데이터베이스가 제 기능을 수행하기 위해서는 데이터베이스 내에서 업데이트가 이루어질 때마다 모든 함수 종속성이 지켜져야 한다.1 그런데 모든 종속성을 확인하는 것은 비용이 많이 들기 때문에, FF와 동일한 클로저를 가지지만 더 단순한 집합이 있다면 이쪽을 사용하는 것이 더 효율적이다. 이러한 집합은 실제로 존재하며, 이를 캐노니컬 커버Canonical Cover라 부르고 기호로는 FcF_c라고 한다. 이제 이 캐노니컬 커버를 만드는 과정을 살펴보자.

Extraneous Attribute

우선 불필요한 속성에 대해 알아보자. 함수 종속 α→β\alpha \to \beta에서 함수 종속의 한 속성 AA가 불필요Extraneous하다는 것은 AA를 제거해도 F+F^+가 변하지 않는다는 의미다. 이게 무슨 뜻인지 이해하려면 함수 종속 내에서 AA가 자리한 위치를 기준으로 나누어 생각해 보아야 한다.

좌항에서의 불필요성

함수 종속의 좌항에서 어떤 속성을 제거한다는 것은 기본적으로 제약을 더욱 강하게 만든다는 것을 의미한다. 그러나 속성 A∈αA \in \alpha가 좌항에서 불필요하다면 AA를 제거해도 함수 종속의 제약은 변하지 않으며, FF는 (F−{α→β})∪{(α−A)→β}(F - \{\alpha \to \beta\}) \cup \{(\alpha - A) \to \beta\}를 논리적으로 함축한다. 이를 테스트하기 위해서는 γ=α−{A}\gamma = \alpha - \{A\}에 대해 γ+\gamma^+를 FF 하에서 계산하고, γ+\gamma^+가 β\beta의 모든 속성을 포함하는지 확인하면 된다.

우항에서의 불필요성

함수 종속의 우항에서 어떤 속성을 제거한다는 것은 기본적으로 제약을 더욱 약하게 만들어낸다는 것을 의미한다. 그러나 속성 A∈βA \in \beta가 우변에서 불필요하다면 AA를 제거해도 함수 종속의 제약은 변하지 않으며, (F−{α→β})∪{α→(β−A)}(F - \{\alpha \to \beta\}) \cup \{\alpha \to (\beta - A)\}가 FF를 논리적으로 함축한다. 이를 테스트하기 위해서는 F′=(F−{α→β})∪{α→(β−A)}F' = (F - \{\alpha \to \beta\}) \cup \{\alpha \to (\beta - A)\} 하에서 α+\alpha^+를 계산하고, α+\alpha^+가 AA를 포함하는지 확인한다.

예를 들어 F={AB→CD,A→E,E→C}F = \{AB \to CD, A \to E, E \to C\}에서 AB→CDAB \to CD의 CC가 불필요한지 확인하려면, F′={AB→D,A→E,E→C}F' = \{AB \to D, A \to E, E \to C\} 하에서 (AB)+(AB)^+를 계산해보면 된다. 그 결과는 ABCDEABCDE로, 여기에 CC가 포함되므로 CC는 불필요하다는 결론에 도달하게 된다.

캐노니컬 커버 계산하기

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

Definition

캐노니컬 커버 FcF_c는 다음 조건을 만족한다:

  1. FF와 FcF_c는 논리적으로 동등하다. (F+=Fc+F^+ = F_c^+)
  2. FcF_c의 어떤 함수 종속도 불필요한 속성을 포함하지 않는다.
  3. FcF_c의 각 함수 종속의 좌항은 유일하다. 즉, 같은 좌항을 가진 함수 종속이 없다.

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

우선 FF를 출발점으로 삼고 더 이상 집합에 변동이 없을 때까지 다음의 과정을 반복한다.

  1. 합집합 규칙을 사용하여 FcF_c에서 α1→β1\alpha_1 \to \beta_1과 α2→β2\alpha_2 \to \beta_2 형태의 모든 종속을 α1→β1β2\alpha_1 \to \beta_1\beta_2로 대체한다.
  2. 불필요한 속성을 가진 함수 종속을 찾고, 있으면 해당 함수 종속에서 불필요한 속성을 제거한다. 이를 위한 테스트는 FcF_c를 기준으로 진행한다.
Fc←Frepeat합집합 규칙을 사용하여 Fc에서 α1→β1과 α1→β2 형태의종속을 α1→β1β2로 결합Fc에서 α 또는 β에 불필요한 속성을 가진 함수 종속 α→β를 찾음(테스트는 F가 아닌 Fc를 사용)불필요한 속성이 발견되면 α→β에서 삭제until Fc가 더 이상 변하지 않을 때까지\begin{aligned} & F_c \leftarrow F \\ & \textbf{repeat} \\ & \quad \text{합집합 규칙을 사용하여 } F_c\text{에서 } \alpha_1 \to \beta_1\text{과 } \alpha_1 \to \beta_2 \text{ 형태의} \\ & \quad \text{종속을 } \alpha_1 \to \beta_1\beta_2\text{로 결합} \\[4pt] & \quad F_c\text{에서 } \alpha \text{ 또는 } \beta\text{에 불필요한 속성을 가진 함수 종속 } \alpha \to \beta\text{를 찾음} \\ & \quad \text{(테스트는 } F\text{가 아닌 } F_c\text{를 사용)} \\[4pt] & \quad \text{불필요한 속성이 발견되면 } \alpha \to \beta\text{에서 삭제} \\ & \textbf{until } F_c \text{가 더 이상 변하지 않을 때까지} \end{aligned}

예를 들어 F={A→BC,B→C,A→B,AB→C}F = \{A \to BC, B \to C, A \to B, AB \to C\}에 대해 캐노니컬 커버를 계산하는 과정은 아래와 같다.

  1. A→BCA \to BC와 A→BA \to B를 결합하면 A→BCA \to BC가 된다.
  2. B→CB \to C가 이미 존재하기 때문에 AB→CAB \to C에서 AA가 불필요하다.
  3. A→BA \to B와 B→CB \to C를 통해 이행 규칙으로 A→CA \to C를 유도할 수 있기 때문에, A→BCA \to BC에서 CC가 불필요하다.
  4. 그 결과, Fc={A→B,B→C}F_c = \{A \to B, B \to C\}이다.

캐노니컬 커버의 유일성

캐노니컬 커버는 유일하지 않을 수 있다. 어떤 불필요한 속성을 먼저 제거하느냐에 따라 다른 캐노니컬 커버가 생성될 수 있는데, 예를 들어 F={A→BC,B→AC,C→AB}F = \{A \to BC, B \to AC, C \to AB\}의 경우 Fc={A→B,B→C,C→A}F_c = \{A \to B, B \to C, C \to A\}, Fc={A→C,C→B,B→A}F_c = \{A \to C, C \to B, B \to A\} 등등 여러 가지 버전의 캐노니컬 커버가 존재한다.

Dependency Preservation

데이터베이스 스키마 RR을 R1,R2,…,RnR_1, R_2, \ldots, R_n으로 분해할 때, 각 RiR_i에 대한 FF의 한정restriction FiF_i은 F+F^+에서 RiR_i의 속성만을 포함하는 모든 함수 종속의 집합이다. 이때 분해가 종속성을 보존Dependency Preserving한다는 것은 F′=F1∪F2∪⋯∪FnF' = F_1 \cup F_2 \cup \cdots \cup F_n의 클로저가 F+F^+와 같다는 의미다. 즉, (F1∪F2∪⋯∪Fn)+=F+(F_1 \cup F_2 \cup \cdots \cup F_n)^+ = F^+를 만족하는 분해를 종속성 보존 분해Dependency-Preserving Decomposition이라 부른다.

각 FiF_i의 함수 종속은 해당 RiR_i 관계만 확인하면 되므로 종속성 보존을 활용하면 효율적으로 검증할 수 있다.

종속성 보존 테스트

compute F+for each Ri∈D doFi←{f∈F+∣f가 Ri의 속성만 포함}F′←∅for each Fi doF′←F′∪Ficompute F′+if F′+=F+ then return trueelse return false\begin{aligned} & \text{compute } F^+ \\ & \textbf{for each } R_i \in D \textbf{ do} \\ & \quad F_i \leftarrow \{ f \in F^+ \mid f \text{가 } R_i\text{의 속성만 포함} \} \\ & F' \leftarrow \emptyset \\ & \textbf{for each } F_i \textbf{ do} \\ & \quad F' \leftarrow F' \cup F_i \\ & \text{compute } {F'}^+ \\ & \textbf{if } {F'}^+ = F^+ \textbf{ then return } \text{true} \\ & \textbf{else return } \text{false} \end{aligned}

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

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

for each (α→β)∈F doresult←αrepeatfor each Ri∈D dot←(result∩Ri)+∩Riresult←result∪tuntil result가 더 이상 변하지 않을 때까지if β⊈result then return falsereturn true\begin{aligned} & \textbf{for each } (\alpha \to \beta) \in F \textbf{ do} \\ & \quad result \leftarrow \alpha \\ & \quad \textbf{repeat} \\ & \qquad \textbf{for each } R_i \in D \textbf{ do} \\ & \qquad \quad t \leftarrow (result \cap R_i)^+ \cap R_i \\ & \qquad \quad result \leftarrow result \cup t \\ & \quad \textbf{until } result \text{가 더 이상 변하지 않을 때까지} \\ & \quad \textbf{if } \beta \not\subseteq result \textbf{ then return } \text{false} \\ & \textbf{return } \text{true} \end{aligned}

또 다른 방법은 F+F^+를 계산하지 않는 방법인데, FF의 각 함수 종속 α→β\alpha \to \beta에 대하여 위의 테스트를 적용하면 된다. 각 RiR_i에 대해 resultresult와 RiR_i의 교집합의 속성 클로저를 구한 뒤 RiR_i 내 속성만 취하는 과정을 반복하면서, 최종 resultresult가 β\beta를 포함하는지 확인한다.

함수 종속의 활용

함수 종속은 크게 두 가지 상황에서 사용하는데, 관계의 인스턴스들이 함수 종속의 집합 FF를 만족하는지 확인하는 검증Verification 상황이며, 다른 하나는 합법적인 관계들의 집합에 존재하는 제약 조건을 기술하는 명세Specification 상황이다. 또한 만약 관계 스키마 RR 전체에 대하여 FF가 충족한다면 그때는 FF가 RR에서 유지된다고 말한다. 함수 종속은 정규화Normalization 과정에서 좋은 데이터베이스 설계를 판단하는 핵심 도구로 사용된다.

출처

  • Silberschatz, A., Korth, H.F. and Sudarshan, S. (2020) Database system concepts. Seventh edition. New York, NY: McGraw-Hill.

Footnotes

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