[데이터 베이스] 함수적 종속성(Functional dependency)

오늘은 함수적 종속성에 대해 이야기해 보고자 한다.

 

함수적 종속성에 대해 얘기하기에 앞서, 이 개념이 나오게 된 배경을 알아보려면, 좋은 릴레이션 스키마를 설정하는 기준에 대해 고민해 보아야 한다.

 

그럼, 좋은 릴레이션 스키마를 설정하는 기준에는 무엇이 있는가.

우선 중복된 정보가 없어야 한다.

다음 '학생-수강 과목' 릴레이션을 살펴보자, 학번이 15032인 사람의 이름이 John이라는 정보가 3번이나 들어가 있다.

 

학번	이름	과목코드	과목 이름
15032	John	CS-1023	데이터베이스
15032	John	CS-238	알고리즘
15032	John	LG-335	심리 언어학
16028	Amy	CS-238	알고리즘

이게 왜 문제가 될까?

위의 릴레이션 내 값들을 수정할 때 문제가 발생한다. 

예를 들어 편입생 James가 들어온다고 하면, 이 학생은 아직 과목을 수강하지 않았기 때문에, 과목 코드와 과목이름에 null값이 들어갈 수밖에 없다. 그러나 과목 코드가 PK(기본키)이기에 null값^[각주:1]이 들어가면 문제가 발생한다. 

 

또 John이 자퇴를 한다고 하면, John이 들어간 튜플 전체를 삭제해야 하며, '알고리즘' 과목 이름이 '자료구조와 알고리즘'으로 바뀐다고 할 때에도 같은 과목 코드를 갖는 과목들을 모두 바꿔주어야 한다. 

 

게다가 John이 자퇴한다고 할때, John과 관련된 정보가 사라지게 되는데, 데이터베이스와 심리 언어학은 John 한 명만 수강하고 있는 상태여서 John이 있는 tuple이 사라짐과 동시에 과목 정보도 사라지게 된다. 

 

이렇게 릴레이션 값을 갱신할 때 여러 문제점이 나타날 수 있다.

 

그럼 이를 해결하기 위해 릴레이션을 적절하게 나눠주면 될 것 같다. 그러나 나누는 데에도 적절히 나눠야 한다. 무조건 잘게 나눈다고 좋은 것이 아니다. 여기서 좋은 릴레이션 스키마를 구성하는 두 번째 기준을 생각해 볼 수 있다. Join overhead이다.

 

이는 데이터베이스의 성능을 좌우하는 중요한 부분이다. join 연산은 다른 연산보다 많은 연산량을 요구한다. 따라서 많은 시간이 소요되고, 여기서 시간을 줄여주는 것이 중요하다. 릴레이션이 너무 잘게 쪼개져 있으면, 사용자가 원하는 정보를 제공할 때, 많은 join 연산이 필요하게 된다. 즉, join overhead를 최소화하려면, 하나의 릴레이션에 모든 정보를 표현하면 된다. 그러나 이는 위에서 해결하고자 했던 문제에 역행한다. 즉, join overhead와 정보의 중복성 문제는 서로 trade-off의 관계에 있다. 따라서 둘을 적절히 고려하여 릴레이션을 나눠야 한다.  

 

그럼 릴레이션을 어떤 기준으로 나눠야 할까?

이 기준을 정하는 데 사용되는 개념이 바로 함수적 종속성(Functional Dependency, FD)이다. 함수적 종속성을 잘 찾아서 릴레이션을 나눠주어야 나중에 다시 join했을 때 원하는 릴레이션을 얻을 수 있다. 또 함수적 종속성은 키와 함께 정규형^[각주:2]을 정의할 때 사용되며, 우리가 DB로 실세계의 내용들을 표현하고 자 할 때 적용되는 실세계의 제약조건들을 담아내기도 한다. 

 

함수적 종속성의 정의

함수적 종속성의 정의는 다음과 같다. 

임의의 애트리뷰트 집합 X와 Y가 있다고 할 때, 임의의 X의 값을 하나 선택했을 때, Y가 유일하게 결정된다면, X는 Y를 함수적으로 결정한다고 하며, Y는 X에 "함수적으로 종속된다"라고 한다. 

이를 수식으로 다음과 같이 나타낼 수 있다.

$\forall t_{1} t_{2} \in r(R) $, $t_{1}[X] = t_{2}[X] \Rightarrow t_{1}[Y] = t_{2}[Y] $

 

앞에서 언급한 릴레이션을 참고해 함수적 종속성을 확인해 보자. 

학번	이름	과목코드	과목 이름
15032	John	CS-1023	데이터베이스
15032	John	CS-238	알고리즘
15032	John	LG-335	심리 언어학
16028	Amy	CS-238	알고리즘

예를 들어, '학번'은 '이름'을 함수적으로 결정한다. 학번 애트리뷰트에서 임의의 값을 골랐을 때, 이름 애트리뷰트에서 하나의  값으로 귀결되기 때문이다. 학번 15032에 대해서는 항상 John으로 학번 16028에 대해서는 항상 Amy에 대응되는 것을 확인할 수 있다. 

 

수식으로 접근해 보자면, 수식은 if p then q구조를 따르고 있다고 볼 수 있다. 이 명제에 대한 진리표는 다음과 같다. 

p	q	p->q
T	T	T
T	F	F
F	T	T
F	F	T

여기서 p에 해당하는 부분은 $t_{1}[X] = t_{2}[X]$이고, q에 해당하는 부분은 $t_{1}[Y] = t_{2}[Y] $이다.

p->q가 거짓인 경우는 p가 참일 때, q가 거짓인 경우밖에 없기 때문에 함수적 종속성을 검사하기 위해선 p가 참일 때 q가 거짓인지만 확인해 보면 된다. 

 

또한 고등학교 때 배운 지식을 활용해 대우 명제로도 확인 해 볼 수 있다. 

$t_{1}[Y] != t_{2}[Y] \Rightarrow t_{1}[X] != t_{2}[X] $ 에 대해 확인해 보면 된다. 만일 $t_{1}[Y]$과 $t_{2}[Y]$가 다른데, t_{1}[X]$과 $t_{2}[X]$이 같다면, 함수적 종속성이 없는 것이다. 

 

 

Key 애트리뷰트는 해당 릴레이션의 모든 애트리뷰트들에 대해 함수적으로 결정한다. 위의 예시에서는 (학번, 과목코드)가 (기본)키이다. 따라서 이 둘의 조합은 나머지 애트리뷰트들에 대해 함수적으로 결정한다. 이는 키의 특성을 고려해 보아도 유추해 볼 수 있다. 키는 릴레이션 내의 튜플들을 구분해주는 역할을 한다. 따라서 애초에 중복되는 값들을 가질 수 없어 항상 성립할 수밖에 없다.

 

또한 위의 릴레이션의 임의의 애트리뷰트(과목 이름이라 해보자)에서 서로 다른  데이터베이스와 알고리즘을 골랐을 때,  키 애트리뷰트들인 (학번, 과목코드) 조합 중 같은 값을 갖는 튜플을 찾을 수 없다.

 

 

 

 

1. null값은 해석에 어려움을 가져다 준다. 값이 없다는 뜻이거나 아직 입력이 안 됐다거나 이 튜플에만 적용이 안 된다는 등 여러 의미로 해석이 가능하다. 또count나 avg같은 집계 연산 시에도 어려움을 가져다 준다. [본문으로]
2. 좋은 릴레이션 여부를 검사하는 방법 [본문으로]