후보키, 슈퍼키

이전 글에서 얘기한 함수 종속성을 알아보기 위해서는 후보키슈퍼키라는 개념을 알아야 한다.

후보키란 릴레이션에서 튜플의 값을 고유하게 만드는 속성의 집합이다. 즉, 후보키가 정해지면 해당 row의 값이 모두 정해진다는 것이다. 이 때 후보키는 더는 속성을 줄일 수 없는 상태여야 한다. 잘 와닿지 않으니 다음 테이블들을 살펴보며 이해해보자.

id 이름
1 A
2 B
3 C

가장 간단한 예다. id가 정해지면 그에 따라 이름도 정해지는 것을 알 수 있다. SQL에서 우리가 보는 Primary Key가 후보키의 대표적인 예다. id가 정해지면 다른 row의 값이 모두 결정된다.

주민번호 출생지 이름
20200101 서울 A
19870312 경기 B
19990815 서울 C

Primary Key만이 후보키가 될 수 있는 건 아니다. 다음과 같은 예를 생각해보자. 이 테이블에는 id 컬럼이 존재하지 않는다. 하지만 주민번호가 결정되면 출생지와 이름 모두 결정된다는 사실을 알 수 있으므로 주민번호가 바로 후보키가 된다.

이 때 {주민번호, 이름}이 후보키가 될 수는 없을까? 위에서 말했듯이 후보키는 더는 속성을 줄일 수 없는 상태여야 한다. 이 테이블은 주민번호출생지 모두를 알아야 이름을 결정지을 수 있는 것이 아니라 주민번호만 알아도 출생지와 이름을 결정지을 수 있으므로 속성을 최대한으로 줄인 주민번호가 후보키가 된다.

그럼 반대로 슈퍼키는 무엇일까? 슈퍼키는 후보키와 다르게 추가 속성을 지니고 있는 집합을 말한다. 쉽게 말해 위 테이블에서 후보키주민번호였지만 슈퍼키{주민번호, 출생지}도 될 수 있고 {주민번호, 이름}도 될 수 있고 {주민번호, 출생지, 이름} 또한 될 수 있다.

후보키슈퍼키 둘다 정해지면 나머지 속성들 또한 결정된다는 공통점을 가지며 차이점은 추가 속성을 포함할 수 있냐의 차이 뿐이다. 당연히 후보키슈퍼키에 포함된다.

릴레이션에는 중복이 없으므로 최소 후보키 1개는 존재하며 속성 전체 집합은 반드시 슈퍼키가 된다.

후보키는 테이블에서 밑줄을 그어서 표시한다.

함수 종속성

2NF부터 BCNF까지는 모두 함수 종속성에 관한 내용이며 BCNF는 최대한으로 함수 종속성을 배제한 상태를 말한다. 그렇다면 함수 종속성은 무엇일까?

어떤 릴레이션의 속성의 부분집합 A, B가 존재할 때 A 값이 정해지면 B 값이 정해질 때 B는 A에 함수 종속한다고 하고, 이런 관계를 A -> B라고 한다.

이 때 명심해야 할 점은 A가 같을 때 B가 같은 경우이므로 A가 다르다면 B는 중복되어도 상관없다.

조금 더 쉽게 알기위해 위 테이블을 다시 살펴보자

주민번호 출생지 이름
20200101 서울 A
19870312 경기 B
19990815 서울 C

이 테이블에서는 주민번호를 알면 출생지이름을 알 수 있다. 따라서

  • 주민번호 -> 출생지
  • 주민번호 -> 이름

이라는 함수 종속성이 존재한다. 즉,

임의의 속성은 후보키에 반드시 함수 종속한다.

눈치가 빠른 사람은 알겠지만 다음 사실 또한 항상 성립한다

임의의 속성은 슈퍼키에 반드시 함수 종속한다

또한 다음 사실 또한 항상 성립한다.

