다치 종속

1. 개요

다치 종속은 관계형 데이터베이스에서 데이터의 종속성을 나타내는 개념으로, 특정 속성 집합(α)의 값에 따라 다른 속성 집합(β)의 값이 여러 개로 결정될 수 있음을 의미한다. 다치 종속 α

β는 릴레이션 r(R)에서 α의 값이 같은 튜플들이 β의 값을 서로 독립적으로 가질 수 있음을 나타낸다. 이는 함수 종속을 일반화한 개념으로, 데이터베이스 정규화의 제4 정규형(4NF)을 이해하는 데 중요한 역할을 한다. 다치 종속이 있는 데이터베이스는 데이터 중복 문제를 야기할 수 있으며, 이를 해결하기 위해 릴레이션을 분해하는 과정이 필요하다.

2. 정의

관계 스키마 $R$에서 속성 집합 $\backslash alpha$와 $\backslash beta$가 있을 때, $\backslash alpha$의 각 값에 대해 $\backslash beta$의 값 집합이 독립적으로 결정되면, $\backslash alpha$가 $\backslash beta$를 다치 종속한다고 한다. 이는 $\backslash alpha$

$\backslash beta$로 표기한다.

2.1. 형식적 정의

Relation scheme^영어 $R$을 관계 스키마라고 하고, $\backslash alpha\; \backslash subseteq\; R$와 $\backslash beta\; \backslash subseteq\; R$를 속성 집합이라고 하자. 다치 종속 $\backslash alpha\; \backslash twoheadrightarrow\; \backslash beta$ ("$\backslash alpha$는 $\backslash beta$를 다결정한다")는 임의의 유효한 관계 $r(R)$에서 $t\; \_1[\backslash alpha]=t\; \_2[\backslash alpha]$인 모든 튜플 쌍 $t\; \_1$과 $t\; \_2$에 대해, 다음을 만족하는 튜플 $t\; \_3$과 $t\; \_4$가 $r$에 존재할 때 성립한다.

:$$
\begin{matrix}
t_1[\alpha] = t_2[\alpha] = t_3[\alpha] = t_4[\alpha]\\
t_1[\beta] = t_3[\beta]\\
t_2[\beta] = t_4[\beta]\\
t_1[R\setminus(\alpha\cup\beta)] = t_4[R\setminus(\alpha\cup\beta)]\\
t_2[R\setminus(\alpha\cup\beta)] = t_3[R\setminus(\alpha\cup\beta)]
\end{matrix}


비공식적으로, $(x,y,z)$를 $\backslash alpha,$ $\backslash beta,$ $R\; -\; \backslash alpha\; -\; \backslash beta$에 대한 값을 갖는 튜플로 표시하여 각각 $x,$ $y,$ $z$라고 하면, 튜플 $(a,b,c)$와 $(a,d,e)$가 $r$에 존재할 때마다 튜플 $(a,b,e)$와 $(a,d,c)$도 $r$에 존재해야 한다.

다치 종속은 아래와 같이 도식적으로 나타낼 수 있다.

:$$
\begin{matrix}
\text{튜플} & \alpha & \beta & R\setminus(\alpha\cup\beta) \\
t_1 & a_1 .. a_n & b_1 .. b_m & d_1 .. d_k \\
t_2 & a_1 .. a_n & c_1 .. c_m & e_1 .. e_k \\
t_3 & a_1 .. a_n & b_1 .. b_m & e_1 .. e_k \\
t_4 & a_1 .. a_n & c_1 .. c_m & d_1 .. d_k
\end{matrix}

3. 예제

대학교 강의 데이터베이스를 예로 들어 설명하면 다음과 같다.

위 표에서 강사는 코스에 속해 있고, 참고 도서도 코스에 속해 있다. 하지만 강사와 참고 도서는 서로 독립적이다. 따라서 이 데이터베이스 설계에는 다치 종속이 존재한다. 예를 들어 AHA 코스에 새로운 참고 도서를 추가하려면, 해당 코스의 각 강사 데이터에 대해 참고 도서를 추가해야 한다.

3.1. 다치 종속이 있는 데이터베이스

"강좌", "교재", "강사" 속성을 가진 릴레이션에서 다치 종속의 예시는 다음과 같다. 한 강좌에 여러 교재와 강사가 배정될 수 있고, 이들이 서로 독립적일 때 다치 종속이 발생한다.

위 표에서 {강좌} →→ {도서} 및 {강좌} →→ {강사} 다치 종속이 존재한다. 이는 AHA 강좌에 새로운 도서를 추가하려면, 해당 강좌의 각 강사에 대해 레코드를 하나씩 추가해야 함을 의미한다. {강좌}