속성의 부분집합 x, y가 있을 때 {x, y} -> {x}, {x, y} -> {y}는 항상 성립한다
예를 들어 {출생지, 이름} -> {이름}, {출생지, 이름} -> {출생지}는 당연히 성립한다

이와 같이 어떠한 릴레이션에서든 항상 성립하는 함수 종속성을 **자명한 함수 종속성(trivial Functional Dependency)**라고 한다. 자명한 함수 종속성은 릴레이션에서 제외할 수 없다.

문제는 바로 이렇지 않은, **자명하지 않은 함수 종속성(Non trivial Functional Dependency)**이 문제가 된다.

일반적으로 릴레이션에서는 가 정해지면 나머지 속성 또한 알 수 있다. 이 때 자명하지 않은 함수 종속성이 존재한다는 것은 키가 아닌 A에 대해서 B가 결정된다는 것이다. 이 때 A는 키가 아니므로 반복되어 나타날 수 있으므로 문제가 되는 것이다. 앞으로의 과정은 이러한 함수 종속성을 없애나가는 과정이다.

2NF

2NF는 후보키의 진부분집합에서 키가 아닌 속성에 함수 종속성을 제거하는 작업이다. 이런 종속성을 **부분 함수 종속성(Partial Functional Dependency)**라고 한다.

진 부분집합이란 부분집합 중 원래 자신의 집합을 제외한 것을 말한다

즉, 다음과 같은 종속성을 제거하는 작업이다

1NF를 만족하는 릴레이션 중 부분 함수 종속성을 가지지 않는다면 릴레이션은 바로 2NF가 된다. 예를 들어 후보키가 1개인 1NF 릴레이션은 진부분집합이 공집합 뿐이므로 자동으로 2NF를 만족한다.

학부 이름 평균 학점 등록금
전자전기공학부 A 4.34 400
화학공학부 B 3.25 450
전자전기공학부 C 3.7 400
경영학부 D 4.5 350

학부에 동명이인이 존재하지 않는다고 가정하면 위 테이블의 기본키는 {학부, 이름}이다. 학부와 이름이 결정되면 학생을 알 수 있으므로 평균 학점과 등록금을 알 수 있다.

하지만 학부를 알면 등록금을 알 수 있다. 즉, 학부 -> 등록금이라는 부분 함수 종속성이 존재한다.

위 테이블은 어떠한 문제가 발생할까? 만약 전자전기공학부의 등록금이 올랐을 때 A 학생과 C 학생 모두의 등록금을 수정해주지 않으면 모순이 발생할 수 있다.

이러한 함수 종속성 문제를 해결하는 방법은 바로 **무손실 분해(Non-loss Decomposition)**이다.

무손실 분해란 한 개의 릴레이션에 대해 다른 두 개의 패턴의 프로젝션을 해 두 개의 릴레이션을 생성하는 것을 말한다

다르게 말하면 나눠진 두 개의 릴레이션을 Join을 통해 원래의 릴레이션으로 복구할 수 있는 경우가 바로 무손실 분해다.

위 함수 종속성을 해결하기 위해서는 문제가 되는 종속성 즉, 학부 -> 등록금에 대해서 {학부} -> {등록금}으로 프로젝션 해 하나의 릴레이션을 만들고 종속된 속성 즉, 등록금을 제외하고 나머지 속성인 {학부, 이름} -> {평균 학점}으로 프로젝션을 해 릴레이션을 나눈다.

학부 이름 평균 학점
전자전기공학부 A 4.34
화학공학부 B 3.25
전자전기공학부 C 3.7
경영학부 D 4.5
학부 등록금
전자전기공학부 400
화학공학부 450
경영학부 350

위와 같이 릴레이션을 나누면 전자전기공학부의 등록금이 올라도 갱신 이상이 발생하지 않는다. 즉, 2NF를 만족하게 된다.

3NF

3NF란 **추이 함수 종속성(Transitive Dependency)**을 제거하는 작업이다.

추이 함수 종속성이란 키가 아닌 속성 사이의 함수 종속성을 말한다.