{교재} 및 {강좌}

{강사}로 표현할 수 있다.

이러한 다치 종속은 데이터 중복을 야기하며, 데이터베이스 정규화 과정 중 제4 정규형에서 제거되어야 한다.

3.2. 제4 정규형으로 정규화

다치 종속으로 인해 발생하는 데이터 중복 문제를 해결하기 위해, 릴레이션을 분해하여 제4 정규형을 만족시킬 수 있다. 주어진 예시에서는 릴레이션을 {강좌, 교재}와 {강좌, 강사}로 분해하면 된다. 이렇게 하면 각 릴레이션에서 다치 종속성이 제거되어 데이터 중복이 사라진다.

원래의 'Teaching database'는 다음과 같았다.

이 릴레이션에는 {강좌}

{도서} 및 {강좌}

{강사} 라는 두 개의 다치 종속이 존재하여 제4 정규형을 만족하지 못했다.

이를 {강좌, 교재}와 {강좌, 강사} 두 릴레이션으로 분해하면 다음과 같다.




위와 같이 분해하면, 각 릴레이션은 제4 정규형을 만족하게 된다.

4. 성질

다치 종속은 함수 종속을 일반화한 개념이다. 다치 종속과 관련하여 다음 성질들이 성립한다.

* R에서 X --|]] Y 가 성립하는 것과, R을 (X,Y) 및 (X,R-Y)로 분해하는 것이 무손실 분해라는 것은 동치이다.
* 만약 $\backslash alpha\; \backslash twoheadrightarrow\; \backslash beta$이면, $\backslash alpha\; \backslash twoheadrightarrow\; R\; -\; \backslash beta$이다. (보완성)
* 만약 $\backslash alpha\; \backslash twoheadrightarrow\; \backslash beta$이고 $\backslash gamma\; \backslash subseteq\; \backslash delta$이면, $\backslash alpha\; \backslash delta\; \backslash twoheadrightarrow\; \backslash beta\; \backslash gamma$이다. (증대성)
* 만약 $\backslash alpha\; \backslash twoheadrightarrow\; \backslash beta$이고 $\backslash beta\; \backslash twoheadrightarrow\; \backslash gamma$이면, $\backslash alpha\; \backslash twoheadrightarrow\; \backslash gamma\; -\; \backslash beta$이다. (전이성)

함수 종속성과 관련된 규칙은 다음과 같다.

* 만약 $\backslash alpha\; \backslash rightarrow\; \backslash beta$이면, $\backslash alpha\; \backslash twoheadrightarrow\; \backslash beta$이다. (복제)
* 만약 $\backslash alpha\; \backslash twoheadrightarrow\; \backslash beta$이고 $\backslash beta\; \backslash rightarrow\; \backslash gamma$이면, $\backslash alpha\; \backslash rightarrow\; \backslash gamma\; -\; \backslash beta$이다.

위 규칙은 건전하고 완전하다.

4.1. 다치 종속의 추론 규칙

다치 종속(MVD)의 추론 규칙은 다음과 같으며, 암스트롱의 공리와 유사하다.

* 보완성: $\backslash alpha\; \backslash twoheadrightarrow\; \backslash beta$이면, $\backslash alpha\; \backslash twoheadrightarrow\; R\; -\; \backslash beta$이다.
* 증대성: $\backslash alpha\; \backslash twoheadrightarrow\; \backslash beta$이고 $\backslash gamma\; \backslash subseteq\; \backslash delta$이면, $\backslash alpha\; \backslash delta\; \backslash twoheadrightarrow\; \backslash beta\; \backslash gamma$이다.
* 전이성: $\backslash alpha\; \backslash twoheadrightarrow\; \backslash beta$이고 $\backslash beta\; \backslash twoheadrightarrow\; \backslash gamma$이면, $\backslash alpha\; \backslash twoheadrightarrow\; \backslash gamma\; -\; \backslash beta$이다.

함수 종속성과 관련된 규칙은 다음과 같다.

* 복제: $\backslash alpha\; \backslash rightarrow\; \backslash beta$이면, $\backslash alpha\; \backslash twoheadrightarrow\; \backslash beta$이다.
* $\backslash alpha\; \backslash twoheadrightarrow\; \backslash beta$이고 $\backslash beta\; \backslash rightarrow\; \backslash gamma$이면, $\backslash alpha\; \backslash rightarrow\; \backslash gamma\; -\; \backslash beta$이다.