만약 키가 아닌 속성의 집합 A, B 사이에 A -> B가 성립한다면 슈퍼키를 통해 A의 값이 정해질 수 있고 함수 종속성에 따라 B 또한 결정되게 된다. 이렇게 단계적으로 함수 종속성이 존재해 추이 함수 종속성이라고 부른다.

다만 슈퍼키에 의해 B 또한 결정되므로 잘 와닿지 않는다면 키가 아닌 속성 사이의 함수 종속성이라 생각해도 된다.

학번 학부 학부 사무실 위치 전화번호
20172312 전자전기공학부 310-504 02-123-123
20102832 화학공학부 207-510 02-321-321
20005831 전자전기공학부 310-504 02-123-123
20202020 경영학부 103-102 02-123-456

다음과 같은 테이블이 존재한다고 해보자. 학번이 주어지면 학생이 속하는 학부가 정해지고 그 학부 사무실 위치전화번호를 알 수 있다. 당연히 학부가 정해지면 학부 사무실의 위치전화번호 또한 정해지기 때문에 추이 함수 종속성이 존재한다.

이 또한 무손실 분해를 통해 함수 종속성을 제거할 수 있다.

{학부} -> {학부 사무실 위치, 전화번호}라는 함수 종속성이 존재하므로 학부가 기본키가 되는 릴레이션을 새롭게 만들면 된다.

학번 학부
20172312 전자전기공학부
20102832 화학공학부
20005831 전자전기공학부
20202020 경영학부
학부 학부 사무실 위치 전화번호
전자전기공학부 310-504 02-123-123
화학공학부 207-510 02-321-321
전자전기공학부 310-504 02-123-123
경영학부 103-102 02-123-456

BCNF(Boyce-Codd Normal Form)

마지막으로 BCNF란 자명하지 않은 함수 종속성이 모두 제거된 상태의 정규형이다. 우리가 아직 제거하지 못한 함수 종속성은 키가 아닌 속성에서 후보키의 진부분집합에 대한 함수 종속성이다.

학번 학부 분야
20172312 전자전기공학부 전자
20102832 화학공학부 생화학
20005831 전자전기공학부 전기
20202020 경영학부 회계

다음과 같은 릴레이션을 생각해보자. 여기서 문제가 되는 점은 분야학부보다 더 자세한 정보라는 것이다. 바꿔서 말하면 분야가 결정되면 학부 또한 결정된다. 즉, 분야 -> 학부가 성립한다.

그렇다면 분야가 더 자세한 정보니까 {학번, 분야}를 기본키로 설정하면 어떻게 될까? 그렇게 하면 키가 아닌 속성에서 후보키의 진부분집합에 대한 함수 종속성은 사라진다. 하지만 분야 -> 학부라는 함수 종속성은 여전히 존재하므로 부분 함수 종속성이 오히려 생겨버린다. 즉, 2NF마저 만족하지 않게 되어버린다. 이처럼 BCNF를 위반하는지 찾기 위해서는 또 다른 후보키가 존재하지 않는지 생각해보면 좋다.

결국 이와같은 문제를 해결하는 방법은 다음과 같이 무손실 분해를 하는 것이다. 분해하는 과정은 다음과 같다.

  • BCNF를 위반하게 만드는 함수 종속성 X -> Y를 찾느다
  • 아래와 같이 분해한다
    • {X, Y}로 구성된 릴레이션
    • X와 나머지 속성으로 구성된 릴레이션

이를 위에 적용하면 다음과 같다.

  • BCNF를 위반하는 함수 종속성은 분야 -> 학부
  • 따라서 다음과 같이 분해한다
    • {분야, 학부}로 분해한 릴레이션
    • 분야와 나머지 속성 즉, {학번, 분야}로 구성된 릴레이션
분야 학부
전자 전자전기공학부
생화학 화학공학부
전기 전자전기공학부
회계 경영학부
학번 분야
20172312 전자
20102832 생화학
20005831 전기
20202020 회계