또한, 다음이 성립한다.

* R에서 X --|]] Y 가 성립하는 것과, R을 (X,Y) 및 (X,R-Y)로 분해하는 것이 무손실 조인 분해이라는 것은 동치이다.

위에 언급된 규칙들은 건전하고 완전하다.

4.2. 함수 종속과의 관계

함수 종속은 다치 종속의 특수한 경우이다. 이는 다음과 같이 표현할 수 있다.

* $\backslash alpha\; \backslash rightarrow\; \backslash beta$이면, $\backslash alpha\; \backslash twoheadrightarrow\; \backslash beta$이다.

즉, 어떤 속성 집합 $\backslash alpha$가 다른 속성 집합 $\backslash beta$를 함수적으로 결정하면, $\backslash alpha$는 $\backslash beta$를 다치 결정한다.

또한, 다치 종속과 함수 종속 사이에 다음과 같은 관계가 성립한다.

* $\backslash alpha\; \backslash twoheadrightarrow\; \backslash beta$이고 $\backslash beta\; \backslash rightarrow\; \backslash gamma$이면, $\backslash alpha\; \backslash rightarrow\; \backslash gamma\; -\; \backslash beta$이다.

이는 $\backslash alpha$가 $\backslash beta$를 다치 결정하고, $\backslash beta$가 $\backslash gamma$를 함수적으로 결정하면, $\backslash alpha$는 $\backslash gamma$에서 $\backslash beta$를 제외한 속성들을 함수적으로 결정한다는 의미이다.

5. 용어 정의

관계 스키마 $R$과 $R$의 부분집합인 속성 집합 $\backslash alpha$, $\backslash beta$가 있다고 하자. $r(R)$이 $R$의 임의의 유효한 관계라고 할 때, $r$에 있는 모든 튜플 쌍 $t\_1$과 $t\_2$에 대해 $t\_1[\backslash alpha]\; =\; t\_2[\backslash alpha]$이면, 다음 조건을 만족하는 튜플 $t\_3$과 $t\_4$가 $r$에 존재하면 다치 종속 $\backslash alpha\; \backslash twoheadrightarrow\; \backslash beta$ ("$\backslash alpha$는 $\backslash beta$를 다결정한다")가 $R$에서 성립한다.

$$
\begin{matrix}
t_1[\alpha] = t_2[\alpha] = t_3[\alpha] = t_4[\alpha]\\
t_1[\beta] = t_3[\beta]\\
t_2[\beta] = t_4[\beta]\\
t_1[R\setminus(\alpha\cup\beta)] = t_4[R\setminus(\alpha\cup\beta)]\\
t_2[R\setminus(\alpha\cup\beta)] = t_3[R\setminus(\alpha\cup\beta)]
\end{matrix}


이를 비공식적으로 표현하면 다음과 같다. $(x,\; y,\; z)$를 각각 $\backslash alpha$, $\backslash beta$, $R\; -\; \backslash alpha\; -\; \backslash beta$에 대한 값을 갖는 튜플이라고 하고, $x$, $y$, $z$로 표현하면, 튜플 $(a,\; b,\; c)$와 $(a,\; d,\; e)$가 $r$에 존재할 때마다 튜플 $(a,\; b,\; e)$와 $(a,\; d,\; c)$도 $r$에 존재해야 한다.

다치 종속은 아래와 같이 도식적으로 나타낼 수 있다.

$$
\begin{matrix}
\text{튜플} & \alpha & \beta & R\setminus(\alpha\cup\beta) \\
t_1 & a_1 .. a_n & b_1 .. b_m & d_1 .. d_k \\
t_2 & a_1 .. a_n & c_1 .. c_m & e_1 .. e_k \\
t_3 & a_1 .. a_n & b_1 .. b_m & e_1 .. e_k \\
t_4 & a_1 .. a_n & c_1 .. c_m & d_1 .. d_k
\end{matrix}


* 전체 제약: 데이터베이스의 모든 속성에 대한 내용을 표현하는 제약 조건이다. 다치 종속성이 전체 제약인 것은 $R\; -\; \backslash beta$ 속성에 대해 말하는 정의에 따른다.
* [[튜플 생성 종속성]]: 관계에 특정 튜플이 존재해야 함을 명시적으로 요구하는 종속성이다.
* 자명한 다치 종속성:
* 관계의 모든 속성을 포함하는 다치 종속성 ( $R\; =\; \backslash alpha\; \backslash cup\; \backslash beta$ ).
* $\backslash beta\; \backslash subseteq\; \backslash alpha$인 다치 종속성.